Premium
Polyhedral techniques in combinatorial optimization II: applications and computations
Author(s) -
Aardal K.,
Van Hoesel C. P. M.
Publication year - 1999
Publication title -
statistica neerlandica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.52
H-Index - 39
eISSN - 1467-9574
pISSN - 0039-0402
DOI - 10.1111/1467-9574.00104
Subject(s) - cutting plane method , convex hull , linear programming relaxation , polyhedron , linear programming , mathematical optimization , relaxation (psychology) , integer programming , mathematics , combinatorial optimization , computation , branch and cut , hull , regular polygon , computer science , algorithm , combinatorics , psychology , social psychology , geometry , marine engineering , engineering
The polyhedral approach is one of the most powerful techniques available for solving hard combinatorial optimization problems. The main idea behind the technique is to consider the linear relaxation of the integer combinatorial optimization problem, and try to iteratively strengthen the linear formulation by adding violated strong valid inequalities , i.e., inequalities that are violated by the current fractional solution but satisfied by all feasible solutions, and that define high‐dimensional faces, preferably facets, of the convex hull of feasible solutions. If we have the complete description of the convex hull of feasible solutions at hand all extreme points of this formulation are integral, which means that we can solve the problem as a linear programming problem. Linear programming problems are known to be computationally easy. In Part 1 of this article we discuss theoretical aspects of polyhedral techniques. Here we will mainly concentrate on the computational aspects. In particular we discuss how polyhedral results are used in cutting plane algorithms. We also consider a few theoretical issues not treated in Part 1, such as techniques for proving that a certain inequality is facet defining, and that a certain linear formulation gives a complete description of the convex hull of feasible solutions. We conclude the article by briefly mentioning some alternative techniques for solving combinatorial optimization problems.