EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

419. Perspective Benders Cuts for Resource Allocation Problems with Separable Convex Costs

Invited abstract in session WB-4: Mixed Integer Nonlinear Programming and Nonconvex Optimization , stream MINLP.

Wednesday, 10:30-12:00
Room: 1001 (building: 202)

Authors (first author is the speaker)

1. Kang Yang
College of Systems Engineering, National University of Defense Technology
2. Guopeng Song
National University of Defense Technology

Abstract

We investigate two broad categories of resource allocation problems in which resources can be activated to fulfill the demand of one or multiple customers, respectively, with the objective of minimizing the total cost. Each resource incurs a fixed activation cost, and for each resource-customer pair, there is a variable allocation cost represented by separable convex functions. The traditional mixed-integer programming models for these problems are enhanced using the technique of perspective reformulation, which involves substituting each term in the separable objective function with its perspective term. In this work, we have developed a branch-and-Benders-cut algorithm to address the perspective reformulation models of these two general problem classes. Our approach incorporates two novel features. Firstly, a family of generalized Benders optimality cuts expressions suitable for perspective reformulation models, referred to as perspective Benders cuts, is derived, which are tighter than classic generalized Benders cuts. Secondly, we have developed a unified ad-hoc procedure, named reduce and recover, to efficiently separate perspective Benders cuts by solving the reduced quadratic subproblems. These features have led to a highly efficient solution method on these two general problem classes, which is verified through extensive computational experiments based on benchmark instances with four different classes of nonlinear allocation functions.

Keywords

Status: accepted

Back to the list of papers