Sometimes approaching a problem with the right tools can mean the difference between weeks of work and months or years of work on the same feature. While helping companies, I’ve observed many engineering teams set out to write custom code for their central problem but have the code mysteriously grow in complexity to the point where their progress slowed to a crawl. When looking at the code, I could recognize that the problematic piece of code effectively boiled down to a complex constraint satisfaction problem. That is, a problem like, “Given five locations, what is the shortest trip that visits all of them?” or, “Given 20 people that are available at certain times during the day, create a schedule where as many as possible of them can meet.”
These problems are often extremely tricky to solve in something like JavaScript and without any background in the science. Unwittingly, these engineers have been dragged kicking and screaming into the world of Operations Research, the study of optimal decision-making.
Tackling Operations Research
They are bravely tackling some of the hardest computer science problems that exist. It’s not that surprising to find yourself solving one of these problems, as these “optimization under constraints” problems are actually all around us and have a rich history in business. Solving these problems directly and iteratively with the tools at hand often creates “ball of mud” code that is surprisingly slow to run and hard to optimize. There certainly are times when you might want to “hand code” a solution, but it’s often much later, when you truly get a better appreciation for the scope of the problem.
It can definitely be easier and faster (in terms of development and in terms of runtime) to solve these optimization problems, and tools exist that light a better way. These tools can seem niche and difficult, and everyone that works on them may seem to have a PhD and/or 20+ years of experience in the field. But don’t let any of that intimidate you, it’s more accessible than you might think. These folks have worked hard to make it as easy as possible on you. Let’s dive in.
In this post, I’d like to introduce you to MiniZinc and Google’s OR Tools. And I’ll also touch a bit on how to integrate it into your Node backend.
MiniZinc and OR Tools
MiniZinc is a language and a toolchain for expressing a problem’s constraints and translating these constraints into an input for many different kinds of constraint solvers. One of the better solvers to use for this is the CP-SAT solver that comes with Google’s OR Tools (for the curious, the CP-SAT name refers to the fact that this is a “constraint programming” solver that uses “satisfiability” methods). The way you might judge this is via the results of a yearly challenge that MiniZinc holds where they test these solvers. You can check out that competition here, where you’ll see that the OR Tools CP-SAT solver does quite well and is even getting better every year.
MiniZinc is developed by some wonderful researchers at Monash University, lead by Peter Stuckey and Guido Tack (by the way, check out Dr. Stuckey’s very accessible Coursera course on using MiniZinc here). The toolkit is a great choice for young companies and projects because it’s powerful, open source, and free to use. It has pretty good documentation and a fairly robust community of users.
OR Tools is a toolkit developed by a team of researchers at Google. It includes many kinds of solvers, of which CP-SAT is just one. It has a ton of functionality beyond what we’re going to use, and, in fact, has its own API for expressing discrete optimization problems in Python, Java, C++, and C#. We’ll use MiniZinc because of the relative simplicity and flexibility to try other solvers as the backed, but using OR Tools directly would be a fine choice, too.
Installation
If you have a Mac with Homebrew installed, the easiest way to install both tools is by running:
brew install minizinc brew install or-tools
You can look at the MiniZinc and Google OR Tools documentation if your situation differs from that. There may be a little bit of configuration you have to do with MiniZinc to get it to recognize OR Tools as a solver, too.
Expressing a Scheduling Problem in MiniZinc
Let’s set up a simple problem to model. We’re going to pretend that we’re running a singles tennis league and we’re going to schedule some games. Given a list of matches between players and some quantity of time slots, we’d like to schedule games so that a player is never scheduled to play two games at once (as this can be terribly straining!).
Here’s an example of what this might look like as a MiniZinc file:
% 1. Parameters
int: num_players = 4; % Number of players
int: num_games = 3; % Number of games to schedule
int: num_time_slots = 5; % Total number of time slots available
% 1a. Define the range of values that GAMES/PLAYERS can have
set of int: GAMES = 1..num_games; % Set of games; each game will be represented by a number between 1 and num_games
set of int: PLAYERS = 1..num_players; % Set of players; each player will be represented by a number between 1 and num_players
% 1b. Define which games are to be played, each game is 2-element entry in an array of length GAMES.
% This array gives the pair of players for each game.
% Here, game 1 has players 1 and 2, game 2 has players 3 and 4, and game 3 has players 1 and 3.
array[GAMES, 1..2] of int: game_players = [| 1, 2
| 3, 4
| 1, 3 |];
% 2. Decision variables
% Which game starts at which time? Solver will figure out what this array looks like (note the "var" keyword, indicating a variable to solve for).
array[GAMES] of var 1..num_time_slots: game_start_times; % Start time for each game
% 3. Constraints
% Constraint: Some more advanced syntax going on here. This constrain essentially means: No player should play two games simultaneously
constraint forall(g1, g2 in GAMES where g1 < g2) ( let {set of int: common_players = {game_players[g1, 1], game_players[g1, 2]} intersect {game_players[g2, 1], game_players[g2, 2]}} in if card(common_players) > 0 then
game_start_times[g1] != game_start_times[g2]
else
true
endif
);
% 3a. Objective
% Objective (optional): Minimize the latest time slot used by a game. That is, start each game ASAP!
var 1..num_time_slots: makespan;
constraint makespan = max([game_start_times[g] | g in GAMES]);
% 4. Solution mode: Minimize the value of the "makespan" constraint. That is, minimize the maximum start time of a game.
solve minimize makespan;
% 5. Output: Format how the solution is printed in the terminal
output [ "Game \(g): starts at slot \(game_start_times[g]) with players \(game_players[g, 1]) and \(game_players[g, 2]) \n" | g in GAMES];
Parts of a MinZinc File
MinZinc files have five main sections:
-
Parameters – These are the inputs to the problem. The number of players, number of games, and number of time slots are the parameters of our scheduling problem. It’s also something likely to vary if, say, our tennis league grows. It’s possible to specify these separately from the main solution file so that it doesn’t have to be rewritten for each new instance of this problem, but we do that in-line in our example for simplicity.
-
Variables – This is what our solver will figure out. A variable has the
varkeyword in its declaration. The solver will adjust this variable until it fits our constraints and will then give its value to us in the solution. In this case, our variable to solve for is an array of time slot numbers for each game (that is, the time slot when each game will start) -
Constraint – Next we describe the constraints on the variables to the solver. Each constraint has the keyword
constraintnext to it. In human language, our constraint says that “for each game, if a player in game 1 is the same as the player in game 2, then the time of these games must not be the same.” Note that many assignments of variables to this constraint could be a solution, so with just this constraint MiniZinc could spit out multiple solutions. -
Solution mode (with optional objective) – MiniZinc can ask the solver to give us either solutions that “satisfy” our constraints or, we can provide some constraint and “minimize”/”maximize” a value. In our file, we have defined an objective constraint called
makespanthat takes on the value of the last time slot of the last game. We’d like all the games to happen as quickly as possible, so we’d like the last game to happen as soon as possible. The linesolve minimize makespantells the solver to find a combination of variables that minimizes this value. Not all problems have solutions, and, in that case, the solver would tell us the problem is “unsatisfiable.” -
Output – This tells MiniZinc what to output. Usually, these will be the values of your variables in the format that you’d like to read/parse them. We’ve formatted our output to tell us when each game will start and who the players will be. During solving, when the solver finds a possible solution, it will output a single-dashed line like
----------between possible solutions as it finds them. Then it will write a double-dashed==========once it finds an optimal solution.
Solution
To solve this problem, you can run:
minizinc --solver cp-sat ./schedule.mzn
Where the `–solver cp-sat` indicates that we want to use the solver configuration for our OR Tools CP-SAT solver and `./schedule.mzn` is the location of the file we show above. Once you run this, you will see an output that looks like:
Game 1: starts at slot 1 with players 1 and 2 Game 2: starts at slot 1 with players 3 and 4 Game 3: starts at slot 2 with players 1 and 3 ---------- ==========
On modern hardware, the answer will be spat out almost instantaneously! And if you’re still developing the rules for your tennis league, iterating on the mzn file will go a lot faster than coding and re-coding the solver yourself. If you have the time, I encourage you to try scaling the inputs to see how the solver scales to larger inputs.
Using MiniZinc from JavaScript
It’s really neat to have something that will solve particularly challenging optimization problems, but it would definitely be more practical if we could use this in a web application! For example, if we were building web app for managing tennis games, we’d want to be able to invoke MiniZinc programmatically and ingest the solution in a machine-readable format.
Fortunately, MiniZinc does have a library that supports this. You can choose to use a WebAssembly version of MiniZinc.js if you’re running it just in the browser, and you’d have a limited set of solvers. But, it can also interact with a binary installation of MiniZinc if you’re running it as part of a Node back end.
To install the library, you would run npm install minizinc. Note that this requires that you have the minizinc binary and also the Google OR Tools installation too. Here’s a snippet using TypeScript, with Node and Express, of what this might look like:
import * as MiniZinc from "minizinc";
// Configure the MiniZinc library. Here we're pointing it to the "minizinc" executable in the PATH, your environment might require more configuration
await MiniZinc.init({
minizinc: "minizinc",
});
const model = new MiniZinc.Model();
// Add the mzn file that represents our problem
model.addFile("schedule.mzn");
// Pass the parameter values to use
model.addJson(parameters); // parameters looks like { num_games: 4, num_players: 5, num_timeslots: 6 }
// Run the solver
const solve = model.solve({
options: {
solver: "cp-sat", // Use the OR Tools CP-SAT solver
"time-limit": 10000, // Run for 10 seconds max
statistics: true, // Output the stats about the run every so often
},
});
// Listen to when the solver solves or spits out statistics and log it out
solve.on("solution", (solution) => console.log(solution.output.json));
solve.on("statistics", (stats) => console.log(stats.statistics));
const result = await solve;
// The final result will be a JSON object with the value of every variable (among other data)
console.log(result)Solving Optimization Problems with MiniZinc and Google OR Tools
I’ve tried to save space here, but please check out this GitHub repository if you want to see a more complete version of this solution! I hope that someone finds this useful and that it saves them a whole lot of development time.