// © 2019-present nextmv.io inc
// package main holds the implementation of the mip-meal-allocation template.
package main
import (
"context"
"log"
"math"
"github.com/nextmv-io/go-highs"
"github.com/nextmv-io/go-mip"
"github.com/nextmv-io/sdk/run"
"github.com/nextmv-io/sdk/run/schema"
)
// This template demonstrates how to solve a Mixed Integer Programming problem.
// To solve a mixed integer problem is to optimize a linear objective function
// of many variables, subject to linear constraints. We demonstrate this by
// solving a made up problem we named MIP meal allocation.
//
// MIP meal allocation is a demo program in which we maximize the number of
// binkies our bunnies will execute by selecting their meals.
//
// A binky is when a bunny jumps straight up and quickly twists its hind end,
// head, or both. A bunny may binky because it is feeling happy or safe in its
// environment.
func main() {
err := run.CLI(solver).Run(context.Background())
if err != nil {
log.Fatal(err)
}
}
// The options for the solver.
type options struct {
Solve mip.SolveOptions `json:"solve,omitempty"`
}
// Input of the problem.
type input struct {
Items []struct {
Name string `json:"name"`
// Maximum stock of the item.
Stock float64 `json:"stock"`
} `json:"items"`
Meals []struct {
Name string `json:"name"`
Ingredients []struct {
Name string `json:"name"`
Quantity float64 `json:"quantity"`
} `json:"ingredients"`
// Number of binkies generated by the meal.
Binkies float64 `json:"binkies"`
} `json:"meals"`
}
type solution struct {
Meals []mealQuantity `json:"meals,omitempty"`
}
type mealQuantity struct {
Name string `json:"name,omitempty"`
Quantity float64 `json:"quantity,omitempty"`
}
type mealVariable struct {
Name string
Variable mip.Int
}
// solver is the entrypoint of the program where a model is defined and solved.
func solver(_ context.Context, input input, options options) (schema.Output, error) {
// Translate the input to a MIP model.
model, variables := model(input)
// Create a solver using a provider. Please see the documentation on
// [mip.SolverProvider] for more information on the available providers.
solver := highs.NewSolver(model)
// Solve the model and get the solution.
solution, err := solver.Solve(options.Solve)
if err != nil {
return schema.Output{}, err
}
// Format the solution into the desired output format and add custom
// statistics.
output := mip.Format(options, format(solution, variables), solution)
output.Statistics.Result.Custom = mip.DefaultCustomResultStatistics(model, solution)
return output, nil
}
// model creates a MIP model from the input. It also returns the decision
// variables.
func model(input input) (mip.Model, []mealVariable) {
// We start by creating a MIP model.
model := mip.NewModel()
// We want to maximize the number of binkies.
model.Objective().SetMaximize()
// Map the name of the item to a constraint so we can retrieve it to add a
// term for the quantity used by each meal.
capacityConstraints := make(map[string]mip.Constraint)
for _, item := range input.Items {
// We create a constraint for each item which will constrain the
// number of items we use to what we have in stock.
capacityConstraints[item.Name] = model.NewConstraint(
mip.LessThanOrEqual,
item.Stock,
)
}
// Map the name of the meal to the variable so we can retrieve it for
// reporting purposes.
mealsVariables := make([]mealVariable, len(input.Meals))
for i, meal := range input.Meals {
// We create an integer variable for each meal representing how
// many instances of meal we will serve.
variable := model.NewInt(0, math.MaxInt64)
mealsVariables[i] = mealVariable{
Name: meal.Name,
Variable: variable,
}
// We add the term of the variable to the objective function, which
// corresponds to the number of binkies generated by the number of
// meals.
model.Objective().NewTerm(meal.Binkies, variable)
for _, ingredient := range meal.Ingredients {
// We add the number of ingredients we use in each meal to the
// constraint that limits how many ingredients are in stock.
capacityConstraints[ingredient.Name].NewTerm(
ingredient.Quantity,
variable,
)
}
}
return model, mealsVariables
}
// format the solution from the solver into the desired output format.
func format(solverSolution mip.Solution, mealsVariables []mealVariable) solution {
meals := make([]mealQuantity, 0)
for _, variable := range mealsVariables {
value := solverSolution.Value(variable.Variable)
if value == 0 {
continue
}
meals = append(meals, mealQuantity{
Name: variable.Name,
Quantity: math.Round(value),
})
}
return solution{
Meals: meals,
}
}
Copy