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]

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

1. Outrata JV, Ferris MC, Červinka M, Outrata M (2016). "On Cournot–Nash–Walras equilibria and their computation". Set-Valued and Variational Analysis. 24 (3): 387–402. doi:10.1007/s11228-016-0377-4. S2CID 255062482.
2. Britz W, Ferris MC, 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.
3. Bauman A, Goemans C, Pritchett J, 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.
4. 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.
5. Philpott A, Ferris MC, 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. S2CID 891228.
6. Gabriel SA, Conejo AJ, Fuller JD, Hobbs BF, Ruiz C (2013). Complementarity Modeling in Energy Markets. International Series in Operations Research & Management Science. Vol. 180. New York: Springer. pp. 181–220, 323–384.
7. 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.

External links

• www.gams.com