Linear Programming

Linear Programming
A Brute Force Approach

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

A Problem You've Seen:
- Minimize/maximize a function of one (or more) variable(s)
A Problem You May Have Seen:
- Minimize/maximize a function of one or more variables subject to one or more constraints

Background (cont.)

Solving an Unconstrained Problem:
- Take the derivative (or partials derivatives), set it (them) to zero, and solve
Solving the Constrained Problem:
- Introduce Lagrange multipliers and treat it as an unconstrained problem

Background (cont.)

What You're Never Told:
- This only works (in closed form) when the derivatives turn out to be "simple"
What About Other Problems:
- Numerical algorithms exist that depend on the form of the problem

Linear Programming/Optimization

The Problem:
- Minimize/maximize a linear function of \(n\) decision variables subject to \(m\) functional constraints (and \(n\) non-negativity constaints)
The Canonical Form:
- \(\text{max } Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n\)
- subject to the constraints
- \( \begin{array}{c c c c c c c c c} a_{11}x_1 & + & a_{12}x_2 & + & \cdots & + & a_{1n}x_n & \leq & b_1 \\ a_{21}x_1 & + & a_{22}x_2 & + & \cdots & + & a_{2n}x_n & \leq & b_2 \\ & & & \vdots \\ a_{m1}x_1 & + & a_{m2}x_2 & + & \cdots & + & a_{mn}x_n & \leq & b_m \\ \end{array} \)
- and
- \(x_1 \geq 0, x_2 \geq 0, \ldots, x_n \geq 0\)

Some Terminology

Decision Variables:
- The variables whose values are being chosen (i.e., the \(x\) variables in the canonical form)
Feasible Solution:
- Values for the decision variables that satisfy all of the constraints
Optimal Solution:
- A "best" possible (in terms of the objective function) feasible solution

An Example with Two Decision Variables

The Setting:
- A commercial bakery with three plants that makes two kinds of cookies. Chocolate chip cookies earn a profit of 3 (thousand) dollars per truckoad, and peanut butter cookies earn a profit of 5 (thousand) dollars per truckload. Plant 1 can only produce chocolate chip cookies, plant 2 can only produce peanut butter cookies, and plant 3 can produce both. The three plants require different amounts of resources and have different capacities.
The Optimization Problem:
- \( \begin{array}{l l l l l l} \text{max} & 3 x_1 & + & 5 x_2 \\ \text{s.t.} & 1 x_1 & & & \leq & 4 \\ & & & 2 x_2 & \leq & 12 \\ & 3 x_1 & + & 2 x_2 & \leq & 18 \\ & x_1 & & & \geq & 0 \\ & & & x_2 & \geq & 0 \\ \end{array} \)

Visualizing Problems with Two Decision Variables

The Objective Function:
- We could plot \(Z\) as a function of \(x_1\) and \(x_2\) in three dimensions, but we can also plot the level sets in two dimensions
The Constraints:
- Ignoring the inequality, each constraint can be plotted as a line in two dimensions

Visualizing (cont.)

Level Sets of the Objective Function

Visualizing (cont.)

Functional Constraints

Visualizing (cont.)

Solution

The Simplex Algorithm

An Important Observation:
- An optimal solution must be a corner-point feasible solution (i.e., a feasible solution that does not lie on any line segment connecting two other feasible solutions)
The Terminology:
- Each is a solution of solving \(n\) equations (out of \(m + n\)) in \(n\) unknowns
An Unfortunate Fact:
- There can be as many as \(\frac{(m + n)!}{m!n!}\) such solutions

The Simplex Algorithm (cont.)

The Approach:
- Move from one corner-point feasible solution to an adjacent "better" corner-point feasible solution
The Stopping Rule:
- Stop when there is no "better" adjacent point

A Brute Force Algorithm

The Approach:
- Evaluate the objective function at all corner-points and choose the feasible corner-point with the best objective function value
Practicality of this Approach:
- For \(n=2\) and \(n=3\) there are 10 such points
- For \(n=50\) and \(m=50\) there are \(10^{29}\) such points

What's Left to the Brute Force Approach?