Integer Programming
Optimizing problems where decisions must be whole numbers
How do you optimize problems where the decision has to be a whole number, such as the number of products, employees or vehicles? Linear programming (Ch. 02) assumes decision variables can take continuous values, so it can produce solutions with decimals, such as 2.5 units or 3.7 people.
What is integer programming?
You can’t hire 3.5 people.
You can’t deploy 2.4 vehicles.
You can’t buy 1.7 machines.
An optimization method that adds the condition that decision variables must be integers like this is called integer programming (IP). If the objective function and constraints stay linear and only the integer condition is added, it is linear integer programming.
Why does the integer condition matter?
The optimal solution of the production planning model (Ch. 02) was x = y = 8/3. Mathematically it is a valid solution, but if products are made only as finished units, you can’t carry it out as is. Integer programming adds the following condition.
ℤ≥0: the set of non-negative integers, including 0
As Figure 1 shows, the only possible solutions now are the grid points inside the feasible region. Rounding the LP solution (8/3, 8/3) to (3, 3) needs 9 hours in both processes, so it is infeasible; rounding down to (2, 2) is feasible, but its profit of $320 isn’t the best. Rounding the continuous optimal solution can’t guarantee the integer optimal solution.
Finding the optimal solution in integer programming
| Product A (x) | Product B (y) | Total profit | Feasible? |
|---|---|---|---|
| 0 | 4 | $400 | Feasible |
| 2 | 3 | $420 | Feasible |
| 3 | 2 | $380 | Feasible |
| 4 | 0 | $240 | Feasible |
| 1 | 4 | $460 | Infeasible (process 1: 1 + 2(4) = 9 hours) |
The best integer combination is 2 of product A and 3 of product B, with Z = 60(2) + 100(3) = $420. That is slightly lower than the optimal profit of linear programming with continuous variables (about $426.67). Adding the integer condition narrows the range of solutions you can choose from, so the optimal value of an integer program can’t exceed the LP optimal value of the same problem. This difference (here, $6.67) is called the integrality gap.
Three types of integer programming
A model in which every decision variable must be an integer
Examples: production quantities, number of employees, number of vehicles
A model in which some variables are integers and the rest are continuous
Example: whether to install equipment (integer) and production quantity (continuous) — Ch. 05
A model in which variables can only be 0 or 1
Example: 1 if a project is chosen, 0 if not
Expressing selection problems with binary variables
Integer programming can also turn the choice itself into a variable. Suppose a company wants to pick some of three projects, and its total budget is $14,000.
| Project | Expected profit | Budget needed |
|---|---|---|
| A | $16,000 | $8,000 |
| B | $12,000 | $6,000 |
| C | $10,000 | $4,000 |
Amounts in thousands of dollars
Figure 2 lists all 8 possible combinations. Choosing A and B uses a budget of $14,000 for a profit of $28,000; A and C uses $12,000 for $26,000; B and C uses $10,000 for $22,000. Doing all three projects would need a budget of $18,000, so it is infeasible. The optimal choice is therefore A and B. This structure is called the knapsack problem, and it shows up all over: investment planning, project selection, facility location, choosing ad campaigns and more.
If you relax the integer condition (allowing any real number between 0 and 1), the optimal solution is 0.5 of A and 1 each of B and C, for a profit of $30,000. It amounts to packing C and B, which have the highest efficiency (profit/budget), first and filling the remaining budget with half of A; rounding this down to pick only B and C gives $22,000, far below the optimum ($28,000). In selection problems, the rounding trap gets even bigger.
How is integer programming solved?
In linear programming you could find the optimal solution at a vertex, but in integer programming not every point in the continuous feasible region is allowed, so the computation is more complex. As the number of variables grows, the number of possible combinations explodes, and you can’t even list them all.
Branch and bound
Temporarily drop the integer condition and solve the LP. Its value is an upper bound on the integer optimum.
Split the problem in two on a variable that isn’t an integer (e.g. x ≤ 2 and x ≥ 3).
Solve each subproblem and check its objective value and feasibility.
Drop any subproblem that can’t beat the best integer solution found so far.
In Figure 3, the solution of the LP with the integer condition dropped has x = 8/3, which isn’t an integer, so we split into x ≤ 2 and x ≥ 3. The LP solution of the left problem, (2, 3), is already an integer, so its profit of 420 becomes the incumbent best solution; the best of the right problem (380) is smaller, so it isn’t explored further. In this way, branch and bound doesn’t blindly enumerate every integer combination; it cuts away regions that have no chance of containing the optimal solution.
Cutting plane method
This method narrows the feasible region step by step by adding extra constraints (cuts) that rule out solutions that don’t satisfy the integer condition. It adds constraints that shave off only fractional vertices without cutting away a single integer grid point, so the LP solution moves closer to an integer one. Real optimization software combines both methods with heuristics.
Where integer programming is used
| Field | Decision problem |
|---|---|
| Production management | Deciding how many of each product to make |
| Workforce management | Number of employees and shift scheduling |
| Logistics | Number of vehicles, delivery plans, route choice |
| Investment | Project selection and budget allocation |
| Facility location | Deciding where to put distribution centers or stores |
| Marketing | Campaign mix and allocating a limited budget |
| Public policy | Choosing program targets and support programs |
Because binary variables express whether something is chosen, they are especially useful for problems where you pick some of several alternatives or allow a decision only under certain conditions.
Solving an integer programming model that restricts production to whole units with branch and bound, profit was maximized at $420 by producing 2 of product A and 3 of B. This is $6.67 lower than the LP optimal value with the integer condition relaxed (1280/3 ≈ $426.67), and (3, 3), the rounded LP solution, violated the process time constraints. In the project selection problem with a $14,000 budget, profit was maximized at $28,000 by choosing A and B.
With an integer condition, don’t round: search again among the integer solutions.
- Integer programming: A way to find the optimal solution after adding an integer condition to the decision variables.
- The rounding trap: Rounding the LP solution can violate constraints or fail to be optimal.
- Binary variables: Represent whether something is chosen as 0 or 1, expressing project selection, location, campaign choice and so on.
- Integrality gap: The integer condition narrows the range of solutions, so the integer optimum can’t exceed the LP optimum.
- Solution methods: Branch and bound narrows the search by relaxing, branching and pruning; the cutting plane method does it with extra constraints.
Up next: 05 Mixed-Integer Programming. We’ll look at how to handle integer and continuous variables together in one model, such as whether to install equipment and how much to produce.