Primal cutting plane algorithms revisited

Primal cutting plane algorithms revisited

0.00 Avg rating0 Votes
Article ID: iaor20032516
Country: Germany
Volume: 56
Issue: 1
Start Page Number: 67
End Page Number: 81
Publication Date: Jan 2002
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: ,
Keywords: programming: branch and bound, programming: fractional
Abstract:

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent. In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0–1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.

Reviews

Required fields are marked *. Your email address will not be published.