A new interface for MIP solving with Nextmv

Whether you’re finding optimized solutions for marketing campaign spend, sports team rostering, or warehouse location placement, it’s likely you’ll come across mixed integer programming (MIP). MIP is a well-known, widely used optimization paradigm for solving these types of problems, and we’ve made it available as another solving paradigm in Nextmv. 

Nextmv is a platform designed for building, testing, deploying, and operating decision models at speed and scale. It treats decisions as code and bridges the gap between mathematical optimization and production infrastructure more easily and faster. Nextmv also seeks to provide the flexibility to model and solve many types of optimization problems using many techniques, whether that’s decision diagrams, heuristics, or, in this case MIP. We’ve added MIP solving capabilities to Nextmv by way of a Go module using the HiGHS interface, the first MIP-based solving paradigm available in Nextmv. 

In this blog post, I’ll explain the Nextmv MIP module and demonstrate how to stand up a customizable MIP model with Nextmv in minutes. You can work with MIP templates in Nextmv with a free account.

A mixed integer programming and HiGHS primer 

MIP is commonly used for optimizing operations in supply chain management, retail, logistics, employee scheduling, and beyond. It has an active community of users, modelers, and developers in both academia and industry. 

To solve a mixed integer problem is to optimize a linear objective function of many variables, subject to linear constraints. Solving this problem is called linear programming or linear optimization. When variables are constrained to be integer values then this is called mixed integer programming or mixed integer optimization. (Interesting aside: mixed integer programming does not come from programming code, rather it refers to a schedule in military terms.) 

Solutions to mixed integer problems are found using MIP solvers. There are many commercial and open source varieties, each with its strengths and weaknesses. Modeling a mixed integer problem consists of defining variables and using these variables in the form of constraints and an objective. Because the user is limited to expressing a linear objective and linear constraint, the underlying solver can find good solutions relatively quickly. 

HiGHS is an MIT-licensed open source linear optimization solver created in 2016 by a team at the University of Edinburgh. It includes a branch-and-cut MIP solver suited to solving all kinds of allocation problems, and features several interfaces for working with Julia, Rust, Python, R, and more. We use the HiGHS solver as our first provider for solving MIP problems in Go in the Nextmv SDK.

A Go module for solving MIP problems

Nextmv’s solver framework is extensible. We’ve extended it to solve MIP problems by creating a Go module for MIP, which is capable of supporting many solver providers. 

This post demonstrates how to use the HiGHS solver with Nextmv. HiGHS already shows impressive performance, comes with a permissive license, and is actively maintained.   

Our HiGHS solver interface can readily be used within the Nextmv modeling framework. It is distributed as part of our SDK, so there is no extra installation or compilation required. We support ^arm64 and ^amd64 both on ^linux and ^darwin. 

Under the hood, the interface uses CGO to interface HiGHS’ C API and we use zig for cross-compiling. 

Using HiGHS and MIP to solve a meal allocation problem

To explain MIP modeling in Nextmv, let’s explore a fun problem where we try to optimize the meals of bunnies. In this example, we’ll know that the bunnies are getting good meals by their happiness levels as measured by binkies: playful leaps that usually feature a 180-degree midair rotation. 

We have a limited supply of food to feed our bunnies: 12 units of endive and 5 units of carrot. There are two types of carrot-endive meals we can feed our bunnies: 

• Meal A = 1 unit of carrot and 3 units of endive for 6 binkies
• Meal B = 1 unit of carrot and 2 units of endive for 5 binkies

Based on this, how many A and B meals do we serve to maximize the happiness of our bunnies? We can use MIP in Nextmv to quickly model and solve this problem. At Nextmv, we code in Go and model our meal allocation MIP problem as follows:

model	          := mip.NewModel()

numberOfMealsA 	  := model.NewInt(0, 100)
numberOfMealsB    := model.NewInt(0, 100)

model.Objective().SetMaximize()
model.Objective().NewTerm(6.0, numberOfMealsA)
model.Objective().NewTerm(5.0, numberOfMealsB)

endivesConstraint := model.NewConstraint(mip.LessThanOrEqual, 12.0)
endivesConstraint.NewTerm(3.0, numberOfMealsA)
endivesConstraint.NewTerm(2.0, numberOfMealsB)

carrotsConstraint := model.NewConstraint(mip.LessThanOrEqual, 5.0)
carrotsConstraint.NewTerm(1.0, numberOfMealsA)
carrotsConstraint.NewTerm(1.0, numberOfMealsB)

Now that we’ve modeled our MIP problem using the Nextmv code-based framework, we can now ask the HiGHS solver for a solution to our bunny binky problem with Nextmv. Here’s what that looks like:

solverProvider 	:= mip.SolverProvider("highs")

solver, err 	:= mip.NewSolver(solverProvider, model)
…
solution, err 	:= solver.Solve(mip.NewSolveOptions())
…
if solution.HasValues() {
	fmt.Printf("binkies = %v\n", solution.ObjectiveValue())
        fmt.Printf("optimal = %v\n", solution.IsOptimal())
	fmt.Printf("# meal A = %v\n", solution.Value(numberOfMealsA))
	fmt.Printf("# meal  B = %v\n", solution.Value(numberOfMealsB))
} else {
	fmt.Printf("no solution found\n")
}

This produces the following output:

binkies = 27
optimal = true
# meal A = 2.0000000000000004
# meal B = 2.9999999999999996

In microseconds, we got an optimal solution to our problem: serving 2 of meal A and 3 of meal B will yield the most bunny binkies (and therefore happiness) based on our food supplies. (Note: Meal B isn’t printed as an integer because the solver uses float values. Within its precision, this can be interpreted as 3.)

Next steps

Our meal allocation example is obviously a small scale MIP problem. But it serves as a speedy starting point for working toward solving larger problems consisting of many constraints and variables, which MIP algorithms such as HiGHS are well suited for. It’s just a hop, skip, and a binky to go from happy bunnies to happy customers of subscription box services for fashion, dog toys, and more. 

We’re continuing to develop and mature the MIP solving capabilities of Nextmv to include more solver providers, as part of our multi-solver framework. There’s an exciting future ahead and we’d love feedback from the community. To get started with MIP solving and Nextmv, please visit our documentation.