A lift-and-project cutting plane algorithm for mixed 0-1 programs (Q2367913): Difference between revisions

The paper is organized as follows. An iterated lifting/projecting procedure for obtaining the convex hull of the feasible set of mixed 0-1 linear program is suggested. In each iteration, the set is relaxed through nonlinearization, then linearized by using a known technique for linearization of quadratic function in 0-1 variables and finally projected into the space of the original variables. The advantage of the procedure over existing ones is in the less number of variables needed in the lifting phase. It is then shown that the procedure is equivalent to the sequential convexification procedure for facial disjunctive programs, introduced by Balas earlier. The next section discuss cutting plane algorithms for mixed 0-1 programs based on sequential convexification procedure. A specialized cutting plane algorithm is proposed and its finiteness is proved. The last section is in fact an extensive and very informative report on the computational behaviour of the algorithm with the primary intention to analyze and compare cuts on their own merit.