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