MIT 6.1220 — Lecture 11

Linear Programming (Part I)

Definition (Linear Programming). We seek to optimize a linear objective function subject to linear equality and linear inequality constraints. It will always look like:

\text{Max / min of } \left(\sum_{i = 1}^n c_i x_i\right) \text{ given } x_i \in \mathbb{R}^{\geq 0} \text{ and } \left \{ \left(\sum_{i = 1}^n A_{j, i} x_i \ \right) \bigstar_j \ b_j \right \}_{j = 1}^m \text{ for } \bigstar_j \in \{ \leq , \geq , =\}.

Problem. (Claw Machine) You have two claw machines $K_1$ and $K_2$ . Putting $\$x_1$ into $K_1$ yields a return of $\$ \left(\frac{x_1}{3}\right)$ , and putting $\$x_2$ into $K_2$ yields a return of $\$ \left(\frac{x_2}{2}\right)$ . Also, you must put at least as much into $K_1$ as $K_2$ . You have $\$60$ .

Solution. (Claw Machine LP) We can write the above setup as a linear program like so:

\text{Max / min of } \dfrac{1}{3}x_1 + \dfrac{1}{2}x_2 \text{ given } x_i \in \mathbb{R}^{\geq 0} \text{ and } x_1 - x_2 \geq 0 \text{ and } x_1 + x_2 \leq 60.

We can determine a normal form for linear programs.

Finding the max of a linear program $\mathcal{P}$ is the same as finding the min of $-\mathcal{P}$ . So we'll default max.
If $\bigstar_j$ is only allowed to be $\leq$ , then we can also implement constraints with $\geq$ and $=$ .
- (Using slack variables, we can implement $\{\leq, \geq, =\}$ using just $=$ . But we'll use $\leq$ .)

We can also rewrite our constraints in linear algebra notation. (Here, we say $\vec{m} \leq \vec{n}$ iff $m_i \leq n_i$ for all indices $i$ .)

\text{Find max of } \vec{c} \cdot \vec{x} \text{ given } \vec{x} \geq \vec{0} \text{ and } A\vec{x} \leq \vec{b}.

Definition. Given a set of constraints $A \vec{x} \leq \vec{b}$ of a linear program $\mathcal{P}$ ,

We say a feasible solution is some $\vec{\tilde{x}} \geq \vec{0}$ such that $A\vec{\tilde{x}} \leq \vec{b}$ .
We say $\textsc{Feasible}(\mathcal{P})$ is the set of all $\vec{x} \in \mathbb{R}^{\geq 0}$ such that $A\vec{x} \leq \vec{b}$ .
Some constraints might be degenerate in that they can be removed without changing $\textsc{Feasible}$ .
- This can happen by weakening via $\{x \geq 2, x \geq 0\} \to \{x \geq 2\}$ .
- This can happen by linear combination via $\{a \geq 2, b \geq 3, a + b \geq 5\} \to \{a \geq 2, b \geq 3\}$ .
We say the optimal value, possibly $\infty$ , is the supremum of $\vec{c} \cdot \vec{x}$ over $\textsc{Feasible}(\mathcal{P})$ ; if it is finite, it is achieved by some optimal solution.
- If the optimal value is finite, then the LP is bounded. Otherwise, the LP is unbounded.
- If $\textsc{Feasible}(\mathcal{P})$ is bounded (topologically speaking), then LP must be bounded.
- There is always a unique optimal value, possibly $\infty$ . (Pandora's box…)
- There may not always be a unique optimal solution, though.
  - Exercise: Prove that if there are two optimal solutions, then there are infinitely many.

Some optimal solution always occurs at a corner point, obviously. There exist polynomial-time solving algorithms.

There's this idea of duality that's also pretty obvious. You want to minimize the RHS of a nonnegative linear combination $\vec{y}$ of the constraints $A \vec{x} \leq \vec{b}$ , constrained on the LHS of this linear combination being at least $\vec{c} \cdot \vec{x}$ .