Gruppe 1

Cutting-plane method

Cutting plane method is an approach to the solution of integer linear programming problems.First of all we do not consider that variables $x_{i}$ is an integer. But by adding linear constraints (so called cutting plane) the original feasible region will be cut.That part which was cut off contains only non-integer solution.Any integer feasible solution is kept in the ”modified” feasible region. This method is to point out how to find the right kinds of cutting planes (not necessarily only one to find), so that after cutting the feasible region finally we actually the get integer optimal solution. This method is proposed by R. E. Gomory, and it is also known as Gomory's cutting plane method.

Example

Consider the integer optimization problem

Maximize $Z=3x_{1}+4x_{2}$

Subject to

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_1-x_2 \le 12

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 3x_1+11x_2 \le 66

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \geq 0

and $x_{1},x_{2}$ integer

Introduce slack variables $y_{A},y_{B}$ to produce the standard form

Maximize Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Z = 3x_1-x_2

Subject to

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_A+3x_1-x_2 \le 12

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_B+3x_1+11x_2 \le 66

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1,x_2 \geq 0

and $x_{1},x_{2}$ integer

Initial tableau

	$x_{1}$	$x_{2}$
$Z$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -3	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -4	$0$
$y_{A}$	$3$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1	$12$
$y_{B}$	$3$	$11$	$66$

We use simplex method to get the optimal solution.(See "First optimal solution")

	$x_{1}$	$y_{B}$
$Z$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{21}{11}	${\frac {4}{11}}$	$24$
$y_{A}$	${\frac {36}{11}}$	${\frac {1}{11}}$	$18$
$x_{2}$	${\frac {3}{11}}$	${\frac {1}{11}}$	$6$

First optimal solution

	$y_{A}$	$y_{B}$
$Z$	${\frac {7}{12}}$	${\frac {5}{12}}$	${\frac {69}{2}}$
$x_{1}$	${\frac {11}{36}}$	${\frac {1}{36}}$	${\frac {11}{2}}$
$x_{2}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{12}	${\frac {1}{12}}$	${\frac {9}{2}}$

From the tableau above we can get the following equations

$x_{1}+{\tfrac {11}{36}}y_{A}+{\tfrac {1}{36}}y_{B}={\tfrac {11}{2}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 - \tfrac{1}{12} y_A + \tfrac{1}{12} y_B = \tfrac{9}{2}

Each of these equations produces the same cutting plane.In this example we choose the first equation $x_{1}+{\tfrac {11}{36}}y_{A}+{\tfrac {1}{36}}y_{B}={\tfrac {11}{2}}$. It can be written as following:

$x_{1}+{\tfrac {11}{36}}y_{A}+{\tfrac {1}{36}}y_{B}=5+{\tfrac {1}{2}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \tfrac{11}{36} y_A + \tfrac{1}{36} y_B = \tfrac{1}{2} + (5-x_1)

Here we introduce a new slack variable $y_{C}$,so the equation will be writen:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_C-\tfrac{11}{36} y_A - \tfrac{1}{36} y_B = -\tfrac{1}{2}

First optimal solution extended

	$y_{A}$	$y_{B}$
$Z$	${\frac {7}{12}}$	${\frac {5}{12}}$	${\frac {69}{2}}$
$x_{1}$	${\frac {11}{36}}$	${\frac {1}{36}}$	${\frac {11}{2}}$
$x_{2}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{12}	${\frac {1}{12}}$	${\frac {9}{2}}$
$y_{C}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{11}{36}	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{36}	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{2}

Second optimal solution

	$y_{C}$	$y_{B}$
$Z$	${\frac {21}{11}}$	${\frac {4}{11}}$	${\frac {369}{11}}$
$x_{1}$	$1$	$0$	$5$
$x_{2}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{11}	${\frac {1}{11}}$	${\frac {51}{11}}$
$y_{A}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{36}{11}	${\frac {1}{11}}$	${\frac {18}{11}}$

So we have found the solution ,namely $x_{1}=5$ and $x_{2}={\frac {51}{11}}$. This solution is non-integral, so we seek a cut. For this purpose, we choose a row of the optimal tableau with a non-integral right-hand side. For instance, the second row of the optimal tableau says:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2-\tfrac{3}{11} y_C + \tfrac{1}{11} y_B = \tfrac{51}{11}

We can introduce a new slack variable y_D and rewrite the cut as

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_D-\tfrac{8}{11} y_C - \tfrac{1}{11} y_B = -\tfrac{7}{11}

With this new variable and this new constraint, the simplex tableau becomes

Second optimal solution extended

	$y_{C}$	$y_{B}$
$Z$	${\frac {21}{11}}$	${\frac {4}{11}}$	${\frac {369}{11}}$
$x_{1}$	$1$	$0$	$5$
$x_{2}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{11}	${\frac {1}{11}}$	${\frac {51}{11}}$
$y_{A}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{36}{11}	${\frac {1}{11}}$	${\frac {18}{11}}$
$y_{D}$	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{8}{11}	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{11}	Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{7}{11}