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. 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.

In this first part of the IP mini-series, we define the problem formally, introduce the LP relaxation, and show through examples why naive approaches like rounding fail. In Part 2 we cover branch and bound, and in Part 3 we explore cutting planes and branch-and-cut.

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. This can go wrong in several ways.

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 is infeasible. Rounding both down gives objective $0$. The true IP optimum is $x_1 = 1, x_2 = 0$ (or vice versa) with objective $100$. No simple rounding strategy recovers this.

The facility location gap

Consider a facility location problem where we decide which facilities to open and how to assign customers to them. The LP relaxation might "half-open" several facilities, fractionally distributing the fixed cost. Rounding these fractions can either violate capacity constraints (round up too many) or leave customers unserved (round down too many). The gap between LP and IP can be significant.

These examples show that we need principled algorithms — not ad hoc rounding — to solve IPs. The key algorithms are branch and bound (Part 2) and cutting planes (Part 3).

Example 1: 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 the total value without exceeding the capacity?

$\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 = 50$.

LP relaxation: Greedily fill by value-to-weight ratio. Take item 1 (weight 10, value 60), take item 2 (weight 20, value 100), and take $2/3$ of item 3 (weight 20, value 80). Total: weight 50, value 240.

IP optimum: Take items 1 and 2 (weight 30, value 160) or items 1 and 3 (weight 40, value 180) or items 2 and 3 (weight 50, value 220). The best is items 2 and 3 with value 220.

The LP relaxation gives a bound of 240. Rounding down the fractional item gives items 1 and 2 with value 160 — far from the IP optimum of 220.

Solving with Gurobi

import gurobipy as gp
from gurobipy import GRB

items = [1, 2, 3]
weight = {1: 10, 2: 20, 3: 30}
value = {1: 60, 2: 100, 3: 120}
capacity = 50

model = gp.Model('knapsack')

# Binary decision variables
x = model.addVars(items, vtype=GRB.BINARY, name='x')

# Objective: maximize total value
model.setObjective(gp.quicksum(value[j] * x[j] for j in items), GRB.MAXIMIZE)

# Capacity constraint
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 220.

Example 2: Uncapacitated facility location

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.$

Note that $x_{ij}$ can be continuous — once the binary facility decisions $y_i$ are fixed, the assignment is a simple LP that will naturally produce integer solutions (this is a property of the constraint structure).

Solving with Gurobi

import gurobipy as gp
from gurobipy import GRB

# Data
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')

# Binary: open facility i?
y = model.addVars(facilities, vtype=GRB.BINARY, name='open')

# Continuous: fraction of customer j served by facility i
x = model.addVars(serve_cost.keys(), lb=0, name='assign')

# Objective: minimize fixed + service costs
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.keys()),
    GRB.MINIMIZE
)

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

# Can only assign to open facilities
for i, j in serve_cost.keys():
    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 would typically "half-open" facilities and fractionally split customers, yielding a lower bound. The MIP solver uses branch and bound (and cutting planes) internally to find the optimal integer solution.

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. Consider two formulations of the same problem: if formulation A always gives an LP bound closer to the IP optimum than formulation B, then A is stronger.

Stronger formulations lead to:

• Tighter bounds at every node of the branch-and-bound tree.
• More pruning and fewer nodes explored.
• Faster solve times.

Finding strong formulations is a key skill in integer programming. We will see in Part 3 how cutting planes can strengthen a formulation dynamically during the solve.

What makes IP hard?

The feasible region of an IP is a set of discrete points — the integer points inside the LP feasible polytope. Unlike LP, where the feasible region is convex and we can use gradient-based methods, IP requires searching through a combinatorial space.

The number of feasible solutions can be astronomical. 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. Exhaustive enumeration is out of the question.

Yet modern IP solvers routinely solve problems with thousands or even millions of binary variables. They achieve this through a combination of:

• Branch and bound — systematic enumeration with intelligent pruning (Part 2).
• Cutting planes — tightening the LP relaxation to eliminate fractional solutions (Part 3).
• Presolve — simplifying the problem before solving (fixing variables, tightening bounds, removing redundant constraints).
• Heuristics — finding good feasible solutions quickly to improve pruning.

We explore the first two of these in the next parts of this mini-series.