• Integer Optimization

Linear optimization problems that require some of the variables to be integers are called Mixed Integer Programs (MIPs).

These variables can arise in a couple of ways:

  • Integer variables that represent numbers of items, such as cars or television sets, and the problem is to decide how many of each item to manufacture in order to maximize profit.
    Typically, such problems can be set up as standard linear optimization problems, with the added requirement that the variables must be integers. The next section shows an example of this type of problem.

  • Boolean variables that represent decisions with 0-1 values.
    As an example, consider a problem that involves assigning workers to tasks ( see Assignment). To set up this type of problem, you can define Boolean variables xi,j that equal 1 if worker i is assigned to task j, and 0 otherwise.

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

Tools

Google provides few ways to solve MIP problems:

  • MPSolver: A wrapper for several third-party MIP solvers, which use standard branch-and-bound techniques.
  • CP-SAT solver: A constraint programming solver that uses SAT (satisfiability) methods.
  • Original CP solver: A constraint programming solver.

Which solver should I use?

There's no ironclad rule for deciding whether to use a MIP solver or the CP-SAT solver. As a rough guide:

  • MIP solvers are better suited for problems that can be set up as a standard LP , but with arbitrary integer variables, like the first example above.
  • The CP-SAT solver is better suited for problems in which most of the variables are Boolean, like the second example above.

For typical MIPs that have both integer and Boolean variables, there's often no clear difference in speed between the two solvers, so your choice may come down to personal preference.

For examples that use both the MIP and CP-SAT solvers, see Solving an Assignment Problem and the other assignment sections.

Another way to solve integer programming problems is using a network flow solver.
See Assignment as a Min Cost Flow Problem for an example.
For a problem that can be set up as a network flow, the min cost flow solver can be faster than either the MIP or CP-SAT solvers. However, not all MIPs can be set up this way.