摘要: This paper provides an analysis of capacitated network design cut–set polyhedra. We give a complete linear description the polyhedron single commodity – facility problem. Then we extend to multifacility and multicommodity problems. Valid inequalities described here are applicable directed problems with any number types level capacities. report results from computational study done for testing effectiveness new inequalities.
springer.com
core.ac.uk
berkeley.edu参考文章(18)
M. Florian, G. Bushell, J. Ferland, G. Guérin, L. Nastansky, The Engine Scheduling Problem In A Railway Network Infor. ,vol. 14, pp. 121- 138 ,(1976) , 10.1080/03155986.1976.11731632
Zonghao Gu, George L. Nemhauser, Martin W.P. Savelsbergh, Sequence independent lifting in mixed integer programming Journal of Combinatorial Optimization. ,vol. 4, pp. 109- 129 ,(2000) , 10.1023/A:1009841107478
Laurence Wolsey, Facets and strong valid inequalities for integer programs Operational Research. ,vol. 24, pp. 367- 372 ,(1976)
Daniel Bienstock, Oktay Günlük, Capacitated Network Design—Polyhedral Structure and Computation Informs Journal on Computing. ,vol. 8, pp. 243- 259 ,(1996) , 10.1287/IJOC.8.3.243
L. A. Wolsey, Valid Inequalities and Superadditivity for 0--1 Integer Programs Mathematics of Operations Research. ,vol. 2, pp. 66- 77 ,(1977) , 10.1287/MOOR.2.1.66
Yves Pochet, Laurence A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation Discrete Applied Mathematics. ,vol. 59, pp. 57- 74 ,(1995) , 10.1016/0166-218X(95)90600-K
Oktay Günlük, A branch-and-cut algorithm for capacitated network design problems Mathematical Programming. ,vol. 86, pp. 17- 39 ,(1999) , 10.1007/S101070050077
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization Combinatorica. ,vol. 1, pp. 169- 197 ,(1981) , 10.1007/BF02579273
Richard M. Karp, Christos H. Papadimitriou, On Linear Characterizations of Combinatorial Optimization Problems SIAM Journal on Computing. ,vol. 11, pp. 620- 632 ,(1982) , 10.1137/0211053
Daniel Bienstock, Sunil Chopra, Oktay Günlük, Chih-Yang Tsai, Minimum cost capacity installation for multicommodity network flows Mathematical Programming. ,vol. 81, pp. 177- 199 ,(1998) , 10.1007/BF01581104