Primal cutting plane algorithms revisited |
| |
Authors: | Adam N. Letchford Andrea Lodi |
| |
Affiliation: | (1) Department of Management Science, Lancaster University, Lancaster LA1 4YW, England (e-mail: A.N.Letchford@lancaster.ac.uk), GB;(2) D.E.I.S., University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy (e-mail: alodi@deis.unibo.it), IT |
| |
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. |
| |
Keywords: | : integer programming cutting planes primal algorithms |
本文献已被 SpringerLink 等数据库收录! |
|