Inverse optimization for linearly constrained convex separable programming problems. (English) Zbl 1177.90321
Summary: We study inverse optimization for linearly constrained convex separable programming problems that have wide applications in industrial and managerial areas. For a given feasible point of a convex separable program, the inverse optimization is to determine whether the feasible point can be made optimal by adjusting the parameter values in the problem, and when the answer is positive, find the parameter values that have the smallest adjustments. A sufficient and necessary condition is given for a feasible point to be able to become optimal by adjusting parameter values. Inverse optimization formulations are presented with \(\ell _{1}\) and \(\ell _{2}\) norms. These inverse optimization problems are either linear programming when \(\ell _{1}\) norm is used in the formulation, or convex quadratic separable programming when \(\ell _{2}\) norm is used.
Keywords:
inverse optimization; convex separable program; KKT conditions; linear programming; quadratic programmingReferences:
| [1] | Ahuja, R. K.; Orlin, J. B., Inverse optimization, Operations Research, 49, 771-783 (2001) · Zbl 1163.90764 |
| [2] | Ahuja, R. K.; Orlin, J. B., A faster algorithm for the inverse spanning tree problem, Journal of Algorithms, 34, 177-193 (2000) · Zbl 0968.68192 |
| [3] | Ahuja, R. K.; Orlin, J. B., Combinatorial algorithms for inverse network flow problems, Networks, 40, 181-187 (2002) · Zbl 1026.90089 |
| [4] | Baldick, R., Refined proximity and sensative results in linearly constrained convex separable integer programming, Linear Algebra and its Applications, 226-228, 389-407 (1995) · Zbl 0838.90083 |
| [5] | Bitran, D. P.; Hax, A. C., Disaggregation and resource allocation using convex knapsack problems with bounded variables, Management Science, 27, 431-441 (1981) · Zbl 0454.90059 |
| [6] | Bitran, G. R.; Tirupati, D., Tradeoff curves, targeting and balancing in manufacturing queueing network, Operations Research, 37, 431-441 (1989) |
| [7] | Bretthauer, K. M.; Shetty, B., The nonlinear knapsack problem – algorithms and applications, European Journal of Operational Research, 138, 459-472 (2002) · Zbl 1003.90036 |
| [8] | Bretthauer, K. M.; Shetty, B.; Syam, S., A model for resource constrained production and inventory management, Decision Sciences, 25, 561-580 (1994) |
| [9] | Brucker, P., An O(n) algorithm for quadratic knapsack problems, Operations Research Letter, 3, 163-166 (1984) · Zbl 0544.90086 |
| [10] | Burton, D.; Toint, Ph. L., On an instance of the inverse shortest paths problem, Mathematical Programming, 53, 45-61 (1992) · Zbl 0756.90089 |
| [11] | Burton, D.; Toint, Ph. L., On the use of an inverse shortest paths algorithm for recovering correlated costs, Mathematical Programming, 63, 1-22 (1994) · Zbl 0795.90080 |
| [12] | Carr, S.; Lovejoy, W., The inverse newsvendor problem: Choosing an optimal demand portfolio for capacitated resources, Management Science, 46, 912-927 (2000) · Zbl 1231.90015 |
| [13] | Cochran, W. G., Sampling Techniques (1963), Wiley: Wiley New York · Zbl 0051.10707 |
| [14] | Christopher, S. T., Reducing separable convex programs with tree constraints, Management Science, 36, 1407-1412 (1990) · Zbl 0727.90060 |
| [15] | Dembo, R.; Rosen, D., The practice of portfolio replication: A practical overview of forward and inverse problems, Annals of Operations Research, 85, 267-284 (1999) · Zbl 0920.90006 |
| [16] | Gerla, M.; Kleinrock, L., On the topological design of distributed computer network, IEEE Transactions on Communications, 25, 48-60 (1977) |
| [17] | M.J. Hartley, G.S. Bakshi, Markowitz models of portfolio selection: The inverse problem, October, 1998.; M.J. Hartley, G.S. Bakshi, Markowitz models of portfolio selection: The inverse problem, October, 1998. |
| [18] | Hax, A. C.; Candea, D. C., Production and Inventory Management (1984), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [19] | Heuberger, C., Inverse combinatorial optimization: A survey on problems, methods, and results, Journal of Combinatorial Optimization, 8, 329-361 (2004) · Zbl 1084.90035 |
| [20] | D.S. Hochbaum, Inverse problems and efficient convex optimization algorithms, Research Report, Department of Industrial Engineering and Operations Research, University of California, Berkeley, March, 2004.; D.S. Hochbaum, Inverse problems and efficient convex optimization algorithms, Research Report, Department of Industrial Engineering and Operations Research, University of California, Berkeley, March, 2004. |
| [21] | Hochbaum, D. S.; Shanthikumar, J. G., Convex separable optimization is not much harger than linear optimization, ACM, 37.4, 843-862 (1990) · Zbl 0721.90060 |
| [22] | Hochbaum, D. S., A nonlinear knapsack problem, Operations Research Letters, 17, 103-110 (1995) · Zbl 0838.90092 |
| [23] | Ibaraki, T.; Katoh, N., Resource Allocation Problems (1988), MIT Press: MIT Press Cambridge, MA · Zbl 0786.90067 |
| [24] | Iyengar, G.; Kang, W., Inverse conic programming and applications, Operations Research Letters, 33, 319-330 (2005) · Zbl 1140.90465 |
| [25] | Katoh, N.; Ibaraki, T.; Mine, H., A polynomial time algorithm for the resource allocation problem with a convex objective function, Journal of the Operations Research Society, 30, 449-455 (1979) · Zbl 0407.90062 |
| [26] | Kodialam, M. S.; Luss, H., Algorithms for separable nonlinear resource allocation problems, Operations Research, 46, 272-284 (1998) · Zbl 0979.90109 |
| [27] | Li, Han-Lin; Yu, Chian-Son, A global optimization method for nonconvex separable programming problems, European Journal of Operational Research, 117, 275-292 (1999) · Zbl 0998.90063 |
| [28] | Luss, H.; Gupta, S. K., Allocation of effort resources among competing activities, Operations Research, 23, 360-366 (1975) · Zbl 0298.90015 |
| [29] | Michaeli, I.; Pollatschek, M. A., On some nonlinear knapsack problems, Annals of Discrete Mathematics, 1, 403-414 (1977) · Zbl 0369.90088 |
| [30] | Maloney, B. M.; Klein, C. M., Constrained multi-item inventory systems: An implicit approach, Computers and Operations Research, 20, 639-649 (1993) · Zbl 0792.90023 |
| [31] | Mathur, K.; Salkin, H. M.; Morito, S., A branch and search algorithm for a class of nonlinear knapsack problems, Operations Research Letters, 2, 155-160 (1983) · Zbl 0526.90066 |
| [32] | McCarl, B. A.; Onal, H., Linear approximation using MOTAD and separable programming: Should it be done?, American Journal of Agricultural Economy, February, 158-166 (1989) |
| [33] | Michaud, R. O., Efficient asset management: A practical guide to stock portfolio management and asset allocation, Financial Management Association Survey and Synthesis Series (1998), HBS Press |
| [34] | Monteiro, R. D.C.; Adler, I., An extension of Karmarkar type algorithm to a class of convex separable programming problems with global linear rate of convergence, Mathematics of Operations Research, 15, 409-422 (1990) · Zbl 0708.90068 |
| [35] | More, J. J.; Vavasis, S. A., On the solution of concave knapsack problems, Mathematical Programming, 49, 341-397 (1991) · Zbl 0723.90059 |
| [36] | Pardalos, P. M.; Ye, Y.; Han, C.-G., Algorithms for the solution of quadratic knapsack problems, Linear Algebra and its Applications, 152, 69-91 (1991) · Zbl 0729.65047 |
| [37] | Porteus, E. L., Optimal lot sizing, process quality improvement and setup cost reduction, Operations Research, 34, 137-144 (1986) · Zbl 0591.90043 |
| [38] | Robinson, A. G.; Jiang, N.; Lerme, C. S., On the continuous quadratic knapsack problem, Mathematical Programming, 55, 99-108 (1992) · Zbl 0762.90061 |
| [39] | Sokkalingam, P. T.; Ahuja, R.; Orlin, J. B., Solving inverse spanning tree problems through network flow techniques, Operations Research, 47, 291-298 (1999) · Zbl 0979.90119 |
| [40] | Stefanov, S. M., Convex knapsack problem with bounded variables, (Ivanchev, D., Applications of Mathematics in Engineering, vol. 19 (1994), Technical University of Sophia: Technical University of Sophia Sofia), 189-194 |
| [41] | Stefanov, S. M., Convex separable minimization subject to bounded variables, Computational Optimization and Applications, 18, 27-48 (2001) · Zbl 0963.90048 |
| [42] | Stefanov, S. M., On the implementation of stochastic quasigradient methods to some facility location problems, YUJOR, 10, 235-256 (2000) · Zbl 1029.90517 |
| [43] | Vavasis, S. A., Local minima for indefinite quadratic knapsack problems, Mathematical Programming, 54, 127-153 (1992) · Zbl 0751.90058 |
| [44] | Ventura, J. A.; Klein, C. M., A note on multi-item inventory systems with limited capacity, Operations Research Letters, 7, 71-75 (1988) · Zbl 0643.90020 |
| [45] | Werman, M.; Magagnosc, D., The relationship between integer and real solutions of constrained convex programming, Mathematical Programming, 51, 133-135 (1991) · Zbl 0753.90049 |
| [46] | Zhang, J.; Ma, Z.; Yang, C., A column generation method for inverse shortest paths problems, ZOR Mathematical Methods of Operations Research, 41, 347-358 (1995) · Zbl 0838.90134 |
| [47] | Zhang, J.; Liu, Z.; Ma, Z., On the inverse problem of minimum spanning tree with partition constraints, ZOR Mathematical Methods of Operations Research, 44, 171-188 (1996) · Zbl 0861.90120 |
| [48] | Zhang, J.; Liu, Z., Calculating some inverse linear programming problems, Journal of Computational and Applied Mathematics, 72, 261-273 (1996) · Zbl 0856.65069 |
| [49] | Yang, C.; Zhang, J.; Ma, Z., Inverse maximum flow and minimum cut problems, Optimization, 40, 147-170 (1997) · Zbl 0880.90041 |
| [50] | Zhang, J.; Cai, M. C., Inverse problem of minimum cuts, Mathematical Methods of Operations Research, 47, 51-58 (1998) · Zbl 0941.90013 |
| [51] | Zhang, J.; Liu, Z., A further study on inverse linear programming problems, Journal of Computational and Applied Mathematics, 106, 345-359 (1999) · Zbl 0971.90051 |
| [52] | Ziegler, H., Solving certain singly constrained convex optimization problems in production planning, Operations Research Letters, 1, 246-252 (1982) · Zbl 0497.90029 |
| [53] | Zipkin, P. H., Simple ranking methods for allocation of one resource, Management Science, 26, 34-43 (1980) · Zbl 0448.90049 |
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.
