Stay organized with collections
Save and categorize content based on your preferences.
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.
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.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-28 UTC."],[[["\u003cp\u003eMixed Integer Programs (MIPs) are linear optimization problems where some variables must be integers, representing quantities or decisions.\u003c/p\u003e\n"],["\u003cp\u003eGoogle offers tools for solving MIPs: MPSolver uses standard techniques, while CP-SAT solver employs constraint programming, particularly suitable for problems with many Boolean variables.\u003c/p\u003e\n"],["\u003cp\u003eChoosing between MIP and CP-SAT solvers depends on the problem structure, with MIP solvers often preferred for problems with standard LP formulations and arbitrary integer variables, while CP-SAT excels in scenarios dominated by Boolean variables.\u003c/p\u003e\n"],["\u003cp\u003eNetwork flow solvers can offer faster solutions for specific MIPs that can be formulated as network flow problems.\u003c/p\u003e\n"]]],["Mixed Integer Programs (MIPs) handle linear optimization problems requiring integer variables, which can represent item counts or Boolean decisions. Google offers MPSolver for MIPs, CP-SAT, and original CP solvers for constraint programming. MIP solvers suit problems with arbitrary integer variables, while CP-SAT excels with predominantly Boolean variables. Network flow solvers are faster for problems adaptable to this format, although not all MIPs fit this structure. The choice between MIP and CP-SAT often depends on problem structure and personal preference.\n"],null,["- Integer Optimization\n\nLinear optimization problems that require some of the variables to be integers\nare called *Mixed Integer Programs* (MIPs).\n\nThese variables can arise in a couple of ways:\n\n- **Integer variables** that represent numbers of items, such as cars or\n television sets, and the problem is to decide how many of each item to\n manufacture in order to maximize profit. \n\n Typically, such problems can be set up as standard linear optimization\n problems, with the added requirement that the variables must be integers.\n The [next section](/optimization/mip/mip_example) shows an example of this\n type of problem.\n\n- **Boolean variables** that represent decisions with 0-1 values. \n\n As an example, consider a problem that involves assigning workers to tasks (\n see [Assignment](/optimization/assignment)). To set up this type of problem,\n you can define Boolean variables `x`~i,j~ that equal 1 if worker `i`\n is assigned to task `j`, and 0 otherwise.\n\nFor a good primer on integer optimization, we recommend the\n[Mosek modeling cookbook](https://docs.mosek.com/modeling-cookbook/index.html).\n\nTools\n-----\n\nGoogle provides few ways to solve problems:\n\n- [MPSolver](/optimization/lp/mpsolver): A wrapper for several third-party MIP solvers, which use standard branch-and-bound techniques.\n- [CP-SAT solver](/optimization/cp/cp_solver): A **constraint programming** solver that uses SAT (satisfiability) methods.\n- [Original CP solver](/optimization/cp/original_cp_solver): A **constraint programming** solver.\n\n| **Note:** Google also offers a cloud API to a [MILP](https://aihub.cloud.google.com/u/0/p/products%2F03a54ca4-f9ba-489b-bbb3-b6ca8c22c5cf) solver through AI Workshop. If you are interested in using that solver, you can [apply for access](https://events.withgoogle.com/ai-workshop/registrations/new).\n\nWhich solver should I use?\n--------------------------\n\nThere's no ironclad rule for deciding whether to use a MIP solver or the CP-SAT\nsolver. As a rough guide:\n\n- 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.\n- The CP-SAT solver is better suited for problems in which most of the variables are Boolean, like the second example above.\n\nFor typical MIPs that have both integer and Boolean variables, there's often no\nclear difference in speed between the two solvers, so your choice may come down\nto personal preference.\n\nFor examples that use both the MIP and CP-SAT solvers, see\n[Solving an Assignment Problem](/optimization/assignment/assignment_example)\nand the other assignment sections.\n\nAnother way to solve integer programming problems is using a\n[network flow](/optimization/flow) solver. \n\nSee [Assignment as a Min Cost Flow Problem](/optimization/flow/assignment_min_cost_flow)\nfor an example. \n\nFor a problem that can be set up as a network flow, the min cost flow solver can\nbe faster than either the MIP or CP-SAT solvers. However, not all MIPs can be\nset up this way.\n\n*[MIP]: Mixed Integer Programming"]]