Mixed Integer Programming

This reference guide assumes you already completed the steps described in the 5-minute getting started experience. To test that the Nextmv CLI is correctly configured, you can optionally 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

The Nextmv Software Development Kit (SDK) lets you automate any operational decision in a way that looks and feels like writing other code. It provides the guardrails to turn your data into automated decisions and test and deploy them into production environments.

Introduction

The mip package, part of the Nextmv SDK, is an interface for solving various types of Mixed-Integer Problems (MIP). This example aims to solve a basic problem to demonstrate the steps required to solve a MIP.

Consider the following MIP:

Text

maximize    6x + 5y
subject to  3x + 2y <= 12
            1x + 1y <= 5
             x      >= 0
                  y >= 0
x, y are integer

This guide will teach you how to solve this MIP.

Let's see how.

Set up the environment

Somewhere in your computer, create a Go module called mip. You should obtain an output similar to the one depicted.

Bash
Output

go mod init mip

Now add the Nextmv SDK to your dependencies. You should observe the latest version being pulled as part of the output.

Bash
Output

go get github.com/nextmv-io/sdk@latest

You should now have a go.mod file that looks like this:

Text

module mip

go 1.19

require github.com/nextmv-io/sdk VERSION // indirect

To proceed with running the example, create an empty main.go file in the mip directory, like the code snippet below.

package main

func main() {}

Your application should roughly contain this structure:

Text

.
├── go.mod
├── go.sum
└── main.go

The following steps showcase how to complete the main function of your program to solve the basic MIP described above.

Create the model

A Model is the main interface to model a Mixed-Integer Problem. You define a problem by adding variables, an objective and constraints to a model.

// Create a MIP model
model := mip.NewModel()

First, you add the variables to a model. In this case you add two int variables, x and y, with initial bounds that seem reasonable for the problem you are solving.

// Create an int variable x with bounds [0, 1_000_000]
x := model.NewInt(0, 1_000_000)

// Create an int variable y with bounds [0, 1_000_000]
y := model.NewInt(0, 1_000_000)

Next you define the objective, 6x + 5y, and define it is a maximization problem.

// Create the terms in the objective
model.Objective().NewTerm(6, x)
model.Objective().NewTerm(5, y)
model.Objective().SetMaximize()

Lastly, you define the constraints. For each constraint you define the sense, the right hand side and you add the terms on the constraint.

// Create the two constraints
// A: 3x + 2y <= 12
constraintA := model.NewConstraint(mip.LessThanOrEqual, 12)
constraintA.NewTerm(3, x)
constraintA.NewTerm(2, y)
// B: 1x + 1y <= 5
constraintB := model.NewConstraint(mip.LessThanOrEqual, 5)
constraintB.NewTerm(1, x)
constraintB.NewTerm(1, y)

Solve the model

You can solve your MIP defined in the model by using a Solver. In this guide we suggest you use the HiGHS solver. After creating the solver you can solve the problem by invoking solver.Solve with the options for the invocation.

// Create solver for the problem
solver, err := mip.NewSolver("highs", model)
if err != nil {
	panic(err)
}

// Invoke the solver with default solve options
solution, err := solver.Solve(mip.NewSolveOptions())
if err != nil {
	panic(err)
}

You can find the solution of a Solver invocation in the Solution returned.

// If the solver has created a solution print the result
if solution.HasValues() {
	fmt.Printf("objective = %v\n", solution.ObjectiveValue())
	fmt.Printf("x = %v\n", math.Round(solution.Value(x)))
	fmt.Printf("y = %v\n", math.Round(solution.Value(y)))
} else {
	fmt.Println("No solution found")
}

The complete main.go file should now look like the code snippet below.

package main

import (
	"fmt"
	"math"

	"github.com/nextmv-io/sdk/mip"
)

func main() {
	// Create a MIP model
	model := mip.NewModel()

	// Create an int variable x with bounds [0, 1_000_000]
	x := model.NewInt(0, 1_000_000)

	// Create an int variable y with bounds [0, 1_000_000]
	y := model.NewInt(0, 1_000_000)

	// Create the terms in the objective
	model.Objective().NewTerm(6, x)
	model.Objective().NewTerm(5, y)
	model.Objective().SetMaximize()

	// Create the two constraints
	// A: 3x + 2y <= 12
	constraintA := model.NewConstraint(mip.LessThanOrEqual, 12)
	constraintA.NewTerm(3, x)
	constraintA.NewTerm(2, y)
	// B: 1x + 1y <= 5
	constraintB := model.NewConstraint(mip.LessThanOrEqual, 5)
	constraintB.NewTerm(1, x)
	constraintB.NewTerm(1, y)

	// Create solver for the problem
	solver, err := mip.NewSolver("highs", model)
	if err != nil {
		panic(err)
	}

	// Invoke the solver with default solve options
	solution, err := solver.Solve(mip.NewSolveOptions())
	if err != nil {
		panic(err)
	}

	// If the solver has created a solution print the result
	if solution.HasValues() {
		fmt.Printf("objective = %v\n", solution.ObjectiveValue())
		fmt.Printf("x = %v\n", math.Round(solution.Value(x)))
		fmt.Printf("y = %v\n", math.Round(solution.Value(y)))
	} else {
		fmt.Println("No solution found")
	}
}

Run the program using the Nextmv CLI. You can check the output to see the actual solution to the problem.

Bash
Output

nextmv sdk run main.go

The precision of the values printed can be different depending on your machine.

Click here for more information on the mip package

Mixed Integer Programming

Learn to model and solve a MIP with the Nextmv SDK.

Introduction

Set up the environment

Create the model

Solve the model

Contents