Using Interval Graphs to solve the Minimization of Open Stack problem

Martedi' 18 Ottobre 2011 - J.M. Valério de Carvalho


Martedi' 18 ottobre 2011 alle ore 14.30 in aula 2BC30 il Prof. J.M. Valério de Carvalho della Universidade do Minho (Braga, Portogallo) terra' un seminario dal titolo "Using Interval Graphs to solve the Minimization of Open Stack problem".

We present a recent integer programming formulation for the minimization of the maximum number of open stacks (MOSP) based on the completion of the client graph (introduced by Yanasse) with edges. The duration of each stack is associated with an interval of time. The graph admits a linear ordering of the vertices that defines an ordering of the stacks, and consequently decides a sequence for the cutting patterns. We use Olariu’s characterization of interval graphs to derive inequalities, which were strengthened and proved to be facets. There is a rich theory in interval (and perfect) graphs. Additional inequalities are derived based on the properties of chordal and comparability graphs. A polynomial model with symmetry reduced for the MOSP and other problems related to MOSP are also addressed, and computational tests are presented.

Rif. int. L. De Giovanni