Polyhedral proof methods in combinatorial optimization

anti-blocking polyhedra blocking cutting planes integer linear programming LP-relaxations matching polytope max-flow min cut theorem optimum branching total unimodularity totally dual integrality

Mathematics Subject Classification ID

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

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.

Recommendations

Cites work

Cited in

(46)

This page was built for publication: Polyhedral proof methods in combinatorial optimization

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