Please use this identifier to cite or link to this item:
|Title:||Cutting plane methods for general integer programming|
|Citation:||Maths Technical Papers (Brunel University). June 1993, pp 1-27|
|Abstract:||Integer programming (IP) problems are difficult to solve due to the integer restrictions imposed on them. A technique for solving these problems is the cutting plane method. In this method, linear constraints are added to the associated linear programming (LP) problem until an integer optimal solution is found. These constraints cut off part of the LP solution space but do not eliminate any feasible integer solution. In this report algorithms for solving IP due to Gomory and to Dantzig are presented. Two other cutting plane approaches and two extensions to Gomory's algorithm are also discussed. Although these methods are mathematically elegant they are known to have slow convergence and an explosive storage requirement. As a result cutting planes are generally not computationally successful.|
|Appears in Collections:||Dept of Mathematics Research Papers|
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.