×

Inverse problems of submodular functions on digraphs. (English) Zbl 1034.90012

Summary: We study the inverse problem of submodular functions on digraphs. Given a feasible solution \(x^*\) for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector \(c\) of the objective function, optimally and within bounds, such that \(x^*\) becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in strongly polynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions.

MSC:

90C35 Programming involving graphs or networks
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Burton, D., and Toint, P. L., On an Instance of the Inverse Shortest Paths Problem, Mathematical Programming, Vol. 53, pp. 45–61, 1992. · Zbl 0756.90089
[2] Cai, M., and Li, Y., Inverse Matroid Intersection Problems, ZOR-Mathematical Methods of Operations Research, Vol. 45, pp. 235–243, 1997. · Zbl 0882.90107
[3] Cai, M., and Yang, X., Inverse Shortest Path Problems, Operations Research and Its Applications, Lecture Notes in Operations Research, Edited by D. Du, X. Zhang, and K. Cheng, Beijing World Publishing Corporation, Beijing, China, Vol. 1, pp. 242–248, 1995.
[4] Cai, M., Yang, X., and Li, Y., Inverse Polymatroidal Flow Problem, Journal of Combinatorial Optimization, Vol. 3, pp. 115–126, 1999. · Zbl 0957.90126 · doi:10.1023/A:1009877408258
[5] Hu, Z., and Liu. Z., A Strongly Polynomial Algorithm for the Inverse Shortest Arborescence Problem, Discrete Applied Mathematics, Vol. 82, pp. 135–154, 1998. · Zbl 0897.90188
[6] Sokkalingam, P. T., Ahuja, R. K., and Orlin, J. B., Inverse Spanning Tree Problems: Formulations and Algorithms, Working Paper 3890–96, Sloan School of Management, MIT, 1996.
[7] Xu, S., and Zhang, J., An Inverse Problem of the Weighted Shortest Path Problem, Japan Journal of Industrial and Applied Mathematics, Vol. 12, pp. 47–59, 1995. · Zbl 0827.05031 · doi:10.1007/BF03167381
[8] Yang, C., and Zhang, J., Inverse Maximum Flow and Minimum Cut Problems, Optimization, Vol. 40, pp. 147–170, 1997. · Zbl 0880.90041 · doi:10.1080/02331939708844306
[9] Zhang, J., and Cai, M., Inverse Problem of Minimum Cuts, ZOR-Mathematical Methods of Operations Research, Vol. 48, pp. 51–58, 1998. · Zbl 0941.90013 · doi:10.1007/BF01193836
[10] Zhang, J., and Liu, Z., Calculating Some Inverse Linear Programming Problems, Journal of Computational and Applied Mathematics, Vol. 72, pp. 261–273, 1996. · Zbl 0856.65069 · doi:10.1016/0377-0427(95)00277-4
[11] Zhang, J., and Liu, Z., A Further Study on Inverse Linear Programming Problems, Journal of Computational and Applied Mathematics (to appear). · Zbl 0971.90051
[12] Zhang, J., Liu, Z., and Ma, Z., On the Inverse Problem of Minimum Spanning Tree with Partition Constraints, ZOR-Mathematical Methods of Operations Research, Vol. 44, pp. 171–187, 1996. · Zbl 0861.90120 · doi:10.1007/BF01194328
[13] Zhang, J., Liu, Z., and Ma, Z., Inverse Fractional Matching Problem, Journal of the Australian Mathematics Society, Series B: Applied Mathematics, Vol. 40, pp. 484–496, 1999. · Zbl 0971.90076
[14] Zhang, J., and MA, Z., A Network Flow Method for Solving Some Inverse Combinatorial Optimization Problems, Optimization, Vol. 37, pp. 59–72, 1996. · Zbl 0866.90099 · doi:10.1080/02331939608844197
[15] Zhang, J., and Ma, Z., Solution Structure of Some Inverse Optimization Problems, Journal of Combinatorial Optimization, Vol. 3, pp. 127–139, 1999. · Zbl 0932.90034 · doi:10.1023/A:1009829525096
[16] Zhang, J., Ma, Z., and Yang, C., A Column Generation Method for Inverse Shortest Path Problems, ZOR-Mathematical Methods of Operations Research, Vol. 41, pp. 347–358, 1995. · Zbl 0838.90134 · doi:10.1007/BF01432364
[17] Zhang, J., Xu, S., and Ma, Z., An Algorithm for Inverse Minimum Spanning Tree Problem, Optimization Methods and Software, Vol. 8, pp. 69–84, 1997. · Zbl 0894.90157 · doi:10.1080/10556789708805666
[18] Edmonds, J., and Giles, R., A Min-Max Relation for Submodular Functions on Graphs, Annals of Discrete Mathematics, Vol. 1, pp. 185–204, 1977. · Zbl 0373.05040 · doi:10.1016/S0167-5060(08)70734-9
[19] Schrijver, A., Total Dual Integrality from Directed Graphs, Crossing Families, and Submodular and Supermodular Functions, Progress in Combinatorial Optimization, Edited by W. R. Pulleyblank, Academic Press, Toronto, Canada, pp. 315–361, 1984.
[20] LovÁsz, L., Flats in Matroids and Geometric Graphs, Combinatorial Surveys, Edited by P. J. Cameron, Academic Press, New York, NY, pp. 45–86, 1977.
[21] Frank, A., An Algorithm for Submodular Functions on Graphs, Annals of Discrete Mathematics, Vol. 16, pp. 97–120, 1982. · Zbl 0504.05059
[22] LovÁsz, L., Submodular Functions and Convexity, Mathematical Programming: The State of the Art, Edited by A. Bachen, M. Grötschel, and B. Korte, Springer, Berlin, Germany, pp. 235–257, 1983.
[23] Tardos, ö., A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs, Operations Research, Vol. 34, pp. 250–256, 1986. · Zbl 0626.90053 · doi:10.1287/opre.34.2.250
[24] Goldberg, A. V., Tardos, É., and Tarjan, R. E., Network Flow Algorithms, Technical Report 860, School of Operations Research and Industrial Engineering, Cornell University, 1989. · Zbl 0728.90035
[25] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B., Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, Englewood Cliffs, New Jersey, 1993. · Zbl 1201.90001
[26] Tardos, É., A Strongly Polynomial Minimum Cost Circulation Algorithm, Combinatorica, Vol. 5, pp. 247–255, 1985. · Zbl 0596.90030 · doi:10.1007/BF02579369
[27] Orlin, J. B., A Faster Strongly Polynomial Minimum Cost Flow Algorithm, Proceedings of the 20th ACM Symposium on the Theory of Computers, pp. 377–387, 1988.
[28] Ford, L. R., and Fulkerson, D. R., Flows in Networks, Princeton University Press, Princeton, New Jersey, 1962. · Zbl 0106.34802
[29] Lawler, E., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, New York, NY, 1976. · Zbl 0413.90040
[30] Cai, M., Yang, X., and Zhang, J., The Complexity Analysis of the Inverse-Centre Location Problem, Journal of Global Optimization, Vol. 15, pp. 213–218, 1999. · Zbl 0978.90065 · doi:10.1023/A:1008360312607
[31] Yang, C., and Zhang, J., Inverse Maximum Capacity Problem, Operations Research Spektrum, Vol. 20, pp. 97–100, 1998. · Zbl 0904.90168 · doi:10.1007/BF01539860
[32] Yang, C., and Zhang, J., Two General Methods for Inverse Optimization Problems, Applied Mathematics Letters, Vol. 12, pp. 69–72, 1999. · Zbl 0935.90023 · doi:10.1016/S0893-9659(98)00151-7
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.