Please use this identifier to cite or link to this item:
Title: Cutting plane methods for general integer programming
Authors: Hamid, FA
Mitra, G
Darby-Dowman, K
Issue Date: 1993
Publisher: Brunel University
Citation: Maths Technical Papers (Brunel University). June 1993, pp 1-27
Series/Report no.: ;TR/04/93
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
Mathematical Sciences

Files in This Item:
File Description SizeFormat 
TR_04_93.pdf318.13 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.