Integer Optimization

Problems that require some of the variables to be integers, but not all, are often called Mixed Integer Programs or Mixed Integer Linear Programs. 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.)

OR-Tools offers several options for solving problems like these:

The first two of these — MIP and CP — are very general solvers, which you can use to solve any integer optimization problem. The next two sections present an example with solutions using both options. Comparing MIP and CP provides examples of larger problems and compares the speed of the two solvers for them.

The min cost flow solver is a more specialized solver, which you can apply to problems that are set up as network flow problems — see Assignment as a Min Cost Flow Problem for an example. For these problems, min cost flow is much faster than either MIP or CP.

Send feedback about...