|
Mixed-integer rounding cutting planes for integer programming problems| old_uid | 2083 |
|---|
| title | Mixed-integer rounding cutting planes for integer programming problems |
|---|
| start_date | 2007/01/19 |
|---|
| schedule | 11h |
|---|
| online | no |
|---|
| summary | Cutting planes, or linear inequalities satisfied by all integral points in a polyhedron, are very useful in solving integer programming problems. In this talk, we discuss two aspects of the most important class of general cutting planes, namely mixed-integer rounding (MIR) cutting planes. We describe recent results on the separation problem for MIR cutting planes - given a point contained in a polyhedron, test if there exists an MIR cutting plane violated by this point or prove that none exists - and discuss their use in solving integer programs. This is joint work with Oktay Gunluk, and Andrea Lodi. An important aspect of MIR cuts is the following: any integer program, and therefore any problem in NP, can be solved by generating a sequence of MIR cuts. We show that exponentially many MIR cuts are needed in the worst case. |
|---|
| oncancel | ANNULE |
|---|
| responsibles | Carlo, Bardet, Cottrell |
|---|
| |
|