Demand allocation with latency cost functions (Q2429466)

This article studies a non-linear, mixed-integer programming problem which models a demand allocation constrained by minimum demand requirements (a covering constraint). The objective is to minimize the total cost of using the available resources, the cost of which consists of a fixed cost and variable cost. The variable cost is defined via latency functions and the authors prove that this problem is NP-complete even in the case of linear latency functions. The authors consider the continuous and the Lagrangian relaxations of the problem and derive efficient algorithms for the calculation of the dual bound. This yields to a very efficient branch and bound method for solving the problem, which is further enhanced with symmetry-breaking branching and compares favorably against the efficient, general-purpose integer programming solvers Cplex and Bonmin. The article concludes with a summary of the results of the computational experimentation and a list of relevant references.