Convex hull results for generalizations of the constant capacity single node flow set

Laurence, Wolsey () and Hande, Yaman ()
Additional contact information
Laurence, Wolsey: CORE, UCLouvain
Hande, Yaman: KU Leuven

No 2018031, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: For single node flow sets with fixed costs and constant capacities on the inflow and outflow arcs, a family of constant capacity flow covers are known to provide the convex hull in different special cases and are conjectured to provide it in the general case. Here we study more general mixed integer sets for which such single node flow cover inequalities suffice to give the convex hull. In particular we consider the case of a path in which each node has one (or several) incoming and outgoing arcs with constant capacities and fixed costs. This can be seen as a lot-sizing set with production and sales decisions driven by costs and prices and by the lower and upper bounds on stocks instead of being driven by demands as in the standard lot-sizing model. The approach we take is classical: We characterize the extreme points, derive tight extended formulations and project out the additional variables. Specifically we show that Fourier-Motzkin elimination, though far from elegant, can be used to carry out the non-trivial projections. The validity of the conjecture for the single node flow set follows from our results.

Keywords: single node flow set; flow cover inequalities; convex hull; extended formulation; Fourier-Motzkin elimination (search for similar items in EconPapers)
Date: 2018-12-07
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2018.html (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2018031

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().