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

Aktuelle Version vom 1. Juli 2013, 12:24 Uhr

Idea

The cutting-plane method is an Algorithm for solving integer linear optimization problems. The basic idea of the cutting plane method is to look on the LP-Relaxations (without integrality) of the linear program instead of looking on the integer linear program. It tries to tighten gradually, by the Addition of further inequalities until a integer solution is found.

The cutting plane method was developed in the 1950´s by Delbert Ray Fulkerson, George Dantzig, Egon Balas and Ralph Gomory. It´s one of the standard-methods in the integer optimization and still a subject of current research.

Theory

The setting of the method is to apply the simplex method until the integer optimum is found.

If the optimum is not integer, a Cutting Plane gets blended in.

The row ${\displaystyle i}$ which is used for a Cutting Plane, is the row ${\displaystyle i}$ with the greatest fraction of ${\displaystyle b_{i}}$. We call it now the row ${\displaystyle c}$.

Our row ${\displaystyle c}$ now has the following form:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_{c}+\sum \left ( a_{cj}*NBV_{j} \right )=b_{c}

Now we have to split all ${\displaystyle a_{cj}}$ in the integer part ${\displaystyle g_{cj}}$ and the fraction part ${\displaystyle f_{cj}}$. We also split ${\displaystyle b_{c}}$ equivalent in ${\displaystyle g_{c}}$ and ${\displaystyle f_{c}}$. So we have:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): BV_{c}+\sum \left ( \left ( g_{cj}+f_{cj} \right )*NBV_{j} \right )=g_{c}+f_{c}

,with Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): a_{cj}=g_{cj}+f_{cj}\forall j, g_{cj}\leq a_{cj}
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0\leq f_{cj}\leq 1
and ${\displaystyle b_{c}=g_{c}+f_{c}}$, Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_{c}\leq b_{c}
and Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0\leq f_{c}

Now we bring the integer parts on the right side of the equation:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum \left ( f_{cj}*NBV_{j} \right )=f_{c}+g_{c}-BV_{c}-\sum \left ( g_{cj}*NBV_{j} \right )

In the next step we build a ne slack variable out of the integer parts:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{A}=g_{c}-BV_{c}-\sum \left ( g_{cj}*NBV_{j} \right )

So we got the following equation:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum \left ( f_{cj}*NBV_{j} \right )=f_{c}+y_{A}

We bring it in the same form like the other equations. That means that all parts which gets multiply by variables stay on the right side. The slack variable ${\displaystyle y_{A}}$ has a positive sign. We receive the line:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_{A}-\sum \left ( g_{cj}*NBV_{j} \right )=-f_{c}

This line gets blended in the simplex and we start from the beginning.

This Cutting plane cuts the solution space to that effect, that the continuous optimum is not longer part of it. To record it in the graphical solution, ${\displaystyle y_{A}}$ has to be express with the structure variable ${\displaystyle x}$.

Example

A typical example of cutting planes is to plan bowling alleys and tennis courts in a restricted area and with a restricted budget. It doesn't make sense to iterate with a 'normal' simplex method, because the solution wouldn't be integer. A half tennis court couldn't be used. It is only profitable if we build up a whole tennis court or bowling alley. So the cutting plane method helps us to find integer solutions without an easy round up of the coefficients.

Presentation of the problem

For each tennis court the marginal return is 50,000 Money Units (MU). For each bowling alley the marginal return is 20,000 MU.
We have a budget of 90,000 MU. One tennis court costs 20,000 MU whereas a bowling alley costs 5,000 MU. The region is famous for its excellent bowling players what leads to a strong lobby containing rich people. This people are willing to contribute 15,000 MU for each bowling alley.
The area contains of 3,100 square meters (SM). One tennis court has a space of 200 SM, each bowling area has a space of 800 SM

It is sought after a non-negative, integer quantity of bowling alleys and tennis courts, which maximizes the marginal return.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{objective function}{10000}:G(x_1, x_2)= 2x_1+5x_2 \rightarrow max!

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{budget}{10000}:2x_1-x_2 \le 9

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{area}{100}: 2x_1-8x_2 \le 31

Detailed solution process with explanation

Objective Function: ${\displaystyle max\;G=2x_{1}+5x_{2}}$
Restrictions:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1 - x_2 \le 9
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 2x_1 - 8x_2 \le 31
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1, x_2 \ge 0, integer

After introducing the slack variables ${\displaystyle y_{1}}$ and ${\displaystyle y_{2}}$ we can build the simplex tableau with equations.

Two Simplex iterations lead us from the initial tableau to the optimal solution depicted above. We must consider that this solution is optimal but not integer. Now we have to determine the greatest fraction of the RHS. Here this is given by ${\displaystyle {\frac {13}{18}}}$. Also the fraction of the objective function can be chosen if this would be the greatest! After that we construe an artificial restriction by separating the fractions of the coefficients from integer parts in the equation with the greatest fraction. It is important that the fractions are still positive before introducing a slack variable for the integer parts.

${\displaystyle x_{1}+{\tfrac {4}{9}}y_{1}+{\tfrac {1}{18}}y_{2}=5{\tfrac {13}{18}}}$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow x_1 + (0 + \tfrac{4}{9})y_1 + (0+ \tfrac{1}{18})y_2 = 5 + \tfrac{13}{18}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow \tfrac{4}{9}y_1 + \tfrac{1}{18}y_2 = \tfrac{13}{18} + (5-x_1-0y_1-0y_2)

For the term which contains only integer coefficients a new slack variable will be introduced and a new restriction is built.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  y_A - \frac{4}{9}y_1 - \frac{1}{18}y_2 = -\frac{13}{18}

To determine the 1st cutting plane we have to insert the values of the variables in the initial problem in the new restriction.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_A - \tfrac{4}{9}y_1 - \tfrac{1}{18}y_2 = -\tfrac{13}{18}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_A -\tfrac{4}{9}(-2x_1+x_2+9) - \tfrac{1}{18}(-2x_1-8x_2+31)= -\tfrac{13}{18}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_A +\tfrac{8}{9}x_1-\tfrac{4}{9}x_2-4+\tfrac{1}{9}x_1+\tfrac{4}{9}x_2-\tfrac{31}{18}=-\tfrac{13}{18}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_A + x_1 =5

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

Now we have to add the new restriction to the 1st optimal solution. The new pivot element is be chosen by the dual simplex method and so it has to be the smallest negative quotient of the objective function coefficient and the corresponding element in the row of the new restriction. After that the iteration is equal to the 'normal' simplex method.

In the second optimal solution we can see that there are two greatest fractions. If we use both greatest fractions once we see that both lead to the same 2nd restriction. The bottom line is that it is equal which one we use.

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow x_2+(-1+\tfrac{3}{4})y_A+(0+\tfrac{1}{8})y_2=2+\tfrac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow \tfrac{3}{4}y_A+\tfrac{1}{8}y_2=\tfrac{5}{8}+(2-x_2+y_A-0y_2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_B-\frac{3}{4}y_A-\frac{1}{8}y_2=-\frac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_1-\tfrac{9}{4}y_A+\tfrac{1}{8}y_2=1\tfrac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_1+(-3+\tfrac{3}{4})y_A+(0+\tfrac{1}{8})y_2=1+\tfrac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow \tfrac{3}{4}y_A+\tfrac{1}{8}y_2=\tfrac{5}{8}+(1-y_1+3y_A-0y_2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_B-\frac{3}{4}y_A-\frac{1}{8}y_2=-\frac{5}{8}

The way of determining the 2nd cutting plane is analog to the 1st cutting plane.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_B-\tfrac{3}{4}y_A-\tfrac{1}{8}y_2=-\tfrac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_B-\tfrac{3}{4}(-x_1-5)-\tfrac{1}{8}(-2x_1-8x_2+31)=-\tfrac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_B+\tfrac{3}{4}x_1-\tfrac{15}{4}+\tfrac{1}{4}x_1+x_2-\tfrac{31}{8}=-\tfrac{5}{8}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow y_B+x_1+x_2=7

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

Now we add the 2nd restriction to the 2nd optimal solution and execute the dual simplex method for the new row. This leads us to the third optimal solution. Here we can see that ${\displaystyle y_{A}}$ comes back into the basis. In this case we can cancel the restriction.

With the third optimal solution we can construe a 3rd restriction, because the solution is not yet integer.

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow x_2+(-1+\tfrac{2}{3})y_B+(0+\tfrac{1}{6})y_2=2+\tfrac{5}{6}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow \tfrac{2}{3}y_B+\tfrac{1}{6}y_2=\tfrac{5}{6}+(2-x_2+y_B-0y_2)

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

The corresponding 3rd cutting plane can be determined in the same way as shown above.

${\displaystyle y_{C}+x_{1}+2x_{2}=9}$ respectively Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+2x_2 \le 9

Adding the third restriction to the third optimal solution lead us to the following tableau. ${\displaystyle y_{B}}$ comes to the basis and can be canceled.

With the fourth optimal solution we can construe a 4th restriction, because the solution is not yet integer.

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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow x_1+(0+2)y_C+(-1+\tfrac{1}{2})y_2=2+\tfrac{1}{2}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Leftrightarrow \tfrac{1}{2}y_2=\tfrac{1}{2}+(2-x_1-2y_C+y_2)

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

The corresponding 4th cutting plane can be determined in the same way as shown above.

${\displaystyle y_{D}+x_{1}+4x_{2}=15}$ respectively Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+4x_2 \le 15

Adding the fourth restriction to the fourth optimal solution lead us to the following tableau. This fifth tableau is optimal and integer.

With ${\displaystyle x_{1}=3}$ and ${\displaystyle x_{2}=3}$ a gain of ${\displaystyle G=21}$ is reached.

Sources and Authors

Müller-Merbach, Heiner: Operations Research - Methoden und Modelle zur Optimalplanung, 3.Auflage. München, Vahlen 1973.
Ellinger, Theodor; Beuermann, Günter; Leisten, Rainer: Operations Research - Eine Einführung, 6. Auflage. Heidelberg, Springer 2003.

Christian Böhm
Rüdiger Stoffel
Simon Ernst