Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6892498 | Computers & Operations Research | 2018 | 14 Pages |
Abstract
This paper focuses on the polyhedral study of the arc-based formulations for both problems. We prove that 3 classes of constraints are facet-defining for the CCMcP polytope, identify 4 new classes of constraints and prove their validity. We then prove that the non-negativity and the degree constraints are facet-defining for the CCCCP polytope. Even though we cannot expect to find a complete polyhedral description (CPD) of the CCMcP or the CCCCP, as both problems are NP-hard, any partial description is always interesting for both theoretical and computational purposes, since the wider the linear description, the less need for branching. A CPD is composed of facet-defining constraints, hence the major contribution of this paper is one step towards finding a CPD for the CCMcP and the CCCCP. We tested the strengths of the facet-defining constraints and new valid constraints on two sets of randomly generated data instances. We reported the numerical results and discussed future research directions.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Vicky Mak-Hau,