When solving hard multicommodity network flow problems using an LP-based approach, the number of commodities is a driving factor in the speed at which the LP can be solved, as it is linear in the number of constraints and variables. The conventional approach to improve the solve time of the LP relaxation of a Mixed Integer Programming (MIP) model that encodes such an instance is to aggregate all commodities that have the same origin or the same destination. However, the bound of the resulting LP relaxation can significantly worsen, which tempers the efficiency of aggregating techniques. In this paper, we introduce the concept of partial aggregation of commodities that aggregates commodities over a subset of the network instead of the conventional aggregation over the entire underlying network. This offers a high level of control on the trade-off between size of the aggregated MIP model and quality of its LP bound. We apply the concept of partial aggregation to two different MIP models for the multicommodity network design problem. Our computational study on benchmark instances confirms that the trade-off between solve time and LP bound can be controlled by the level of aggregation, and that choosing a good trade-off can allow us to solve the original large-scale problems faster than without aggregation or with full aggregation.
翻译:在采用基于LP的方法解决硬多通性网络流动问题时,商品的数量是一个驱动因素,因为它是制约和变量数量的线性,因此是解决LP速度的一个驱动因素,因为它是限制和变量数量的线性。改进LP放松混合整数编程模式(混合整数编程模式)的解决时间的常规办法,将这种模式编码起来,就是将所有来源相同或目的地相同的商品合并起来。然而,由此产生的LP放松的界限会大大恶化,从而抑制集成技术的效率。在本文中,我们引入了将商品比网络的一个子集成起来,而不是对整个基本网络进行常规集成的商品部分合并的概念。这为综合综合的MIP模式的大小与LP所约束的质量之间的权衡提供了高度的控制。我们对多通度网络设计问题的两个不同的MIP模式适用部分合并的概念。我们对基准实例的计算研究证实,解决时间和LP约束之间的权衡可以受集成水平的控制,而选择一个良好的贸易模式可以使我们不比全面合并更快地解决原型或总合。