Monday, December 1, 2008
Konrad-Zuse-Zentrum für Informationstechnik (ZIB)
Takustr. 7
14195 Berlin
room 2005
Lecture - 14:15
Abstract:
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
Abstract:
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.