Invited Session Mon.3.H 2032

Monday, 15:15 - 16:45 h, Room: H 2032

Cluster 11: Integer & mixed-integer programming [...]

Trends in mixed integer programming I


Chair: Andrea Lodi and Robert Weismantel



Monday, 15:15 - 15:40 h, Room: H 2032, Talk 1

Giacomo Nannicini
On the safety of Gomory cut generators

Coauthors: Gérard Cornuéjols, Francois Margot


Gomory mixed-integer cuts are one of the key components
in branch-and-cut solvers for mixed-integer linear programs. The
textbook formula for generating these cuts is not used directly in
open-source and commercial software due to the limited numerical
precision of the computations: Additional steps are performed to avoid
the generation of invalid cuts. This paper studies the impact of some
of these steps on the safety of Gomory mixed-integer cut
generators. As the generation of invalid cuts is a relatively rare
event, the experimental design for this study is particularly
important. We propose an experimental setup that allows statistically
significant comparisons of generators. We also propose a parameter
optimization algorithm and use it to find a Gomory mixed-integer cut generator that is as safe as a benchmark cut generator from a commercial solver even though it rejects much fewer cuts.



Monday, 15:45 - 16:10 h, Room: H 2032, Talk 2

Utz-Uwe Haus
Split cuts for robust and generalized mixed-integer programming

Coauthor: Frank Pfeuffer


Robust Mixed-Integer optimization problems are conventionally solved by
reformulation as non-robust problems. We propose a direct method to
separate split cuts for robust mixed-integer programs with polyhedral
uncertainty sets, for both worst-case as well as best-case robustness.
The method generalizes the well-known cutting plane procedure of Balas.
Computational experiments show that applying cutting planes directly is
favorable to the reformulation approach. It is thus viable to solve
robust MIP problems in a branch-and-cut framework using a Generalized
Linear Programming oracle.



Monday, 16:15 - 16:40 h, Room: H 2032, Talk 3

Oktay Günlük
Lattice-free sets, branching disjunctions, and mixed-integer programming

Coauthors: Sanjeeb Dash, Neil B. Dobbs, Tomasz J. Nowicki, Grzegorz M. Swirszcz


We study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and structured disjunctive cuts, especially the t-branch split cuts introduced by Li and Richard (2008).
By analyzing n-dimensional lattice-free sets, we prove that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with n integer variables is a t-branch split cut for some positive integer t.
Moreover, this number t does not depend on the data defining the polyhedral set and is bounded by a function of the dimension n only.
We use this result to give a finitely convergent cutting-plane algorithm to solve mixed-integer programs.
We also show that the minimum value t, for which all facets of polyhedral mixed-integer sets with n integer variables
can be expressed as t-branch split cuts, grows exponentially with n. In particular, when n=3, we observe that not all facet-defining inequalities are 6-branch split cuts.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.