Discrete relaxations of combinatorial programs

DOI10.1016/S0166-218X(00)00307-3MaRDI QIDQ5946814zbMATH OpenFDO

Authors Ralf Borndörfer, Robert Weismantel

Publication date 2001

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00307-3

zbMATH Keywords

Integer programmingCutting planesPolyhedral combinatorics

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Integer programming (90C10)

Recommendations

• Set packing relaxations of some integer programs
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Relaxations of discrete sets with semicontinuous variables
• The matching relaxation for a class of generalized set partitioning problems
• scientific article; zbMATH DE number 2159269

Cites work

• scientific article; zbMATH DE number 1263275 (Why is no real title available?)
• (1,k)-configurations and facets for packing problems
• A note on node packing polytopes on hypergraphs
• An analytical comparison of different formulations of the travelling salesman problem
• Faces for a linear inequality in 0–1 variables
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• Geometric algorithms and combinatorial optimization
• On certain polytopes associated with graphs
• On the 0,1 facets of the set covering polytope
• On the \(0/1\) knapsack polytope
• On the facial structure of set packing polyhedra
• Set packing relaxations of some integer programs
• The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph
• The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets
• The Steiner tree problem. II: Properties and classes of facets
• The perfectly matchable subgraph polytope of an arbitrary graph
• Valid inequalities for 0-1 knapsacks and MIPs with generalised upper bound constraints
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts

Cited in

(5)

• Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
• McCormick-Based Relaxations of Algorithms
• The matching relaxation for a class of generalized set partitioning problems
• Set packing relaxations of some integer programs
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems

This page was built for publication: Discrete relaxations of combinatorial programs

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