Benders, metric and cutset inequalities for multicommodity capacitated network design
Contribuinte(s) |
UNIVERSIDADE DE SÃO PAULO |
---|---|
Data(s) |
20/10/2012
20/10/2012
2009
|
Resumo |
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. |
Identificador |
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, v.42, n.3, p.371-392, 2009 0926-6003 http://producao.usp.br/handle/BDPI/28953 10.1007/s10589-007-9122-0 |
Idioma(s) |
eng |
Publicador |
SPRINGER |
Relação |
Computational Optimization and Applications |
Direitos |
restrictedAccess Copyright SPRINGER |
Palavras-Chave | #Multicommodity capacitated network design #Benders decomposition #Metric inequalities #Cutset inequalities #CYCLE-BASED NEIGHBORHOODS #SET POLYHEDRA #MODELS #Operations Research & Management Science #Mathematics, Applied |
Tipo |
article original article publishedVersion |