Demand allocation with latency cost functions

作者：Agnetis Alessandro; Grande Enrico^*; Pacifici Andrea

来源：Mathematical Programming, 2012, 132(1-2): 277-294.

DOI：10.1007/s10107-010-0398-y

• MINLP
• Latency functions
• Convex functions
• Branch and bound
• Resource allocation

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.

• 出版日期2012-4