On the mixed set covering, packing and partitioning polytope

DOI10.1016/J.DISOPT.2016.05.004MaRDI QIDQ1751181zbMATH OpenOpenAlexFDO

Authors Yong-Hong Kuo, Janny Leung

Publication date 24 May 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2016.05.004

zbMATH Keywords

facet-defining inequalitiesodd holepolyhedral structureset coveringset packingset partitioning

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the facial structure of the set covering polytope
• The mixed vertex packing problem.
• Projecting an extended formulation for mixed-integer covers on bipartite graphs
• The Continuous Mixing Polyhedron

Cites work

• A class of facet producing graphs for vertex packing polyhedra
• A generalization of antiwebs to independence systems and their canonical facets
• A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows
• Anti-blocking polyhedra
• Balanced matrices
• Blocking and anti-blocking pairs of polyhedra
• Combinatorial auction design
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Edmonds polytopes and a hierarchy of combinatorial problems
• scientific article; zbMATH DE number 3874956 (Why is no real title available?)
• scientific article; zbMATH DE number 1187141 (Why is no real title available?)
• scientific article; zbMATH DE number 3699703 (Why is no real title available?)
• scientific article; zbMATH DE number 3557519 (Why is no real title available?)
• scientific article; zbMATH DE number 3345048 (Why is no real title available?)
• Ideal 0, 1 matrices
• Lehman's forbidden minor characterization of ideal 0-1 matrices
• Lifting the facets of zero–one polytopes
• Matroids and the greedy algorithm
• Maximum matching and a polyhedron with 0,1-vertices
• Normal hypergraphs and the perfect graph conjecture
• Odd Hole Recognition in Graphs of Bounded Clique Size
• On certain polytopes associated with graphs
• On stable set polyhedra for K//(1,3)free graphs
• On the 0,1 facets of the set covering polytope
• On the complexity of testing for odd holes and induced odd paths
• On the facial structure of set packing polyhedra
• On the facial structure of the set covering polytope
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the width—length inequality
• Outline of an algorithm for integer solutions to linear programs
• Perfect zero–one matrices
• Properties of vertex packing and independence system polyhedra
• Recognizing Berge graphs
• Routing Trains Through Railway Stations: Model Formulation and Algorithms
• Set packing relaxations of some integer programs
• Set Partitioning: A survey
• Solving Airline Crew Scheduling Problems by Branch-and-Cut
• The iterated exponential integers
• The strong perfect graph theorem
• The train driver recovery problem-a set partitioning based model and solution method
• Wheel inequalities for stable set polytopes

Cited in

(6)

• The matching relaxation for a class of generalized set partitioning problems
• Set covering problem with conflict constraints
• Projecting an extended formulation for mixed-integer covers on bipartite graphs
• Finding a fully mixed cell in a mixed subdivision of polytopes
• Mixed-Integer Vertex Covers on Bipartite Graphs
• An exact algorithm for the minimum gap graph partitioning problem

This page was built for publication: On the mixed set covering, packing and partitioning polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751181)