Extended Mathematical Programming
Algebraic modeling languages like AIMMS, AMPL, GAMS, MPL and others have been developed to facilitate the description of a problem in mathematical terms and to link the abstract formulation with data-management systems on the one hand and appropriate algorithms for solution on the other. Robust algorithms and modeling language interfaces have been developed for a large variety of mathematical programming problems such as linear programs (LPs), nonlinear programs (NPs), Mixed Integer Programs (MIPs), mixed complementarity programs (MCPs) and others. Researchers are constantly updating the types of problems and algorithms that they wish to use to model in specific domain applications.
Extended Mathematical Programming (EMP) is an extension to algebraic modeling languages that facilitates the automatic reformulation of new model types by converting the EMP model into established mathematical programming classes to solve by mature solver algorithms. A number of important problem classes can be solved. Specific examples are variational inequalities, Nash equilibria, disjunctive programs and stochastic programs.
EMP is independent of the modeling language used but currently it is implemented only in GAMS. The new types of problems modeled with EMP are reformulated with the GAMS solver JAMS to well established types of problems and the reformulated models are passed to a suitable GAMS solver to be solved. The core of EMP is a file called emp.info where the annotations that are needed for the reformulations are added to the model.
Equilibrium problems
Equilibrium problems model questions arising in the study of economic equilibria in a mathematically abstract form. Equilibrium problems include Variational Inequalities, problems with Nash Equilibria, and Multiple Optimization Problems with Equilibrium Constraints (MOPECs). Use EMP's keywords to reformulate these problems as mixed complementarity problems (MCPs), a class of problems for which mature solver technology exists. Solve the newly reformulated EMP keyword version of the problem with the PATH solver or other GAMS MCP solvers.
Examples of the use of EMP to solve equilibrium problems include the computation of Cournot–Nash–Walras equilibria..,[1] modeling water allocation,[2][3] long-term planning of transmission line expansion of the electrical grid,[4] modeling risk-averse agents in hydro-thermal electricity markets with uncertain inflows into hydro reservoirs [5] and modeling variational inequalities in energy markets [6]
Hierarchical optimization
Hierarchical optimization problems are mathematical programs with an additional optimization problem in their constraints. A simple example is the bilevel programming problem that optimizes an upper level objective over constraints that include another lower level optimization problem. Bilevel programming is used in many areas. One example is the design of optimal tax instruments. The tax instrument is modeled in the upper level and the clearing market is modeled in the lower level. In general, the lower level problem may be an optimization problem or a variational inequality. Several keywords are provided to facilitate reformulating hierarchical optimization problems. Bilevel optimization problems modeled with EMP are reformulated to mathematical programs with equilibrium constraints (MPECs) and then they are solved with one of the GAMS MPEC solvers (NLPEC or KNITRO).
Disjunctive programming
Mathematical programs involving binary variables and disjunction definitions for modeling discrete choices are called disjunctive programs. Disjunctive programs have many applications, including ordering of tasks in a production process, organizing complex projects in a time saving manner and choosing the optimal route in a circuit. Procedures for linear and nonlinear disjunctive programming extensions are implemented within EMP. Linear disjunctive programs are reformulated as mixed integer programs (MIPs) and nonlinear disjunctive programs are reformulated as mixed integer nonlinear programs (MINLPs). They are solved with the solver LogMIP 2.0 and possibly other GAMS subsolvers.
Examples of the use of EMP for disjunctive programming include scheduling problems in the chemical industry[7]
EMP for stochastic programming
EMP SP is the stochastic extension of the EMP framework. A deterministic model with fixed parameters is transformed into a stochastic model where some of the parameters are not fixed but are represented by probability distributions. This is done with annotations and specific keywords. Single and joint discrete and parametric probability distributions are possible. In addition, there are keywords for the expected value, value at risk (VaR) and conditional value at risk (CVaR). Variables that are risk measures can feature in the objective equation or in constraints. EMP SP facilitates the optimization of a single risk measure or a combination of risk measures (for example, the weighted sum of Expected Value and CVaR). In addition, the modeler can choose to trade off risk measures. It is also possible to model constraints that only hold with certain probabilities (chance constraints). Currently, the following GAMS solvers can be used with EMP SP: DE, DECIS, JAMS and LINDO. Any GAMS solver can be used to process the pre-sampled deterministic equivalent problem.
See also
- Algebraic modeling language
- Complementarity theory
- General Algebraic Modeling System – GAMS
- SAMPL – stochastic extension of AMPL
References
- Outrata, JV, Ferris, MC, Červinka, M and Outrata, M (2015). "On Cournot–Nash–Walras equilibria and their computation". Cite journal requires
|journal=
(help)CS1 maint: multiple names: authors list (link) - Britz, W, Ferris, MC and Kuhn, A (2013). "Modeling Water Allocating Institutions based on Multiple Optimization Problems with Equilibrium Constraints". Environmental Modelling & Software. 46: 196–207. doi:10.1016/j.envsoft.2013.03.010.CS1 maint: multiple names: authors list (link)
- Bauman, A, Goemans, C, Pritchett, J and McFadden, DT (2015). "Modeling Imperfectly Competitive Water Markets in the Western U.S". Selected Paper Prepared for Presentation at the 2015 Agricultural & Applied Economics Association and Western Agricultural Economics Association Annual Meeting, San Francisco, CA, July 26–28.CS1 maint: multiple names: authors list (link)
- Tang, L; Ferris, MC (2015). "A Hierarchical Framework for Long-Term Power Planning Models". IEEE Transactions on Power Systems. 30 (1): 46–56. Bibcode:2015ITPSy..30...46T. doi:10.1109/TPWRS.2014.2328293.
- Philpott, A, Ferris, MC and Wets, R (2016). "Equilibrium, uncertainty and risk in hydro-thermal electricity systems". Mathematical Programming, Series B. 157 (2): 483–513. doi:10.1007/s10107-015-0972-4.CS1 maint: multiple names: authors list (link)
- Gabriel, SA, Conejo, AJ, Fuller, JD, Hobbs, BF and Ruiz (2013). Complementarity Modeling in Energy Markets. International Series in Operations Research & Management Science. 180. Springer New York, pp 181–220 and 323–384.CS1 maint: uses authors parameter (link)
- Grossmann, IE (2012). "Advances in mathematical programming models for enterprise-wide optimization". Computers and Chemical Engineering. 47: 2–18. doi:10.1016/j.compchemeng.2012.06.038.