Learning Outcomes

A.

Learn classic integer programming formulations.

B.

Demonstrate different uses of binary and integer variables.

C.

Demonstrate the format for modeling an optimization problem with sets, parameters, variables, and the model.

Your linear program says to build 2.7 warehouses and route 3.4 trucks. Rounding up to 3 warehouses might blow the budget; rounding down to 2 might leave demand unmet; and neither rounded plan is necessarily anywhere near the best whole-number plan. Worse, many decisions are not quantities at all but choices (open this facility or don’t, assign this job to that machine or not) where “0.7 of a yes” means nothing. Requiring variables to take integer values looks like a small change to a linear program. It is not: it buys enormous modeling power, and this chapter is a tour of what that power can express.

In this section, we will describe classical integer programming formulations. These formulations may reflect a real world problem exactly, or may be part of the setup of a real world problem.

Binary Knapsack Problem

NP-complete

Given a non-negative weight vector $a\in {\mathbb{Q}}_{+}^n$, a capacity $b\in {\mathbb{Q}}_{+}$, and objective coefficients $c\in {\mathbb{Q}}^n$,

Example 15.1: Knapsack

Example 15.2: Min Coins

The capital budgeting problem is a nice generalization of the knapsack problem. This problem has the same structure as the knapsack problem, except now it has multiple constraints. We will first describe the problem, give a general model, and then look at an explicit example.

Capital Budgeting

A firm has $n$ projects it could undertake to maximize revenue, but budget limitations require that not all can be completed.

• Project $j$ expects to produce revenue $c_j$ dollars overall.

• Project $j$ requires investment of $a_{ij}$ dollars in time period $i$ for $i=1,\dots ,m$.

• The capital available to spend in time period $i$ is $b_i$.

Which projects should the firm invest in to maximize its expected return while satisfying its weekly budget constraints?

We will first provide a general formulation for this problem.

Capital Budgeting Model

Sets:

• Let $I=\{1,\dots ,m\}$ be the set of time periods.

• Let $J=\{1,\dots ,n\}$ be the set of possible investments.

Parameters:

• $c_j$ is the expected revenue of investment $j$ for $j\in J$

• $b_i$ is the available capital in time period $i$ for $i$ in $I$

• $a_{ij}$ is the resources required for investment $j$ in time period $i$, for $i$ in $I$, for $j$ in $J$.

Variables:

• let $x_j=1$ if investment $j$ is chosen

• let $x_j=0$ if investment $j$ is not chosen

Model:

Consider the example given in the following table.

Example 15.3: Capital Budgeting

The Capacitated Lot Sizing Problem (CLSP) is a fundamental optimization problem in production planning, where the goal is to determine an optimal production schedule that minimizes total costs while adhering to capacity constraints. The objective function accounts for production costs, setup costs, and inventory holding costs over a given planning horizon.

Let $T$ denote the number of discrete time periods, indexed by $t\in \{1,2,\dots ,T\}$. The problem parameters are defined as follows:

• $d_t$ is the demand in period $t$,

• $p_t$ represents the unit production cost,

• $f_t$ is the fixed setup cost incurred if production takes place,

• $h_t$ denotes the unit inventory holding cost, and

• $c_t$ represents the maximum production capacity in period $t$.

The decision variables are:

• $x_t$ denotes the quantity produced in period $t$,

• $s_t$ is the inventory level at the end of period $t$, and

• $y_t$ is a binary variable that takes value 1 if production occurs in period $t$, and 0 otherwise.

The CLSP can be formulated as the following mixed-integer linear program:

The basic model of the facility location problem is to determine where to place your stores or facilities in order to be close to all of your customers and hence reduce the costs of transportation to your customers. Each customer is known to have a certain demand for a product, and each facility has a capacity on how much of that demand it can satisfy. We also need to consider the cost of building the facility in a given location.

This basic framework can be applied in many types of problems and there are a number of variants to this problem. Here we present the capacitated facility location problem. Additional variants and alternative formulations are covered in Book 2.

Capacitated Facility Location 1

NP-complete

Given connection costs $c_{ij}$, fixed building costs $f_i$, demands $d_j$, and facility capacities $u_i$, the capacitated facility location problem is formulated as follows:

Sets:

• Let $I=\{1,\dots ,n\}$ be the set of facilities.

• Let $J=\{1,\dots ,m\}$ be the set of customers.

Parameters:

• $f_i$ — the cost of opening facility $i$.

• $c_{ij}$ — the cost of serving one unit of demand of customer $j$ from facility $i$.

• $u_i$ — the capacity (in units) of facility $i$.

• $d_j$ — the total demand (in units) of customer $j$.

Variables:

• $y_i\in \{0,1\}$ — equals 1 if facility $i$ is opened; 0 otherwise.

• $x_{ij}\ge 0$ — the number of units of customer $j$’s demand served by facility $i$.

Model:

Example 15.4: Capacitated Facility Location: Retail Distribution Example

Model Formulation: The capacitated facility location model described earlier can be applied to this scenario with the given data to determine the optimal number and location of distribution centers to open, and which stores each center should serve.

If you build and solve this instance, you will discover that it is infeasible: the stores demand $1150$ units in total, while the three centers combined can supply at most $270$. This is on purpose. Not every problem has a nice solution, and discovering infeasibility is itself useful information a model gives you. As an exercise, decide how you would repair the instance: reduce demand or add capacity.

Case Study: Where Should the Water Bombers Sleep? Airtanker Basing in Ontario

Ontario fights forest fires with a fleet of airtankers (water bombers). A fire caught within the first few hours is usually a small story; a fire missed grows into a big one. So the province’s ability to hit new fires quickly depends on where the airtankers are based each morning. In the early 1990s the Ontario Ministry of Natural Resources asked operations researchers to help decide the home bases, and the resulting mathematical programming model informed the province’s actual basing strategy from the 1993 fire season onward.

Fires do not announce where they will start. What is known is the historical pattern: some fire management zones see far more fire starts than others, and an airtanker can only provide effective initial attack on fires within a limited flying range of its base. With a fixed fleet, where should the aircraft be based so that as much expected fire activity as possible is within reach?

Model type: integer program (facility location / coverage). No machine learning; the fire-frequency inputs are historical averages.

Sets and Parameters:

• Let $I$ be the set of fire management zones and $J$ the set of candidate bases.

• Let $n_i$ be the expected number of fires in zone $i$ (from historical records).

• Let $t_{ij}=1$ if an airtanker based at $j$ can reach zone $i$ within the initial-attack time standard, and $0$ otherwise.

• Let $N$ be the number of airtankers in the fleet.

Variables:

• Let $y_j\in {\mathbb{Z}}_{\ge 0}$ be the number of airtankers based at $j$.

• Let $z_i=1$ if zone $i$ is covered by at least one base within reach.

Model:

• The version above counts a zone as covered or not; the published model is finer-grained, accounting for how many aircraft can respond and for daily fire-weather variation.

• Expected fire counts stand in for actual (random) fire occurrence: the model optimizes the average day, not the worst day.

• Airtankers can be re-deployed between bases day to day; the published work treats home-basing (seasonal) and daily deployment as linked decisions.

The Ontario Ministry of Natural Resources used the model to inform its airtanker home-basing strategy beginning with the 1993 fire season, and Ontario’s fire management program has continued to work with operations researchers for decades since, on deployment, dispatch, and detection-patrol planning.

The set covering problem can be used for a wide array of problems. We will see several examples in this section.

Set Covering

NP-complete

Given a set $V$ with subsets $V_1,\dots ,V_l$, determine the smallest subset $S\subseteq V$ such that $S\cap V_i\ne \varnothing$ for all $i=1,\dots ,l$.

The set cover problem can be modeled as

where $x_v$ is a 0/1 variable that takes the value $1$ if we include item $v$ in set $S$ and $0$ if we do not include it in the set $S$.

One specific type of set cover problem is the vertex cover problem.

Example: Vertex Cover

NP-complete

Given a graph $G=(V,E)$ of vertices and edges, we want to find a smallest size subset $S\subseteq V$ such that for every $e=(v,u)\in E$, either $u$ or $v$ is in $S$.

We can write this as a mathematical program in the form:

Example 15.5: Set cover: Fire station placement

https://github.com/open-optimization/open-optimization-or-examples/blob/master/integer-programming/fire-station-covering.ipynb

Example 15.6: Vertex Cover with matrix

We could also allow for a more general type of set covering where we have non-negative integer variables and a right hand side that has values other than $1$.

Covering

NP-complete

Given a non-negative matrix $A\in {\mathbb{Z}}_{+}^{m\times n}$, a non-negative vector $b\in {\mathbb{Z}}^m$, and an objective vector $c\in {ℝ}^n$, the covering problem is

Case Study: Kidney Exchange: Integer Programming that Saves Lives

Thousands of kidney patients have a friend or family member willing to donate a kidney, but with the wrong blood or tissue type. Kidney exchange programs fix this with a swap: donor A gives to patient B while donor B gives to patient A. With three pairs, a three-way cycle works the same way. National programs, including the United States’ kidney paired donation program (UNOS) and the United Kingdom’s Living Kidney Sharing Scheme, decide who swaps with whom by solving an integer program. In the UK, that integer program runs on a fixed schedule several times a year: the solver’s output is literally the list of surgeries to schedule.

Given a pool of incompatible patient–donor pairs, find a set of swap cycles that gives as many patients as possible a compatible kidney. Two hard rules shape the problem. First, a pair can appear in at most one cycle (each donor has one kidney to give). Second, all surgeries in a cycle must happen simultaneously, so that no donor can back out after their loved one has received a kidney; operating-room logistics therefore cap cycles at two or three pairs.

Model type: pure binary integer program. No machine learning; compatibility is determined by medical testing.

Sets:

• Let $P$ be the set of incompatible patient–donor pairs.

• Let $C$ be the set of feasible swap cycles of length at most 3: subsets of pairs where each donor is compatible with the next patient around the cycle.

Variables:

• Let $x_c=1$ if cycle $c$ is selected for surgery, and $0$ otherwise.

Model:

Here $\left|c\right|$ is the number of pairs in cycle $c$, which equals the number of transplants the cycle produces. Real programs also include chains started by altruistic donors (someone who donates without a paired patient) and weight cycles by medical priority rather than just counting transplants; both are small extensions of the same model.

• Compatibility is treated as a yes/no input from blood typing and tissue crossmatching, computed before the optimization.

• The model shown maximizes the number of transplants; deployed programs maximize a weighted sum reflecting waiting time, sensitization, and pediatric status.

• Enumerating all cycles is feasible for cycle length $\le 3$; national-scale pools with long chains need column generation (a Book 2 topic).

Cycle- and chain-based integer programs are the clearing engines of the US and UK national programs, and the published models have been benchmarked directly on real UNOS and UK datasets. The UK scheme’s matching runs are performed with algorithms developed by the University of Glasgow. Economist Alvin Roth shared the 2012 Nobel Prize in part for the market design behind kidney exchange.

Graph coloring

In this section, we describe ways to model a variety of constraints that commonly appear in practice. The goal is changing constraints described in words to constraints defined by math.

Binary variables can allow you to model many types of constraints. We discuss here various logical constraints where we assume that $x_i\in \{0,1\}$ for $i=1,\dots ,n$. We will take the meaning of the variable to be selecting an item.

1.

If item $i$ is selected, then item $j$ is also selected.

$$x_i\le x_j$$

(15.10)

(a)

If any of items $1,\dots ,5$ are selected, then item $6$ is selected.

$$x_1+x_2+\cdots +x_5\le 5\cdot x_6$$

(15.11)

Alternatively!

$$x_i\le x_6\text{ for all }i=1,\dots ,5$$

(15.12)

2.

If item $j$ is not selected, then item $i$ is not selected. This is the contrapositive of the implication above, so the same inequality models it.

$$x_i\le x_j$$

(15.13)

(a)

If item $j$ is not selected, then none of the items $1,\dots ,i$ are selected.

$$x_1+x_2+\cdots +x_i\le i\cdot x_j$$

(15.14)

3.

Either item $i$ is selected or item $j$ is selected, but not both.

$$x_i+x_j=1$$

(15.15)

4.

Item $i$ is selected or item $j$ is selected or both.

$$x_i+x_j\ge 1$$

(15.16)

5.

If item $i$ is selected, then item $j$ is not selected.

$$x_j\le (1-x_i)$$

(15.17)

6.

At most one of items $i$, $j$, and $k$ is selected.

$$x_i+x_j+x_k\le 1$$

(15.18)

7.

At most two of items $i,j,$ and $k$ are selected.

$$x_i+x_j+x_k\le 2$$

(15.19)

8.

Exactly one of items $i,j,$ and $k$ is selected.

$$x_i+x_j+x_k=1$$

(15.20)

Example 15.7: Variable takes one of three values

Suppose that the variable $x$ should take one of the three values $\{4,8,13\}$. This can be modeled using three binary variables as

As a convenient addition, if we want to add the possibility that it takes the value $0$, then we can model this as

Example 15.8: Discount for buying more

Suppose you can choose to buy 1, 2, or 3 units of a product, each with a decreasing cost. The first unit is $10, the second is $5, and the third unit is $3.

Here, $z_i$ represents if we buy the $i$th unit. The inequality constraints impose that if we buy unit $j$, then we must buy all units $i$ with $i<j$.

Big M comes again! It’s extremely useful when trying to activate constraints based on a binary variable.

For instance, if we don’t rent a bus, then we can have at most 3 passengers join us on our trip. Consider passengers $A,B,C,D,E$ and let $x_i\in \{0,1\}$ be 1 if we take passenger $i$ and 0 otherwise. We can model the constraint that we can have at most 3 passengers as

We want to be able to activate this constraint in the event that we don’t rent a bus.

Let $\delta \in \{0,1\}$ be 1 if we rent a bus, and 0 otherwise.

Then we want to say

If $\delta =0$ , then

$$x_A+x_B+x_C+x_D+x_E\le 3.$$

We can formulate this using a big-M constraint as

Notice the two cases

In the second case, we choose $M$ to be so large that the second case inequality is vacuous. That said, choosing smaller $M$ values (that are still valid) will help the computer program solve the problem faster. In this case, it suffices to let $M=2$.

We can speak about this technique more generally as

Big-M: If then

We aim to model the relationship

By letting $M$ be an upper bound on the quantity $a^{\top }x-b$, we can model this condition as

Below are several applications of this modeling technique:

• Facility Location with Fixed Costs:
  To ensure that a facility $i$ must be open in order to serve customer $j$, we write

  $$x_{ij}\le M{\delta }_i,$$

  where $x_{ij}$ is the quantity shipped and ${\delta }_i=1$ if facility $i$ is open.

• Power Plant Operation Constraints:
  A generator can only produce power when it is turned on. Letting ${\delta }_t=1$ indicate that the generator is on at time $t$, we write:

  $$P_{\min }{\delta }_t\le P_t\le P_{\max }{\delta }_t.$$

• Task Scheduling with Precedence Constraints:
  To ensure task $B$ starts only after task $A$ ends, if a binary $\delta =1$ indicates the precedence relation is active, we write:

  $${\text{Start}}_B\ge {\text{End}}_A-M(1-\delta ).$$

• Routing and Time Windows:
  In vehicle routing problems, to model time consistency across arcs, we use:

  $$t_j\ge t_i+s_i-M(1-{\delta }_{ij}),$$

  where ${\delta }_{ij}=1$ indicates travel from node $i$ to node $j$, and $s_i$ is service time at node $i$.

• Production Planning and Setup Costs:
  To ensure production $x_t$ is positive only if a setup decision ${\delta }_t=1$ is made:

  $$x_t\le M{\delta }_t.$$

Example 15.9: Network Flow with Toll Charges Using Big-M Constraints

Consider a transportation network where some arcs incur a toll cost if used. Let:

• $G=(V,A)$ be a directed graph with nodes $V$ and arcs $A$.

• $x_{ij}\ge 0$ be the flow on arc $(i,j)\in A$.

• ${\delta }_{ij}\in \{0,1\}$ indicate whether arc $(i,j)$ is used.

• $c_{ij}$ be the per-unit flow cost on arc $(i,j)$.

• $t_{ij}$ be the fixed toll incurred if arc $(i,j)$ is used.

• $M_{ij}$ be a large constant upper bound on possible flow through arc $(i,j)$.

The objective is to route flow from a source node $s$ to a sink node $t$ at minimum total cost, including tolls when applicable:

Subject to:

• Manhattan

• Brooklyn

• Queens

• Bronx

• Staten Island

can be used to enforce toll cost and flow constraints, where $x_{ij}$ is the flow over arc $(i,j)$, and $M$ is a suitably large upper bound on the possible flow.

Case Study: 108, 000 Fewer Truck Routes: Walmart’s Load Planning

Walmart moves goods from distribution centers to about 4,700 US stores on one of the largest private trucking fleets in the world. For the 2023 Franz Edelman Award (which it won), Walmart described an end-to-end optimization framework, from long-term network design down to daily routing and trailer load planning. In fiscal year 2023 the system eliminated 108,000 truck routes and 33 million driving miles, saving $91.5 million and preventing 98.6 million pounds of CO${}_2$ emissions.

Every day, each store needs a set of orders delivered. Orders take up trailer space; trucks have capacity; stores have delivery windows; and every truck dispatched costs money and emissions. The daily question at the heart of load planning: pack the orders into as few trailer-loads as possible while respecting capacities and delivery requirements.

Model type: integer programming for load consolidation and routing, inside a framework whose strategic layers are also optimization models. Forecasts feed the models as data.

The consolidation core, simplified:

Sets and Parameters:

• Let $O$ be the set of orders for a delivery region, with sizes $q_o$ (trailer cube).

• Let $T$ be the set of available trailer-loads (trucks), each with capacity $Q$.

• Compatibility data: $s_{ot}=1$ if order $o$ can ride on truck $t$ (same route corridor, feasible delivery window).

Variables:

• Let $x_{ot}=1$ if order $o$ is loaded on truck $t$.

• Let $y_t=1$ if truck $t$ is dispatched.

Model:

The capacity constraint again uses the big-$M$ linking pattern with $M=Q$. The deployed system couples this packing decision with routing (which stores share a route) and with strategic network design; the Edelman paper describes the full architecture.

• Order sizes and delivery windows are data; in practice they come from demand forecasts.

• The simplified model minimizes truck count; Walmart’s objective also prices miles, so consolidating onto fewer, fuller, shorter routes is what produced the 33-million-mile reduction.

• Routing (the order in which a truck visits stores) is a separate, harder layer, in Book 2 territory; this box shows the consolidation layer.

Deployed across Walmart’s US supply chain: 108,000 routes and 33 million miles eliminated in FY2023, $91.5 million saved, 98.6 million pounds of CO${}_2$ avoided. 2023 INFORMS Franz Edelman Award winner.

The Big-M technique from the previous subsection activated a single constraint. A closely related situation is when we have two constraints and we need at least one of them to hold: an inclusive or. For example, a delivery might need to arrive either before a morning deadline or after an afternoon opening, or a budget must be satisfied in at least one of two currencies. The trick is to use one binary variable to decide which constraint is enforced, and a pair of Big-M constraints to relax whichever one is not selected.

Either Or

can be modeled as

where $M_1$ is an upper bound on $a^{\top }x-b$ and $M_2$ is an upper bound on $c^{\top }x-d$.

• If $\delta =0$, then the first constraint becomes $a^{\top }x\le b$, and the second becomes $c^{\top }x\le d+M_2$, which is trivially satisfied if $M_2$ is large enough.

• If $\delta =1$, then the second constraint becomes $c^{\top }x\le d$, while the first is relaxed as $a^{\top }x\le b+M_1$.

Either way, at least one of the two original constraints is enforced; the binary variable $\delta$ simply selects which one.

Example 15.10: Buses or Cars

To shuttle students to the football game, we need either at least $2$ buses or at least $10$ cars.

• Let $x$ be the number of buses we have and

• let $y$ be the number of cars that we have.

We want to enforce that $x\ge 2$ or $y\ge 10$. Writing these in the form used above, we need $-x\le -2$ or $-y\le -10$. Since $x,y\ge 0$, we may take $M_1=2$ as an upper bound on $-x-(-2)=2-x$ and $M_2=10$ as an upper bound on $10-y$. The recipe gives

which simplifies to $x\ge 2(1-\delta )$ and $y\ge 10\delta$. If $\delta =0$ we must have at least $2$ buses; if $\delta =1$ we must have at least $10$ cars.

• If a machine is used, then either a certain energy constraint or a safety constraint must be met.

• In facility planning, either a site must be built with one configuration or another.

• In piecewise models where a variable must fall into one of two feasible regions.

Suppose that we want to model the fact that if we have at most 10 students attending this course, then we must switch to a smaller classroom.

Let $x_i\in \{0,1\}$ be 1 if student $i$ is in the course or not. Let $\delta \in \{0,1\}$ be 1 if we need to switch to a smaller classroom.

Thus, we want to model

If

$$\sum _{i\in I}{x}_i\le 10$$

then

$$\delta =1.$$

Using the recipe below with $b=10$, $𝜖=1$ (the data are integer), and lower bound $m=-10$ on ${\sum }_{i\in I}{x}_i-10$, we can model this as

If $\delta =0$, the constraint forces at least $11$ students; equivalently (by the contrapositive), whenever $10$ or fewer students attend, the model must set $\delta =1$.

If inequality, then indicator

We let $m$ be a lower bound on the quantity $a^{\top }x-b$ and we let $𝜖$ be a tiny number that is an error bound in verifying if an inequality is violated. If the data $a,b$ are integer and $x$ is an integer, then we can take $𝜖=1$.

Now

can be modeled as

Many other combinations of if then statements are summarized in the following table:

These two implications can be used to derive the following longer list of implications.

Lastly, if you insist on having exact correspondence, that is, “$\delta =0$ if and only if $a^{\top }x\le b$” you can simply include both constraints for “if $\delta =0$, then $a^{\top }x\le b$” and “if $a^{\top }x\le b$, then $\delta =0$”. Although many problems may be phrased in a way that suggests you need “if and only if”, it is often not necessary to use both constraints due to the objectives in the problem that naturally prevent one of these from happening.

For example, if we want to add a binary variable $\delta$ that means

If $\delta =1$ does not affect the rest of the optimization problem, then adding the constraint regarding $\delta =1$ is not necessary. Hence, typically, in this scenario, we only need to add the constraint $a^{\top }x\le b+M\delta$.

A disjunction is a generalization of an “or” statement. Suppose that we have $n$ constraints

and we want to enforce at least $k$ of them. This can be accomplished linearly by introducing a new binary indicator variable ${\delta }_i$ for each of the disjunctive constraints $i\in \{1,\dots ,n\}$:

If ${\delta }_i=1$, then the $i^{}$

th$disjunctiveconstraintisactivelyenforced.Thelastconstraint$$\left({\sum }_{i=1}^n{\delta }_i\ge k\right)$ ensures that at least $k$ of the constraints are active.