Integer Optimization

Problems that require some of the variables to be integers, but not all, are often called Mixed Integer Programs (MIPs) or Mixed Integer Linear Programs (MILPs). Here are a couple of examples:

  • A company that sells various consumer items needs to decide how many of each to manufacture per month in order to maximize profit. In this type of problem, the variables represent quantities of discrete items, such as cars or television sets, which must be integers.
  • A package delivery company needs to assign trucks to various routes in order to meet their delivery schedule while minimizing cost. Sometimes the best way to set up a problem like this is to let the variables represent binary (0-1) decisions of which trucks to assign to which routes. The variable is 1 if a given truck is assigned to a specific route, and 0 otherwise. Since the variables can only take on the values 0 or 1, this is also an integer optimization problem. (In particular, it's a Boolean optimization problem, which OR-Tools has specialized techniques for solving.)

For a good primer on integer optimization, we recommend the Mosek modeling cookbook.

The main tools for solving MIPs with OR-Tools are the MIP solver and the CP-SAT solver. The next two sections present an example with solutions using both solvers.

If your problem can be set up as network flow problem, the fastest way to solve it is with the min cost flow solver. See Assignment as a Min Cost Flow Problem for an example. For these special types of problems, min cost flow is much faster than either the MIP or CP-SAT solvers.