Optimization Online


A new combinatorial algorithm for separable convex resource allocation with nested bound constraints

Zeyang Wu (wuxx1164***at***umn.edu)
Kameng Nip (niejm3***at***mail.sysu.edu.cn)
He Qie (qiehe01***at***gmail.com)

Abstract: The separable convex resource allocation problem with nested bound constraints aims to allocate $B$ units of resources to $n$ activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve this model exactly. Our algorithm is capable of solving instances of with millions of activities in several minutes. The running time of our algorithm is at most $65\%$ of the running time of the current best algorithm for benchmark instances with three classes of convex objectives. The efficiency of our algorithm derives from the combination of constraint relaxation and use of infeasibility information. In particular, nested bound constraints are relaxed first; if the obtained solution violates some bound constraint, we show that the problem can be divided into two subproblems of the same structure and smaller size, according to the bound constraint with the largest violation.

Keywords: Resource allocation, Divide and conquer, Greedy algorithm, Mixed-integer convex program

Category 1: Combinatorial Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 11/02/2018
Entry Accepted: 11/02/2018
Entry Last Modified: 07/24/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society