Integer linear optimization: Cutting Planes 5
Inhaltsverzeichnis
Introduction
There is a large amount of problems within linear and nonlinear programming problems. The simplex-method is one of the most used opportunities to solve such linear programming-problems. But there is a big lack of methods which concentrate specially on an integer solution. The simplex-method mostly finds the optimal solution in a non-integer variable. In industry there is often a decision between different options needed, which only can appear in integer form. So if a manager for example needs to decide between different investments objects, he can’t choose parts from a few of them to use the complete budget. He needs a method, which finds an integer solution.
In the common literature there are a few methods for this described problem. For example there are a heuristic-method, a decision-tree-method or a branch and bound etc.
Cutting-Plane-Method
Ralph E. Gromory (1958) was the first, who tried to find a method which only search for integer solutions. He created the cutting-plane-method.
Later he improved his own cutting-plane method, so there is a need to different between his first and his second cutting-plane-method.
Adding this additional restriction into the tableu:
In the following we only present the first method, which assumes the solution from the simplex-method and extend it to an integer-solution by adding more restrictions.
His later and second method finds a direct way for an integer solution. The need for his direct method was given by the problem that his first method may interrupt by not finding an optimal integer solution.
The first Gromory-cutting-plane-method starts with the previously calculated optimal simplex-method solution. If this solution is an integer solution the problem is solved and the algorithm will end there. If it is not, the cutting-plane-method starts here to restrict the problem. The additional restriction will restrain the problem, so that the optimal non-integer solution isn’t valid anymore. It “cuts” the solution away from the possible solution space. If the next step won’t find an integer solution the algorithm will start again with further cut. The cutting-plane-method stops when an optimal solution is found or when it is proved that the problem haven’t an integer solution.
Example
To show detailed the solution way from Gromorys first cutting-plane-method we will introduce an example:
The small company Born GmbH wants to maximize their profit. They can produce two different articles, article 1 and article 2.
For producing, the company are able to use the two different types of machine, machine A and machine B. Qualified workers are limited in a little amount. The following table will show the problem in a structured way.
The values in the middle will represent the utilization from the machines through the articles in hours per piece (h/p). So you need to produce one piece of article 1 five hours of machine A, one hour of machine B and six hours assembly work.
This leads directly to the known simplex initial tableau. Shown in the following table:
The first pivot element is marked yellow (here it is five). The pursuited aim is to maximize the profit in the top right corner. But with the restriction to accept only integer solutions. This restriction for integer variables includes automatically an integer profit and only integer slack variables.
To get the linear solution through the cutting-plane-method we first need the optimal nonlinear solution. The common used simnplex-method leads to the optimal solution in the following table.
You can see, that the maximum profit is 4350 Euro and it is reachable, when the Born Gmbh would produce 1,5 units of article 1 and 4,5 units of article 2. There are still 4,5 units not used capacity from machine A.
This solution is not integer. With the help by Gomorys` cutting-plane-method it is possible to transferm the tableu into the optimal integer solution. At first we need to cut the non integer restriction as a possible point. To erase this point out of the solution space we create an additional restriction. So a cutting plane will restrict the solution space.
To create a cutting plane, we transform the equations. In our example we choose as our first equation the row.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): X_{2} - \frac{1}{4}Y_{3} + \frac{1}{4}Y_{2} = 4\frac{1}{2}
Now it is important to seperate the integer-coefficients from the fractions:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): X_{2} + (-1 + \frac{3}{4})Y_{3} + (0 + \frac{1}{4})Y_{2} = (4 + \frac{1}{2})
After transferring the integers to the right side we will get the following equation:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{3}{4}Y_{3} + \frac{1}{4}Y_{2} = \frac{1}{2} + (4 - X_{2} - Y_{3} - 0Y_{2})
Because we can assume that all variables are integers, the clip on the right side must be in integer form, too. So we can wright as well:
If we substitute the integer with a new variable we would reach the following equation:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Y_{A} - \frac{3}{4}Y_{3} - \frac{1}{4}Y_{2} = -\frac{1}{2}
Adding this restriction to the tableu:
To choose the pivot we use the known binary simplex method:
, because of we choose Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): - \frac{1}{4}
as the next pivot, which is already marked yellow.
Of course we iterate once more by the known simplex method, which will lead to the following tableu:
Now we see that we found the optimal soultion and it is only with integer variables. We can stopp here with this result.
Finally we can advise Born GmbH to produce two units of article 1 and four units of article 2. The company can so reach a profit of 4200 Euro, and would still have an unused capacity of machine A with six unit and 2 units of machine B.
Sources
Müller-Merbach, Operations Research, 3 edition, Munich 1973
Wofgang Domschke, Einführung in Operations Research, Springer Verlag
Authors
Thomas Wagemann
Marcel Hotzelt
Sandra Born
