Optimization Online


Coordinated cutting plane generation via multi-objective separation

Edoardo Amaldi (amaldi***at***elet,polimi.it)
Stefano Coniglio (stefano.coniglio***at***gmail.com)
Stefano Gualandi (stefano.gualandi***at***gmail.com)

Abstract: 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.

Keywords: Cutting plane methods, Coordinated cutting planes generation, Multi-objective separation

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Other Topics (Multi-Criteria Optimization )

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

Download: [PDF]

Entry Submitted: 06/23/2011
Entry Accepted: 06/23/2011
Entry Last Modified: 09/16/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society