Set packing relaxations of some integer programs

DOI10.1007/S101070000154MaRDI QIDQ1587935zbMATH OpenFDO

Authors Ralf Borndörfer, Robert Weismantel

Publication date 3 December 2000

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

combinatorial optimizationinteger programmingcutting planespolyhedral combinatoricscutslinear orderingsmulticutsacyclic digraphsset packing relaxationsset packings

Mathematics Subject Classification ID

Integer programming (90C10)

Recommendations

• Discrete relaxations of combinatorial programs
• Graph theoretic relaxations of set covering and set partitioning problems
• Node-Packing Problems with Integer Rounding Properties
• Tighter representations for set partitioning problems
• Computational Experience with Stable Set Relaxations

Cited in

(16)

• A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem
• A two-level graph partitioning problem arising in mobile wireless communications
• Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint
• On the combinatorial structure of the approval-voting polytope
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• Projection results for the \(k\)-partition problem
• Facets from gadgets
• A computational study of a cutting plane algorithm for university course timetabling
• Upper bounds on the average number of iterations for some algorithms of solving the set packing problem
• Node-Packing Problems with Integer Rounding Properties
• A combinatorial study of partial order polytopes
• Discrete relaxations of combinatorial programs
• Strengthened clique-family inequalities for the stable set polytope
• The biorder polytope
• On the mixed set covering, packing and partitioning polytope
• Facets of the linear ordering polytope: a unification for the fence family through weighted graphs

Describes a project that uses

Uses Software

• LOLIB

This page was built for publication: Set packing relaxations of some integer programs

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