Continuous knapsack sets with divisible capacities
We 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.
|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
References listed on IDEAS
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.:
- Manuel Förster & Ana Mauleon & Vincent J. Vannetelbosch, 2014.
"Trust and Manipulation in Social Networks,"
2014.50, Fondazione Eni Enrico Mattei.
- 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.
- 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," Documents de travail du Centre d'Economie de la Sorbonne 13065, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
- 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, March.
- 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).
When requesting a correction, please mention this item's handle: RePEc:cor:louvco:2013063. 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.