Demand allocation with latency cost functions

• 成果类型: Article
• 署名作者: Agnetis, Alessandro; Grande, Enrico; Pacifici, Andrea
• 署名单位: University of Rome Tor Vergata; University of Siena
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0398-y
• 发表日期: 2012
• 页码: 277-294
• 关键词: assignment

摘要

We address the exact resolution of a Mixed Integer Non Linear Programming model where resources can be activated in order to satisfy a demand (a covering constraint) while minimizing total cost. For each resource, there is a fixed activation cost and a variable cost, expressed by means of latency functions. We prove that this problem is NP-hard even for linear latency functions. A branch and bound algorithm is devised, having two important features. First, a dual bound (equal to that obtained by continuous relaxation) can be computed very efficiently at each node of the enumeration tree. Second, to break symmetries resulting in improved efficiency, the branching scheme is n-ary (instead of binary). These features lead to a successful comparison against two popular commercial and open-source solvers, CPLEX and Bonmin.