Examples

Meal allocation

A how-to guide for solving meal allocation problems.

This how-to guide assumes you already completed the get started with MIP tutorial.

This example uses the Nextmv Go SDK to solve the incentive allocation problem.

The meal allocation problem states the following:

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.

Determine the number of meals you should use to maximize binkies, given that each meal uses one or more items that have a limited stock.

This problem can be formulated as follows:

\begin{equation} \max \sum_{\forall j \in M}(b_{j} \cdot x_{j}) \end{equation} Subject to: \begin{flalign} \sum_{\forall j \in M}(q_{ij} \cdot x_{j}) &\leq s_{i}, &\forall i \in I; &&\\ x_{j} &\in \mathbb{N} \cup \set{0}, &\forall j \in M. \end{flalign} Where: \begin{flalign} -& I \text{ is the set of ingredients.} &\\ -& M \text{ is the set of meals.} &\\ -& b_{j} \text{ is the number of binkies that meal } j \in M \text{ produces.} &\\ -& q_{ij} \text{ is the quantity of ingredient } i \in I \text{ used in meal } j \in M. &\\ -& s_{i} \text{ is the available stock of ingredient } i \in I. &\\ -& x_{j} \text{ is the number of times meal } j \in M \text{ is used.} &\\ \end{flalign}

Get started by initializing the knapsack-gosdk community app:

nextmv community clone -a knapsack-gosdk
Copy

Change directories into the knapsack-gosdk folder. Rename the directory if desired.

cd knapsack-gosdk
Copy

Replace the input.json contained in the app with sample data for the meal allocation problem.

{
  "items": [
    {
      "name": "Endive",
      "stock": 12
    },
    {
      "name": "Carrots",
      "stock": 5
    }
  ],
  "meals": [
    {
      "name": "A",
      "binkies": 6,
      "ingredients": [
        {
          "name": "Endive",
          "quantity": 3
        },
        {
          "name": "Carrots",
          "quantity": 1
        }
      ]
    },
    {
      "name": "B",
      "binkies": 5,
      "ingredients": [
        {
          "name": "Endive",
          "quantity": 2
        },
        {
          "name": "Carrots",
          "quantity": 1
        }
      ]
    }
  ]
}
Copy

Similarly, replace the main.go included in the app with the code to solve meal allocation.

// 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"`
}

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, 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, []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

The code showcases several aspects when working with MIPs:

  • How to define variables based on the input data.
  • How to programmatically add terms to constraints and the objective by looping over input data.
  • How to interact with solve options.

Please note that HiGHS is used as the default solver provider. To use a different one, please visit the supported solvers page to learn more about working with different providers.

Run the code, specifying the file to be used as input, and the file to be used as output, along with other options.

nextmv sdk run . -- -runner.input.path input.json -runner.output.path output.json -solve.duration 10s
Copy

After running, an output.json file should have been created with the solution, similar to this one:

{
  "options": {
    "solve": {
      "control": {
        "bool": [],
        "float": [],
        "int": [],
        "string": []
      },
      "duration": 10000000000,
      "mip": {
        "gap": {
          "absolute": 0.000001,
          "relative": 0.0001
        }
      },
      "verbosity": "off"
    }
  },
  "solutions": [
    {
      "meals": [
        {
          "name": "A",
          "quantity": 2
        },
        {
          "name": "B",
          "quantity": 3
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "constraints": 2,
        "provider": "highs",
        "status": "optimal",
        "variables": 2
      },
      "duration": 0.123,
      "value": 27
    },
    "run": {
      "duration": 0.123
    },
    "schema": "v1"
  },
  "version": {
    "sdk": "VERSION"
  }
}
Copy

Page last updated