Solution Structure of Some Inverse Combinatorial Optimization Problems
作者： Jianzhong Zhang , Zhongfan Ma
关键词: Mathematics 、 Cutting stock problem 、 Computational problem 、 Mathematical optimization 、 Combinatorial optimization 、 Generalized assignment problem 、 Steiner tree problem 、 Optimization problem 、 1-center problem 、 Quadratic assignment problem
摘要: In this paper we consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions an problem, wish to know: under what weight vectors (or capacity vectors) will these become optimal solutions? We analysed shortest path minimum cut spanning tree problem and maximum-weight matching found in each cases, the solution is charaterized by solving another problem. The main tool our approach Fulkerson's theory blocking anti-blocking polyhedra with necessary revisions.
springer.com
sci-hub.se 参考文章(12)
Cai Mao-Cheng, Yanjun Li, Inverse Matroid Intersection Problem Mathematical Methods of Operations Research. ,vol. 45, pp. 235- 243 ,(1997) , 10.1007/BF01193863
Alexander Schrijver, Theory of Linear and Integer Programming ,(1986)
Jianzhong Zhang, Shaoji Xu, Zhongfan Ma, An algorithm for inverse minimum spanning tree problem Optimization Methods & Software. ,vol. 8, pp. 69- 84 ,(1997) , 10.1080/10556789708805666
D. Burton, Ph. L. Toint, On an instance of the inverse shortest paths problem Mathematical Programming. ,vol. 53, pp. 45- 61 ,(1992) , 10.1007/BF01585693
Laurence A. Wolsey, George L. Nemhauser, Integer and Combinatorial Optimization ,(1988)
Jianzhong Zhang, Zhenhong Liu, Zhongfan Ma, On the inverse problem of minimum spanning tree with partition constraints Mathematical Methods of Operations Research. ,vol. 44, pp. 171- 187 ,(1996) , 10.1007/BF01194328
C. Yang, J. Zhang, Z. Ma, Inverse maximum flow and minimum cut problems Optimization. ,vol. 40, pp. 147- 170 ,(1997) , 10.1080/02331939708844306
Jianzhong. Zhang, Zhongfan. Ma, A network flow method for solving some inverse combinatorial optimization problems Optimization. ,vol. 37, pp. 59- 72 ,(1996) , 10.1080/02331939608844197
Jianzhong Zhang, Zhenhong Liu, Calculating some inverse linear programming problems Journal of Computational and Applied Mathematics. ,vol. 72, pp. 261- 273 ,(1996) , 10.1016/0377-0427(95)00277-4
Jianzhong Zhang, Zhongfan Ma, Chao Yang, A column generation method for inverse shortest path problems Mathematical Methods of Operations Research. ,vol. 41, pp. 347- 358 ,(1995) , 10.1007/BF01432364