×

A further study on inverse linear programming problems. (English) Zbl 0971.90051

Summary: The authors continue their previous study [J. Comput. Appl. Math. 72, 261-273 (1996; Zbl 0856.65069)] on inverse linear programming problems which requires us to adjust the cost coefficients of a given LP problem as less as possible so that a known feasible solution becomes the optimal one. In particular, they consider the cases in which the given feasible solution and one optimal solution of the LP problem are 0-1 vectors which often occur in network programming and combinatorial optimization, and give very simple methods for solving this type of inverse LP problems. Besides, instead of the commonly used \(l_1\) measure, they also consider the inverse LP problems under \(l_\infty\) measure and propose solution methods.

MSC:

90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C27 Combinatorial optimization
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
65K05 Numerical mathematical programming methods

Citations:

Zbl 0856.65069

Software:

DEA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berman, O.; Ingco, D. L.; Odoni, A. R., Improving the location of minsum facility through network modification, Ann. Oper. Res., 40, 1-16 (1992) · Zbl 0787.90035
[2] Berman, O.; Ingco, D. L.; Odoni, A. R., Improving the location of minmax facility through network modification, Networks, 24, 31-41 (1994) · Zbl 0799.90074
[3] Burton, D.; Pulleyblank, W. R.; Toint, Ph. L., The inverse shortest paths problem with upper bounds on shortest paths costs, (Pardalos, P. M.; Hearn, D. W.; Hager, W. W., Network Optimization (1997), Springer: Springer Berlin), 156-171 · Zbl 0878.90098
[4] Burton, D.; Toint, Ph. L., On an instance of the inverse shortest paths problem, Math. Programming, 53, 45-61 (1992) · Zbl 0756.90089
[5] Burton, D.; Toint, Ph. L., On the use of an inverse shortest paths algorithm for recovering linearly correlated costs, Math. Programming, 63, 1-22 (1994) · Zbl 0795.90080
[6] Cai, M.; Li, Y., Inverse matroid intersection problem, ZOR Math. Methods Oper. Res, 45, 235-243 (1997) · Zbl 0882.90107
[7] Charnes, A., Data Envelopment Analysis: Theory, Methodology and Applications (1994), Kluwer: Kluwer Boston, MA
[8] Q. Wei, J. Zhang, X. Zhang, An inverse DEA model for inputs/outputs estimate, European J. Oper. Res., in press.; Q. Wei, J. Zhang, X. Zhang, An inverse DEA model for inputs/outputs estimate, European J. Oper. Res., in press. · Zbl 0948.91019
[9] Yang, C.; Zhang, J., Inverse maximum flow and minimum cut problem, Optimization, 40, 147-170 (1997) · Zbl 0880.90041
[10] Yang, C.; Zhang, J., Inverse maximum capacity problem, Oper. Res. Spektrum, 20, 97-100 (1998) · Zbl 0904.90168
[11] Zhang, J.; Liu, Z., Calculating some inverse linear programming problem, J. Comput. Appl. Math., 72, 261-273 (1996) · Zbl 0856.65069
[12] Zhang, J.; Ma, Z., A network flow method for solving some inverse combinatorial optimization problems, Optimization, 37, 59-72 (1996) · Zbl 0866.90099
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.