Optimization Online


Multi-Row Intersection Cuts based on the Infinity Norm

Alinson S. Xavier(axavier***at***anl.gov)
Ricardo Fukasawa(rfukasawa***at***uwaterloo.ca)
Laurent Poirrier(lpoirrier***at***uwaterloo.ca)

Abstract: When generating multi-row intersection cuts for Mixed-Integer Linear Optimization problems, an important practical question is deciding which intersection cuts to use. Even when restricted to cuts that are facet-defining for the corner relaxation, the number of potential candidates is still very large, specially for instances of large size. In this paper, we introduce a subset of intersection cuts based on the infinity norm that is very small, works for relaxations having arbitrary number of rows, and, unlike many subclasses studied in the literature, that takes into account the entire data from the simplex tableau. We describe an algorithm for generating these inequalities and run extensive computational experiments in order to evaluate their practical effectiveness in real-world instances. We conclude that this subset of inequalities yields, in terms of gap closure, around 50% of the benefits of using all valid inequalities for the corner relaxation simultaneously, but at a small fraction of the computational cost, and with a very small number of cuts.

Keywords: Mixed-Integer Linear Programming, Cutting Planes, Intersection Cuts

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 07/16/2019
Entry Accepted: 07/16/2019
Entry Last Modified: 07/16/2019

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