ILP Basics with PuLP

Integer Linear Programming (ILP) is one of the most important methods in mathematical optimization. It models problems with linear equations and requires some or all variables to be integers.

Why ILP?

Many business decisions involve discrete choices:

• How many units of each product to manufacture?
• Which warehouse should serve which customer?
• How many employees to assign to each shift?

These cannot be modeled with simple continuous equations. ILP handles discrete decisions naturally.

What Is ILP?

An ILP problem has three components:

Objective: maximize/minimize c1*x1 + c2*x2 + ... + cn*xn

Subject to:
  a11*x1 + a12*x2 + ... + a1n*xn <= b1
  a21*x1 + a22*x2 + ... + a2n*xn <= b2
  ...
  am1*x1 + am2*x2 + ... + amn*xn <= bm

  x1, x2, ..., xn >= 0
  Some or all xi are integers

The Three Elements

| Element | Description | Example | |:-------:|-------------|---------| | Decision Variables | What you decide | Units of A and B to produce | | Objective Function | What to maximize or minimize | Profit = 40A + 30B | | Constraints | Resource limits | A + 2*B <= 100 hours |

How ILP Works

Install PuLP:

pip install pulp

Production Planning Example

A factory produces two products with limited materials and labor:

import pulp

# Create problem (maximize profit)
prob = pulp.LpProblem("Production Planning", pulp.LpMaximize)

# Decision variables
product_a = pulp.LpVariable("Product_A", lowBound=0, cat="Integer")
product_b = pulp.LpVariable("Product_B", lowBound=0, cat="Integer")

# Objective: maximize profit
prob += 40 * product_a + 30 * product_b, "Total_Profit"

# Constraints
prob += 2 * product_a + 1 * product_b <= 100, "Material_Constraint"
prob += 1 * product_a + 2 * product_b <= 80, "Labor_Constraint"
prob += product_a <= 40, "Market_Demand_A"

# Solve
prob.solve()

print(f"Status: {pulp.LpStatus[prob.status]}")
print(f"Product A: {int(product_a.value())} units")
print(f"Product B: {int(product_b.value())} units")
print(f"Total Profit: ${pulp.value(prob.objective)}")

ILP vs LP

| Aspect | Linear Programming | Integer Linear Programming | |--------|:-----------------:|:-------------------------:| | Variables | Continuous | Integer or mixed | | Solver | Simplex | Branch-and-Bound | | Complexity | Polynomial O(n^3) | NP-hard | | Real-world fit | Resource allocation | Discrete decisions |

Real-World Applications

1. Manufacturing Planning

Decide how many units of each product to produce given limited materials, labor, and machine time. Maximize profit.

2. Logistics

Which warehouse should ship to which customer? ILP finds the optimal assignment minimizing transportation costs.

3. Staff Scheduling

How many employees to schedule each day given demand forecasts and labor rules?

4. Investment

Which stocks to buy given a budget and risk constraints?

The Vibe Coding Approach

"I have a factory that makes two products. Product A uses 2 units of material and 1 hour of labor, profit $40. Product B uses 1 unit of material and 2 hours of labor, profit $30. I have 100 material units and 80 labor hours. Maximize profit."

The AI will generate the complete PuLP model.

Summary

ILP models problems with linear equations and integer variables. PuLP makes modeling intuitive in Python.

Key takeaways:

• ILP = linear objective + linear constraints + integer variables
• Three elements: decision variables, objective, constraints
• Branch-and-bound is the standard solution algorithm
• PuLP provides clean Python syntax for ILP modeling
• ILP is NP-hard but solvers handle moderate instances well
• Real applications in manufacturing, logistics, scheduling

What's Next: Staff Scheduling

The next chapter applies ILP to staff scheduling - assigning employees to shifts while respecting preferences, qualifications, and labor regulations.

Branch-and-Bound: How ILP Solvers Work

ILP solvers use branch-and-bound, a clever search algorithm:

1. Relax: Solve the LP relaxation (ignore integer constraints) - gives an upper bound
2. Branch: Pick a fractional variable, create two sub-problems (x <= floor(val) and x >= ceil(val))
3. Bound: Track the best integer solution found so far (lower bound)
4. Prune: If a sub-problem's upper bound is worse than current best, skip it
5. Repeat: Continue until all sub-problems are solved or pruned

Initial LP relaxation: A=33.3, B=33.3, Profit=$2333
  -> Branch on A (value 33.3)
    -> Branch 1: A <= 33
       LP: A=33, B=33, Profit=$2310 (integer feasible!)
       -> Best solution found: $2310
    -> Branch 2: A >= 34
       LP: A=34, B=32, Profit=$2320 (integer feasible!)
       -> Better solution: $2320
       -> Update best to $2320
    -> Prune: No better solutions possible
  -> Optimal: A=34, B=32, Profit=$2320

Advanced ILP Modeling Techniques

Binary Decision Variables

Many decisions are yes/no: "Should we build a new factory?" Use binary variables:

build_factory = pulp.LpVariable("Build_Factory", cat="Binary")

Big-M Constraints

Model conditional logic using large constants:

# If we build factory, production capacity >= 1000
# production_capacity <= M * build_factory
# production_capacity >= 1000 * build_factory
M = 10000  # Larger than any possible production
prob += production_capacity <= M * build_factory
prob += production_capacity >= 1000 * build_factory

Fixed Cost Modeling

Some costs are incurred only when production > 0:

# Total cost = fixed_cost * build_factory + variable_cost * production
prob += total_cost == fixed_cost * build_factory + variable_cost * production

Common ILP Applications

| Industry | Problem | Decision Variables | |----------|---------|:-----------------:| | Manufacturing | Production planning | How many units of each product | | Logistics | Facility location | Which warehouses to open | | Retail | Inventory management | How much to order of each SKU | | Finance | Portfolio optimization | Which stocks to buy | | Healthcare | Hospital staffing | How many nurses per shift | | Telecom | Network design | Which towers to build |

Performance Considerations

| Problem Size | Variables | Constraints | Typical Solve Time | |:-------------|:---------:|:-----------:|:------------------:| | Tiny | < 100 | < 100 | < 1 second | | Small | 100-1K | 100-1K | 1-10 seconds | | Medium | 1K-10K | 1K-10K | 10-60 seconds | | Large | 10K-100K | 10K-100K | Minutes to hours | | Huge | 100K+ | 100K+ | Hours to days |

Summary

ILP with PuLP is a powerful tool for solving discrete optimization problems. The combination of linear constraints and integer variables models a wide range of business decisions.

Key takeaways:

• ILP extends LP with integer variables for discrete decisions
• Branch-and-bound is the standard ILP solution algorithm
• PuLP makes ILP modeling accessible in Python
• Binary variables model yes/no decisions
• Big-M constraints model conditional logic
• Fixed costs modeled with binary + continuous variables
• Problem size directly affects solve time

What's Next: Staff Scheduling

The next chapter applies ILP to a classic business problem: scheduling employees across shifts while respecting preferences, qualifications, and labor regulations.