co250.md

Module 1: Formulations

*** weak 1 ***

Linear Programs

A mathematical program that is not an LP.

• Dividing by variables is not allowed. $$ \bold{-1/x_1} - x_3 $$

• Cannot have strict inequalities.

• Must have finite number of constraints.

Integer Program

An integer program is a linear program with added integrality constraints for some/all of the variables. $$ max:\ x_1 + x_2 +2x_4 \ s.t.\ \ \ x1+x2\leq 1 \ -x_2 - x_3 \geq -1 \ x_1 + x_3 = 1 \ \ \ x_1, x_2, x_3 \geq 0 \ \quad \bold{x1, x3 \ integer.} $$ Note LPs are easy to solve, IPs are not.

*** weak 2** *

Constraints methods:

1. when y1 = 0, x1 = 0;

   when y1 =1, 1000<=x1<=M; $$ Give \ L(y1)<=x1<=U(y1), \ 1000y1 \leq x1 \leq My1 $$

2. If x3 >= 500, then x2 <= 400; $$ Z = \begin{cases} 1, & 500 \leq x_3 \leq 6000 & and & 0 \leq x_2\leq 400\ 0, & 0 \leq x_3 \leq 499 & and & 0\leq x_2 \leq10000 \end{cases} \ 500Z \leq x_3 \leq 6000Z + 499(1-Z) \ 0 \leq x_2 \leq 400(Z)+10000(1-Z) $$

*** weak 4 ***

Three certificates

• **Proving Infeasibility **

  find a $y^T$ where

  $y^T$Ax = $y^T$b

  $y^TA \geq 0 \ y^T b &lt; 0$

• Proving Optimality

  

• Proving Unboundedness

find a set of feasible solutions x(t).

$x(t) = \bar{x} + tr$

*** weak 5 ***

Two Phase Method

Step 1: $\forall b_i &lt; 0 \ multiply \ row_j \ by -1$

Step 2: convert to Auxp $$ max (1, 4, 2, 3)x \ \begin{pmatrix} 1 & -2 &2& 9 \ 1 & 5 & 4 & 3 \end{pmatrix} x = \begin{pmatrix} -5 \ 6 \end{pmatrix} \ \ \ \ converting \ to \ Auxp \
\ max (0, 0, 0, 0, -1, -1)x \ \begin{pmatrix} -1 & 2 &-2& -9 &1 &0 \ 1 & 5 & 4 & 3 &0 & 1 \end{pmatrix} x = \begin{pmatrix} 5 \ 6 \end{pmatrix} \ \ \ \ $$ Step 3: use Simplex Algorithm.

Properties of Aux Problem

• Aux is always feasible ($b \geq 0$)

• Aux objective function always bounded up by 0

  Eg. (0 0 0 0 -1 -1) $\leq$ 0

  Therefore, Aux always has optimal solution.

• if opt value = 0, Aux Problem feasible, with a feasible basis.

  else if opt value < 0, Aux Problem Infeasible.