Linear Programming

• Handwritten note
• Definition
  • Minimize objective function $c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$.
  • Subject to constraints $a_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n\le b_n$, …
  • Optimization under linear constraints!

Solution

• A solution with feasible region
  • Form feasible region
  • In convex cases, we know that the solution must be on the endpoints. We may simply find out all the values and compare.
  • Or, probe at one of the endpoint, and binary search to find the minimum.
• Another solution without feasible region, similar to prune-and-search
  • Pair constraints (half-plane boundaries) in arbitrary manner.
  • Probe anywhere, the local slope tells us where the minimum is at, this allows us to eliminate half of the half-planes.
  • Repeat the process.
  • Similarly for the upper convex hull.