A breakpoint search approach for convex resource allocation problems with bounded variables

A. de Waegenaere, J.L. Wielhouwer

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

We present an efficient approach to solve resource allocation problems with a single resource, a convex separable objective function, a convex separable resource-usage constraint, and variables that are bounded below and above. Through a combination of function evaluations and median searches, information on whether or not the upper- and lowerbounds are binding is obtained. Once this information is available for all upper and lower bounds, it remains to determine the optimum of a smaller problem with unbounded variables. This can be done through a multiplier search procedure. The information gathered allows for alternative approaches for the multiplier search which can reduce the complexity of this procedure. © 2011 The Author(s).
Original languageEnglish
Pages (from-to)629-640
JournalOptimization Letters
Volume6
Issue number4
DOIs
Publication statusPublished - 2012

Fingerprint

Resource Allocation
Multiplier
Resources
Evaluation Function
Upper and Lower Bounds
Objective function
Alternatives

Cite this

@article{73476c00a340460d9711a8ecc38397a4,
title = "A breakpoint search approach for convex resource allocation problems with bounded variables",
abstract = "We present an efficient approach to solve resource allocation problems with a single resource, a convex separable objective function, a convex separable resource-usage constraint, and variables that are bounded below and above. Through a combination of function evaluations and median searches, information on whether or not the upper- and lowerbounds are binding is obtained. Once this information is available for all upper and lower bounds, it remains to determine the optimum of a smaller problem with unbounded variables. This can be done through a multiplier search procedure. The information gathered allows for alternative approaches for the multiplier search which can reduce the complexity of this procedure. {\circledC} 2011 The Author(s).",
author = "{de Waegenaere}, A. and J.L. Wielhouwer",
year = "2012",
doi = "10.1007/s11590-011-0288-0",
language = "English",
volume = "6",
pages = "629--640",
journal = "Optimization Letters",
issn = "1862-4472",
publisher = "Springer Verlag",
number = "4",

}

A breakpoint search approach for convex resource allocation problems with bounded variables. / de Waegenaere, A.; Wielhouwer, J.L.

In: Optimization Letters, Vol. 6, No. 4, 2012, p. 629-640.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - A breakpoint search approach for convex resource allocation problems with bounded variables

AU - de Waegenaere, A.

AU - Wielhouwer, J.L.

PY - 2012

Y1 - 2012

N2 - We present an efficient approach to solve resource allocation problems with a single resource, a convex separable objective function, a convex separable resource-usage constraint, and variables that are bounded below and above. Through a combination of function evaluations and median searches, information on whether or not the upper- and lowerbounds are binding is obtained. Once this information is available for all upper and lower bounds, it remains to determine the optimum of a smaller problem with unbounded variables. This can be done through a multiplier search procedure. The information gathered allows for alternative approaches for the multiplier search which can reduce the complexity of this procedure. © 2011 The Author(s).

AB - We present an efficient approach to solve resource allocation problems with a single resource, a convex separable objective function, a convex separable resource-usage constraint, and variables that are bounded below and above. Through a combination of function evaluations and median searches, information on whether or not the upper- and lowerbounds are binding is obtained. Once this information is available for all upper and lower bounds, it remains to determine the optimum of a smaller problem with unbounded variables. This can be done through a multiplier search procedure. The information gathered allows for alternative approaches for the multiplier search which can reduce the complexity of this procedure. © 2011 The Author(s).

U2 - 10.1007/s11590-011-0288-0

DO - 10.1007/s11590-011-0288-0

M3 - Article

VL - 6

SP - 629

EP - 640

JO - Optimization Letters

JF - Optimization Letters

SN - 1862-4472

IS - 4

ER -