Integer linear optimization: Cutting Planes 4: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Kbrill (Diskussion | Beiträge) (→Reference) |
Kbrill (Diskussion | Beiträge) (→Authors) |
||
Zeile 127: | Zeile 127: | ||
===Authors=== | ===Authors=== | ||
− | Joshua Müller | + | Joshua Müller<br> |
− | Björn Linse | + | Björn Linse<br> |
Kim Brill | Kim Brill |
Aktuelle Version vom 26. Juni 2013, 14:27 Uhr
Inhaltsverzeichnis
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:
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