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

Version vom 27. Juni 2013, 18:14 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.