Invited Session Tue.1.H 2032

Tuesday, 10:30 - 12:00 h, Room: H 2032

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

Trends in mixed integer programming II


Chair: Andrea Lodi and Robert Weismantel



Tuesday, 10:30 - 10:55 h, Room: H 2032, Talk 1

Gustavo Angulo
Semi-continuous network flow problems

Coauthors: Shabbir Ahmed, Santanu S. Dey


We consider network flow problems where some of the variables are restricted to be semi-continuous. We introduce the single-node semi-continuous flow set with variable upper bounds as a relaxation. Two
particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We study the efficacy of the polyhedral results
on a class of semi-continuous transportation problems.



Tuesday, 11:00 - 11:25 h, Room: H 2032, Talk 2

Domenico Salvagnin
Randomness and tree search

Coauthors: Matteo Fischetti, Michele Monaci


Many mixed integer linear programs exhibit a high performance variability when solved with current state-of-the-art solvers, meaning that seemingly performance-neutral changes in the environment or in the input format have a great influence in the actual solution process.
Such variability is intrinsic in the enumerative nature of the branch-and-cut methods used to solve MIP instances and is mainly due to the fact that many decisions taken during the tree search (e.g., branching strategies, primal heuristics) are just heuristics and are subject to imperfect tie-breaking (degeneracy of the instance at hand further complicates the picture).
We investigate whether randomness can be a useful tool to overcome the issue of performance
variability and to actually take advantage of it to speed up the solution process. Preliminary
computational results show that the proposed approach is promising.



Tuesday, 11:30 - 11:55 h, Room: H 2032, Talk 3

Stefano Smriglio
Interdiction branching

Coauthors: Andrea Lodi, Ted K. Ralphs, Fabrizio Rossi


Interdiction branching is a branching method for binary integer
programs that is designed to overcome some difficulties that may be
encountered by branching on a variable dichotomy. Unlike traditional
methods, the branching disjunction is selected taking into account the
best feasible solution found so far. In particular, the method
computes an improving solution cover, which is a set of variables of
which at least one must be nonzero in any improving solution. From an
improving solution cover, we can obtain a branching disjunction such
that each child node is guaranteed to contain at least one improving
solution. Computing a minimal improving solution cover amounts to
solving a discrete bilevel program, which is difficult in general. In
practice, a solution cover, although not necessarily minimal nor
improving, can be found using a heuristic that achieves a profitable
trade-off between the size of the enumeration tree and the
computational burden of computing the cover. An empirical study shows
that such an implementation of the method reduces significantly the
size of the enumeration tree compared to branching on variables.


  Do you need Missouri Payday Loans as soon as possible? 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.