Perspective Benders Decomposition with Applications to Fixed-Charge Nonlinear Resource Allocation

Decision-making processes involving fixed charges arise in various real-world applications and can often be modeled as mixed-integer nonlinear programs (MINLPs) with semicontinuous variables. Perspective reformulation, a technique leveraging perspective functions, offers tight formulations for such MINLPs. In this article, we address the challenge of solving such reformulations by introducing perspective Benders cuts, a family of generalized Benders optimality cuts, and compare them with the classic generalized Benders cuts and the perspective cuts. We focus on their applications to two fixed-charge nonlinear resource allocation problems: a generalized sensor placement problem and a generalized uncapacitated facility location problem. The original quadratic allocation cost functions in these problems are extended to a class of reducible convex functions. By leveraging the reducible property of nonlinear resource allocation problems, we develop an ad-hoc procedure of solving the reduced quadratic subproblems to efficiently separate perspective Benders cuts. These features contribute to a highly efficient branch-and-Benders-cut approach, as demonstrated through extensive computational experiments on various sets of benchmark instances.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: K. Yang acknowledges financial support from China Scholarship Council [Grant 202406110031]. This work was also supported by the National Science Fund for Outstanding Young Scholars [Grant 62122093], the National Natural Science Foundation of China [Grants 72101264, 72431011, and 72421002], the Science and Technology Innovation Program of Hunan Province [Grant 2023RC3008], Open Project of Xiangjiang Laboratory [Grant 22XJ02003], and the University Fundamental Research Fund [Grant 23-ZZCX-JDZ-28]. H. Yang’s work is funded by National Natural Science Foundation of China [Grant 72201232 and 72231008], Guangdong Provincial Key Laboratory of Mathematical Foundations for Artificial Intelligence [Grant 2023B1212010001], and Shenzhen Key Laboratory of Crowd Intelligence Empowered Low-Carbon Energy Network [Grant ZDSYS20220606100601002].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0984) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0984). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.