Linear Programming

Summary

We look at what it means to solve a Linear Programming problem and look at example algorithms like Simplex.

Contents

• Max Flow as LP
• Simple Example
• Key Issues
• LP Algorithms
  • Simplex

Max Flow as LP

Input: Directed graph G=(V,E)

LP: m variables, $\forall e \in E, f_e$

Objective function: $\max{ \left\lbrace \displaystyle\sum_{\overrightarrow{sv} \in E}f_{sv} \right\rbrace }$

• max sum of every edge out of source vertex

Subject to:

• $\forall e \in E : 0 \le f_e \le c_e$
• $\forall v \in V - \lbrace s,t \rbrace, \displaystyle\sum_{\overrightarrow{wv} \in E} f_{wv} = \displaystyle\sum_{\overrightarrow{vz} \in E} f_{vz}$

Simple Example

Company makes A and B

How many of each to maximize profit?

• Each unit of A makes $1 profit
• Each unit of B makes $6 profit

Demand:

• at most 300 units of A
• at most 200 units of B

Supply:

• Max of 700 hours of work per day
• 1 A takes 1 hour
• 1 B takes 3 hour

Variables:

• Let x = # of units of A to produce
• Let y = # of units of B to produce

Objective function: $\max{x + 6y}$

Constraints:

• $0 \le x \le 300$
• $0 \le y \le 200$
• $x + 3y \le 700$

Key Issues

• Optimum may be non-integer
  • Keeps it in P
    • Integer-only LP is NP-Complete
• Feasibility space is convex
• Optimum point lays at a vertex, except when LP is infeasible or unbounded

How do I find a vertex?

• Satisfy two inequalities, then find if it matches the other inequalities?
  • i.e. Set the lines equal to each other and solve for x,y

LP Algorithms

Polynomial time:

• Ellipsoid
• Interior point methods
  • Simplex

Simplex

Worst-case is exponential time, still widely-used

Output is guaranteed to be optimal

Works efficiently on huge LPs

Steps:

• Start at x = 0
• Look for neighbor with higher objective value
  • if found, move there and repeat
  • else, return x