In cutting plane methods, the question of how to generate the “best possible” set of cuts is both central and crucial. We propose a lexicographic multi-objective cutting plane generation scheme that generates, among all the maximally violated valid inequalities of a given family, an inequality that is undominated and maximally diverse w.r.t. the cuts that were previously found. By optimizing a diversity measure, we introduce a form of coordination between successive cuts. Our focus is on valid inequalities with 0-1 coefficients in the left-hand side and a constant right-hand side, which encompasses several families of valid inequalities. As cut diversity measure, we consider an aggregate of the 1-norm distances w.r.t. the normal vectors of the previous cuts. In this case, our lexicographic multi-objective separation problem reduces to the standard separation problem with diff erent values for the objective function coefficients. The impact of our coordinated cutting plane generation scheme is assessed in a pure cutting plane setting when separating Stable Set and Cut Set inequalities for, respectively, the Max Clique and Min Steiner Tree problems. Compared to the standard separation of undominated maximally violated cuts, we close the same fraction of the duality gap in a considerably smaller number of rounds and cuts. The potential of our scheme is also indicated by the results obtained in a cut-and-branch setting for Max Clique, where cut coordination allows for a substantial reduction, on average, of the number of branch-and-bound nodes.
Citation
Please cite as: E. Amaldi, S. Coniglio, S. Gualandi: Coordinated cutting plane generation via multi-objective separation. Mathematical Programming A. pp 1-24 (2012). DOI 10.1007/s10107-012-0596-x