Polyhedral proof methods in combinatorial optimization

DOI10.1016/0166-218X(86)90056-9zbMath0602.90111MaRDI QIDQ1082268

Alexander Schrijver

Publication date: 1986

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

zbMATH Keywords

integer linear programmingcutting planesblockingtotal unimodularitymatching polytopeLP-relaxationsanti-blocking polyhedramax-flow min cut theoremoptimum branchingtotally dual integrality

Mathematics Subject Classification ID

Integer programming (90C10) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

Some new results on generalized additive games, Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming, Fixed interval scheduling: models, applications, computational complexity and algorithms, Irreducible decomposition of powers of edge ideals, A note on the problem of \(r\) disjoint \((s, t)\)-cuts and some related issues, Minimum weighted clique cover on claw‐free perfect graphs, Circular zero-sum \(r\)-flows of regular graphs, Generic global rigidity of body-hinge frameworks, Colorful linear programming, Nash equilibrium, and pivots, A branch-price-and-cut algorithm for the capacitated multiple vehicle traveling purchaser problem with unitary demand, Some efficiently solvable problems over integer partition polytopes, On the transportation problem with market choice, On line sum optimization, Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion, On matching numbers of tree and bipartite degree sequences, An incentive compatible, efficient market for air traffic flow management, Social exchange networks with distant bargaining, Uncapacitated flow-based extended formulations, Assortment optimisation under a general discrete choice model: a tight analysis of revenue-ordered assortments, Computing valuations of the Dieudonné determinants, Normality criteria for monomial ideals, Unions of perfect matchings in cubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition of regular matroids
• How to make a digraph strongly connected
• The ellipsoid method and its consequences in combinatorial optimization
• On two minimax theorems in graph
• On certain polytopes associated with graphs
• Elementare Theorie der konvexen Polyeder
• Anti-blocking polyhedra
• Normal hypergraphs and the perfect graph conjecture
• Edmonds polytopes and a hierarchy of combinatorial problems
• A decomposition theorem for partially ordered sets
• Maximal Flow Through a Network
• Outline of an algorithm for integer solutions to linear programs
• On Cutting Planes
• Odd Minimum Cut-Sets and b-Matchings
• A generalization of max flow—min cut
• Finding optimum branchings
• A Minimax Theorem for Directed Graphs
• Local Unimodularity in the Matching Polytope
• Graph Theory and Integer Programming
• On Linear Characterizations of Combinatorial Optimization Problems
• Packing rooted directed cuts in a weighted directed graph
• Maximum matching and a polyhedron with 0,1-vertices
• Optimum branchings
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Blocking and anti-blocking pairs of polyhedra