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

Version vom 30. Juni 2013, 21:25 Uhr

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.

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 X1 row.

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