- | ||||
|
![]()
|
New facets for the consecutive ones polytope
Luigi De Giovanni(luigi 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 Modify/Update this entry | ||
Visitors | Authors | More about us | Links | |
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository
|
Submit Update Policies |
Coordinator's Board Classification Scheme Credits Give us feedback |
Optimization Journals, Sites, Societies | |
![]() |