Hostname: page-component-7bb8b95d7b-dtkg6 Total loading time: 0 Render date: 2024-09-13T18:31:10.120Z Has data issue: false hasContentIssue false
  • English
  • Français

Analyse de sensibilité pour les problèmes linéaires en variables 0-1

Published online by Cambridge University Press:  15 March 2004

Babacar Thiongane ,
Anass Nagih  and
Gérad Plateau
Babacar Thiongane
Affiliation:
LIPN, UMR CNRS 7030, Université de Paris, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse, France; [email protected].
Anass Nagih
Affiliation:
LIPN, UMR CNRS 7030, Université de Paris, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse, France; [email protected].
Gérad Plateau
Affiliation:
LIPN, UMR CNRS 7030, Université de Paris, 99 avenue Jean-Baptiste Clément, 93430 Villetaneuse, France; [email protected].
Get access

Abstract

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.

Keywords

Analyse de sensibilitéréoptimisationrayon de stabilitéproblèmes linéaires en 0-1.
Type
Research Article
Information
RAIRO - Operations Research , Volume 37 , Issue 4: ROADEF 2002 , October 2003 , pp. 291 - 309
Copyright
© EDP Sciences, 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Balas, E., An additive algorithm for solving linear programs with zero-one variables. Oper. Res. 13 (1965) 517-546 . CrossRef
Bell, D.E and Shapiro, J.F, A convergent duality theory for integer programming. Oper. Res. 1 (1977) 467-477.
Blair, C., Sensitivity analysis for knapsack problems: a negative result. Discrete Appl. Math. 81 (1998) 133-139 . CrossRef
Carstensen, P.J., Complexity of some parametric integer and network programming problems. Math. Program. 26 (1983) 64-75 . CrossRef
Chakravarti, N. and Wagelmans, A.P.M., Calculation of stability radius for combinatorial optimization problems. Oper. Res. Lett. 23 (1999) 1-7. CrossRef
Cook, W., Gerards, A.M.H., Schrijver, A. and Tardos, E., Sensitivity theorems in integer linear programming. Math. Program. 34 (1986) 251-264 . CrossRef
Crema, A., An algorithm for the multiparametric 0-1 integer linear programming problem relative to the objective function. Eur. J. Oper. Res. 125 (2000) 18-24 . CrossRef
Crema, A., The multiparametric 0-1 integer linear programming problem: A unified approach. Eur. J. Oper. Res. 139 (2002) 511-520 . CrossRef
Desrochers, M. and Soumis, F., A reoptimization algorithm for the shortest path problem with time windows. Eur. J. Oper. Res. 35 (1988) 242-254 . CrossRef
Fisher, M.L., Northup, W.D. and Shapiro, J.F., Using duality to solve discrete optimization problems: Theory and computational experience. Math. Prog. Study 3 (1975) 56-94. CrossRef
Fisher, M.L. and Shapiro, J.F., Constructive duality in integer programming. SIAM J. Appl. Math. 27 (1974) 31-52 . CrossRef
T. Gal and H.J. Greenberg, Advances in sensitivity analysis and parametric programming. Kluwer Academic Publishers, Boston-Dordrecht-London (1997).
R.S Garfinkel and G.L. Nemhauser, Integer programming. Wiley, New York (1972).
Geoffrion, A.M. and Nauss, K., Parametric and postoptimality analysis in integer linear programming. Manage. Sci. 23 (1977) 453-466. CrossRef
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).
Gordeev, E.N., Solution stability in a shortest path problem. Discrete Math. 1 (1989) 45-56 (en russe).
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
D. Gusfield, Sensitivity analysis for combinatorial optimization. Memo. No. UCB/ERL M80/22, Electronics Research Laboratory, Univ. of California, Berkeley, California (1980).
Gusfield, D., Parametric combinatorial computing and a problem of program module distribution. J. Association for Computing Machinery 30 (1983) 551-563 . CrossRef
Hoesel, S.V. and Wagelmans, A., Sensitivity analysis of the economic lot-sizing problem. Discrete Appl. Math. 45 (1993) 291-312 . CrossRef
Hoesel, S.V. and Wagelmans, A., On the complexity of postoptimality analysis of 0/1 programs. Discrete Appl. Math. 91 (1999) 251-263 . CrossRef
Holm, S. and Klein, D., Three methods for postoptimal analysis in integer linear programming. Math. Prog. Study 21 (1984) 97-109. CrossRef
Jenkins, L., Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res. 31 (1987) 102-109 . CrossRef
Jenkins, L., Parametric methods in integer linear programming. Ann. Oper. Res. 27 (1990) 77-96 . CrossRef
Klein, D. and Holm, S., Discrete right hand-side parametrization for linear integer programs. Eur. J. Oper. Res. 2 (1978) 50-53 .
Klein, D. and Holm, S., Integer programming postoptimal analysis with cutting planes. Manage. Sci. 25 (1979) 64-72 . CrossRef
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).
Leontev, V.K., Stability in traveling salesman problem. At. i Mat. Fiz. 15 (1975) 1298-1309 (en russe).
Leontev, V.K., Stability in combinatorial choice problems. Dokl. Akad. Nauk SSSR 1 (1976) 23-25 (en russe).
Leontev, V.K., Stability in linear discrete problems. Cybernet. Probl. 35 (1979) 169-184 (en russe).
Libura, M., Sensitivity analysis for integer knapsack problem. Archiwum Automatyki i Telemechanik 22 (1977) 313-322 (en polonais).
Libura, M., Optimality conditions and sensitivity analysis for combinatorial optimization problems. Control Cybernet. 25 (1996) 1165-1180 .
Libura, M., Van der Poort, E.S., Sierksma, G. and Van der Veen, J.A.A., Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Appl. Math. 87 (1998) 159-185 . CrossRef
Loukakis, E. and Muhlemann, A.P., Parametrisation algorithms for the integer linear programs in binary variables. Eur. J. Oper. Res. 17 (1984) 104-115 . CrossRef
K. Nauss, Parametric integer programming. Ph.D. thesis, Western Management Science Institute, UCLA (1975).
Piper, C.J. and Zoltners, A., Implicit enumeration based algorithms for post-optimising zero-one programs. Naval Res. Logist. Quarterly 22 (1975) 791-809 . CrossRef
Piper, C.J. and Zoltners, A., Some easy postoptimality analysis for zero-one programming. Manage. Sci. 22 (1976) 759-765. CrossRef
Roodman, G.M., Postoptimality analysis in zero-one programming by implicit enumeration. Naval Res. Logist. Quarterly 19 (1972) 435-447 . CrossRef
Roodman, G.M., Postoptimality analysis in zero-one programming by implicit enumeration. The mixed integer case. Naval Res. Logist. Quarterly 21 (1974) 595-607 . CrossRef
Schrage, L. and Wolsey, L., Sensitivity analysis for branch and bound integer programming. Oper. Res. 33 (1985) 1008-1023 . CrossRef
Shapiro, J.F., Generalized lagrange multipliers in integer programming. Oper. Res. 19 (1971) 68-76 . CrossRef
Sotskov, Y.N., Stability of an optimal schedule. Eur. J. Oper. Res. 55 (1991) 91-102 . CrossRef
Sotskov, Y.N, The stability of the appoximate boolean minimization of a linear form. USSR Comput. Math. Math. Phys. 33 (1993) 699-707.
Sotskov, Y.N., Leontev, V.K. and Gordeev, E.N., Some concepts of stability analysis in combinatorial optimization. Discrete Appl. Math. 58 (1995) 169-190 . CrossRef
Sotskov, Y.N, Wagelmans, A.P.M. and Werner, F., On the calculation of the stability radius of an optimal or an approximate schedule. Ann. Oper. Res. 83 (1998) 213-252 . CrossRef
Tarjan, R.E., Sensitivity analysis of minimum spanning trees and shortest path trees. Inform. Proc. Lett. 14 (1982) 30-33 . CrossRef
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).
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).
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).
A.P.M Wagelmans, Sensitivity analysis in combinatorial optimization. Ph.D. thesis, Eramsus University, Rotterdam (1990).
Winter, P., Steiner problem in networks : A survey. Networks 17 (1987) 129-167 . CrossRef