Many optimization problems may be formulated as a linear program. Given matrix and vectors , , we seek some vector that satisfies
where elements in are nonnegative. We call the objective function, and are known as the constraints.
Flow Networks as Linear Programs
Pushing flow through a network reduces to linear programming!
Decision Problem Formulation
Note that linear programs can be formulated as a decision problem. Given some , does there exist some such that
If YES, then simple provide the vector to be verified. If NO, we need some polynomial certificate to verify there exists no such vector. This is where the notion of a ‘dual’ program comes in. But first, perhaps an example is appropriate
Suppose you are given the following meal choices: burger at $9, yogurt at $6, and ramen at $2. You also want to satisfy some dietary needs: you require at least 180 calories of protein, 100 calories of carbohydrates, and 20 calories of fat.
Given the above caloric breakdown of each meal, how can you satisfy your requirements while spending as little as possible? Let us formulate our problem as a linear program. Let be the units of burgers, yogurts, and ramen we purchase. Note that we have the following constraints
where we want to minimize our objective . Note that this is a minimization linear program, and to convert it to standard form, all we need to do is negate the objective and constraints, which yields the following linear program
Consider following linear program
Let us assign variable to constraint inequality (j), ensuring . Note that
Adding each inequality together and grouping by yields
For each , constrain multiplicative term to be greater than or equal to , yielding following constraints
These constraints ensure that . As such, this is the dual program for original linear program with objective that we seek to minimize and constraints given above.
Let be matrix and , be vectors.
Given linear program with following objective and constraints
Dual program is given as follows
where , . Weak duality states
Linear Programing Duality Theorem
Given primal program , dual program , there exist four possibilities
- P is infeasible, which implies D is unbounded
- P is unbounded, which implies D is infeasible
- P, D are both infeasible
- P, D are feasible
Linear program is infeasible if there exists no solution that satisfies all constraints, and is unbounded if objective function may be incremented towards positive or negative infinity. We shall demonstrate that in case (4), P, D have the same optimal value. We will need the following lemma to do this
For any matrix , vector , exactly one of the following holds
- There exists such that
- There exists such that