New facets for the consecutive ones polytope

Luigi De Giovanni(luigimath.unipd.it)
Laura Brentegani(brentegani.laurayahoo.it)
Mattia Festa(oddworldheregmail.com)

Abstract: A 0/1 matrix has the Consecutive Ones Property if a permutation of its columns exists such that the ones appear consecutively in each row. In many applications, one has to find a matrix having the consecutive ones property and optimizing a linear objective function. For this problem, literature proposes, among other approaches, an Integer Linear Programming formulation, based on Tucker characterization and on some classes of facet defining inequalities introduced by Oswald and Reinelt. We propose a method based on asteroidal triple free-graphs to derive new and more general classes of facets, and we embed them in a branch-and-cut algorithm applied to random and real instances.

Keywords: Consecutive Ones Problem, Facets, Branch-and-Cut

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: Technical report, Dipartimento di Matematica 'Tullio Levi-Civita', Università degli Studi di Padova

Download: [PDF]

Entry Submitted: 06/23/2018
Entry Accepted: 06/24/2018
Entry Last Modified: 06/23/2018

Modify/Update this entry