Benders,metric and cutset inequalities for multicommodity capacitated network design |
| |
Authors: | Alysson M Costa Jean-François Cordeau Bernard Gendron |
| |
Institution: | 1.Instituto de Ciências Matemáticas e de Computa??o,Universidade de S?o Paulo,S?o Carlos,Brazil;2.Chaire de recherche du Canada en distributique and Centre de recherche sur les transports,HEC Montréal,Montréal,Canada;3.Département d’informatique et de recherche opérationnelle, and Centre de recherche sur les transports,Université de Montréal,Montréal,Canada |
| |
Abstract: | Solving multicommodity capacitated network design problems is a hard task that requires the use of several strategies like
relaxing some constraints and strengthening the model with valid inequalities. In this paper, we compare three sets of inequalities
that have been widely used in this context: Benders, metric and cutset inequalities. We show that Benders inequalities associated
to extreme rays are metric inequalities. We also show how to strengthen Benders inequalities associated to non-extreme rays
to obtain metric inequalities. We show that cutset inequalities are Benders inequalities, but not necessarily metric inequalities.
We give a necessary and sufficient condition for a cutset inequality to be a metric inequality. Computational experiments
show the effectiveness of strengthening Benders and cutset inequalities to obtain metric inequalities. |
| |
Keywords: | Multicommodity capacitated network design Benders decomposition Metric inequalities Cutset inequalities |
本文献已被 SpringerLink 等数据库收录! |
|