Seminário de Otimização Combinatória


        On the Sum Constraint: Relaxation and Applications


                       Tallys Hoover Yunes
          Graduate School of Industrial Administration
                Carnegie Mellon University

                      Sexta-feira, 21 de junho
                     sala: IC2-96 horario: 18hs


Resumo:
=======




The global constraint sum can be used as a tool to implement
summations over sets of variables whose indices are not known in
advance.  This paper has two major contributions.  On the theoretical
side, we present the convex hull relaxation for the sum constraint in
terms of linear inequalities, whose importance in the context of
hybrid models is then justified.  On the practical side, we
demonstrate the applicability of the sum constraint in a scheduling
problem that arises as part of the development of new products in the
pharmaceutical and agrochemical industries.  This problem can be
modeled in two alternative ways: by using the sum constraint in a
natural and straightforward manner, or by using the element constraint
in a trickier fashion.  With the convex hull relaxation developed
earlier, we prove that the linear relaxation obtained from the former
model is tighter than the one obtained from the latter.  Moreover, our
computational experiments indicate that the CP model based on the sum
constraint is significantly more efficient as well.

OBSERVACAO:

Esta palestra sera ministrada em portugues.
Os minutos iniciais serao dedicados a uma revisao de alguns dos
conceitos e definicoes principais necessarios a uma melhor
compreensao do material apresentado.