CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Algorithms for the continuous nonlinear resource allocation problem - New implementations and numerical studies

Michael Patriksson (Institutionen för matematiska vetenskaper, matematik) ; Christoffer Strömberg
European Journal of Operational Research (0377-2217). Vol. 243 (2015), 3, p. 703-722.
[Artikel, refereegranskad vetenskaplig]

Patriksson (2008) provided a then up-to-date survey on the continuous, separable, differentiable and convex resource allocation problem with a single resource constraint. Since the publication of that paper the interest in the problem has grown: several new applications have arisen where the problem at hand constitutes a subproblem, and several new algorithms have been developed for its efficient solution. This paper therefore serves three purposes. First, it provides an up-to-date extension of the survey of the literature of the field, complementing the survey in Patriksson (2008) with more then 20 books and articles. Second, it contributes improvements of some of these algorithms, in particular with an improvement of the pegging (that is, variable fixing) process in the relaxation algorithm, and an improved means to evaluate subsolutions. Third, it numerically evaluates several relaxation (primal) and breakpoint (dual) algorithms, incorporating a variety of pegging strategies, as well as a quasi-Newton method. Our conclusion is that our modification of the relaxation algorithm performs the best. At least for problem sizes up to 30 million variables the practical time complexity for the breakpoint and relaxation algorithms is linear.

Nyckelord: Resource allocation; Convex optimization; Lagrangian duality; Applications; Numerical analysis

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2015-04-30. Senast ändrad 2015-12-03.
CPL Pubid: 216160


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Hållbar utveckling
Innovation och entreprenörskap (nyttiggörande)
Numerisk analys
Optimeringslära, systemteori

Chalmers infrastruktur