Integer linear optimization: Cutting Planes 2: Unterschied zwischen den Versionen

Aktuelle Version vom 21. Juni 2013, 17:32 Uhr

Idea

The Idea of the Cutting Plane is to add Restrictions (the Cutting Planes) to contract the solution space more and more to get an integer solution. These restrictions cut off the non-integer parts of the solution.

Approach

First of all you should divide your restrictions trough the greates common factor.

Example: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6*x_1 + 15*x_2 <= 120

| gcf = 3

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2*x_1 + 5*x_2 <= 40

(1) You search for the continous Optimum with the Simplex Algorithm. If your solution is integer you are finished.

(2) Otherwise you have to insert Cutting Planes

Your source row is the one with the greates non integer part.

Row r:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_r+\sum (a_{ij}*NBV_j) = b_r

Converting r to: You have to break all ${\displaystyle a_{rj}}$ and ${\displaystyle b_{j}}$ into the integer part ${\displaystyle g_{rj}}$ and the rest (non integer) ${\displaystyle f_{j}}$.

${\displaystyle a_{ij}=g_{ij}+f_{ij}}$ ${\displaystyle \qquad }$ (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_{ij} < 1

)

${\displaystyle b_{i}=g_{i}+f_{i}}$ ${\displaystyle \qquad }$ (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_i < 1

)

We convert r to:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_r+\sum ((f_{rj} + g_{rj})*NBV_j) = g_r + f_r

Take the integer parts on the right side of the formula

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum(f_{rj}*NBV_j) = g_r + f_r - \sum(g_{rj}*NBV_j)-BV_r

Merge the integer parts into the slack variable ${\displaystyle y_{neu}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{neu} = g_r - \sum(g_{rj}*NBV_j)-BV_r

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum(f_{rj}*NBV_j) = f_r + y_{neu}

Now we have to constract our new formula in the same form like the others. You have to consider, that ${\displaystyle y_{neu}}$ cannot have an algebraic sign.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{neu} - (f_{rj}*NBV_j) = -f_r

This is now our Cutting Plane.

Example

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): max G = 2*x_1 + 3*x_2

Subject to

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6*x_1 + 15*x_2 <= 120

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 14*x_1 + 6*x_2 <= 141

(0) if possible: round

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 6*x_1 + 15*x_2 <= 120

|:3

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2*x_1 + 5*x_2 <= 40

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 14*x_1 + 6*x_2 <= 141

|:2

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 7*x_1 + 3*x_2 <= 70

(1) Create the Simplex-Tableau and find the continuous optimum with the Simplex-Algorithm:

Initial tableau

	${\displaystyle x_{1}}$	${\displaystyle x_{2}}$
${\displaystyle G}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -2	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -3	${\displaystyle 0}$
${\displaystyle y_{1}}$	${\displaystyle 2}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -5	${\displaystyle 40}$
${\displaystyle y_{2}}$	${\displaystyle 7}$	${\displaystyle 3}$	${\displaystyle 10}$

After one iteration we get the first optimal solution. But it's not integer yet.

Optimal solution (non integer)

	${\displaystyle x_{1}}$	${\displaystyle y_{2}}$
${\displaystyle G}$	${\displaystyle 5}$	${\displaystyle 1}$	${\displaystyle 70}$
${\displaystyle y_{1}}$	${\displaystyle {\frac {41}{3}}}$	${\displaystyle {\frac {5}{3}}}$	${\displaystyle {\frac {470}{3}}}$
${\displaystyle x_{2}}$	${\displaystyle {\frac {7}{3}}}$	${\displaystyle {\frac {1}{3}}}$	${\displaystyle {\frac {70}{3}}}$

Now we have to insert the Cutting Plane. We choose ${\displaystyle y_{1}}$ because it has the greatest non integer part.

Source row:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_1 + \frac{41}{3} * x_1 + \frac{5}{3} * y_2 =\frac{470}{3}

Divided:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_1 + (13 + \frac{2}{3}) * x_1 + (1 + \frac{2}{3}) * y_2 =156 + \frac{2}{3}

with slack variable:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_1 + \frac{2}{3} * x_1 + \frac{2}{3} * y_2 =\frac{2}{3} + y_3

Restriction for the Simplex_Tableau:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_3 - \frac{2}{3} * x_1 - \frac{2}{3} * y_2 = -\frac{2}{3}

Extended Simplex Tableau

	${\displaystyle x_{1}}$	${\displaystyle y_{2}}$
${\displaystyle G}$	${\displaystyle 5}$	${\displaystyle 1}$	${\displaystyle 70}$
${\displaystyle y_{1}}$	${\displaystyle {\frac {41}{3}}}$	${\displaystyle {\frac {5}{3}}}$	${\displaystyle {\frac {470}{3}}}$
${\displaystyle x_{2}}$	${\displaystyle {\frac {7}{3}}}$	${\displaystyle {\frac {1}{3}}}$	${\displaystyle {\frac {70}{3}}}$
${\displaystyle y_{3}}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{2}{3}	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{2}{3}	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{2}{3}

After two further iterations we get the optimal integer solution:

Optimal Solution (Integer)

	${\displaystyle y_{3}}$	${\displaystyle x_{1}}$
${\displaystyle G}$	${\displaystyle {\frac {3}{2}}}$	${\displaystyle 4}$	${\displaystyle 69}$
${\displaystyle y_{1}}$	${\displaystyle {\frac {5}{2}}}$	${\displaystyle 12}$	${\displaystyle 155}$
${\displaystyle x_{2}}$	${\displaystyle {\frac {1}{2}}}$	${\displaystyle 2}$	${\displaystyle 23}$
${\displaystyle y_{2}}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{2}	${\displaystyle 1}$	${\displaystyle 1}$

The solution is integer an optimal.

References

[1] Wikipedia Article about Cutting Planes