Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

MILP Factory › Visualizing Mixed Integer Linear Programming

Michael BrenndoerferAugust 29, 20257 min read

Machine Learning from ScratchAll chapters

Part 9 of 9Optimization

Chapter 62MILP Factory › Visualizing Mixed Integer Linear Programming

Reading section 3 of 8 · Visualizing Mixed Integer Linear Programming · 7 minSection 3 of 8 · 7 min

Section 3 of 8 · 7 min read

MILP Factory › Visualizing Mixed Integer Linear ProgrammingOne section · Sections in this chapter3 / 8 ↓

Sections in this chapter8

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Let's create visualizations to understand how MILP works in practice. We'll examine a simple factory optimization problem with two products and capacity constraints.

Out[3]:

Visualization

Feasible region plot showing continuous LP solutions as shaded area with linear constraints forming triangular region. — Continuous linear programming feasible region showing all allowed solutions. The shaded area represents all combinations of Product 1 and Product 2 that satisfy both machine capacity constraints. The blue line represents Machine A's constraint (2x₁ + 3x₂ ≤ 12), while the red line represents Machine B's constraint (4x₁ + 2x₂ ≤ 16). Corner points are marked, with the optimal solution at (3, 2) where both constraints are binding.

Discrete MILP solutions shown as red dots at integer coordinates within the same constraint boundaries. — Mixed integer linear programming feasible points restricted to integer values only. While the continuous LP allows any point within the shaded region, MILP restricts solutions to discrete integer coordinates. Each red dot represents a feasible integer solution where both x₁ and x₂ are whole numbers satisfying the capacity constraints. The optimal integer solution (3, 2) coincides with the continuous optimal solution in this case.

Integer feasible solutions and their profits:
(0, 0): Profit = 0
(0, 1): Profit = 2
(0, 2): Profit = 4
(0, 3): Profit = 6
(0, 4): Profit = 8
(1, 0): Profit = 3
(1, 1): Profit = 5
(1, 2): Profit = 7
(1, 3): Profit = 9
(2, 0): Profit = 6
(2, 1): Profit = 8
(2, 2): Profit = 10
(3, 0): Profit = 9
(3, 1): Profit = 11
(3, 2): Profit = 13
(4, 0): Profit = 12

Now let's visualize the branch-and-bound process that MILP solvers use:

Out[4]:

Visualization

Tree diagram showing branch-and-bound process with colored nodes representing LP relaxation, branching nodes, subproblems, integer solutions, and infeasible branches. — Branch-and-bound tree visualization showing how MILP solvers systematically explore the solution space. The tree starts with the LP relaxation solution at the root (green), then branches on integer variables to create subproblems (coral). Each branch explores a different region of the solution space, with some branches leading to integer solutions (gold) and others becoming infeasible (gray). The process continues until all branches are explored or pruned, ultimately finding the optimal integer solution. This visualization demonstrates the systematic search strategy that makes MILP solvers efficient despite the exponential solution space.