Polyhedral Techniques in Combinatorial Optimization

摘要

The basic idea behind polyhedral techniques is to derive a good liner formulationof the set of solutions by identifying linear inequalities that can be proved to be necessary in the description of the convex hull of feasible solutions. The purpose of this article is to give an overview of the developments in polyhedral theory, starting with the pioneering work by Dantzig, Fulkerson and Johnson on the traveling salesman problem, and by Gomory on integer programming. The authors also discuss several computational aspects and implementation issues related to the use of polyhedral methods.