Get started with Mixed Integer Programming (MIP)

I want an interesting synonym
To describe this thing
That you say we're all grandfathered in
I'll use the search engine (we've got much to discuss)
Too much to discuss
Over a bucket of balls
I can recall the glow of your low beams
It's the big night in Tinsel City
Life became a spectator sport
I launch my fragrance called "Integrity"
I sell the fact that I can't be bought
Have I told you all about the time
That I got sucked into a hole through a hand held device?
I will flashback now and again but I'm usually alright
Thankfully the process has been simplified
Since the last time you tried

-- Alex Turner

Nextmv offers a comprehensive set of tools for solving Mixed Integer Programs (MIP). To get started with MIP use Platform for a fully customizable solution.

Platform

Please make sure you already completed the steps described in the 5-minute getting started experience.

To test that the Nextmv CLI is correctly configured, please run the following command on your terminal. It will get some files that are necessary to work with the Nextmv Platform. You can see the expected output as well.

Bash
Output

nextmv sdk install

To get started with MIP, consider the knapsack problem, which is a classical example of a MIP:

Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

This problem can be formulated as follows:

Math

\begin{equation} \max \sum_{\forall i \in I}(v_{i} \cdot x_{i}) \end{equation} Subject to: \begin{flalign} \sum_{\forall i \in I}(w_{i} \cdot x_{i}) &\leq W; &&\\ x_{i} &\in \set{0, 1}, &\forall i \in I. &&\\ \end{flalign} Where: \begin{flalign} -& I \text{ is the set of items.} &\\ -& W \text{ is the capacity of the knapsack.} &\\ -& v_{i} \text{ is the value of item } i \in I. &\\ -& w_{i} \text{ is the weight of item } i \in I. &\\ -& x_{i} = \begin{cases} 1 & \text{item } i \in I \text{ is selected;} \\ 0 & \text{otherwise.} \end{cases} \end{flalign}

These are the supported solvers and solver interfaces for MIP:

Provider	Description	Use with
FICO Xpress	Commercial solver.	Go (Nextmv SDK), Python
HiGHS	Open-source solver.	Go (Nextmv SDK)
OR-Tools	Open-source solver interface for various solvers. Included open-source solvers: `CLP`, `GLOP`, `PDLP`, `SCIP`.	Java, Python
Pyomo	Open-source interface for various solvers. Included open-source solvers in Cloud: `CBC`, `GLPK`.	Python

Depending on the solver of your choice, Get started by initializing one of the available community apps:

nextmv community clone -a knapsack-gosdk

Change directories into the template’s folder. For Java, build the main.jar.

cd knapsack-gosdk

You should see an input.json file with a sample knapsack problem.

JSON

{
  "items": [
    {
      "id": "cat",
      "value": 100,
      "weight": 20
    },
    {
      "id": "dog",
      "value": 20,
      "weight": 45
    },
    {
      "id": "water",
      "value": 40,
      "weight": 2
    },
    {
      "id": "phone",
      "value": 6,
      "weight": 1
    },
    {
      "id": "book",
      "value": 63,
      "weight": 10
    },
    {
      "id": "rx",
      "value": 81,
      "weight": 1
    },
    {
      "id": "tablet",
      "value": 28,
      "weight": 8
    },
    {
      "id": "coat",
      "value": 44,
      "weight": 9
    },
    {
      "id": "laptop",
      "value": 51,
      "weight": 13
    },
    {
      "id": "keys",
      "value": 92,
      "weight": 1
    },
    {
      "id": "nuts",
      "value": 18,
      "weight": 4
    }
  ],
  "weight_capacity": 50
}

Depending on the template's language, you can find the main code to solve the problem in one of the following files/directories:

Go: main.go file.
Java: src/main/java/com/nextmv/example directory, Main.java file.
Python: main.py file.

// package main holds the implementation of the mip-knapsack template.
package main

import (
	"context"
	"log"

	"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 the well known knapsack problem.
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          []item  `json:"items"`
	WeightCapacity float64 `json:"weight_capacity"`
}

// An item has a Value and Weight. ID is used to identify the item.
type item struct {
	ID     string  `json:"id,omitempty"`
	Value  float64 `json:"value"`
	Weight float64 `json:"weight"`
}

// solution represents the decisions made by the solver.
type solution struct {
	Items []item `json:"items,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.
	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(input, 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.Bool) {
	// We start by creating a MIP model.
	model := mip.NewModel()

	// Create a map of ID to decision variables for each item in the knapsack.
	itemVariables := make(map[string]mip.Bool, len(input.Items))
	for _, item := range input.Items {
		// Create a new binary decision variable for each item in the knapsack.
		itemVariables[item.ID] = model.NewBool()
	}

	// We want to maximize the value of the knapsack.
	model.Objective().SetMaximize()

	// This constraint ensures the weight capacity of the knapsack will not be
	// exceeded.
	capacityConstraint := model.NewConstraint(
		mip.LessThanOrEqual,
		input.WeightCapacity,
	)

	// For each item, set the term in the objective function and in the
	// constraint.
	for _, item := range input.Items {
		// Sets the value of the item in the objective function.
		model.Objective().NewTerm(item.Value, itemVariables[item.ID])

		// Sets the weight of the item in the constraint.
		capacityConstraint.NewTerm(item.Weight, itemVariables[item.ID])
	}

	return model, itemVariables
}

// format the solution from the solver into the desired output format.
func format(input input, solverSolution mip.Solution, itemVariables map[string]mip.Bool) solution {
	if !solverSolution.IsOptimal() && !solverSolution.IsSubOptimal() {
		return solution{}
	}

	items := make([]item, 0)
	for _, item := range input.Items {
		if solverSolution.Value(itemVariables[item.ID]) > 0.9 {
			items = append(items, item)
		}
	}

	return solution{
		Items: items,
	}
}

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

go run . -runner.input.path input.json -runner.output.path output.json -solve.duration 10s

After running, an output.json file should have been created with the solution.

Go (Nextmv SDK)

{
  "options": {
    "solve": {
      "control": {
        "bool": [],
        "float": [],
        "int": [],
        "string": []
      },
      "duration": 10000000000,
      "mip": {
        "gap": {
          "absolute": 0.000001,
          "relative": 0.0001
        }
      },
      "verbosity": "off"
    }
  },
  "solutions": [
    {
      "items": [
        {
          "id": "cat",
          "value": 100,
          "weight": 20
        },
        {
          "id": "water",
          "value": 40,
          "weight": 2
        },
        {
          "id": "phone",
          "value": 6,
          "weight": 1
        },
        {
          "id": "book",
          "value": 63,
          "weight": 10
        },
        {
          "id": "rx",
          "value": 81,
          "weight": 1
        },
        {
          "id": "coat",
          "value": 44,
          "weight": 9
        },
        {
          "id": "keys",
          "value": 92,
          "weight": 1
        },
        {
          "id": "nuts",
          "value": 18,
          "weight": 4
        }
      ]
    }
  ],
  "statistics": {
    "result": {
      "custom": {
        "constraints": 1,
        "provider": "HiGHS",
        "status": "optimal",
        "variables": 11
      },
      "duration": 0.123,
      "value": 444
    },
    "run": {
      "duration": 0.123
    },
    "schema": "v1"
  },
  "version": {
    "go-mip": "VERSION",
    "sdk": "VERSION"
  }
}

🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉 🎉

You are all set to keep exploring! Here are the next steps to continue your journey:

Deploy your app to Nextmv Cloud.
Run remotely on Nextmv Cloud.
Test and experiment with your app.
Take a deeper look at the supported solvers.
Explore more examples of solving MIP problems using the Nextmv Go SDK.
- Meal allocation: allocate meals to bunnies to maximize binkies.
- Incentive allocation: allocate discounts to users while not exceeding a budget.

If you are working with Go (Nextmv SDK) please continue reading.

Go (Nextmv SDK) considerations

In general, the steps to solve a MIP are:

Create a Model.
Add Variables to the model, by calling methods on the Model.
Set the Objective of the model, and the sense (max or min), by calling methods on the Model.
Add Constraints to the model, by calling methods on the Model. For each Constraint, you define the sense, the right hand side and add terms to it.
Solve the MIP defined in the Model by using a Solver.

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.

Options

All MIP applications are configurable through options.

Runner options change how the runner outputs solutions and reads/writes data.
Solve options change the behavior of the solver.

Options can be configured when running locally with the Nextmv platform or when running remotely on Nextmv Cloud. Running remotely is possible when a custom app built has been deployed.

Visit the options reference for detailed information on all the available options.

Options - running locally

CLI flags. They are added after the double-dash character (--). Consider the same example that was shown in the platform section for running the code from the template:

Bash

go run . -runner.input.path input.json -runner.output.path output.json -solve.duration 10s

Environment variables. To set an environment variable, convert its corresponding CLI flag to uppercase, replacing each period (.) with an underscore (_) and removing the leading dash (-). For example: -solve.duration is equivalent to SOLVE_DURATION. Here you can find the same example that was shown above. This time, however, we show how to use environment variables instead of CLI flags. Notice that there is no need for the double-dash character (--) anymore.

Bash

RUNNER_INPUT_PATH=input.json RUNNER_OUTPUT_PATH=output.json SOLVE_DURATION=10s go run .

If both an environment variable and its corresponding CLI flag are defined, the CLI flag will overwrite the environment variable.

Options - running remotely

Use the "options" key in the JSON payload when executing a run on Nextmv cloud. The leading dash (-) is removed from the option name, when compared to running locally. For example, -solve.duration on a local run is equivalent to solve.duration run remotely.

Note that all values should be set as a string, regardless of the type.

Here is an example of how to use options when running remotely:

JSON

{
  "input": {},
  "options": {
    "solve.duration": "3s",
    "solve.mip.gap.relative": "0.15",
    "solve.verbosity": "high"
  }
}

Options - output

Most options are parsed to the output, under the options key:

JSON

"options": {
  "solve": {
    "control": {
      "bool": [],
      "float": [],
      "int": [],
      "string": []
    },
    "duration": 10000000000,
    "mip": {
      "gap": {
        "absolute": 0.000001,
        "relative": 0.0001
      }
    },
    "verbosity": "off"
  }
},

When working with platform, you may also modify the options in code, which would override the ones passed from the runner.

Options - solver control parameters

Visit the options reference for more detail on using solver control parameters.

Please find relevant links and examples for each provider in the supported solvers page.

Each provider has its own set of parameters for controlling their solver. Depending on the option's data type, you can use one of the following flags to set these parameters. The list showcases CLI-style flags.

-solve.control.bool: parameters with bool values.
-solve.control.float: parameters with float values.
-solve.control.int: parameters with int values.
-solve.control.string parameters with string values.

Each of these options receives a name=value pair. To set multiple options of the same type, use a comma-separated list: name1=value1,name2=value2. Note that not all providers support all data types.

For example: -solve.control.float "mip_heuristic_effort=0.7"