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|
|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.:
- Gautier Axel & Poudou Jean-Christophe, 2014. "Reforming the Postal Universal Service," Review of Network Economics, De Gruyter, vol. 13(4), pages 453-477, December.
- Förster, Manuel & Mauleon, Ana & Vannetelbosch, Vincent J., 2016.
"Trust and manipulation in social networks,"
Cambridge University Press, vol. 4(02), pages 216-243, June.
- 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.
- Manuel Förster & Ana Mauleon & Vincent J. Vannetelbosch, 2014. "Trust and Manipulation in Social Networks," Working Papers 2014.50, Fondazione Eni Enrico Mattei.
- 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.
- 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).
- 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, January.
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 you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.