Extended Mathematical Programming

Last updated

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.

Contents

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

Related Research Articles

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

<span class="mw-page-title-main">AMPL</span>

AMPL is an algebraic modeling language to describe and solve high-complexity problems for large-scale mathematical computing . It was developed by Robert Fourer, David Gay, and Brian Kernighan at Bell Laboratories. AMPL supports dozens of solvers, both open source and commercial software, including CBC, CPLEX, FortMP, MOSEK, MINOS, IPOPT, SNOPT, KNITRO, and LGO. Problems are passed to solvers as nl files. AMPL is used by more than 100 corporate clients, and by government agencies and academic institutions.

The general algebraic modeling system (GAMS) is a high-level modeling system for mathematical optimization. GAMS is designed for modeling and solving linear, nonlinear, and mixed-integer optimization problems. The system is tailored for complex, large-scale modeling applications and allows the user to build large maintainable models that can be adapted to new situations. The system is available for use on various computer platforms. Models are portable from one platform to another.

MPS is a file format for presenting and archiving linear programming (LP) and mixed integer programming problems.

IPOPT, short for "Interior Point OPTimizer, pronounced I-P-Opt", is a software library for large scale nonlinear optimization of continuous systems. It is written in Fortran and C and is released under the EPL. IPOPT implements a primal-dual interior point method, and uses line searches based on Filter methods. IPOPT can be called from various modeling environments and C.

<span class="mw-page-title-main">COIN-OR</span>

Computational Infrastructure for Operations Research (COIN-OR), is a project that aims to "create for mathematical software what the open literature is for mathematical theory." The open literature provides the operations research (OR) community with a peer-review process and an archive. Papers in operations research journals on mathematical theory often contain supporting numerical results from computational studies. The software implementations, models, and data used to produce the numerical results are typically not published. The status quo impeded researchers needing to reproduce computational results, make fair comparisons, and extend the state of the art.

The TOMLAB Optimization Environment is a modeling platform for solving applied optimization problems in MATLAB.

Algebraic modeling languages (AML) are high-level computer programming languages for describing and solving high complexity problems for large scale mathematical computation. One particular advantage of some algebraic modeling languages like AIMMS, AMPL, GAMS, Gekko, MathProg, Mosel, and OPL is the similarity of their syntax to the mathematical notation of optimization problems. This allows for a very concise and readable definition of problems in the domain of optimization, which is supported by certain language elements like sets, indices, algebraic expressions, powerful sparse index and data handling variables, constraints with arbitrary names. The algebraic formulation of a model does not contain any hints how to process it.

Bilevel optimization is a special kind of optimization where one problem is embedded (nested) within another. The outer optimization task is commonly referred to as the upper-level optimization task, and the inner optimization task is commonly referred to as the lower-level optimization task. These problems involve two kinds of variables, referred to as the upper-level variables and the lower-level variables.

A complementarity problem is a type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a function of two vector variables subject to certain requirements (constraints) which include: that the inner product of the two vectors must equal zero, i.e. they are orthogonal. In particular for finite-dimensional real vector spaces this means that, if one has vectors X and Y with all nonnegative components (xi ≥ 0 and yi ≥ 0 for all : in the first quadrant if 2-dimensional, in the first octant if 3-dimensional), then for each pair of components xi and yi one of the pair must be zero, hence the name complementarity. e.g. X = (1, 0) and Y = (0, 2) are complementary, but X = (1, 1) and Y = (2, 0) are not. A complementarity problem is a special case of a variational inequality.

Mathematical programming with equilibrium constraints (MPEC) is the study of constrained optimization problems where the constraints include variational inequalities or complementarities. MPEC is related to the Stackelberg game.

In mathematical optimization, Lemke's algorithm is a procedure for solving linear complementarity problems, and more generally mixed linear complementarity problems. It is named after Carlton E. Lemke.

nl is a file format for presenting and archiving mathematical programming problems. Initially, this format has been invented for connecting solvers to AMPL. It has also been adopted by other systems such as COIN-OR, FortSP, and Coopr.

AIMMS is a prescriptive analytics software company with offices in the Netherlands, United States and Singapore.

<span class="mw-page-title-main">Siconos</span> Open source scientific software for modeling non-smooth dynamical systems

SICONOS is an Open Source scientific software primarily targeted at modeling and simulating non-smooth dynamical systems (NSDS):

SAMPL, which stands for "Stochastic AMPL", is an algebraic modeling language resulting by expanding the well-known language AMPL with extended syntax and keywords. It is designed specifically for representing stochastic programming problems and, through recent extensions, problems with chance constraints, integrated chance constraints and robust optimization problems. It can generate the deterministic equivalent version of the instances, using all the solvers AMPL connects to, or generate an SMPS representation and use specialized decomposition based solvers, like FortSP.

MINOS is a Fortran software package for solving linear and nonlinear mathematical optimization problems. MINOS may be used for linear programming, quadratic programming, and more general objective functions and constraints, and for finding a feasible point for a set of linear or nonlinear equalities and inequalities.

Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems.

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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.