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

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Example)
(→‎Authors)
 
(42 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 3: Zeile 3:
 
The cutting plane algorithm was developed in 1950 by Delbert Ray Fulkerson and George Dantzig and later costumized by Egon Balas and Ralph Gomory. Today it is one of the standart methodes for solving a integer optimisation problem.
 
The cutting plane algorithm was developed in 1950 by Delbert Ray Fulkerson and George Dantzig and later costumized by Egon Balas and Ralph Gomory. Today it is one of the standart methodes for solving a integer optimisation problem.
 
The basic idea behind this methode is to treat your linear programm not as usual as an integer linear programm. Instead you should consider it as a LP-Relaxation and add further inequalities untill an integer solution is found.
 
The basic idea behind this methode is to treat your linear programm not as usual as an integer linear programm. Instead you should consider it as a LP-Relaxation and add further inequalities untill an integer solution is found.
 +
==Approach==
 +
At the beginning you use the simplex algorythm to find the continous optimum. Afterwards you check your solution for integer.
 +
If not, use cutting planes. Otherwise you have already reached the optimal solution.
 +
You have to start with the cutting plane algorythm in the row with the greatest non integer part
 +
 +
:Using the simplex method to solve a linear program produces a set of equations of the form
 +
 +
:::<math>BV_i+\sum a_{ij}NBV_j = b_i</math> (<math>\alpha</math>)
 +
 +
Seperate both <math>a_ij</math> and <math>b_i</math> into integer fraction <math>g</math> and the rest <math>f</math>:
 +
 +
:::<math>a_{ij} = g_{ij} + f_{ij}</math> <math>\qquad</math>  (<math>0 \leq f_{ij} < 1</math>)
 +
:::<math>b_i = g_i + f_i</math>  <math>\qquad</math>  (<math>0 \leq f_i < 1</math>)
 +
 +
construct the equation (<math>\alpha</math>) to
 +
 +
::::<math>BV_i+\sum g_{ij}NBV_j -g_i= f_i-\sum f_{ij}NBV_j</math>
 +
 +
Use a new slack variable to obtain a cutting plane:
 +
 +
::::<math>BV_i'-\sum f_{ij}NBV_j -g_i= -f_i</math>
  
 
== Example ==
 
== Example ==
−
<math>x_{1}+2x_{2}
+
:: max <math>x_{1}+2x_{2}</math>
−
</math>
+
::s.t. <math>2x_{1}+x_{2} \leq  10</math>
−
<math>s.t. 2x_{1}+x_{2} \leq  10
+
:::<math>-x_{1}+x_{2} \leq 5</math>
−
</math>
+
:::<math>x_{1} \leq 4</math>
−
<math>-x_{1}+x_{2} \leq 5</math>
+
:::<math>x_{1}\geq0</math> integer
−
<math>x_{1} \leq 4</math>
+
:::<math>x_{2}\geq0</math> integer
−
<math>x_{1}\geq0</math> integer
+
<br>
−
<math>x_{2}\geq0</math> integer
+
Now we transfer it into an minimum problem
 +
<br>
 +
:: min <math>-x_{1}-2x_{2}</math>
 +
::s.t. <math>2x_{1}+x_{2} \leq  10</math>
 +
:::<math>-x_{1}+x_{2} \leq 5</math>
 +
:::<math>x_{1} \leq 4</math>
 +
:::<math>x_{1}\geq0</math> integer
 +
:::<math>x_{2}\geq0</math> integer
 +
<br>
 +
The correspondending Tableau is:<br>
 +
{| class="wikitable float-right"  style="text-align:center"
 +
|+ Initial tableau
 +
|- style="height: 50px;"
 +
| scope="col" width="50" |  || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>x_2</math> ||  scope="col" width="50" |
 +
|- style="height: 50px;"
 +
| <math>Z</math> || <math>-1</math> || <math>-2</math> || <math>0</math>
 +
|- style="height: 50px;"
 +
| <math>y_A</math> || <math>2</math> || <math>1</math> || <math>10</math>
 +
|- style="height: 50px;"
 +
| <math>y_B</math> || <math>-1</math> || <math>1</math> || <math>5</math>
 +
|- style="height: 50px;"
 +
| <math>y_C</math> || <math>1</math> ||  <math>0</math> || <math>4</math>
 +
|}
 +
<br>Now we use the Simplex Algorythm.<br>
 +
Pivot operation leads to:<br>
 +
{| class="wikitable float-right"  style="text-align:center"
 +
|- style="height: 50px;"
 +
| scope="col" width="50" |  || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>x_2</math> ||  scope="col" width="50" |
 +
|- style="height: 50px;"
 +
| <math>Z</math> || <math>-3</math> || <math>2</math> || <math>10</math>
 +
|- style="height: 50px;"
 +
| <math>y_A</math> || <math>3</math> || <math>-1</math> || <math>5</math>
 +
|- style="height: 50px;"
 +
| <math>y_B</math> || <math>-1</math> || <math>1</math> || <math>5</math>
 +
|- style="height: 50px;"
 +
| <math>y_C</math> || <math>1</math> ||  <math>0</math> || <math>4</math>
 +
|}
 +
<br>2. Iteration<br>
 +
{| class="wikitable float-right"  style="text-align:center"
 +
|- style="height: 50px;"
 +
| scope="col" width="50" |  || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>x_2</math> ||  scope="col" width="50" |
 +
|- style="height: 50px;"
 +
| <math>Z</math> || <math>1</math> || <math>1</math> || <math>15</math>
 +
|- style="height: 50px;"
 +
| <math>y_A</math> || <math>\frac{1}{3}</math> || <math>-\frac{1}{3}</math> || <math>\frac{5}{3}</math>
 +
|- style="height: 50px;"
 +
| <math>y_B</math> || <math>\frac{1}{3}</math> || <math>\frac{2}{3}</math> || <math>\frac{20}{3}</math>
 +
|- style="height: 50px;"
 +
| <math>y_C</math> || <math>-\frac{1}{3}</math> ||  <math>\frac{1}{3}</math> || <math>\frac{7}{3}</math>
 +
|}
 +
<br>We reached the minimum.<br>
 +
::<math>x_1 = \frac{5}{3}</math>, <math>x_2 = \frac{20}{3}</math>, <math>c^Tx = -15</math>
 +
The objective function is integer, but the solution not.
 +
We need to import a new restriction.
 +
::<math>\frac{1}{3}x_1 + \frac{2}{3}x_2\geq \frac{2}{3}</math>
 +
<br>as result we get a new Tableau:
 +
{| class="wikitable float-right"  style="text-align:center"
 +
|- style="height: 50px;"
 +
| scope="col" width="50" |  || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>x_2</math> ||  scope="col" width="50" |
 +
|- style="height: 50px;"
 +
| <math>Z</math> || <math>1</math> || <math>1</math> || <math>15</math>
 +
|- style="height: 50px;"
 +
| <math>y_A</math> || <math>\frac{1}{3}</math> || <math>-\frac{1}{3}</math> || <math>\frac{5}{3}</math>
 +
|- style="height: 50px;"
 +
| <math>y_B</math> || <math>\frac{1}{3}</math> || <math>\frac{2}{3}</math> || <math>\frac{20}{3}</math>
 +
|- style="height: 50px;"
 +
| <math>y_C</math> || <math>\frac{1}{3}</math> || <math>\frac{1}{3}</math> || <math>\frac{7}{3}</math>
 +
|- style="height: 50px;"
 +
| <math>y_D</math> || <math>-\frac{1}{3}</math> ||  <math>-\frac{2}{3}</math> || <math>-\frac{2}{3}</math>
 +
|}
 +
<br>the final simplex tableau:<br>
 +
{| class="wikitable float-right"  style="text-align:center"
 +
|- style="height: 50px;"
 +
| scope="col" width="50" |  || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>x_2</math> ||  scope="col" width="50" |
 +
|- style="height: 50px;"
 +
| <math>Z</math> || <math>\frac{1}{2}</math> || <math>\frac{3}{2}</math> || <math>14</math>
 +
|- style="height: 50px;"
 +
| <math>y_A</math> || <math>\frac{1}{2}</math> || <math>-\frac{1}{2}</math> || <math>2</math>
 +
|- style="height: 50px;"
 +
| <math>y_B</math> || <math>0</math> || <math>1</math> || <math>6</math>
 +
|- style="height: 50px;"
 +
| <math>y_C</math> || <math>-\frac{1}{2}</math> || <math>\frac{1}{2}</math> || <math>2</math>
 +
|- style="height: 50px;"
 +
| <math>y_D</math> || <math>\frac{1}{2}</math> ||  <math>-\frac{3}{2}</math> || <math>1</math>
 +
|}
 +
<br>we reached the optimal solution:
 +
::<math>x_1 = 2</math>, <math>x_2 = 6</math>, <math>c^Tx = -14</math><br>
 +
As you can see we found the integer solution.
 +
 
 +
===Reference===
 +
[http://num.math.uni-bayreuth.de/de/teaching/archive/ss_2005/01061/s_allescher.pdf Schnittebenenverfahen von Gomory]<br>
 +
[http://www.stanford.edu/class/ee364b/notes/accpm_notes.pdf Analytic Center Cutting-Plane Method]
 +
 
 +
===Authors===
 +
Joshua Müller<br>
 +
Björn Linse<br>
 +
Kim Brill

Aktuelle Version vom 26. Juni 2013, 14:27 Uhr

Idea

The cutting plane algorithm was developed in 1950 by Delbert Ray Fulkerson and George Dantzig and later costumized by Egon Balas and Ralph Gomory. Today it is one of the standart methodes for solving a integer optimisation problem. The basic idea behind this methode is to treat your linear programm not as usual as an integer linear programm. Instead you should consider it as a LP-Relaxation and add further inequalities untill an integer solution is found.

Approach

At the beginning you use the simplex algorythm to find the continous optimum. Afterwards you check your solution for integer. If not, use cutting planes. Otherwise you have already reached the optimal solution. You have to start with the cutting plane algorythm in the row with the greatest non integer part

Using the simplex method to solve a linear program produces a set of equations of the form
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_i+\sum a_{ij}NBV_j = b_i
()

Seperate both and into integer fraction and the rest :

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

)

(Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_i < 1

)

construct the equation () to

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_i+\sum g_{ij}NBV_j -g_i= f_i-\sum f_{ij}NBV_j


Use a new slack variable to obtain a cutting plane:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_i'-\sum f_{ij}NBV_j -g_i= -f_i


Example

max
s.t. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_{1}+x_{2} \leq 10
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}+x_{2} \leq 5
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} \leq 4
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\geq0
integer
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\geq0
integer


Now we transfer it into an minimum problem

min Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}-2x_{2}
s.t. Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_{1}+x_{2} \leq 10
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -x_{1}+x_{2} \leq 5
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1} \leq 4
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{1}\geq0
integer
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_{2}\geq0
integer


The correspondending Tableau is:

Initial tableau
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1 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.): -1


Now we use the Simplex Algorythm.
Pivot operation leads to:

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.): -1
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -1


2. Iteration

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{3}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{3}


We reached the minimum.

, , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c^Tx = -15

The objective function is integer, but the solution not. We need to import a new restriction.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{1}{3}x_1 + \frac{2}{3}x_2\geq \frac{2}{3}


as result we get a new Tableau:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{3}
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{1}{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}


the final simplex tableau:

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


we reached the optimal solution:

, , Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): c^Tx = -14


As you can see we found the integer solution.

Reference

Schnittebenenverfahen von Gomory
Analytic Center Cutting-Plane Method

Authors

Joshua Müller
Björn Linse
Kim Brill

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Integer_linear_optimization:_Cutting_Planes_4&oldid=4433“