A 0/1 matrix has the Consecutive-Ones Property if a permutation of its columns makes the ones consecutive in every row. In many applications, one has to find an optimal matrix with this property, and literature proposes Integer Linear Programming formulations based on Tucker (1972) characterization and on classes of facet defining inequalities (Oswald and Reinelt, 2004). We propose a graph-based method to derive new classes of facets and we embed them in a branch-and-cut algorithm.
New Facets for the Consecutive Ones Polytope
Luigi De Giovanni;
2015
Abstract
A 0/1 matrix has the Consecutive-Ones Property if a permutation of its columns makes the ones consecutive in every row. In many applications, one has to find an optimal matrix with this property, and literature proposes Integer Linear Programming formulations based on Tucker (1972) characterization and on classes of facet defining inequalities (Oswald and Reinelt, 2004). We propose a graph-based method to derive new classes of facets and we embed them in a branch-and-cut algorithm.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
