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)

Full work available at URL https://doi.org/10.1007/S101070000154

zbMATH Keywords

acyclic digraphscombinatorial optimizationcutscutting planesinteger programminglinear orderingsmulticutspolyhedral combinatoricsset 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

(18)

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

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)