×

Sensitivity analysis for 0-1 linear programming problems. (Analyse de sensibilité pour les problèmes linéaires en variables 0-1.) (French) Zbl 1092.90031

Summary: This paper is a state of the art on sensitivity analysis for 0-1 linear programming problems. Several aspects are considered: history and forms of sensitivity analysis, application examples, complexity, optimality conditions, existing algorithms and approaches.

MSC:

90C09 Boolean programming
90C31 Sensitivity, stability, parametric optimization
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] E. Balas , An additive algorithm for solving linear programs with zero-one variables . Oper. Res. 13 ( 1965 ) 517 - 546 . MR 183535 | Zbl 0194.19903 · Zbl 0194.19903 · doi:10.1287/opre.13.4.517
[2] D.E Bell and J.F Shapiro , A convergent duality theory for integer programming . Oper. Res. 1 ( 1977 ) 467 - 477 . MR 444000 | Zbl 0355.90051 · Zbl 0355.90051
[3] C. Blair , Sensitivity analysis for knapsack problems: a negative result . Discrete Appl. Math. 81 ( 1998 ) 133 - 139 . MR 1492006 | Zbl 0895.90155 · Zbl 0895.90155 · doi:10.1016/S0166-218X(97)00080-2
[4] P.J. Carstensen , Complexity of some parametric integer and network programming problems . Math. Program. 26 ( 1983 ) 64 - 75 . MR 696727 | Zbl 0585.90065 · Zbl 0585.90065 · doi:10.1007/BF02591893
[5] N. Chakravarti and A.P.M. Wagelmans , Calculation of stability radius for combinatorial optimization problems . Oper. Res. Lett. 23 ( 1999 ) 1 - 7 . MR 1664225 | Zbl 0954.90037 · Zbl 0954.90037 · doi:10.1016/S0167-6377(98)00031-5
[6] W. Cook , A.M.H. Gerards , A. Schrijver and E. Tardos , Sensitivity theorems in integer linear programming . Math. Program. 34 ( 1986 ) 251 - 264 . MR 839604 | Zbl 0648.90055 · Zbl 0648.90055 · doi:10.1007/BF01582230
[7] A. Crema , An algorithm for the multiparametric 0-1 integer linear programming problem relative to the objective function . Eur. J. Oper. Res. 125 ( 2000 ) 18 - 24 . MR 1783192 | Zbl 0972.90049 · Zbl 0972.90049 · doi:10.1016/S0377-2217(99)00193-9
[8] A. Crema , The multiparametric 0-1 integer linear programming problem: A unified approach . Eur. J. Oper. Res. 139 ( 2002 ) 511 - 520 . MR 1893597 | Zbl 1017.90064 · Zbl 1017.90064 · doi:10.1016/S0377-2217(01)00163-1
[9] M. Desrochers and F. Soumis , A reoptimization algorithm for the shortest path problem with time windows . Eur. J. Oper. Res. 35 ( 1988 ) 242 - 254 . MR 939070 | Zbl 0677.90080 · Zbl 0677.90080 · doi:10.1016/0377-2217(88)90034-3
[10] M.L. Fisher , W.D. Northup and J.F. Shapiro , Using duality to solve discrete optimization problems: Theory and computational experience . Math. Prog. Study 3 ( 1975 ) 56 - 94 . MR 444006 | Zbl 0367.90087 · Zbl 0367.90087
[11] M.L. Fisher and J.F. Shapiro , Constructive duality in integer programming . SIAM J. Appl. Math. 27 ( 1974 ) 31 - 52 . MR 351446 | Zbl 0299.90010 · Zbl 0299.90010 · doi:10.1137/0127003
[12] T. Gal and H.J. Greenberg , Advances in sensitivity analysis and parametric programming . Kluwer Academic Publishers, Boston-Dordrecht-London ( 1997 ). Zbl 0881.00025 · Zbl 0881.00025
[13] R.S Garfinkel and G.L. Nemhauser , Integer programming . Wiley, New York ( 1972 ). MR 381688 | Zbl 0259.90022 · Zbl 0259.90022
[14] A.M. Geoffrion and K. Nauss , Parametric and postoptimality analysis in integer linear programming . Manage. Sci. 23 ( 1977 ) 453 - 466 . Zbl 0358.90041 · Zbl 0358.90041 · doi:10.1287/mnsc.23.5.453
[15] E.N. Gordeev , The complexity of stability study in discrete optimization problems . Cybernetics questions 133, computer center of the USSR academy of sciences, Moscow ( 1989 ) 41 - 77 (en russe). Zbl 0701.90077 · Zbl 0701.90077
[16] E.N. Gordeev , Solution stability in a shortest path problem . Discrete Math. 1 ( 1989 ) 45 - 56 (en russe). MR 1044234
[17] H.J. Greenberg , An annoted bibliography for post-solution analysis in mixed integer programming and combinatorial optimization , in Advances in Computational and Stochastic Optimization, Logic Programming and Heuristic Search, edited by D.L. Woodruff. Kluwer Academic Publishers, Boston, MA ( 1998 ) http://carbon.cudenver.edu/ hgreenbe/aboutme/pubrec.html MR 1602329 | Zbl 0914.90204 · Zbl 0914.90204
[18] D. Gusfield , Sensitivity analysis for combinatorial optimization . Memo. No. UCB/ERL M80/22, Electronics Research Laboratory, Univ. of California, Berkeley, California ( 1980 ). · Zbl 0449.05014
[19] D. Gusfield , Parametric combinatorial computing and a problem of program module distribution . J. Association for Computing Machinery 30 ( 1983 ) 551 - 563 . MR 709832 | Zbl 0628.68035 · Zbl 0628.68035 · doi:10.1145/2402.322391
[20] S.V. Hoesel and A. Wagelmans , Sensitivity analysis of the economic lot-sizing problem . Discrete Appl. Math. 45 ( 1993 ) 291 - 312 . MR 1236732 | Zbl 0790.90028 · Zbl 0790.90028 · doi:10.1016/0166-218X(93)90016-H
[21] S.V. Hoesel and A. Wagelmans , On the complexity of postoptimality analysis of 0/1 programs . Discrete Appl. Math. 91 ( 1999 ) 251 - 263 . MR 1670187 | Zbl 0917.90250 · Zbl 0917.90250 · doi:10.1016/S0166-218X(98)00151-6
[22] S. Holm and D. Klein , Three methods for postoptimal analysis in integer linear programming . Math. Prog. Study 21 ( 1984 ) 97 - 109 . MR 751245 | Zbl 0543.90083 · Zbl 0543.90083 · doi:10.1007/BFb0121213
[23] L. Jenkins , Parametric-objective integer programming using knapsack facets and Gomory cutting planes . Eur. J. Oper. Res. 31 ( 1987 ) 102 - 109 . MR 894602 | Zbl 0624.90072 · Zbl 0624.90072 · doi:10.1016/0377-2217(87)90143-3
[24] L. Jenkins , Parametric methods in integer linear programming . Ann. Oper. Res. 27 ( 1990 ) 77 - 96 . MR 1088988 | Zbl 0718.90088 · Zbl 0718.90088 · doi:10.1007/BF02055191
[25] D. Klein and S. Holm , Discrete right hand-side parametrization for linear integer programs . Eur. J. Oper. Res. 2 ( 1978 ) 50 - 53 . Zbl 0384.90090 · Zbl 0384.90090 · doi:10.1016/0377-2217(78)90123-6
[26] D. Klein and S. Holm , Integer programming postoptimal analysis with cutting planes . Manage. Sci. 25 ( 1979 ) 64 - 72 . MR 530939 | Zbl 0442.90067 · Zbl 0442.90067 · doi:10.1287/mnsc.25.1.64
[27] M.Y. Kovalyev and Y.N Sotskov , \(\epsilon \)-approximate solution stability of boolean linear form minimization . Vesti Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 2 2 ( 1990 ) 111 - 116 1990 (en russe). Zbl 0699.49030 · Zbl 0699.49030
[28] V.K. Leontev , Stability in traveling salesman problem . At. i Mat. Fiz. 15 ( 1975 ) 1298 - 1309 (en russe). MR 406446
[29] V.K. Leontev , Stability in combinatorial choice problems . Dokl. Akad. Nauk SSSR 1 ( 1976 ) 23 - 25 (en russe). MR 401489 | Zbl 0356.90043 · Zbl 0356.90043
[30] V.K. Leontev , Stability in linear discrete problems . Cybernet. Probl. 35 ( 1979 ) 169 - 184 (en russe). MR 539891 | Zbl 0439.93040 · Zbl 0439.93040
[31] M. Libura , Sensitivity analysis for integer knapsack problem . Archiwum Automatyki i Telemechanik 22 ( 1977 ) 313 - 322 (en polonais). MR 456461 | Zbl 0365.90097 · Zbl 0365.90097
[32] M. Libura , Optimality conditions and sensitivity analysis for combinatorial optimization problems . Control Cybernet. 25 ( 1996 ) 1165 - 1180 . MR 1454711 | Zbl 0865.90110 · Zbl 0865.90110
[33] M. Libura , E.S. Van der Poort , G. Sierksma and J.A.A. Van der Veen , Stability aspects of the traveling salesman problem based on \(k\)-best solutions . Discrete Appl. Math. 87 ( 1998 ) 159 - 185 . MR 1650435 | Zbl 0910.90264 · Zbl 0910.90264 · doi:10.1016/S0166-218X(98)00055-9
[34] E. Loukakis and A.P. Muhlemann , Parametrisation algorithms for the integer linear programs in binary variables . Eur. J. Oper. Res. 17 ( 1984 ) 104 - 115 . MR 749142 | Zbl 0542.90063 · Zbl 0542.90063 · doi:10.1016/0377-2217(84)90013-4
[35] K. Nauss , Parametric integer programming . Ph.D. thesis, Western Management Science Institute, UCLA ( 1975 ). · Zbl 0453.90054
[36] C.J. Piper and A. Zoltners , Implicit enumeration based algorithms for post-optimising zero-one programs . Naval Res. Logist. Quarterly 22 ( 1975 ) 791 - 809 . MR 434461 | Zbl 0354.90057 · Zbl 0354.90057 · doi:10.1002/nav.3800220413
[37] C.J. Piper and A. Zoltners , Some easy postoptimality analysis for zero-one programming . Manage. Sci. 22 ( 1976 ) 759 - 765 . Zbl 0325.90048 · Zbl 0325.90048 · doi:10.1287/mnsc.22.7.759
[38] G.M. Roodman , Postoptimality analysis in zero-one programming by implicit enumeration . Naval Res. Logist. Quarterly 19 ( 1972 ) 435 - 447 . MR 316089 | Zbl 0262.90047 · Zbl 0262.90047 · doi:10.1002/nav.3800190304
[39] G.M. Roodman , Postoptimality analysis in zero-one programming by implicit enumeration . The mixed integer case. Naval Res. Logist. Quarterly 21 ( 1974 ) 595 - 607 . MR 368756 | Zbl 0304.90078 · Zbl 0304.90078 · doi:10.1002/nav.3800210404
[40] L. Schrage and L. Wolsey , Sensitivity analysis for branch and bound integer programming . Oper. Res. 33 ( 1985 ) 1008 - 1023 . MR 806917 | Zbl 0583.90074 · Zbl 0583.90074 · doi:10.1287/opre.33.5.1008
[41] J.F. Shapiro , Generalized lagrange multipliers in integer programming . Oper. Res. 19 ( 1971 ) 68 - 76 . MR 275877 | Zbl 0226.90031 · Zbl 0226.90031 · doi:10.1287/opre.19.1.68
[42] Y.N. Sotskov , Stability of an optimal schedule . Eur. J. Oper. Res. 55 ( 1991 ) 91 - 102 . Zbl 0755.90048 · Zbl 0755.90048 · doi:10.1016/0377-2217(91)90194-Z
[43] Y.N Sotskov , The stability of the appoximate boolean minimization of a linear form . USSR Comput. Math. Math. Phys. 33 ( 1993 ) 699 - 707 . MR 1218872 | Zbl 0799.90110 · Zbl 0799.90110
[44] Y.N. Sotskov , V.K. Leontev and E.N. Gordeev , Some concepts of stability analysis in combinatorial optimization . Discrete Appl. Math. 58 ( 1995 ) 169 - 190 . MR 1331170 | Zbl 0833.90098 · Zbl 0833.90098 · doi:10.1016/0166-218X(93)E0126-J
[45] Y.N Sotskov , A.P.M. Wagelmans and F. Werner , On the calculation of the stability radius of an optimal or an approximate schedule . Ann. Oper. Res. 83 ( 1998 ) 213 - 252 . MR 1661683 | Zbl 0911.90222 · Zbl 0911.90222 · doi:10.1023/A:1018960030420
[46] R.E. Tarjan , Sensitivity analysis of minimum spanning trees and shortest path trees . Inform. Proc. Lett. 14 ( 1982 ) 30 - 33 . MR 654072
[47] B. Thiongane , Réoptimisation dans le dual lagrangien du biknapsack en variables 0-1 . Thèse de Doctorat en Informatique, Université de Paris 13 ( 2003 ).
[48] B. Thiongane , A. Nagih and G. Plateau , Adapted step size in a 0-1 biknapsack lagrangean dual solving algorithm . En révision pour Ann. Oper. Res. ( 2002 ). · Zbl 1091.90045
[49] B. Thiongane , A. Nagih , and G. Plateau , Lagrangean heuristics combined with reoptimization for the 0-1 biknapsack problem . En révision pour Discrete Appl. Math. ( 2002 ). · Zbl 1111.90096
[50] A.P.M Wagelmans , Sensitivity analysis in combinatorial optimization . Ph.D. thesis, Eramsus University, Rotterdam ( 1990 ).
[51] P. Winter , Steiner problem in networks : A survey . Networks 17 ( 1987 ) 129 - 167 . MR 883025 | Zbl 0646.90028 · Zbl 0646.90028 · doi:10.1002/net.3230170203
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.