Continuous knapsack sets with divisible capacities
AbstractWe study two continuous knapsack sets Y≥ and Y≤ with n integer, one unbounded continuous and m bounded continuous variables in either ≥ or ≤ form. When the coefficients of the integer variables are integer and divisible, we show in both cases that the convex hull is the intersection of the bound constraints and 2m polyhedra arising from a continuous knapsack set with a single unbounded continuous variable. The latter polyhedra are in turn completely described by an exponential family of partition inequalities. A polynomial size extended formulation is known in the ≥ case. We provide an extended formulation for the ≤ case. It follows that, given a specific objective function, optimization over both Y≥ and Y≤ can be carried out by solving a polynomial size linear program. A consequence of these results is that the coefficients of the continuous variables all take the values 0 or 1 (after scaling) in any non-trivial facet-defining inequality.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) in its series CORE Discussion Papers with number 2013063.
Date of creation: 11 Dec 2013
Date of revision:
Contact details of provider:
Postal: Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium)
Fax: +32 10474304
Web page: http://www.uclouvain.be/core
More information through EDIRC
continuous knapsack set; splittable flow arec set; divisible capacities; partition inequalities; convex hull;
This paper has been announced in the following NEP Reports:
- NEP-ALL-2014-02-08 (All new papers)
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.:
- Nigar Hashimzade & Jean Hindriks & Gareth D. Myles, 2006. "Solutions Manual to Accompany Intermediate Public Economics," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582694, December.
- Manuel Förster & Ana Mauleon & Vincent Vannetelbosch, 2013.
"Trust and Manipulation in Social Networks,"
Documents de travail du Centre d'Economie de la Sorbonne
13065, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
- Manuel Förster & Ana Mauleon & Vincent J. Vannetelbosch, 2014. "Trust and Manipulation in Social Networks," Working Papers 2014.50, Fondazione Eni Enrico Mattei.
- FORSTER, Manuel & MAULEON, Ana & VANNETELBOSCH, Vincent, 2013. "Trust and manipulation in social networks," CORE Discussion Papers 2013050, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Manuel Förster & Ana Mauleon & Vincent Vannetelbosch, 2013. "Trust and Manipulation in Social Networks," UniversitÃ© Paris1 PanthÃ©on-Sorbonne (Post-Print and Working Papers) halshs-00881145, HAL.
- GAUTIER, Axel & POUDOU, Jean-Christophe, 2013. "Reforming the postal universal service," CORE Discussion Papers 2013024, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
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.