Invited Session Wed.2.H 2032

Wednesday, 13:15 - 14:45 h, Room: H 2032

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

Polyhedral theory


Chair: Quentin Louveaux



Wednesday, 13:15 - 13:40 h, Room: H 2032, Talk 1

Carla Michini
How tight is the corner relaxation? Insights gained from the stable set problem

Coauthors: Gérard P. Cornuéjols, Giacomo Nannicini


The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this work we validate with theoretical arguments the empirical results obtained by Fischetti and Monaci: we give a precise characterization of the bounds given by the corner relaxation and three of its extensions, in the special case of the edge formulation of the stable set problem, for which a full description of the corner polyhedron is available. Our theoretical analysis shows that degeneracy plays a major role, as the difference in the bounds given by corner relaxations from two different optimal bases can be significantly large. Therefore, exploiting multiple degenerate bases for cut generation could give better bounds than working with just a single basis.



Wednesday, 13:45 - 14:10 h, Room: H 2032, Talk 2

Laurent Poirrier
The strength of multi-row models

Coauthors: Quentin Louveaux, Domenico Salvagnin


We consider the question of how to generate cutting planes
from arbitrary multi-row mixed-integer relaxations. In general,
these cutting planes can be obtained by row generation,
i.e. solving a ("master'') LP whose constraint are iteratively
constructed by solving ("slave'') MIPs. We show how to reduce
the size of both problems by adopting a two-phases approach
exploiting the bounds on variables and performing sequential
lifting whenever possible.
We use these results to implement a separator for arbitrary
multi-row mixed-integer relaxations and perform computational
tests in order to evaluate and compare the strength of some
important multi-row relaxations.



Wednesday, 14:15 - 14:40 h, Room: H 2032, Talk 3

Mahdi Doostmohammadi
Valid inequalities for the single arc design problem with set-ups

Coauthors: Agostinho Agra, Quentin Louveaux


We consider a variant of the classical single node fixed-charge network set with constant capacities in which the capacity of the node is an integer multiple of some constant value. This set is a generalization of the single arc design set studied by Magnanti et al. (1993). It arises in lot-sizing and network design problems.
We derive several families of facet-defining inequalities. In particular we generalize the residual capacity inequalities. Then we lift some of these valid inequalities through simultaneous lifting.


  quick loans . Moreover, to order Cialis Daily online is highly advantageous because it interacts well with the small portions of alcohol and food.