Reformulations by Discretization for Piecewise Linear Integer Multicommodity Network Flow Problems
针对总流量必须为整数的分段线性多商品网络流问题，利用离散化技术提出新模型，并加入割集不等式或流分解方法增强模型，开发拉格朗日松弛算法高效计算上下界，对随机实例验证了不同建模方案的效率。
We consider the piecewise linear multicommodity network flow problem with the addition of a constraint specifying that the total flow on each arc must be an integer. This problem has applications in transportation and logistics, where total flows might represent vehicles or containers filled with different products. We introduce formulations that exploit this integrality constraint by adapting to our problem a technique known as discretization that has been used to derive mixed-integer programming models for several combinatorial optimization problems. We enhance the discretized models either by adding valid inequalities derived from cut-set inequalities or by using flow disaggregation techniques. Since the size of the formulations derived from discretization and flow disaggregation rapidly increases with problem dimensions, we develop an efficient and effective Lagrangian relaxation method to compute lower and upper bounds. We perform computational results on a large set of randomly generated instances that allow us to compare the relative efficiency of the different modeling alternatives (flow disaggregation plus addition of cut-set inequalities with or without discretization), when used within the Lagrangian relaxation approach.