How many leaves of Victoria regia fit into this pond in Gothenburg's Palm house? MiniZinc can compute the answer.

A web service to solve integer linear programs with MiniZinc+Gecode in a Docker container

In operations research, ILP-solvers (integer linear programming) are a standard tool to find optimized configurations in constrained environments. It can answer questions like:

Which machines should I buy to produce how many products of each sort to maximize profit?
How do I assign wireless communication channels to devices to minimize interference?
How should I put parcels in my truck so that everything fits and the load is evenly distributed on the axes?

The hard thing is to reformulate the problem with constraint equations and a cost function. But once you did that, the ILP-solver does it’s magic and finds a solution. The problem with ILP-solvers is that their input language is often verbose and thus hard to maintain.

The people at Monash University & co have developed a high-level, solver-independent language to interface with a range of open source and commercial ILP-solvers: MiniZinc. I highly recommend taking their free, fun and challenging online course where you need to help out protagonists in the novel Romance of the Three Kingdoms with problems such as maximizing the force of their armies or organizing a glorious banquet.

I believe we should use equation solvers more often in our apps and services. For my startup idea Chaski, I’m using it to solve packing problems to derive pick-up and delivery constraints (which items fit into the truck) that will influence the delivery tour.

Ok 🤔, I admit, solving packing problems with an ILP-solver is a classic. But the next time I find myself developing a complicated heuristic in my day job, I will try to come up with some equations first and let MiniZinc do the heavy lifting. Chances are that the ILP solver is better, faster and more stable than my algorithm. 😉

I created a dockerized Python web service around MiniZinc so that I can hook it up easily in my projects.

Try it!

To build and run the service run the following on a system with Docker installed:

1
2
3
4


git clone https://github.com/gubser/minizinc-webservice.git
cd minizinc-webservice
docker build . -t minizinc --build-arg NUM_BUILD_JOBS=4
docker run -p 5004:80 minizinc

We want to run the following optimization program written in MiniZinc language:

1
2
3
4
5
6
7
8
9


int: budget;
var 0..1000: F;
var 0..400: L;
var 0..500: Z;
var 0..150: J;

constraint 13*F + 21*L + 17*Z + 100*J <= budget;

solve maximize 6*F + 10*L + 8*Z + 40*J;

To do that run the following cURL command:

1
2
3
4
5
6


curl -H "Content-Type: application/json" -X POST -d '{
	"problem": "int: budget;\nvar 0..1000: F;\nvar 0..400: L;\nvar 0..500: Z;\nvar 0..150: J;\n\nconstraint 13*F + 21*L + 17*Z + 100*J <= budget;\n\nsolve maximize 6*F + 10*L + 8*Z + 40*J;\n",
	"data": {"budget": "10000"},
	"args": ["--output-mode", "json", "--output-objective"],
	"timeout_ms": 10000
}' http://localhost:5004/json

It should yield:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


{
	"result": "complete",
	"values": {
		"F": 0, 
		"L": 392, 
		"Z": 104, 
		"J": 0, 
		"_objective": 4752
	}, 
	"stdout": "{\n  \"F\" : 0,\n  \"L\" : 392,\n  \"Z\" : 104,\n  \"J\" : 0,\n  \"_objective\" : 4752\n}\n----------\n==========\n", 
	"stderr": "", 
	"returncode": 0, 
	"queueTimeMs": 0, 
	"computeTimeMs": 84
}

Have fun!

Elio Gubser

A web service to solve integer linear programs with MiniZinc+Gecode in a Docker container

Try it!

Links