Anterior | Inicio | Siguiente

Polyhedral techniques for combinatorial optimization problems: A mini-course: Mourad Barou
In this mini-course, we introduce polyhedral techniques to solve combinatorial optimization problems.
Combinatorial optimization problems are defined, with examples. It is shown how these problems reduce to the solution of linear programs. In general, the system of inequalities is huge and not easy to characterize. However, for particular objective functions, a partial description is sometimes sufficient.
A cutting-plane algorithm is presented to find integer solutions to linear programs having a very big number of inequalities. This approach is base don solving separation problems that generate violated valid inequalities. It is applied to the máximum weight matching and máximum cut problems.