LP Fundamentals

Check Your Knowledge

Before starting, make sure you're comfortable with:

• Matrix multiplication: $Ax = b$
• Solving linear systems (at least conceptually)
• What "optimization" means (finding best values)

If you need a refresher, Khan Academy's linear algebra course is excellent.

---

1. What is Linear Programming?

Linear Programming (LP) finds the best value of a linear objective subject to linear constraints.

The Standard Form

Every LP can be written as:

$$\min_{x} \quad c^T x \quad \text{subject to} \quad Ax = b, \quad x \geq 0$$

Where:

• $x$ is the vector of decision variables
• $c$ is the cost/objective vector
• $A$ is the constraint matrix
• $b$ is the right-hand side

A Concrete Example

Problem: A factory makes chairs and tables. Each chair needs 2 hours carpentry, 1 hour finishing, and profits $20. Each table needs 1 hour carpentry, 2 hours finishing, and profits $30. With 40 hours carpentry and 50 hours finishing available, how many of each should they make?

Formulation: $$\max \quad 20x_1 + 30x_2$$ $$\text{s.t.} \quad 2x_1 + x_2 \leq 40 \quad \text{(carpentry)}$$ $$\quad x_1 + 2x_2 \leq 50 \quad \text{(finishing)}$$ $$\quad x_1, x_2 \geq 0$$

Why LP Matters

LP solvers handle problems with millions of variables. They're used for:

• Supply chain optimization
• Financial portfolio allocation
• Airline crew scheduling
• Power grid management
• As subproblems in integer programming

---

2. Sparse Matrix Storage

Real LP problems have matrices with millions of entries, but most are zero. Sparsity is the key to efficiency.

Dense vs Sparse

A dense 1000×1000 matrix stores 1,000,000 numbers. But in LP, typically only 0.1-1% are nonzero - storing all those zeros wastes memory and computation.

Compressed Sparse Column (CSC) Format

COIN-OR uses CSC format. For a matrix:

$$A = \begin{pmatrix} 1 & 0 & 2 \ 3 & 0 & 0 \ 0 & 4 & 5 \end{pmatrix}$$

We store:

• values: [1, 3, 4, 2, 5] (nonzeros by column)
• row indices: [0, 1, 2, 0, 2] (which row each value is in)
• column starts: [0, 2, 3, 5] (where each column begins in values array)

Column 0 has values at positions 0-1, column 1 at position 2, column 2 at positions 3-4.

Why This Matters

Sparse operations only touch nonzeros:

• Dense matrix-vector multiply: $O(mn)$ operations
• Sparse matrix-vector multiply: $O(\text{nnz})$ operations

For a 10,000×10,000 matrix with 50,000 nonzeros, that's 50,000 vs 100,000,000 operations!

---

3. LU Factorization

The simplex method needs to solve systems like $Bx = b$ at every iteration, where $B$ is the basis matrix. LU factorization makes this fast.

What is LU Factorization?

Factor a matrix into lower and upper triangular parts: $$B = LU$$

Then solve $Bx = b$ in two easy steps:

1. Solve $Ly = b$ (forward substitution)
2. Solve $Ux = y$ (backward substitution)

Triangular systems are fast because you can solve one variable at a time.

Markowitz Pivot Selection

When factoring sparse matrices, pivot choice matters enormously. A bad pivot creates fill-in (zeros become nonzeros).

The Markowitz criterion picks the pivot that minimizes expected fill-in:

$$\text{cost}(i,j) = (r_i - 1)(c_j - 1)$$

Where $r_i$ is the number of nonzeros in row $i$, and $c_j$ is the number in column $j$.

Updating vs Refactoring

After a simplex pivot, $B$ changes by one column. Instead of refactoring from scratch ($O(m^3)$ worst case), we update the factorization ($O(m^2)$ typical).

COIN-OR uses Forrest-Tomlin updates: maintain $L$ and modify $U$ by eliminating a "spike" in the structure.

---

4. The Simplex Method

The simplex method walks along edges of the feasible polytope, improving the objective at each step, until reaching an optimal vertex.

Basic and Non-Basic Variables

At any vertex, some variables are basic (can be nonzero) and others are non-basic (fixed at bounds).

If we have $m$ constraints and $n$ variables, exactly $m$ variables are basic. The basis matrix $B$ is the $m \times m$ submatrix of $A$ for basic columns.

The Simplex Tableau (Conceptually)

Partition variables into basic ($x_B$) and non-basic ($x_N$):

$$Ax = Bx_B + Nx_N = b$$ $$x_B = B^{-1}b - B^{-1}Nx_N$$

The reduced costs tell us if we can improve: $$\bar{c}_N = c_N - N^T(B^{-T}c_B)$$

If all $\bar{c}_j \geq 0$ for minimization, we're optimal.

The Primal Simplex Algorithm

---

5. Worked Example

Let's trace through a complete simplex solve on a small problem.

The Problem

$$\min \quad -2x_1 - 3x_2$$ $$\text{s.t.} \quad x_1 + x_2 + s_1 = 4$$ $$\quad x_1 + 2x_2 + s_2 = 6$$ $$\quad x_1, x_2, s_1, s_2 \geq 0$$

Initial basis: ${s_1, s_2}$ (slack variables), so $B = I$.

Initial solution: $x_B = (s_1, s_2) = (4, 6)$, $x_N = (x_1, x_2) = (0, 0)$. Objective = 0.

Iteration 1

Pricing: Reduced costs for non-basic variables:

• $\bar{c}_1 = -2 - (0,0) \cdot (1,1)^T = -2$
• $\bar{c}_2 = -3 - (0,0) \cdot (1,2)^T = -3$

Both negative. Choose $x_2$ (most negative) to enter.

FTRAN: $d = B^{-1}a_2 = I \cdot (1, 2)^T = (1, 2)^T$

Ratio test:

• $s_1$: $4/1 = 4$
• $s_2$: $6/2 = 3$ ← winner

$s_2$ leaves, $x_2$ enters. $\theta = 3$.

Update: $x_2 = 3$, $s_1 = 4 - 1 \cdot 3 = 1$, $s_2 = 0$. Objective = $-9$.

Iteration 2

New basis: ${s_1, x_2}$.

$$B = \begin{pmatrix} 1 & 1 \ 0 & 2 \end{pmatrix}, \quad B^{-1} = \begin{pmatrix} 1 & -0.5 \ 0 & 0.5 \end{pmatrix}$$

Pricing: $\bar{c}1 = -2 - (-3) \cdot (0.5) = -0.5$ (negative), $\bar{c}{s_2} = 0 - (-3) \cdot 0.5 = 1.5$ (positive)

Enter $x_1$.

FTRAN: $d = B^{-1}(1, 1)^T = (0.5, 0.5)^T$

Ratio test:

• $s_1$: $1/0.5 = 2$ ← winner
• $x_2$: $3/0.5 = 6$

$s_1$ leaves. $\theta = 2$.

Update: $x_1 = 2$, $x_2 = 3 - 0.5 \cdot 2 = 2$. Objective = $-2(2) - 3(2) = -10$.

Iteration 3

New basis: ${x_1, x_2}$.

Pricing: All reduced costs ≥ 0. Optimal!

Solution: $x_1 = 2$, $x_2 = 2$, objective = $-10$.

---

6. Dual Simplex

The dual simplex maintains dual feasibility (reduced costs have correct signs) while working toward primal feasibility (variable bounds satisfied).

When to Use Dual Simplex

Dual simplex is preferred when:

• Starting from a dual-feasible solution (common after adding cuts)
• The problem has many more rows than columns
• Re-optimizing after bound changes

Most modern solvers use dual simplex as the default.

The Algorithm

---

7. Presolve: Making Problems Easier

Before solving, presolve transforms the problem into an equivalent but smaller/easier form.

Common Presolve Reductions

Reduction	What it does
Fixed variable removal	If $l_j = u_j$, substitute $x_j = l_j$
Singleton row	Row with one variable → bound tightening
Singleton column	Column in one constraint → substitute out
Forcing constraint	All variables at bounds → fix them
Dominated column	Variable never useful → fix at bound
Doubleton equality	Two variables in equation → substitute

Example: Singleton Row

If constraint is $3x_1 = 6$, then $x_1 = 2$ is forced. Remove $x_1$ from the problem.

Why Presolve Matters

• Reduces problem size (fewer pivots needed)
• Detects infeasibility/unboundedness early
• Tightens bounds (helps branch-and-bound later)
• Improves numerical stability

A good presolve can reduce solve time by 10-100x on real problems!

---

What's Next?

You now understand the core LP algorithms! Next steps:

• MIP Journey - Add integer variables and learn branch-and-bound
• Browse the source - Explore the actual implementations
• Algorithm index - Deep-dive into specific algorithms