Skip to main content
Top

2020 | OriginalPaper | Chapter

3. Multi-parametric Linear and Mixed Integer Linear Programming Under Global Uncertainty

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this chapter, two algorithms for the exact explicit solution of mp-(MI)LPs under global uncertainty are presented. The algorithms comprise of two key steps: (i) analytical solution of the problem’s KKT system with the uncertain parameters and the integer variables treated as symbols using \(Gr\ddot{o}bner\) Bases and (ii) the computation of the related possibly non-convex and discontinuous CRs using Cylindrical Algebraic Decompositions on the parametric space. Problems related to process synthesis and scheduling highlight the potential of the proposed work while for the first time the functional nature of the explicit solution is theoretically characterised and proven.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
2
Details about the related case study and its explicit solution can be found in Charitopoulos et al. [30].
 
Literature
1.
go back to reference Acevedo J, Pistikopoulos EN (1997) A multiparametric programming approach for linear process engineering problems under uncertainty. Ind Eng Chem Res 36(3):717–728CrossRef Acevedo J, Pistikopoulos EN (1997) A multiparametric programming approach for linear process engineering problems under uncertainty. Ind Eng Chem Res 36(3):717–728CrossRef
2.
go back to reference Pistikopoulos EN, Dua V (1998) Planning under uncertainty: a parametric optimization approach. In: 3rd international conference on foundations of computer-aided process operations. AIChE Pistikopoulos EN, Dua V (1998) Planning under uncertainty: a parametric optimization approach. In: 3rd international conference on foundations of computer-aided process operations. AIChE
3.
go back to reference Ryu J-H, Dua V, Pistikopoulos EN (2007) Proactive scheduling under uncertainty: a parametric optimization approach. Ind Eng Chem Res 46(24):8044–8049CrossRef Ryu J-H, Dua V, Pistikopoulos EN (2007) Proactive scheduling under uncertainty: a parametric optimization approach. Ind Eng Chem Res 46(24):8044–8049CrossRef
4.
go back to reference Jia Z, Ierapetritou MG (2006) Uncertainty analysis on the righthand side for MILP problems. AIChE J 52(7):2486–2495CrossRef Jia Z, Ierapetritou MG (2006) Uncertainty analysis on the righthand side for MILP problems. AIChE J 52(7):2486–2495CrossRef
5.
go back to reference Li Z, Ierapetritou MG (2007) Process scheduling under uncertainty using multiparametric programming. AIChE J 53(12):3183–3203CrossRef Li Z, Ierapetritou MG (2007) Process scheduling under uncertainty using multiparametric programming. AIChE J 53(12):3183–3203CrossRef
6.
go back to reference Oberdieck R, Diangelakis NA, Papathanasiou MM, Nascu I, Pistikopoulos EN (2016) Pop–parametric optimization toolbox. Ind Eng Chem Res 55(33):8979–8991 Oberdieck R, Diangelakis NA, Papathanasiou MM, Nascu I, Pistikopoulos EN (2016) Pop–parametric optimization toolbox. Ind Eng Chem Res 55(33):8979–8991
7.
go back to reference Acevedo J, Pistikopoulos EN (1999) An algorithm for multiparametric mixed-integer linear programming problems. Oper Res Lett 24(3):139–148CrossRef Acevedo J, Pistikopoulos EN (1999) An algorithm for multiparametric mixed-integer linear programming problems. Oper Res Lett 24(3):139–148CrossRef
8.
go back to reference Dua V, Pistikopoulos EN (2000) An algorithm for the solution of multiparametric mixed integer linear programming problems. Ann Oper Res 99(1–4):123–139CrossRef Dua V, Pistikopoulos EN (2000) An algorithm for the solution of multiparametric mixed integer linear programming problems. Ann Oper Res 99(1–4):123–139CrossRef
10.
go back to reference Faísca NP, Kosmidis VD, Rustem B, Pistikopoulos EN (2009) Global optimization of multi-parametric MILP problems. J Global Optim 45(1):131–151CrossRef Faísca NP, Kosmidis VD, Rustem B, Pistikopoulos EN (2009) Global optimization of multi-parametric MILP problems. J Global Optim 45(1):131–151CrossRef
11.
go back to reference Wittmann-Hohlbein M, Pistikopoulos EN (2012) On the global solution of multi-parametric mixed integer linear programming problems. J Global Optim 57(1):51–73CrossRef Wittmann-Hohlbein M, Pistikopoulos EN (2012) On the global solution of multi-parametric mixed integer linear programming problems. J Global Optim 57(1):51–73CrossRef
12.
go back to reference Oberdieck R, Wittmann-Hohlbein M, Pistikopoulos EN (2014) A branch and bound method for the solution of multiparametric mixed integer linear programming problems. J Global Optim 59(2–3):527–543CrossRef Oberdieck R, Wittmann-Hohlbein M, Pistikopoulos EN (2014) A branch and bound method for the solution of multiparametric mixed integer linear programming problems. J Global Optim 59(2–3):527–543CrossRef
13.
go back to reference Buchberger B (2001) Gröbner bases and systems theory. Multidimens Syst Signal Process 12(3–4):223–251CrossRef Buchberger B (2001) Gröbner bases and systems theory. Multidimens Syst Signal Process 12(3–4):223–251CrossRef
14.
go back to reference Charitopoulos VM, Dua V (2016) Explicit model predictive control of hybrid systems and multiparametric mixed integer polynomial programming. AIChE J 62(9):3441–3460CrossRef Charitopoulos VM, Dua V (2016) Explicit model predictive control of hybrid systems and multiparametric mixed integer polynomial programming. AIChE J 62(9):3441–3460CrossRef
15.
go back to reference Jirstrand M (1995) Cylindrical algebraic decomposition-an introduction. Linköping University, Linköping Jirstrand M (1995) Cylindrical algebraic decomposition-an introduction. Linköping University, Linköping
16.
go back to reference Strzebonski A (2000) Solving systems of strict polynomial inequalities. J Symb Comput 29(3):471–480CrossRef Strzebonski A (2000) Solving systems of strict polynomial inequalities. J Symb Comput 29(3):471–480CrossRef
17.
go back to reference Wolfram (2014) Mathematica 10.0, 1998-2014 Wolfram research Wolfram (2014) Mathematica 10.0, 1998-2014 Wolfram research
18.
go back to reference Khalilpour R, Karimi I (2014) Parametric optimization with uncertainty on the left hand side of linear programs. Comput Chem Eng 60:31–40CrossRef Khalilpour R, Karimi I (2014) Parametric optimization with uncertainty on the left hand side of linear programs. Comput Chem Eng 60:31–40CrossRef
19.
go back to reference Bellman R (1997) Introduction to matrix analysis, vol 19. SIAM, Philadelphia Bellman R (1997) Introduction to matrix analysis, vol 19. SIAM, Philadelphia
20.
go back to reference Gueddar T, Dua V (2012) Approximate multi-parametric programming based B&B algorithm for MINLPs. Comput Chem Eng 42:288–297CrossRef Gueddar T, Dua V (2012) Approximate multi-parametric programming based B&B algorithm for MINLPs. Comput Chem Eng 42:288–297CrossRef
21.
go back to reference Dua V (2015) Mixed integer polynomial programming. Comput Chem Eng 72:387–394CrossRef Dua V (2015) Mixed integer polynomial programming. Comput Chem Eng 72:387–394CrossRef
22.
go back to reference Charitopoulos VM, Papageorgiou LG, Dua V (2017) Nonlinear model-based process operation under uncertainty using exact parametric programming. Engineering 3(2):202–213CrossRef Charitopoulos VM, Papageorgiou LG, Dua V (2017) Nonlinear model-based process operation under uncertainty using exact parametric programming. Engineering 3(2):202–213CrossRef
23.
go back to reference Charitopoulos VM, Papageorgiou LG, Dua V (2017) Multi-parametric linear programming under global uncertainty. AIChE J 63(9):3871–3895CrossRef Charitopoulos VM, Papageorgiou LG, Dua V (2017) Multi-parametric linear programming under global uncertainty. AIChE J 63(9):3871–3895CrossRef
24.
go back to reference Gal T (1995) Postoptimal analyses, parametric programming and related topics. Walter de Gruyter, Berlin Gal T (1995) Postoptimal analyses, parametric programming and related topics. Walter de Gruyter, Berlin
25.
go back to reference Dinkelbach W (1970) Sensitivitätsanalysen und parametrische programmierung. J Appl Math Mech 50(6):434–435 Dinkelbach W (1970) Sensitivitätsanalysen und parametrische programmierung. J Appl Math Mech 50(6):434–435
26.
go back to reference Buchberger B, Winkler F (1998) Gröbner bases and applications, vol 251. Cambridge University Press, Cambridge Buchberger B, Winkler F (1998) Gröbner bases and applications, vol 251. Cambridge University Press, Cambridge
27.
go back to reference McCarl B, Meeraus A, Van der Eijk P (2012) Mccarl expanded GAMS user guide version 23:6 McCarl B, Meeraus A, Van der Eijk P (2012) Mccarl expanded GAMS user guide version 23:6
28.
go back to reference Wittmann-Hohlbein M, Pistikopoulos EN (2012) A two-stage method for the approximate solution of general multiparametric mixed-integer linear programming problems. Ind Eng Chem Res 51(23):8095–8107CrossRef Wittmann-Hohlbein M, Pistikopoulos EN (2012) A two-stage method for the approximate solution of general multiparametric mixed-integer linear programming problems. Ind Eng Chem Res 51(23):8095–8107CrossRef
29.
go back to reference Biegler LT, Grossmann IE, Westerberg AW (1997) Systematic methods for chemical process design. Prentice Hall, Old Tappan Biegler LT, Grossmann IE, Westerberg AW (1997) Systematic methods for chemical process design. Prentice Hall, Old Tappan
30.
go back to reference Charitopoulos VM, Papageorgiou LG, Dua V (2018) Multi-parametric mixed integer linear programming under global uncertainty. Comput Chem Eng Charitopoulos VM, Papageorgiou LG, Dua V (2018) Multi-parametric mixed integer linear programming under global uncertainty. Comput Chem Eng
31.
go back to reference Fousse L, Hanrot G, Lefèvre V, Pélissier P, Zimmermann P (2007) MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans Math Softw 33(2):13CrossRef Fousse L, Hanrot G, Lefèvre V, Pélissier P, Zimmermann P (2007) MPFR: A multiple-precision binary floating-point library with correct rounding. ACM Trans Math Softw 33(2):13CrossRef
Metadata
Title
Multi-parametric Linear and Mixed Integer Linear Programming Under Global Uncertainty
Author
Dr. Vassilis M. Charitopoulos
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-38137-0_3