Sensitivity Analysis for 0-1 Linear Programming Problems

Babacar Thiongane; Anass Nagih; Gérad Plateau

RAIRO - Operations Research (2010)

  • Volume: 37, Issue: 4, page 291-309
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Thiongane, Babacar, Nagih, Anass, and Plateau, Gérad. "Analyse de sensibilité pour les problèmes linéaires en variables 0-1." RAIRO - Operations Research 37.4 (2010): 291-309. <http://eudml.org/doc/105296>.

@article{Thiongane2010,
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. },
author = {Thiongane, Babacar, Nagih, Anass, Plateau, Gérad},
journal = {RAIRO - Operations Research},
keywords = {Analyse de sensibilité; réoptimisation; rayon de stabilité; problèmes linéaires en 0-1.},
language = {fre},
month = {3},
number = {4},
pages = {291-309},
publisher = {EDP Sciences},
title = {Analyse de sensibilité pour les problèmes linéaires en variables 0-1},
url = {http://eudml.org/doc/105296},
volume = {37},
year = {2010},
}

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
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 4
SP - 291
EP - 309
AB - 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.
LA - fre
KW - Analyse de sensibilité; réoptimisation; rayon de stabilité; problèmes linéaires en 0-1.
UR - http://eudml.org/doc/105296
ER -

References

top
  1. E. Balas, An additive algorithm for solving linear programs with zero-one variables. Oper. Res.13 (1965) 517-546 .  Zbl0194.19903
  2. D.E Bell and J.F Shapiro, A convergent duality theory for integer programming. Oper. Res.1 (1977) 467-477.  
  3. C. Blair, Sensitivity analysis for knapsack problems: a negative result. Discrete Appl. Math.81 (1998) 133-139 .  Zbl0895.90155
  4. P.J. Carstensen, Complexity of some parametric integer and network programming problems. Math. Program.26 (1983) 64-75 .  Zbl0585.90065
  5. N. Chakravarti and A.P.M. Wagelmans, Calculation of stability radius for combinatorial optimization problems. Oper. Res. Lett.23 (1999) 1-7.  Zbl0954.90037
  6. W. Cook, A.M.H. Gerards, A. Schrijver and E. Tardos, Sensitivity theorems in integer linear programming. Math. Program.34 (1986) 251-264 .  Zbl0648.90055
  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 .  Zbl0972.90049
  8. A. Crema, The multiparametric 0-1 integer linear programming problem: A unified approach. Eur. J. Oper. Res.139 (2002) 511-520 .  Zbl1017.90064
  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 .  Zbl0677.90080
  10. M.L. Fisher, W.D. Northup and J.F. Shapiro, Using duality to solve discrete optimization problems: Theory and computational experience. Math. Prog. Study3 (1975) 56-94.  Zbl0367.90087
  11. M.L. Fisher and J.F. Shapiro, Constructive duality in integer programming. SIAM J. Appl. Math.27 (1974) 31-52 .  Zbl0299.90010
  12. T. Gal and H.J. Greenberg, Advances in sensitivity analysis and parametric programming. Kluwer Academic Publishers, Boston-Dordrecht-London (1997).  Zbl0881.00025
  13. R.S Garfinkel and G.L. Nemhauser, Integer programming. Wiley, New York (1972).  Zbl0259.90022
  14. A.M. Geoffrion and K. Nauss, Parametric and postoptimality analysis in integer linear programming. Manage. Sci.23 (1977) 453-466.  Zbl0358.90041
  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).  
  16. E.N. Gordeev, Solution stability in a shortest path problem. Discrete Math.1 (1989) 45-56 (en russe).  
  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) hgreenbe/aboutme/pubrec.html  URIhttp://carbon.cudenver.edu/
  18. D. Gusfield, Sensitivity analysis for combinatorial optimization. Memo. No. UCB/ERL M80/22, Electronics Research Laboratory, Univ. of California, Berkeley, California (1980).  Zbl0449.05014
  19. D. Gusfield, Parametric combinatorial computing and a problem of program module distribution. J. Association for Computing Machinery30 (1983) 551-563 .  Zbl0628.68035
  20. S.V. Hoesel and A. Wagelmans, Sensitivity analysis of the economic lot-sizing problem. Discrete Appl. Math.45 (1993) 291-312 .  Zbl0790.90028
  21. S.V. Hoesel and A. Wagelmans, On the complexity of postoptimality analysis of 0/1 programs. Discrete Appl. Math.91 (1999) 251-263 .  Zbl0917.90250
  22. S. Holm and D. Klein, Three methods for postoptimal analysis in integer linear programming. Math. Prog. Study21 (1984) 97-109.  Zbl0543.90083
  23. L. Jenkins, Parametric-objective integer programming using knapsack facets and Gomory cutting planes. Eur. J. Oper. Res.31 (1987) 102-109 .  Zbl0624.90072
  24. L. Jenkins, Parametric methods in integer linear programming. Ann. Oper. Res.27 (1990) 77-96 .  Zbl0718.90088
  25. D. Klein and S. Holm, Discrete right hand-side parametrization for linear integer programs. Eur. J. Oper. Res.2 (1978) 50-53 .  Zbl0384.90090
  26. D. Klein and S. Holm, Integer programming postoptimal analysis with cutting planes. Manage. Sci.25 (1979) 64-72 .  Zbl0442.90067
  27. M.Y. Kovalyev and Y.N Sotskov, ϵ -approximate solution stability of boolean linear form minimization. Vesti Akad. Navuk BSSR, Ser. Fiz.-Mat. Navuk 22 (1990) 111-116 1990 (en russe).  
  28. V.K. Leontev, Stability in traveling salesman problem. At. i Mat. Fiz.15 (1975) 1298-1309 (en russe).  
  29. V.K. Leontev, Stability in combinatorial choice problems. Dokl. Akad. Nauk SSSR1 (1976) 23-25 (en russe).  
  30. V.K. Leontev, Stability in linear discrete problems. Cybernet. Probl.35 (1979) 169-184 (en russe).  
  31. M. Libura, Sensitivity analysis for integer knapsack problem. Archiwum Automatyki i Telemechanik22 (1977) 313-322 (en polonais).  Zbl0365.90097
  32. M. Libura, Optimality conditions and sensitivity analysis for combinatorial optimization problems. Control Cybernet.25 (1996) 1165-1180 .  Zbl0865.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 .  Zbl0910.90264
  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 .  Zbl0542.90063
  35. K. Nauss, Parametric integer programming. Ph.D. thesis, Western Management Science Institute, UCLA (1975).  Zbl0453.90054
  36. C.J. Piper and A. Zoltners, Implicit enumeration based algorithms for post-optimising zero-one programs. Naval Res. Logist. Quarterly22 (1975) 791-809 .  Zbl0354.90057
  37. C.J. Piper and A. Zoltners, Some easy postoptimality analysis for zero-one programming. Manage. Sci.22 (1976) 759-765.  Zbl0325.90048
  38. G.M. Roodman, Postoptimality analysis in zero-one programming by implicit enumeration. Naval Res. Logist. Quarterly19 (1972) 435-447 .  Zbl0262.90047
  39. G.M. Roodman, Postoptimality analysis in zero-one programming by implicit enumeration. The mixed integer case. Naval Res. Logist. Quarterly21 (1974) 595-607 .  Zbl0304.90078
  40. L. Schrage and L. Wolsey, Sensitivity analysis for branch and bound integer programming. Oper. Res.33 (1985) 1008-1023 .  Zbl0583.90074
  41. J.F. Shapiro, Generalized lagrange multipliers in integer programming. Oper. Res.19 (1971) 68-76 .  Zbl0226.90031
  42. Y.N. Sotskov, Stability of an optimal schedule. Eur. J. Oper. Res.55 (1991) 91-102 .  Zbl0755.90048
  43. Y.N Sotskov, The stability of the appoximate boolean minimization of a linear form. USSR Comput. Math. Math. Phys.33 (1993) 699-707.  
  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 .  Zbl0833.90098
  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 .  Zbl0911.90222
  46. R.E. Tarjan, Sensitivity analysis of minimum spanning trees and shortest path trees. Inform. Proc. Lett.14 (1982) 30-33 .  
  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).  Zbl1091.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).  Zbl1111.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. Networks17 (1987) 129-167 .  Zbl0646.90028

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.