zbMATH — the first resource for mathematics

Calculating some inverse linear programming problems. (English) Zbl 0856.65069
For the general linear programming problem \[ \min \{cx/Ax = b,\;x \geq 0\} \] the inverse problem is expressed as \[ \min \bigl\{ |c-\widetilde c|/ \widetilde c\in F(x^0) \bigr\} \] where \(c,x \in \mathbb{R}^n\), \(b \in \mathbb{R}^m\), \(A\) is an \(m \times n\) matrix, \(x^0\) is a feasible solution, \[ F(x^0) = \bigl\{\widetilde c \in \mathbb{R}^n/ \min \{\widetilde cx/Ax=b,\;x\geq 0\} = \widetilde cx^0 \bigr\} \] and \(|\dots|\) is the \(l_1\) norm. A method for solving this inverse problem is suggested which is based on the optimality conditions for linear programming problems. For the application of the given method to inverse minimum cost flow or assignment problems is found that this method yields strongly polynomial algorithms.

65K05 Numerical mathematical programming methods
90C05 Linear programming
90B80 Discrete location and assignment
90B10 Deterministic network models in operations research
PDF BibTeX Cite
Full Text: DOI
[1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows, (1993), Prentice-Hall Englewood Cliffs · Zbl 1201.90001
[2] Burton, D.; Toint, Ph.L., On an instance of the inverse shortest paths problem, Math. programming, 53, 45-61, (1992) · Zbl 0756.90089
[3] Lawler, E., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart and Winston New York · Zbl 0413.90040
[4] Ma, Z.; Xu, S.; Zhang, J., Algorithms for inverse minimum spanning tree problem, ()
[5] Xu, S.; Zhang, J., An inverse problem of the weighted shortest path problem, Japan J. indust. appl. math., 12, 47-59, (1995) · Zbl 0827.05031
[6] Zhang, J.; Liu, Z.; Ma, Z., On the inverse problem of minimum spanning tree with partition constraints, ZOR math. methods oper. res., 44, (1996)
[7] Zhang, J.; Ma, Z.; Yang, C., A column generation method for inverse shortest path problems, ZOR math. methods oper. res., 41, 347-358, (1995) · Zbl 0838.90134
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.