Polyhedral proof methods in combinatorial optimization
type: Item
instance of: scholarly article
title: Polyhedral proof methods in combinatorial optimization
zbMATH Open document ID: 0602.90111
DOI: 10.1016/0166-218X(86)90056-9
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: Often a combinatorial optimization problem can be formulated as an integer linear programming problem max\(\{\) cx\(| ax\leq b\), x integral\(\}\). Polyhedral methods in combinatorial optimization try to solve these problems by applying linear programming methods. For polynomial solvable problems one can often give an integer programming formulation for which the LP-relaxation gives an integral solution. The paper concentrates on methods of proving that the LP-relaxations give an integral solution; this often leads to interesting min-max relations. Polyhedral methods can also be used in cutting plane methods for NP-hard problems, but these are only mentioned briefly. The paper uses concepts such as LP-duality, total unimodularity, totally dual integrality, blocking and anti-blocking polyhedra. Many examples are given to illustrate the methods. These examples include the optimum branching theorem, the matching polytope; the max-flow min cut theorem, the Frobenius-König theorem, the Lucchesi-Younger theorem and the perfect graph theorem. The paper concludes with some remarks on cutting planes.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3972646
zbMATH Keywords: integer linear programming
zbMATH Keywords: LP-relaxations
zbMATH Keywords: total unimodularity
zbMATH Keywords: totally dual integrality
zbMATH Keywords: blocking
zbMATH Keywords: anti-blocking polyhedra
zbMATH Keywords: optimum branching
zbMATH Keywords: matching polytope
zbMATH Keywords: max-flow min cut theorem
zbMATH Keywords: cutting planes
MaRDI profile type: Publication
cites work: Edmonds polytopes and a hierarchy of combinatorial problems
cites work: On certain polytopes associated with graphs
cites work: Q5808754
cites work: A decomposition theorem for partially ordered sets
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Optimum branchings
cites work: Q4149476
cites work: Maximal Flow Through a Network
cites work: How to make a digraph strongly connected
cites work: Q5620998
cites work: Blocking and anti-blocking pairs of polyhedra
cites work: Anti-blocking polyhedra
cites work: Packing rooted directed cuts in a weighted directed graph
cites work: Q5722271
cites work: Outline of an algorithm for integer solutions to linear programs
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Q3714900
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: A generalization of max flow—min cut
cites work: Q3236252
cites work: Local Unimodularity in the Matching Polytope
cites work: On Linear Characterizations of Combinatorial Optimization Problems
cites work: Normal hypergraphs and the perfect graph conjecture
cites work: On two minimax theorems in graph
cites work: Q4132259
cites work: Graph Theory and Integer Programming
cites work: A Minimax Theorem for Directed Graphs
cites work: Q5817856
cites work: Odd Minimum Cut-Sets and b-Matchings
cites work: Q4739657
cites work: Q3682240
cites work: On Cutting Planes
cites work: Q3330973
cites work: Q3818127
cites work: Decomposition of regular matroids
cites work: Finding optimum branchings
cites work: Elementare Theorie der konvexen Polyeder
author: Alexander Schrijver
description: scientific article; zbMATH DE number 3972646