Tutorials

Basic MIP Tutorial

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

This tutorial 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.

nextmv install
Copy

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:

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

This tutorial 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-basic. You should obtain an output similar to the one depicted.

go mod init mip-basic
Copy

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

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

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

module mip-basic

go 1.19

require github.com/nextmv-io/sdk v0.20.6 // indirect
Copy

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

package main

func main() {}
Copy

Your application should roughly contain this structure:

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

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()
Copy

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)
Copy

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()
Copy

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)
Copy

Solve the model

You can solve your MIP defined in the model by using a Solver. In this tutorial 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)
}
Copy

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")
}
Copy

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")
	}
}
Copy

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

nextmv run local main.go
Copy

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

Page last updated

Go to on-page nav menu