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.
Cet article est un travail de synthèse autour de l'analyse de sensibilité pour les problèmes linéaires en variables 0-1. De nombreux aspects sont ainsi abordés : historique et formes d'analyse de sensibilité, exemples d'application, complexité, conditions d'optimalité, algorithmes et approches. Nous dressons par ailleurs quelques perspectives de recherche actuelles dans ce domaine.
@article{RO_2003__37_4_291_0, author = {Thiongane, Babacar and Nagih, Anass and Plateau, G\'erad}, title = {Analyse de sensibilit\'e pour les probl\`emes lin\'eaires en variables 0-1}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {291--309}, publisher = {EDP-Sciences}, volume = {37}, number = {4}, year = {2003}, doi = {10.1051/ro:2004002}, mrnumber = {2065244}, zbl = {1092.90031}, language = {fr}, url = {http://archive.numdam.org/articles/10.1051/ro:2004002/} }
TY - JOUR AU - Thiongane, Babacar AU - Nagih, Anass AU - Plateau, Gérad TI - Analyse de sensibilité pour les problèmes linéaires en variables 0-1 JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2003 SP - 291 EP - 309 VL - 37 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2004002/ DO - 10.1051/ro:2004002 LA - fr ID - RO_2003__37_4_291_0 ER -
%0 Journal Article %A Thiongane, Babacar %A Nagih, Anass %A Plateau, Gérad %T Analyse de sensibilité pour les problèmes linéaires en variables 0-1 %J RAIRO - Operations Research - Recherche Opérationnelle %D 2003 %P 291-309 %V 37 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2004002/ %R 10.1051/ro:2004002 %G fr %F RO_2003__37_4_291_0
Thiongane, Babacar; Nagih, Anass; Plateau, Gérad. Analyse de sensibilité pour les problèmes linéaires en variables 0-1. RAIRO - Operations Research - Recherche Opérationnelle, Volume 37 (2003) no. 4, pp. 291-309. doi : 10.1051/ro:2004002. http://archive.numdam.org/articles/10.1051/ro:2004002/
[1] An additive algorithm for solving linear programs with zero-one variables. Oper. Res. 13 (1965) 517-546. | MR | Zbl
,[2] A convergent duality theory for integer programming. Oper. Res. 1 (1977) 467-477. | MR | Zbl
and ,[3] Sensitivity analysis for knapsack problems: a negative result. Discrete Appl. Math. 81 (1998) 133-139. | MR | Zbl
,[4] Complexity of some parametric integer and network programming problems. Math. Program. 26 (1983) 64-75. | MR | Zbl
,[5] Calculation of stability radius for combinatorial optimization problems. Oper. Res. Lett. 23 (1999) 1-7. | MR | Zbl
and ,[6] Sensitivity theorems in integer linear programming. Math. Program. 34 (1986) 251-264. | MR | Zbl
, , and ,[7] 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 | Zbl
,[8] The multiparametric 0-1 integer linear programming problem: A unified approach. Eur. J. Oper. Res. 139 (2002) 511-520. | MR | Zbl
,[9] A reoptimization algorithm for the shortest path problem with time windows. Eur. J. Oper. Res. 35 (1988) 242-254. | MR | Zbl
and ,[10] Using duality to solve discrete optimization problems: Theory and computational experience. Math. Prog. Study 3 (1975) 56-94. | MR | Zbl
, and ,[11] Constructive duality in integer programming. SIAM J. Appl. Math. 27 (1974) 31-52. | MR | Zbl
and ,[12] Advances in sensitivity analysis and parametric programming. Kluwer Academic Publishers, Boston-Dordrecht-London (1997). | Zbl
and ,[13] Integer programming. Wiley, New York (1972). | MR | Zbl
and ,[14] Parametric and postoptimality analysis in integer linear programming. Manage. Sci. 23 (1977) 453-466. | Zbl
and ,[15] 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
,[16] Solution stability in a shortest path problem. Discrete Math. 1 (1989) 45-56 (en russe). | MR
,[17] 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 | Zbl
,[18] Sensitivity analysis for combinatorial optimization. Memo. No. UCB/ERL M80/22, Electronics Research Laboratory, Univ. of California, Berkeley, California (1980).
,[19] Parametric combinatorial computing and a problem of program module distribution. J. Association for Computing Machinery 30 (1983) 551-563. | MR | Zbl
,[20] Sensitivity analysis of the economic lot-sizing problem. Discrete Appl. Math. 45 (1993) 291-312. | MR | Zbl
and ,[21] On the complexity of postoptimality analysis of 0/1 programs. Discrete Appl. Math. 91 (1999) 251-263. | MR | Zbl
and ,[22] Three methods for postoptimal analysis in integer linear programming. Math. Prog. Study 21 (1984) 97-109. | MR | Zbl
and ,[23] Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res. 31 (1987) 102-109. | MR | Zbl
,[24] Parametric methods in integer linear programming. Ann. Oper. Res. 27 (1990) 77-96. | MR | Zbl
,[25] Discrete right hand-side parametrization for linear integer programs. Eur. J. Oper. Res. 2 (1978) 50-53. | Zbl
and ,[26] Integer programming postoptimal analysis with cutting planes. Manage. Sci. 25 (1979) 64-72. | MR | Zbl
and ,[27] -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
and ,[28] Stability in traveling salesman problem. At. i Mat. Fiz. 15 (1975) 1298-1309 (en russe). | MR
,[29] Stability in combinatorial choice problems. Dokl. Akad. Nauk SSSR 1 (1976) 23-25 (en russe). | MR | Zbl
,[30] Stability in linear discrete problems. Cybernet. Probl. 35 (1979) 169-184 (en russe). | MR | Zbl
,[31] Sensitivity analysis for integer knapsack problem. Archiwum Automatyki i Telemechanik 22 (1977) 313-322 (en polonais). | MR | Zbl
,[32] Optimality conditions and sensitivity analysis for combinatorial optimization problems. Control Cybernet. 25 (1996) 1165-1180. | MR | Zbl
,[33] Stability aspects of the traveling salesman problem based on -best solutions. Discrete Appl. Math. 87 (1998) 159-185. | MR | Zbl
, , and ,[34] Parametrisation algorithms for the integer linear programs in binary variables. Eur. J. Oper. Res. 17 (1984) 104-115. | MR | Zbl
and ,[35] Parametric integer programming. Ph.D. thesis, Western Management Science Institute, UCLA (1975).
,[36] Implicit enumeration based algorithms for post-optimising zero-one programs. Naval Res. Logist. Quarterly 22 (1975) 791-809. | MR | Zbl
and ,[37] Some easy postoptimality analysis for zero-one programming. Manage. Sci. 22 (1976) 759-765. | Zbl
and ,[38] Postoptimality analysis in zero-one programming by implicit enumeration. Naval Res. Logist. Quarterly 19 (1972) 435-447. | MR | Zbl
,[39] Postoptimality analysis in zero-one programming by implicit enumeration. The mixed integer case. Naval Res. Logist. Quarterly 21 (1974) 595-607. | MR | Zbl
,[40] Sensitivity analysis for branch and bound integer programming. Oper. Res. 33 (1985) 1008-1023. | MR | Zbl
and ,[41] Generalized lagrange multipliers in integer programming. Oper. Res. 19 (1971) 68-76. | MR | Zbl
,[42] Stability of an optimal schedule. Eur. J. Oper. Res. 55 (1991) 91-102. | Zbl
,[43] The stability of the appoximate boolean minimization of a linear form. USSR Comput. Math. Math. Phys. 33 (1993) 699-707. | MR | Zbl
,[44] Some concepts of stability analysis in combinatorial optimization. Discrete Appl. Math. 58 (1995) 169-190. | MR | Zbl
, and ,[45] On the calculation of the stability radius of an optimal or an approximate schedule. Ann. Oper. Res. 83 (1998) 213-252. | MR | Zbl
, and ,[46] Sensitivity analysis of minimum spanning trees and shortest path trees. Inform. Proc. Lett. 14 (1982) 30-33. | MR
,[47] Réoptimisation dans le dual lagrangien du biknapsack en variables 0-1. Thèse de Doctorat en Informatique, Université de Paris 13 (2003).
,[48] Adapted step size in a 0-1 biknapsack lagrangean dual solving algorithm. En révision pour Ann. Oper. Res. (2002). | MR | Zbl
, and ,[49] Lagrangean heuristics combined with reoptimization for the 0-1 biknapsack problem. En révision pour Discrete Appl. Math. (2002). | Zbl
, , and ,[50] Sensitivity analysis in combinatorial optimization. Ph.D. thesis, Eramsus University, Rotterdam (1990).
,[51] Steiner problem in networks : A survey. Networks 17 (1987) 129-167. | MR | Zbl
,Cited by Sources: