Integer linear optimization: Cutting Planes 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
(→Approach) |
(→Example) |
||
(24 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
− | |||
− | |||
== Idea == | == Idea == | ||
− | The Idea of the Cutting Plane is to add Restrictions (the Cutting Planes) to contract the solution space more and more to get | + | 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 == | == Approach == | ||
First of all you should divide your restrictions trough the greates common factor. | First of all you should divide your restrictions trough the greates common factor. | ||
− | :: Example: | + | :: Example: <math>6*x_1 + 15*x_2 <= 120</math> | gcf = 3 |
− | :: <math>\Rightarrow</math> | + | :: <math>\Rightarrow</math><math>2*x_1 + 5*x_2 <= 40</math> |
:(1) You search for the continous Optimum with the Simplex Algorithm. If your solution is integer you are finished. | :(1) You search for the continous Optimum with the Simplex Algorithm. If your solution is integer you are finished. | ||
Zeile 20: | Zeile 17: | ||
::::<math>a_{ij} = g_{ij} + f_{ij}</math> <math>\qquad</math> (<math>0 \leq f_{ij} < 1</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>) | ::::<math>b_i = g_i + f_i</math> <math>\qquad</math> (<math>0 \leq f_i < 1</math>) | ||
+ | ::We convert r to: | ||
+ | :::<math>BV_r+\sum ((f_{rj} + g_{rj})*NBV_j) = g_r + f_r</math> | ||
+ | ::Take the integer parts on the right side of the formula | ||
+ | :::<math>\sum(f_{rj}*NBV_j) = g_r + f_r - \sum(g_{rj}*NBV_j)-BV_r</math> | ||
+ | ::Merge the integer parts into the slack variable <math>y_{neu}</math> | ||
+ | :::<math>y_{neu} = g_r - \sum(g_{rj}*NBV_j)-BV_r</math> | ||
+ | :: | ||
+ | :::<math>\Rightarrow</math><math>\sum(f_{rj}*NBV_j) = f_r + y_{neu}</math> | ||
+ | ::Now we have to constract our new formula in the same form like the others. You have to consider, that <math>y_{neu}</math> cannot have an algebraic sign. | ||
+ | :::<math>y_{neu} - (f_{rj}*NBV_j) = -f_r</math> | ||
+ | ::This is now our Cutting Plane. | ||
+ | |||
+ | == Example == | ||
+ | |||
+ | :::<math>max G = 2*x_1 + 3*x_2</math> | ||
+ | ::Subject to | ||
+ | :::<math>6*x_1 + 15*x_2 <= 120</math> | ||
+ | :::<math>14*x_1 + 6*x_2 <= 141</math> | ||
+ | :: | ||
+ | :(0) if possible: round | ||
+ | :::<math>6*x_1 + 15*x_2 <= 120</math> |:3 | ||
+ | :::<math>\Rightarrow</math><math>2*x_1 + 5*x_2 <= 40</math> | ||
+ | :: | ||
+ | :::<math>14*x_1 + 6*x_2 <= 141</math> |:2 | ||
+ | :::<math>\Rightarrow</math><math>7*x_1 + 3*x_2 <= 70</math> | ||
+ | :: | ||
+ | :(1) Create the Simplex-Tableau and find the continuous optimum with the Simplex-Algorithm: | ||
+ | |||
+ | :::{| 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>G</math> || <math>-2</math> || <math>-3</math> || <math>0</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_1</math> || <math>2</math> || <math>-5</math> || <math>40</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_2</math> || <math>7</math> || style="background:#fedcba" | <math>3</math> || <math>10</math> | ||
+ | |} | ||
+ | |||
+ | :After one iteration we get the first optimal solution. But it's not integer yet. | ||
+ | :::{| class="wikitable float-right" style="text-align:center" | ||
+ | |+ Optimal solution (non integer) | ||
+ | |- style="height: 50px;" | ||
+ | | scope="col" width="50" | || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>y_2</math> || scope="col" width="50" | | ||
+ | |- style="height: 50px;" | ||
+ | | <math>G</math> || <math>5</math> || <math>1</math> || <math>70</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_1</math> || <math>\frac{41}{3}</math> || <math>\frac{5}{3}</math> || <math>\frac{470}{3}</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>x_2</math> || <math>\frac{7}{3}</math> || <math>\frac{1}{3}</math> || <math>\frac{70}{3}</math> | ||
+ | |} | ||
+ | |||
+ | :Now we have to insert the Cutting Plane. We choose <math>y_1</math> because it has the greatest non integer part. | ||
+ | :: Source row: | ||
+ | ::<math>y_1 + \frac{41}{3} * x_1 + \frac{5}{3} * y_2 =\frac{470}{3}</math> | ||
+ | ::Divided: | ||
+ | ::<math>y_1 + (13 + \frac{2}{3}) * x_1 + (1 + \frac{2}{3}) * y_2 =156 + \frac{2}{3}</math> | ||
+ | ::with slack variable: | ||
+ | ::<math>y_1 + \frac{2}{3} * x_1 + \frac{2}{3} * y_2 =\frac{2}{3} + y_3</math> | ||
+ | ::Restriction for the Simplex_Tableau: | ||
+ | ::<math>y_3 - \frac{2}{3} * x_1 - \frac{2}{3} * y_2 = -\frac{2}{3}</math> | ||
+ | |||
+ | :::{| class="wikitable float-right" style="text-align:center" | ||
+ | |+ Extended Simplex Tableau | ||
+ | |- style="height: 50px;" | ||
+ | | scope="col" width="50" | || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | <math>y_2</math> || scope="col" width="50" | | ||
+ | |- style="height: 50px;" | ||
+ | | <math>G</math> || <math>5</math> || <math>1</math> || <math>70</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_1</math> || <math>\frac{41}{3}</math> || <math>\frac{5}{3}</math> || <math>\frac{470}{3}</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>x_2</math> || <math>\frac{7}{3}</math> || <math>\frac{1}{3}</math> || <math>\frac{70}{3}</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_3</math> || <math>-\frac{2}{3}</math> || <math>-\frac{2}{3}</math> || <math>-\frac{2}{3}</math> | ||
+ | |} | ||
+ | |||
+ | ::After two further iterations we get the optimal integer solution: | ||
+ | |||
+ | :::{| class="wikitable float-right" style="text-align:center" | ||
+ | |+ Optimal Solution (Integer) | ||
+ | |- style="height: 50px;" | ||
+ | | scope="col" width="50" | || scope="col" width="50" | <math>y_3</math> || scope="col" width="50" | <math>x_1</math> || scope="col" width="50" | | ||
+ | |- style="height: 50px;" | ||
+ | | <math>G</math> || <math>\frac{3}{2}</math> || <math>4</math> || <math>69</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_1</math> || <math>\frac{5}{2}</math> || <math>12</math> || <math>155</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>x_2</math> || <math>\frac{1}{2}</math> || <math>2</math> || <math>23</math> | ||
+ | |- style="height: 50px;" | ||
+ | | <math>y_2</math> || <math>-\frac{3}{2}</math> || <math>1</math> || <math>1</math> | ||
+ | |} | ||
+ | |||
+ | ::The solution is integer an optimal. | ||
+ | |||
+ | == References == | ||
+ | [http://en.wikipedia.org/wiki/Cutting-plane_method] Wikipedia Article about Cutting Planes |
Aktuelle Version vom 21. Juni 2013, 17:32 Uhr
Inhaltsverzeichnis
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 and into the integer part and the rest (non integer) .
- (Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0 \leq f_{ij} < 1
- Converting r to: You have to break all and into the integer part and the rest (non integer) .
)
- (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
- We convert r to:
- 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
- Take the integer parts on the right side of the formula
- Merge the integer parts into the slack variable
- Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{neu} = g_r - \sum(g_{rj}*NBV_j)-BV_r
- Merge the integer parts into the slack variable
-
- 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 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
- Now we have to constract our new formula in the same form like the others. You have to consider, that cannot have an algebraic sign.
- 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
- Subject to
- 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 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 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -5
- After one iteration we get the first optimal solution. But it's not integer yet.
Optimal solution (non integer)
- Now we have to insert the Cutting Plane. We choose 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 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) Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -\frac{3}{2}
- The solution is integer an optimal.
References
[1] Wikipedia Article about Cutting Planes