An exact algorithm for large-scale continuous nonlinear resource allocation problems with minimax regret objectives

Jungho Park (Corresponding author), Hadi El-Amine (Corresponding author), Nevin R. Mutlu (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

Samenvatting

We study a large-scale resource allocation problem with a convex, separable, not necessarily differentiable objective function that includes uncertain parameters falling under an interval uncertainty set, considering a set of deterministic constraints. We devise an exact algorithm to solve the minimax regret formulation of this problem, which is NP-hard, and we show that the proposed Benders-type decomposition algorithm converges to an ɛ-optimal solution in finite time. We evaluate the performance of the proposed algorithm via an extensive computational study, and our results show that the proposed algorithm provides efficient solutions to large-scale problems, especially when the objective function is differentiable. Although the computation time takes longer for problems with nondifferentiable objective functions as expected, we show that good quality, near-optimal solutions can be achieved in shorter runtimes by using our exact approach. We also develop two heuristic approaches, which are partially based on our exact algorithm, and show that the merit of the proposed exact approach lies in both providing an ɛ-optimal solution and providing good quality near-optimal solutions by laying the foundation for efficient heuristic approaches.
Originele taal-2Engels
TijdschriftINFORMS Journal on Computing
VolumeXX
Nummer van het tijdschriftXX
Vroegere onlinedatum18 jan 2021
DOI's
StatusE-publicatie vóór gedrukte publicatie - 18 jan 2021

Vingerafdruk Duik in de onderzoeksthema's van 'An exact algorithm for large-scale continuous nonlinear resource allocation problems with minimax regret objectives'. Samen vormen ze een unieke vingerafdruk.

Citeer dit