Aspects of OR - Integer Programming (Part 1)

In the LP mini-series we learned how to optimize linear objectives subject to linear constraints, and we saw that LP solvers can handle millions of variables in seconds. But LP has a fundamental limitation: it assumes that decision variables can take any real value. In many real-world problems, this assumption does not hold. You cannot build 2.7 factories, assign 0.4 of a worker to a shift, or ship 3.14 containers to a warehouse.

Integer Programming (IP) addresses this by requiring some or all decision variables to take integer values. This seemingly small change — from $x \geq 0$ to $x \in \mathbb{Z}_{\geq 0}$ — makes the problem dramatically harder.

What makes IP hard?

Before diving into definitions, let us understand why integrality is such a big deal. The feasible region of an LP is a convex polytope — a smooth, well-behaved shape where the simplex method can slide along edges to the optimum. The feasible region of an IP is a scattered set of discrete points inside that polytope. There are no edges to follow, no gradients to exploit.

How many points are there? A binary program with $n$ variables has up to $2^n$ possible solutions. For $n = 100$, that is $2^{100} \approx 10^{30}$ — more than the number of atoms in a human body. You might think: just check all of them. But even at a billion solutions per second, enumerating $2^{100}$ would take longer than the age of the universe.

LP can be solved in polynomial time. IP is NP-hard in general. Yet IP is indispensable in practice: scheduling, logistics, network design, and countless other applications require discrete decisions. And modern IP solvers routinely handle problems with thousands or millions of binary variables. How? Through clever algorithms that avoid exhaustive enumeration. This mini-series explains how:

• Part 1 (this post): Definitions, LP relaxations, and why naive approaches fail.
• Part 2: Branch and bound — systematic search with intelligent pruning.
• Part 3: Cutting planes — tightening the LP relaxation to eliminate fractional solutions.
• Part 4: Branch-and-cut and how modern solvers work.

Definitions

An Integer Linear Program (ILP or IP) has the same structure as an LP, but with integrality constraints on the variables:

$\min \; c^T x \quad \text{subject to} \quad Ax \leq b, \quad x \geq 0, \quad x \in \mathbb{Z}^n.$

A Mixed-Integer Linear Program (MIP or MILP) relaxes this by requiring only a subset of variables to be integer:

$\min \; c^T x + d^T y \quad \text{subject to} \quad Ax + By \leq b, \quad x \geq 0, \; y \geq 0, \quad x \in \mathbb{Z}^p,$

where $x$ are the integer variables and $y$ are the continuous variables.

A special case that appears constantly is Binary Programming (or 0-1 Programming), where the integer variables are restricted to $\{0, 1\}$. Binary variables naturally model yes/no decisions: should we open a facility? Should we include an item? Should we assign a worker to a task?

The LP relaxation

The most important tool for solving IPs is the LP relaxation: drop the integrality constraints and solve the resulting LP. If the LP relaxation of an IP is:

$\min \; c^T x \quad \text{subject to} \quad Ax \leq b, \quad x \geq 0,$

then the LP optimal value provides a lower bound (for minimization) on the IP optimal value. This is because every IP-feasible solution is also LP-feasible, but not vice versa — the LP feasible region is larger.

The quality of this bound — the integrality gap — varies widely across problem classes. If the LP relaxation happens to return an integer solution, we are done: the LP solution is also optimal for the IP. But in general, the LP solution will have fractional components, and we need more sophisticated methods.

Why rounding fails

The most natural idea is: solve the LP relaxation and round the fractional solution to the nearest integers. Surely that should work? Let us see what happens.

Rounding can be infeasible

Consider the constraints $x_1 + x_2 \leq 1$ with $x_1, x_2 \in \{0,1\}$. The LP relaxation might return $x_1 = 0.5, x_2 = 0.5$. Rounding both up gives $x_1 = 1, x_2 = 1$, which violates the constraint. Rounding both down gives $x_1 = 0, x_2 = 0$, which is feasible but may be far from optimal.

Rounding can be arbitrarily bad

Consider the knapsack problem:

$\max \; 100 x_1 + 100 x_2 \quad \text{s.t.} \quad 51 x_1 + 51 x_2 \leq 100, \quad x_1, x_2 \in \{0,1\}.$

The LP relaxation gives $x_1 = x_2 = 100/102 \approx 0.98$, with objective $\approx 196$. Rounding both up gives $(1,1)$, which is infeasible ($51 + 51 = 102 > 100$). Rounding both down gives $(0,0)$ with objective $0$. Rounding to the nearest integer for each variable independently also gives $(1,1)$ — still infeasible. The true IP optimum is $x_1 = 1, x_2 = 0$ (or vice versa) with objective $100$, but no coordinate-wise rounding rule can discover that exactly one variable should be rounded up and the other down.

Rounding fails structurally in facility location

Consider a facility location problem with 2 potential facilities and 3 customers. Opening each facility costs 100. Each customer must be served by exactly one open facility. The LP relaxation can "half-open" each facility to 50% — paying only $0.5 \times 100 + 0.5 \times 100 = 100$ in fixed costs — and split each customer fractionally between the two half-open facilities. Rounding both facilities up gives a fixed cost of 200, far from the LP bound. Rounding both down means no facility is open and no customer can be served — the solution is infeasible. The LP relaxation exploits the fractional structure in a way that no integer rounding can replicate.

These examples show that we need principled algorithms — not ad hoc rounding — to solve IPs.

Example 1: Uncapacitated facility location

Let us start with the richer of our two examples. A company must decide which of $m$ potential facility locations to open and how to assign $n$ customers to open facilities. Opening facility $i$ incurs a fixed cost $f_i$. Serving customer $j$ from facility $i$ costs $c_{ij}$. Each customer must be assigned to exactly one facility.

$\min \; \sum_{i=1}^{m} f_i y_i + \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}$

subject to

$\sum_{i=1}^{m} x_{ij} = 1 \quad \text{for all } j \quad \text{(each customer assigned)},$ $x_{ij} \leq y_i \quad \text{for all } i, j \quad \text{(only assign to open facilities)},$ $y_i \in \{0, 1\}, \quad x_{ij} \geq 0.$

This is a mixed-integer program: the facility decisions $y_i$ are binary, but the assignment variables $x_{ij}$ are continuous. Once the binary decisions are fixed, the assignment becomes a simple LP that naturally produces integer solutions (a property of the constraint structure).

Solving with Gurobi

import gurobipy as gp
from gurobipy import GRB

facilities = [1, 2, 3]
customers = ['A', 'B', 'C', 'D']

fixed_cost = {1: 100, 2: 150, 3: 120}
serve_cost = {
    (1, 'A'): 10, (1, 'B'): 30, (1, 'C'): 25, (1, 'D'): 40,
    (2, 'A'): 25, (2, 'B'): 10, (2, 'C'): 20, (2, 'D'): 15,
    (3, 'A'): 30, (3, 'B'): 20, (3, 'C'): 10, (3, 'D'): 20,
}

model = gp.Model('facility_location')

y = model.addVars(facilities, vtype=GRB.BINARY, name='open')
x = model.addVars(serve_cost.keys(), lb=0, name='assign')

model.setObjective(
    gp.quicksum(fixed_cost[i] * y[i] for i in facilities) +
    gp.quicksum(serve_cost[i, j] * x[i, j] for i, j in serve_cost),
    GRB.MINIMIZE
)

for j in customers:
    model.addConstr(gp.quicksum(x[i, j] for i in facilities) == 1, f'demand_{j}')

for i, j in serve_cost:
    model.addConstr(x[i, j] <= y[i], f'link_{i}_{j}')

model.optimize()

for i in facilities:
    if y[i].X > 0.5:
        served = [j for j in customers if x[i, j].X > 0.5]
        print(f'Facility {i} open, serves: {served}')
print(f'Total cost: {model.ObjVal:.0f}')

The LP relaxation of this problem "half-opens" facilities and fractionally splits customers, yielding a lower bound. The MIP solver uses branch and bound and cutting planes internally to find the optimal integer solution.

Example 2: The 0-1 knapsack problem

The knapsack problem is one of the most fundamental IPs. A thief breaks into a warehouse and can carry a knapsack with weight capacity $W$. There are $n$ items, each with a weight $w_j$ and a value $v_j$. Which items should be selected to maximize total value?

$\max \; \sum_{j=1}^{n} v_j x_j \quad \text{subject to} \quad \sum_{j=1}^{n} w_j x_j \leq W, \quad x_j \in \{0, 1\}.$

A concrete instance

Capacity $W = 13$.

LP relaxation: Greedily fill by value-to-weight ratio. Take item 2 (ratio 2.75, weight 8), then $5/6$ of item 1 (ratio 2.67, weight 5). Total: weight $8 + 5 = 13$, LP value $= 22 + 5/6 \times 16 \approx 35.33$.

IP optimum: Take items 2 and 3 (weight $8 + 5 = 13$, value $22 + 12 = 34$). The LP bound of 35.33 is close but not achievable by any integer solution.

We will use this exact instance in Part 2 to walk through branch and bound step by step.

Solving with Gurobi

import gurobipy as gp
from gurobipy import GRB

items = [1, 2, 3, 4]
weight = {1: 6, 2: 8, 3: 5, 4: 4}
value = {1: 16, 2: 22, 3: 12, 4: 8}
capacity = 13

model = gp.Model('knapsack')

x = model.addVars(items, vtype=GRB.BINARY, name='x')

model.setObjective(gp.quicksum(value[j] * x[j] for j in items), GRB.MAXIMIZE)
model.addConstr(gp.quicksum(weight[j] * x[j] for j in items) <= capacity, 'capacity')

model.optimize()

for j in items:
    if x[j].X > 0.5:
        print(f'Item {j}: weight={weight[j]}, value={value[j]}')
print(f'Total value: {model.ObjVal:.0f}')

Output: items 2 and 3 are selected, total value 34.

The role of formulation strength

Not all IP formulations for the same problem are equally good. A stronger formulation is one whose LP relaxation provides a tighter bound. Stronger formulations lead to tighter bounds, more pruning, and faster solve times. Finding strong formulations is a key skill in integer programming.

Let us see this in action on the facility location problem. The formulation above uses individual linking constraints $x_{ij} \leq y_i$ for each facility-customer pair. An alternative uses a single aggregate constraint per facility:

$\sum_{j=1}^{n} x_{ij} \leq n \cdot y_i \quad \text{for each } i.$

Both formulations are correct — they have the same set of integer-feasible solutions. But the aggregate formulation is weaker: it allows the LP relaxation to open a facility to just $1/n$ and still assign one full customer to it.

Consider a small instance with 2 facilities and 3 customers, fixed costs $f_1 = 100, f_2 = 80$, and service costs:

The strong formulation ($x_{ij} \leq y_i$) gives an LP bound of 130 — which turns out to be the IP optimum itself. The LP relaxation directly finds the integer solution: open both facilities, cost $100 + 80 + 10 + 15 + 10 = 130$ (sic). No branch and bound needed.

The weak formulation ($\sum_j x_{ij} \leq 3 y_i$) gives an LP bound of only 121.67. The LP relaxation "half-opens" facility 1 to $y_1 = 1/3$ and facility 2 to $y_2 = 2/3$, saving on fixed costs. The solver must now branch and explore multiple nodes to close the gap.

Same problem, same IP optimum — but the stronger formulation solves instantly. We will see in Part 3 how cutting planes can strengthen a formulation dynamically during the solve.