| Abstract: | In Combinatorial Optimization, one is frequently faced with linear programming (LP) problems with exponentially many constraints, which can be solved either using separation or what we call compact optimization. The former technique relies on a separation algorithm, which, given a fractional solution, tries to produce a violated valid inequality. Compact optimization relies on describing the feasible region of the LP by a polynomial number of constraints, in a higher dimensional space. A commonly held belief is that compact optimization does not perform as well as separation in practice. In this paper, we report on an application in which compact optimization does in fact largely outperform separation. The problem arises in structural proteomics, and concerns the comparison of 3-dimensional protein folds. Our computational results show that compact optimization achieves an improvement of up to two orders of magnitude over separation. We discuss some reasons why compact optimization works in this case but not, e.g., for the LP relaxation of the TSP.Received: April 2003, Revised: January 2004, MSC classification: 65K05, 90C05, 90C90Thanks to Arie Tamir for pointing out to us many relevant references, and to Brian Walenz and Giulio Zanetti for helpful discussions. We thank two anonymous referees for their suggestions which improved this paper considerably. The second author wishes to thank Sandia National Labs, Albuquerque, NM, and the Mathematical Biosciences Institute, Columbus, OH, for their hospitality. Sandia is a multiprogram laboratory, operated by Sandia Corporation, a Lockhead Martin Company, for the United States Department of Energy under contract DE-AC04-94AL85000. |
