Mixed-Integer Programming
Optimization that uses integer and continuous variables together
How do you optimize a problem that mixes integer and continuous variables, such as budgets, whether to install equipment, and production quantities? If you run a plant, you have to decide together whether to build a new plant and, if you do, how much to produce, and raw-material and operating costs also change with the production quantity. Whether to build can be expressed as 0 or 1, and the production quantity as a continuous value.
What is mixed-integer programming?
A method that uses integer and continuous variables together in one optimization model is called mixed-integer programming (MIP). If the objective function and constraints are linear, it is called mixed-integer linear programming (MILP).
How is it different from integer programming?
| Model | Variable type | Examples |
|---|---|---|
| Linear programming (LP) | Continuous variables | Raw-material use, budget amounts allocated |
| Integer programming (IP) | Integer variables | Number of employees, number of vehicles |
| Mixed-integer programming (MIP) | A mix of integer and continuous variables | Whether to build a plant, and production quantity |
If we use y for whether the plant is built and x for the production quantity, then y ∈ {0, 1} and x ≥ 0. To make production impossible when the plant isn’t built, we add the following constraint.
M: upper limit on production · if y = 0, then x ≤ 0, so production is 0 · if y = 1, then x ≤ M
This one constraint links the "yes/no" decision of whether to build with the "how much" decision of the production quantity in a single model.
Example: building a plant and deciding how much to produce
| Item | Value |
|---|---|
| Fixed cost of building the plant | $600 |
| Revenue per unit | $200 |
| Variable cost per unit | $80 |
| Maximum production | 10 units |
The profit per unit is $200 − $80 = $120, so the model is:
| Choice | Production x | Built? y | Total profit |
|---|---|---|---|
| Don’t build | 0 | 0 | $0 |
| Build, produce 5 units | 5 | 1 | $0 |
| Build, produce 8 units | 8 | 1 | $360 |
| Build, produce 10 units | 10 | 1 | $600 |
Once the plant is built, the $600 fixed cost is incurred even with no production, and break-even comes at 5 units, where 120x = 600. Beyond that, profit builds up with each unit, reaching its largest value, $600, at the maximum output of 10 units. If maximum output had been 5 units or fewer, not building the plant would be optimal. In problems with fixed costs, profit takes a step shape that "drops once the moment you build," which linear programming alone can’t express, so a binary variable is needed.
Which of several candidate sites should you build at?
Mixed-integer programming is also used to decide where among several candidate sites to build facilities. Suppose a logistics company wants to build distribution centers at some of three candidate sites, and each site differs in building cost, handling capacity and shipping cost to each customer.
yj: whether site j is built (0/1) · xij: volume shipped from site j to customer i · fj: building cost · cij: shipping cost per unit · di: demand · Cj: handling capacity
If a center isn’t built (yj = 0), its shipping volume is 0 too; if it is built, volume can be allocated up to its capacity.
Solving with the hypothetical data in Figure 2 (3 candidate sites, 4 customer regions, total demand 110), it is optimal to build at S2 and S3 and not at S1, and the total cost is $14,900: $9,000 in building costs plus $5,900 in shipping costs.
In Figure 3, building all three sites lets each customer be served from a nearby center, so shipping costs are the lowest at $4,800, but building costs run to $15,000, for a total of $19,800. On shipping costs alone, S1+S3 ($5,500) is also cheaper than the optimal combination, but its building costs are higher. That is why building and shipping costs must be considered together.
Common modeling techniques in mixed-integer programming
Linking a yes/no choice to an activity level
A situation where you can produce only if the equipment is installed is expressed as x ≤ My. However, if M is made needlessly large, the relaxed problem with the integer condition dropped drifts away from reality and computation becomes less efficient, so it’s best to use a meaningful value, such as the upper limit on possible production.
Minimum production condition
if y = 0, then x = 0 · if y = 1, then 5 ≤ x ≤ 10
As on the right of Figure 4, the minimum production condition applies only if the plant is built. A condition like "if you produce at all, at least 5 units" can’t be expressed with continuous variables alone.
Choosing only one of several options
Constraints like these are used in many problems, such as program selection, project investment, facility location and product mix.
How is mixed-integer programming solved?
Because of the integer conditions, computation can be more complex than in linear programming. The standard method is branch and bound (Ch. 04).
Solve the linear program with the integer conditions relaxed.
Split into subproblems on a variable that doesn’t satisfy its integer condition.
Compare the optimization results of each subproblem.
Drop subproblems that can’t produce a better solution.
Search the remaining candidates to find the optimal solution.
Real optimization software combines branch and bound with cutting planes, heuristics and preprocessing. As problems grow, proving optimality can take a long time, so alongside a good solution found within a time limit you may also check the optimality gap: the difference between the current solution and the bound given by the relaxed problem (the same principle as duality, Ch. 03).
Where mixed-integer programming is used
| Field | Example uses |
|---|---|
| Production management | Whether to install equipment and how much of each product to make |
| Logistics | Optimizing distribution center locations and shipping volumes |
| Workforce management | Staff assignments and working hours |
| Energy | Whether to run each generating unit and how much power to generate |
| Investment | Which projects to choose and how much to invest |
| Telecom · networks | Where to put facilities and how much network capacity to build |
Mixed-integer programming is especially suited to problems where yes/no choices and continuous activity levels are linked.
We solved a mixed-integer linear programming model that jointly decides whether to build distribution centers at 3 candidate sites (binary variables) and the shipping volumes to 4 customer regions (continuous variables). The optimal plan was to build at S2 and S3, for a total cost of $14,900 ($9,000 building, $5,900 shipping), $4,900 less than building all three sites ($19,800).
Express "whether" with binary variables and "how much" with continuous ones, and link them with constraints.
- Mixed-integer programming: An optimization method that uses integer and continuous variables together.
- Binary variables: Express whether to install equipment, choose a project or operate a facility.
- Big-M constraints: Link a yes/no choice to the range of an activity level, as in x ≤ My and 5y ≤ x ≤ 10y; set M to a meaningful upper limit.
- Fixed costs and location: Building and operating costs, and capacity and volume, can be considered together in one model.
- Solving: Solved with methods such as branch and bound; for large problems, report the optimality gap too.
Up next: 06 Nonlinear Optimization. We’ll cover problems where cost isn’t proportional to output, or where variables are related through products, squares or curves.