On the mixed set covering, packing and partitioning polytope
Publication in refereed journal


Times Cited
Altmetrics Information
.

Other information
AbstractWe study the polyhedral structure of the mixed set covering, packing and partitioning problem, which has drawn little attention in the literature but has many real-life applications. By considering the “interactions” between the different types of edges of an induced graph, we develop new classes of valid inequalities. In particular, we derive the (generalized) mixed odd hole inequalities, and identify sufficient conditions for them to be facet-defining. In the special case when the induced graph is a mixed odd hole, the inclusion of this new facet-defining inequality provide a complete polyhedral characterization of the mixed odd hole polytope. Computational experiments indicate that these new valid inequalities may be effective in reducing the computation time in solving mixed covering and packing problems.
All Author(s) ListKuo Y.-H., Leung J.M.Y.
Journal nameDiscrete Optimization
Year2016
Month11
Day1
Volume Number22
PublisherElsevier BV
Place of PublicationNetherlands
Pages162 - 182
ISSN1572-5286
LanguagesEnglish-United Kingdom
KeywordsFacet-defining inequalities, Odd hole, Polyhedral structure, Set covering, Set packing, Set partitioning

Last updated on 2020-22-10 at 02:32