Skip to main content
SpringerLink
Log in

On the global solution of multi-parametric mixed integer linear programming problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

This paper deals with the global solution of the general multi-parametric mixed integer linear programming problem with uncertainty in the entries of the constraint matrix, the right-hand side vector, and in the coefficients of the objective function. To derive the piecewise affine globally optimal solution, the steps of a multi-parametric branch-and-bound procedure are outlined, where McCormick-type relaxations of bilinear terms are employed to construct suitable multi-parametric under- and overestimating problems. The alternative of embedding novel piecewise affine relaxations of bilinear terms in the proposed algorithmic procedure is also discussed.

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. Acevedo J., Pistikopoulos E.N.: A parametric MINLP algorithm for process synthesis problems under uncertainty. Ind. Eng. Chem. Res. 35(1), 147–158 (1996)

    Article  Google Scholar 

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

    Article  Google Scholar 

  3. Acevedo J., Salgueir M.: An efficient algorithm for convex multiparametric nonlinear programming problems. Ind. Eng. Chem. Res. 42(23), 5883–5890 (2003)

    Article  Google Scholar 

  4. Al-Khayyal F.A.: Jointly constrained bilinear programs and related problems: an overview. Comput. Math. Appl. 19(11), 53–62 (1990)

    Article  Google Scholar 

  5. Bemporad A., Filippi C.: An algorithm for approximate multiparametric convex programming. Comput. Opt. Appl. 35(1), 87–108 (2006)

    Article  Google Scholar 

  6. Bemporad A., Morari M., Dua V., Pistikopoulos E.: The explicit linear quadratic regulator for constrained systems. Automatica 39(10), 1845–1846 (2003)

    Article  Google Scholar 

  7. Benson H.P.: Algorithms for parametric nonconvex programming. J. Optim. Theory Appl. 38, 319–340 (1982)

    Article  Google Scholar 

  8. Borrelli F., Bemporad A., Morari M.: Geometric algorithm for multiparametric linear programming. J. Optim. Theory Appl. 118(3), 515–540 (2003)

    Article  Google Scholar 

  9. Dinkelbach W.: Sensitivitatsanalysen und Parametrische Programmierung. Springer, Berlin (1969)

    Book  Google Scholar 

  10. Domínguez L.F., Narcisco D.A., Pistikopoulos E.N.: Recent advances in multiparametric nonlinear programming. Comput. Chem. Eng. 34(5), 707–716 (2010)

    Article  Google Scholar 

  11. Dua V., Bozinis A., Pistikopoulos E.N.: A multiparametric programming approach for mixed-integer quadratic engineering problems. Comput. Chem. Eng. 26, 715–733 (2002)

    Article  Google Scholar 

  12. Dua V., Papalexandri K.P., Pistikopoulos E.N.: Global optimization issues in multiparametric continuous and mixed-integer optimization problems. J. Glob. Opt. 30(1), 59–89 (2004)

    Article  Google Scholar 

  13. Dua V., Pistikopoulos E.N.: Algorithms for the solution of multiparametric mixed-integer nonlinear optimization problems. Ind. Eng. Chem. Res. 38(10), 3976–3987 (1999)

    Article  Google Scholar 

  14. Dua V., Pistikopoulos E.N.: An algorithm for the solution of multiparametric mixed integer linear programming problems. Ann. Oper. Res. 99(1–4), 123–139 (2000)

    Article  Google Scholar 

  15. Faísca N.P., Kosmidis V.D., Rustem B., Pistikopoulos E.N.: Global optimization of multi-parametric MILP problems. J. Glob. Opt. 45(1), 131–151 (2009)

    Article  Google Scholar 

  16. Fiacco A., Kyparisis J.: Convexity and concavity properties of the optimal value function in parametric nonlinear-programming. J. Optim. Theory Appl. 48(1), 95–126 (1986)

    Google Scholar 

  17. Fiacco A.V.: Global multi-parametric optimal value bounds and solution estimates for separable parametric programs. Ann. Oper. Res. 27(1), 381–395 (1990)

    Article  Google Scholar 

  18. Filippi C.: An algorithm for approximate multiparametric linear programming. J. Optim. Theory Appl. 120(1), 73–95 (2004)

    Article  Google Scholar 

  19. Floudas C.A.: Deterministic Global Optimization: Theory, Methods, and Applications. Springer, Berlin (2000)

    Book  Google Scholar 

  20. Gal T.: Rim multiparametric linear programming. Manag. Sci. 21(5), 567–575 (1975)

    Article  Google Scholar 

  21. Gal T.: Postoptimal Analyses, Parametric Programming, and Related Topics: Degeneracy, Multicriteria Decision Making, Redundancy. W. de Gruyter, Berlin (1995)

    Google Scholar 

  22. Gal T., Nedoma J.: Multiparametric linear programming. Math. Program. Stud. 18, 406–422 (1972)

    Google Scholar 

  23. Gounaris C.E., Misener R., Floudas C.A.: Computational comparison of piecewise linear relaxations for pooling problems. Ind. Eng. Chem. Res. 48(12), 5742–5766 (2009)

    Article  Google Scholar 

  24. Hasan M.M.F., Karimi I.A.: Piecewise linear relaxation of bilinear programs using bivariate partitioning. AIChE J. 56(7), 1880–1893 (2010)

    Article  Google Scholar 

  25. Horst R., Pardalos P.M., Thoai N.V.: Introduction to Gobal Optimization. Springer, Berlin (2000)

    Google Scholar 

  26. Janak S., Janak S., Floudas C.: A new robust optimization approach for scheduling under uncertainty: II. Uncertainty with known probability distribution. Comput. Chem. Eng. 31(3), 171–195 (2007)

    Article  Google Scholar 

  27. Kvasnica, M., Grieder, P.: M.B.: Multi-Parametric Toolbox (MPT), http://control.ee.ethz.ch/mpt/

  28. Li Z., Ierapetritou M.G.: A new methodology for the general multiparametric mixed-integer linear programming MILP problems. Ind. Eng. Chem. Res. 46(15), 5141–5151 (2007)

    Article  Google Scholar 

  29. Li Z., Ierapetritou M.G.: Process scheduling under uncertainty using multiparametric programming. AIChE J. 53(12), 3183–3203 (2007)

    Article  Google Scholar 

  30. Li Z., Ierapetritou M.G.: Process scheduling under uncertainty: review and challenges. Comput. Chem. Eng. 32(4-5), 715–727 (2008)

    Article  Google Scholar 

  31. Li Z., Ierapetritou M.G.: Robust optimization for process scheduling under uncertainty. Ind. Eng. Chem. Res. 47(12), 4148–4157 (2008)

    Article  Google Scholar 

  32. Lin X., Janak S., Floudas C.: A new robust optimization approach for scheduling under uncertainty: I. Bounded uncertainty. Comput. Chem. Eng. 28(6), 1069–1085 (2004)

    Article  Google Scholar 

  33. McCormick G.P.: Computability of global solutions to factorable nonconvex programs: Part I: Convex underestimating problems. Math. Program. 10(1), 147–175 (1976)

    Article  Google Scholar 

  34. Misener R., Thompson J.P., Floudas C.A.: APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chem. Eng. 35(5), 876–892 (2011)

    Article  Google Scholar 

  35. Mitsos, A., Barton, P.I.: Parametric mixed-integer 0-1 linear programming: The general case for a single parameter. Eur. J. Operat. Res. 194(3), 663–686

  36. Pardalos P.M., Coleman T.F.: Lectures on Global Optimization. American Mathematical Soc, Providence (2009)

    Google Scholar 

  37. ParOS: Parametric optimization solutions ltd (http://www.parostech.co.uk)

  38. Pertsinidis A., Grossmann I.E., McRae G.J.: Parametric optimization of MILP programs and a framework for the parametric optimization of MINLPs. Comput. Chem. Eng. 22(Supplement 1), 205–212 (1998)

    Article  Google Scholar 

  39. Pistikopoulos E.N., Georgiadis M., Dua V.: Multi-Parametric Model-Based Control Vol. 2: Theory and Applications. Wiley-VCH, UK (2007)

    Book  Google Scholar 

  40. Ryu J., Pistikopoulos E.N.: A novel approach to scheduling of zero-wait batch processes under processing time variations. Comput. Chem. Eng. 31(3), 101–106 (2007)

    Article  Google Scholar 

  41. Ryu J., Vivek D., Pistikopoulos E.N.: Proactive scheduling under uncertainty: a parametric optimization approach. Ind. Eng. Chem. Res. 46(24), 8044–8049 (2007)

    Article  Google Scholar 

  42. Sahinidis, N., Tawarmalani, M.: Gams/Baron 5.0: Global optimization of mixed-integer nonlinear programs

  43. Tondel P., Johansen T.A., Bemporad A.: An algorithm for multi-parametric quadratic programming and explicit mpc solutions. Automatica 39(3), 489–497 (2003)

    Article  Google Scholar 

  44. Verderame P.M., Elia J.A., Li J., Floudas C.A.: Planning and scheduling under uncertainty: a review across multiple sectors. Ind. Eng. Chem. Res. 49(9), 3993–4017 (2010)

    Article  Google Scholar 

  45. Wicaksono D.S., Karimi I.A.: Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE J. 54(4), 991–1008 (2008)

    Article  Google Scholar 

  46. Wittmann-Hohlbein, M., Pistikopoulos, E.N.: A two-stage method for the approximate solution of general multi-parametric mixed-integer linear programming (mp-MILP) problems (submitted)

Download references

Author information

Authors and Affiliations

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

    Martina Wittmann-Hohlbein & Efstratios N. Pistikopoulos

Authors
  1. Martina Wittmann-Hohlbein
    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

Corresponding author

Correspondence to Martina Wittmann-Hohlbein.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wittmann-Hohlbein, M., Pistikopoulos, E.N. On the global solution of multi-parametric mixed integer linear programming problems. J Glob Optim 57, 51–73 (2013). https://doi.org/10.1007/s10898-012-9895-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-012-9895-2

Keywords

Mathematics Subject Classification

Search

Navigation