Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design
Matheuristics based on iterative linear programming and slope scaling for multicommodity capacitated fixed charge network design
复制标题
基于迭代线性规划和斜率缩放的数学方法用于多商品容量固定电荷网络设计
DOI：
10.1016/j.ejor.2018.01.022
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Todosijević
中科院分区：
文献类型：
--
作者：
B. Gendron;S. Hanafi;R. Todosijević
提出了多商品容量固定收费网络设计问题（MCND）的新数学。其数学基础是结合迭代线性规划（ILP）方法和斜率变换（SS）启发式方法。每次迭代交替求解通过添加伪切割得到的线性规划和受限混合整数规划（MIP）模型。SS启发式被用作解决受限MIP模型的最先进的通用方法的一个温暖的开始。所得的ILP/SS数学与MCND在一组大规模困难实例上的最先进的启发式方法进行了比较。计算结果表明，该方法具有一定的竞争力：当执行1小时的时间限制时，使用可比的运行时间，它比任何其他启发式方法找到更多的最佳解；当执行时间限制为5小时时，它为已知最优解决方案的每个实例识别一个最优解决方案，并且能够为一些非常困难的实例找到新的最佳解决方案。
We present new matheuristics for the multicommodity capacitated fixed-charge network design problem (MCND). The matheuristics are based on combining iterative linear programming (ILP) methods and slope scaling (SS) heuristics. Each iteration alternates between solving a linear program obtained by adding pseudo-cuts and a restricted mixed-integer programming (MIP) model. The SS heuristic is used as a warm start to a state-of-the-art generic method that solves the restricted MIP model. The resulting ILP/SS matheuristics are compared against state-of-the-art heuristics for the MCND on a set of large-scale difficult instances. The computational results show that the approach is competitive: when performed for a time limit of 1 hour, it finds more best solutions than any other heuristic, using comparable running times; when performed for a time limit of 5 hours, it identifies an optimal solution for each instance for which an optimal solution is known and it is able to find new best solutions for some very hard instances.