// package main holds the implementation of the mip-meal-allocation template.
package main
import (
"context"
"log"
"math"
"github.com/nextmv-io/sdk/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"\`
}
// 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, err := mip.NewSolver(mip.Highs, model)
if err != nil {
return schema.Output{}, err
}
// 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, map[string]mip.Int) {
// 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(map[string]mip.Int, len(input.Meals))
for _, meal := range input.Meals {
// We create an integer variable for each meal representing how
// many instances of meal we will serve.
mealsVariables[meal.Name] = model.NewInt(0, math.MaxInt64)
// 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, mealsVariables[meal.Name])
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,
mealsVariables[meal.Name],
)
}
}
return model, mealsVariables
}
// format the solution from the solver into the desired output format.
func format(solverSolution mip.Solution, mealsVariables map[string]mip.Int) solution {
meals := make([]mealQuantity, 0)
for name, mealVariable := range mealsVariables {
value := solverSolution.Value(mealVariable)
if value == 0 {
continue
}
meals = append(meals, mealQuantity{
Name: name,
Quantity: math.Round(value),
})
}
return solution{
Meals: meals,
}
}
Copy