Polyhedral proof methods in combinatorial optimization (Q1082268)

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.