Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, December 1, 2008

Konrad-Zuse-Zentrum für Informationstechnik (ZIB)
Takustr. 7
14195 Berlin
room 2005

Lecture - 14:15

Laurence A. Wolsey, CORE, Université catholique de Louvain.

Valid Inequalities for General and Structured Mixed Integer Programs

We consider various ways to generate valid inequalities for general and structured mixed integer programs.

Starting with the general case, we present the standard disjunctive/mixed integer rounding/split cuts and some of their generalizations along with their strengths and weaknesses, as well as the alternative approach based upon generalizations of 0-1 cover inequalities. Then considering their more abstract representation as subadditive valid inequalities, we discuss some recent attempts to obtain stronger cuts by considering intersection cuts based on treating several rows simultaneously relating to much earlier work of Gomory and Johnson in the 1970s.

We then consider briefly work on the derivation of the convex hulls of simple mixed integer sets that arise as subproblems in network design and production planning models.

Colloquium - 16:00

Kati Wolter - ZIB Berlin

C-MIR Approach for Flow Cover Cuts

Different classes of valid inequalities for the 0-1 single node flow set have been studied in the literature and superadditive lifting procedures have been suggested to strengthen them. This includes generalized flow cover inequalities. Furthermore, it is well known that particular complemented mixed integer rounding (c-MIR) inequalities for certain mixed knapsack relaxations of the 0-1 single node flow set are at least as strong as special cases of generalized flow cover inequalities.

The branch-and-cut framework SCIP incorporates a cutting plane separator which utilizes this approach. In this talk, we introduce our separation heuristic for the so-called c-MIR flow cover cuts and present computational results concerning the impact of different aspects of the algorithm.

Letzte Aktualisierung: 28.11.2008