期刊名称：CORE Discussion Papers / Center for Operations Research and Econometrics (UCL), Louvain
出版年度：2010
卷号：2010
期号：1
出版社：Center for Operations Research and Econometrics (UCL), Louvain
摘要：Recently there has been considerable research on simple mixed-integer sets, called mixing sets, and closely
related sets arising in uncapacitated and constant capacity lot- sizing. This in turn has led to study of more general
sets, called network-dual sets, for which it is possible to derive extended formulations whose projection gives the
convex hull of the network-dual set. Unfortunately this formulation cannot be used (in general) to optimize in
polynomial time. Furthermore the inequalities definining the convex hull of a network-dual set in the original
space of variables are known only for some special cases.
Here we study two new cases, in which the continuous variables of the network-dual set are linked by a bidirected
path. In the first case, which is motivated by lot-sizing problems with (lost) sales, we provide a
description of the convex hull as the intersection of the convex hulls of 2n mixing sets, where n is the number of
continuous variables of the set. However optimization is polynomial as only n + 1 of the sets are required for any
given objective function. In the second case, generalizing single arc flow sets, we describe again the convex hull
as an intersection of an exponential number of mixing sets and also give a combinatorial polynomial-time
separation algorithm.
