Mixing sets linked by bidirected paths
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 bi- directed 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 2^n 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.
|Date of creation:||01 Oct 2010|
|Date of revision:|
|Contact details of provider:|| Postal: |
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Winfried Pohlmeier & Luc Bauwens & David Veredas, 2007. "High frequency financial econometrics. Recent developments," ULB Institutional Repository 2013/136223, ULB -- Universite Libre de Bruxelles.
- repec:cup:cbooks:9780521681599 is not listed on IDEAS
When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2010063. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Alain GILLIS)
If references are entirely missing, you can add them using this form.