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)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
JournalINFORMS Journal on Computing
VolumeXX
Issue numberXX
Early online date18 Jan 2021
DOIs
Publication statusE-pub ahead of print - 18 Jan 2021

Fingerprint Dive into the research topics of 'An exact algorithm for large-scale continuous nonlinear resource allocation problems with minimax regret objectives'. Together they form a unique fingerprint.

Cite this