An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives

Jungho Park (), Hadi El-Amine () and Nevin Mutlu ()
Additional contact information
Jungho Park: Department of Systems Engineering and Operations Research, George Mason University, Fairfax, Virginia 22030
Hadi El-Amine: Department of Systems Engineering and Operations Research, George Mason University, Fairfax, Virginia 22030
Nevin Mutlu: School of Industrial Engineering, Eindhoven University of Technology, Eindhoven, Netherlands 5600MB

INFORMS Journal on Computing, 2021, vol. 33, issue 3, 1213-1228

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.

Keywords: robust optimization; interval minimax regret; continuous nonlinear optimization; Benders-type decomposition (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2020.0999 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:33:y:2021:i:3:p:1213-1228

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().