Skip to main content
SpringerLink
Log in

An Algorithm for the Solution of Multiparametric Mixed Integer Linear Programming Problems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

In this paper, we present an algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems involving (i) 0-1 integer variables, and, (ii) more than one parameter, bounded between lower and upper bounds, present on the right hand side (RHS) of constraints. The solution is approached by decomposing the mp-MILP into two subproblems and then iterating between them. The first subproblem is obtained by fixing integer variables, resulting in a multiparametric linear programming (mp-LP) problem, whereas the second subproblem is formulated as a mixed integer linear programming (MILP) problem by relaxing the parameters as variables.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Acevedo and E.N. Pistikopoulos, A parametric MINLP algorithm for process synthesis problems under uncertainty, Ind. Eng. Chem. Res. 35 (1996) 147–158.

    Google Scholar 

  2. J. Acevedo and E.N. Pistikopoulos, A multiparametric programming approach for linear process engineering problems under uncertainty, Ind. Eng. Chem. Res. 36 (1997) 717.

    Google Scholar 

  3. J. Acevedo and E.N. Pistikopoulos, An algorithm for multiparametric mixed-integer linear programming problems, Operations Research Letters 24 (1999) 139–148.

    Google Scholar 

  4. M.G. Bailey and B.E. Gillet, Parametric integer programming analysis: a contraction approach, J. Oper. Res. 31 (1980) 257–262.

    Google Scholar 

  5. C. Blair, Integer and mixed-integer programming, in: Advances in Sensitivity Analysis and Parametric Programming, eds. T. Gal and H.J. Greenberg (Kluwer Academic, Dordrecht, The Netherlands, 1997).

    Google Scholar 

  6. A. Brooke, D. Kendrick and A. Meeraus, GAMS: A Users Guide (Scientific Press, California, 1988).

    Google Scholar 

  7. P.J. Carstensen, Complexity of some parametric integer and network programming problems, Mathematical Programming 26 (1983) 64–75.

    Google Scholar 

  8. V. Chankong, Y.Y. Haimes and D.M. Gemperline, A multiobjective dynamic programming method for capacity expansion, IEEE Transactions on Automatic Control 26 (1981) 1195–1207.

    Google Scholar 

  9. G.B. Dantzig, Linear Programming and Extensions (Princeton Univ. Press, NJ, 1963).

    Google Scholar 

  10. J. Dauer and Y.-H. Liu, Multi-criteria and goal programming, in: Advances in Sensitivity Analysis and Parametric Programming, eds. T. Gal and H.J. Greenberg (Kluwer Academic, Dordrecht, The Netherlands, 1997).

    Google Scholar 

  11. G.W. Evans, An overview of techniques for solving multiobjective mathematical programs, Management Science 30 (1984) 1268–1282.

    Google Scholar 

  12. R. Evren, Interactive compromise programming, J. Opl. Res. Soc. 38 (1987) 163–172.

    Google Scholar 

  13. A.V. Fiacco, Introduction to Sensitivity Analysis in Nonlinear Programming (Academic Press, New York, 1983).

    Google Scholar 

  14. T. Gal, Postoptimal Analyses, Parametric Programming, and Related Topics (de Gruyter, New York, 1995).

    Google Scholar 

  15. T. Gal and J. Nedoma, Multiparametric linear programming, Management Science 18 (1972) 406–422.

    Google Scholar 

  16. N. Ganesh and L.T. Biegler, A reduced Hessian strategy for sensitivity analysis of optimal flowsheets, AIChE J. 33 (1987) 282.

  17. A.M. Geoffrion, J.S. Dyer and A. Feinberg, An interactive approach for multi-criterion optimization with an application to the operation of an academic department, Management Science 19 (1972) 357–367.

    Google Scholar 

  18. A.M. Geoffrion and G.W. Graves, Multicommodity distribution system design by Benders decomposition, Management Science 20 (1974) 822–844.

    Google Scholar 

  19. A.M. Geoffrion and R. Nauss, Parametric and postoptimality analysis in integer linear programming, Management Science 23 (1977) 453.

    Google Scholar 

  20. S. Holm and D. Klein, Discrete right hand side parametrization for linear integer programs, Europ. J. Oper. Res. 2 (1978) 50–53.

    Google Scholar 

  21. S. Holm and D. Klein, Three methods for post-optimal analysis in integer linear programming, Math. Prog. Study 21 (1984) 97.

    Google Scholar 

  22. B. Jansen, J.J. de Jong, C. Roos and T. Terlaky, Sensitivity analysis in linear programming: just be careful, Europ. J. Oper. Res. 101 (1997) 15–28.

    Google Scholar 

  23. L. Jenkins, Parametric mixed integer programming: an application to solid waste management, Management Science 28 (1982) 1270–1284.

    Google Scholar 

  24. L. Jenkins, Parametric methods in integer linear programming, Annals of Operations Research 27 (1990) 77.

    Google Scholar 

  25. P. Korhonen, J. Wallenius and S. Zionts, Solving the discrete multiple criteria problems using convex cones, Management Science 30 (1984) 1336–1345.

    Google Scholar 

  26. D. Li and Y.Y. Haimes, Hierarchical generating method for large-scale multiobjective systems, J. Optimization Theory and Applications 54 (1987) 303–333.

    Google Scholar 

  27. G.V. Loganathan and H.D. Sherali, A convergent interactive cutting-plane algorithm for multiobjective optimization, Operations Research 35 (1987) 365–377.

    Google Scholar 

  28. E. Loukakis and A.P. Muhlemann, Parameterisation algorithms for the integer linear programs in binary variables, Europ. J. Oper. Res. 17 (1984) 104–115.

    Google Scholar 

  29. L. Lovász, Certain duality principles in integer programming, Annals of Discr. Math. 1 (1977) 363–374.

    Google Scholar 

  30. T.J. Lowe, J.-F. Thisse, J.E. Ward and R.E. Wendell, On efficient solutions to multiple objective mathematical programs, Management Science 30 (1984) 1346–1349.

    Google Scholar 

  31. O. Marcotte and R.M. Soland, An interactive branch-and-bound algorithm for multiple criteria optimization, Management Science 32 (1986) 61–75.

    Google Scholar 

  32. R.E. Marsten and T.L. Morin, Parametric integer programming: the right-hand side case, Annals of Discr. Math. 1 (1977) 375–390.

    Google Scholar 

  33. K.G. Murty, Computational complexity of parametric linear programming, Mathematical Programming 19 (1980) 213–219.

    Google Scholar 

  34. K.G. Murty, Linear Programming (Wiley, New York, USA, 1983).

    Google Scholar 

  35. N. Nishida and Y. Ohtake, A method for solution of the bicriterion mixed integer programming problems, Computers and Chemical Engineering 10 (1986) 119–122.

    Google Scholar 

  36. Y. Ohtake and N. Nishida, A branch and bound algorithm for 0–1 parametric mixed-integer programming, Oper. Res. Lett. 4 (1985) 41.

    Google Scholar 

  37. A. Palazoglu and Y. Arkun, A multiobjective approach to design chemical plants with robust dynamic operability characteristics, Computers and Chemical Engineering 10 (1986) 567–575.

    Google Scholar 

  38. K.P. Papalexandri and T.I. Dimkou, A parametric mixed-integer optimization algorithm for multiobjective engineering problems involving discrete decisions, Ind. Eng. Chem. Res. 37 (1998) 1866–1882.

    Google Scholar 

  39. S.A. Papoulias and I.E. Grossmann, A structural optimization approach in process synthesis-I: Utility systems, Computers and Chemical Engineering 7 (1983) 695.

  40. A. Pertsinidis, On the parametric optimization of mathematical programs with binary variables and its application in the chemical engineering process synthesis., Ph.D. dissertation, Carnegie-Mellon University, Pittsburgh (1992).

  41. A. Pertsinidis, I.E. Grossmann and G.J. McRae, Parametric optimization of MILP programs and a framework for the parametric optimization of MINLPs, Computers and Chemical Engineering 22 Suppl. (1998) S 205.

  42. C.J. Piper and A.A. Zoltners, Some easy postoptimality analysis for zero-one programming, Management Science 22 (1976) 759–765.

    Google Scholar 

  43. G.M. Roodman, Postoptimality analysis in zero-one programming by implicit enumeration, Naval Res. Log. Quarterly 19 (1972) 435–447.

    Google Scholar 

  44. G.M. Roodman, Postoptimality analysis in integer programming by implicit enumeration: The mixed integer case, Naval Res. Log. Quarterly 21 (1974) 595.

    Google Scholar 

  45. P. Seferlis and A.N. Hrymak, Sensitivity analysis for chemical process optimization, Computers and Chemical Engineering 20 (1996) 1177.

    Google Scholar 

  46. J.F. Shapiro, Sensitivity analysis in integer programming, Annals of Discr. Math. 1 (1977) 467–477.

    Google Scholar 

  47. Y. Shimizu, Optimization of radioactive waste management system by application of multiobjective linear programming, J. Nuclear Sci. Tech. 18 (1981) 773–784.

    Google Scholar 

  48. A. Sophos, E. Rotstein and G. Stephanopoulos, Multiobjective analysis in modeling the petrochemical industry, Chemical Engineering Science 35 (1980) 2415–2426.

    Google Scholar 

  49. T. Tanino, Sensitivity analysis in multiobjective optimization, J. Optimization Theory and Applications 56 (1988) 479–499.

    Google Scholar 

  50. T. Tanino and Y. Sawaragi, Duality theory in multiobjective programming, J. Optimization Theory and Applications 27 (1979) 509–529.

    Google Scholar 

  51. G.K. Tayi, Sensitivity analysis of mixed integer programs: an application to environmental policy making, Europ. J. Oper. Res. 22 (1985) 224–233.

    Google Scholar 

  52. J. Teghem Jr., A survey of techniques for finding efficient solutions to multi-objective integer linear programming, Asia-Pacific J. Oper. Res. 3 (1986) 95–108.

    Google Scholar 

  53. A. Turgeon, An application of parametric mixed-integer linear programming to hydropower development, Water Resources Res. 23 (1987) 399–407.

    Google Scholar 

  54. A.C. Williams, Marginal values in mixed integer linear programming, Mathematical Programming 44 (1989) 67–75.

    Google Scholar 

  55. H.P. Williams, Duality in mathematics and linear and integer programming, J. Optimization Theory and Applications 90 (1996) 257–278.

    Google Scholar 

  56. H.P. Williams, The equivalence of two theorems of integer programming, Bull. London Math. Soc. 28 (1996) 311–316.

    Google Scholar 

  57. D. Wolbert, X. Joulia, B. Koehret and L.T. Biegler, Flowsheet optimization and optimal sensitivity analysis using analytical derivatives, Computers and Chemical Engineering 18 (1994) 1083.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Chemical Engineering, Centre for Process Systems Engineering, Imperial College, London, SW7 2BY, UK

    Vivek Dua & Efstratios N. Pistikopoulos

Authors
  1. Vivek Dua
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Efstratios N. Pistikopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dua, V., Pistikopoulos, E.N. An Algorithm for the Solution of Multiparametric Mixed Integer Linear Programming Problems. Annals of Operations Research 99, 123–139 (2000). https://doi.org/10.1023/A:1019241000636

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019241000636

Search

Navigation