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.


  Most online loan lenders allow getting Payday Loans New Jersey without visiting a bank, straight to your bank account. You can buy Levitra Super Force profitably on our web-site; we offer the medications only of the highest quality and at reasonable prices.