%* gmpl.tex *%

 %***********************************************************************

 %  This code is part of GLPK (GNU Linear Programming Kit).

 %

 %  Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008,

 %  2009, 2010 Andrew Makhorin, Department for Applied Informatics,

 %  Moscow Aviation Institute, Moscow, Russia. All rights reserved.

 %  E-mail: <mao@gnu.org>.

 %

 %  GLPK is free software: you can redistribute it and/or modify it

 %  under the terms of the GNU General Public License as published by

 %  the Free Software Foundation, either version 3 of the License, or

 %  (at your option) any later version.

 %

 %  GLPK is distributed in the hope that it will be useful, but WITHOUT

 %  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY

 %  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public

 %  License for more details.

 %

 %  You should have received a copy of the GNU General Public License

 %  along with GLPK. If not, see <http://www.gnu.org/licenses/>.

 %***********************************************************************

 \documentclass[10pt]{article}

 \usepackage[dvipdfm,linktocpage,colorlinks,linkcolor=blue]{hyperref}

 \begin{document}

 \thispagestyle{empty}

 \begin{center}

 \vspace*{1in}

 \begin{huge}

 \sf\bfseries Modeling Language GNU MathProg

 \end{huge}

 \vspace{0.5in}

 \begin{LARGE}

 \sf Language Reference

 \end{LARGE}

 \vspace{0.5in}

 \begin{LARGE}

 \sf for GLPK Version 4.45

 \end{LARGE}

 \vspace{0.5in}

 \begin{Large}

 \sf (DRAFT, December 2010)

 \end{Large}

 \end{center}

 \newpage

 \vspace*{1in}

 \vfill

 \noindent

 The GLPK package is part of the GNU Project released under the aegis of

 GNU.

 \medskip\noindent

 Copyright \copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,

 2008, 2009, 2010 Andrew Makhorin, Department for Applied Informatics,

 Moscow Aviation Institute, Moscow, Russia. All rights reserved.

 \medskip\noindent

 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,

 MA 02110-1301, USA.

 \medskip\noindent

 Permission is granted to make and distribute verbatim copies of this

 manual provided the copyright notice and this permission notice are

 preserved on all copies.

 \medskip\noindent

 Permission is granted to copy and distribute modified versions of this

 manual under the conditions for verbatim copying, provided also that

 the entire resulting derived work is distributed under the terms of

 a permission notice identical to this one.

 \medskip\noindent

 Permission is granted to copy and distribute translations of this

 manual into another language, under the above conditions for modified

 versions.

 \newpage

 \tableofcontents

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 \newpage

 \section{Introduction}

 {\it GNU MathProg} is a modeling language intended for describing

 linear mathematical programming models.\footnote{The GNU MathProg

 language is a subset of the AMPL language. Its GLPK implementation is

 mainly based on the paper: {\it Robert Fourer}, {\it David M. Gay}, and

 {\it Brian W. Kernighan}, ``A Modeling Language for Mathematical

 Programming.'' {\it Management Science} 36 (1990)\linebreak pp. 519-54.}

 Model descriptions written in the GNU MathProg language consist of

 a set of statements and data blocks constructed by the user from the

 language elements described in this document.

 In a process called {\it translation}, a program called the {\it model

 translator} analyzes the model description and translates it into

 internal data structures, which may be then used either for generating

 mathematical programming problem instance or directly by a program

 called the {\it solver} to obtain numeric solution of the problem.

 \subsection{Linear programming problem}

 \label{problem}

 In MathProg the linear programming (LP) problem is stated as follows:

 \medskip

 \noindent\hspace{.7in}minimize (or maximize)

 $$z=c_1x_1+c_2x_2+\dots+c_nx_n+c_0\eqno(1.1)$$

 \noindent\hspace{.7in}subject to linear constraints

 $$

 \begin{array}{l@{\ }c@{\ }r@{\ }c@{\ }r@{\ }c@{\ }r@{\ }c@{\ }l}

 L_1&\leq&a_{11}x_1&+&a_{12}x_2&+\dots+&a_{1n}x_n&\leq&U_1\\

 L_2&\leq&a_{21}x_1&+&a_{22}x_2&+\dots+&a_{2n}x_n&\leq&U_2\\

 \multicolumn{9}{c}{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .}\\

 L_m&\leq&a_{m1}x_1&+&a_{m2}x_2&+\dots+&a_{mn}x_n&\leq&U_m\\

 \end{array}\eqno(1.2)

 $$

 \noindent\hspace{.7in}and bounds of variables

 $$

 \begin{array}{l@{\ }c@{\ }c@{\ }c@{\ }l}

 l_1&\leq&x_1&\leq&u_1\\

 l_2&\leq&x_2&\leq&u_2\\

 \multicolumn{5}{c}{.\ \ .\ \ .\ \ .\ \ .}\\

 l_n&\leq&x_n&\leq&u_n\\

 \end{array}\eqno(1.3)

 $$

 where $x_1$, $x_2$, \dots, $x_n$ are variables; $z$ is the objective

 function; $c_1$, $c_2$, \dots, $c_n$ are objective coefficients; $c_0$

 is the constant term (``shift'') of the objective function; $a_{11}$,

 $a_{12}$, \dots, $a_{mn}$ are constraint coefficients; $L_1$, $L_2$,

 \dots, $L_m$ are lower constraint bounds; $U_1$, $U_2$, \dots, $U_m$

 are upper constraint bounds; $l_1$, $l_2$, \dots, $l_n$ are lower

 bounds of variables; $u_1$, $u_2$, \dots, $u_n$ are upper bounds of

 variables.

 Bounds of variables and constraint bounds can be finite as well as

 infinite. Besides, lower bounds can be equal to corresponding upper

 bounds. Thus, the following types of variables and constraints are

 allowed:

 \newpage

 \begin{tabular}{@{}r@{\ }c@{\ }c@{\ }c@{\ }l@{\hspace*{38pt}}l}

 $-\infty$&$<$&$x$&$<$&$+\infty$&Free (unbounded) variable\\

 $l$&$\leq$&$x$&$<$&$+\infty$&Variable with lower bound\\

 $-\infty$&$<$&$x$&$\leq$&$u$&Variable with upper bound\\

 $l$&$\leq$&$x$&$\leq$&$u$&Double-bounded variable\\

 $l$&$=$&$x$&=&$u$&Fixed variable\\

 \end{tabular}

 \bigskip

 \begin{tabular}{@{}r@{\ }c@{\ }c@{\ }c@{\ }ll}

 $-\infty$&$<$&$\sum a_jx_j$&$<$&$+\infty$&Free (unbounded) linear

 form\\

 $L$&$\leq$&$\sum a_jx_j$&$<$&$+\infty$&Inequality constraint ``greater

 than or equal to''\\

 $-\infty$&$<$&$\sum a_jx_j$&$\leq$&$U$&Inequality constraint ``less

 than or equal to''\\

 $L$&$\leq$&$\sum a_jx_j$&$\leq$&$U$&Double-bounded inequality

 constraint\\

 $L$&$=$&$\sum a_jx_j$&=&$U$&Equality constraint\\

 \end{tabular}

 \bigskip

 In addition to pure LP problems MathProg also allows mixed integer

 linear programming (MIP) problems, where some or all variables are

 restricted to be integer or binary.

 \subsection{Model objects}

 In MathProg the model is described in terms of sets, parameters,

 variables, constraints, and objectives, which are called {\it model

 objects}.

 The user introduces particular model objects using the language

 statements. Each model object is provided with a symbolic name that

 uniquely identifies the object and is intended for referencing purposes.

 Model objects, including sets, can be multidimensional arrays built

 over indexing sets. Formally, $n$-dimensional array $A$ is the mapping:

 $$A:\Delta\rightarrow\Xi,\eqno(1.4)$$

 where $\Delta\subseteq S_1\times\dots\times S_n$ is a subset of the

 Cartesian product of indexing sets,\linebreak $\Xi$ is a set of array members.

 In MathProg the set $\Delta$ is called the {\it subscript domain}. Its

 members are $n$-tuples $(i_1,\dots,i_n)$, where $i_1\in S_1$, \dots,

 $i_n\in S_n$.

 If $n=0$, the Cartesian product above has exactly one member (namely,

 \linebreak 0-tuple), so it is convenient to think scalar objects as

 0-dimensional arrays having one member.

 The type of array members is determined by the type of corresponding

 model object as follows:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}ll@{}}

 Model object&Array member\\

 \hline

 Set&Elemental plain set\\

 Parameter&Number or symbol\\

 Variable&Elemental variable\\

 Constraint&Elemental constraint\\

 Objective&Elemental objective\\

 \end{tabular}

 \medskip

 In order to refer to a particular object member the object should be

 provided with {\it subscripts}. For example, if $a$ is a 2-dimensional

 parameter defined over $I\times J$, a reference to its particular

 member can be written as $a[i,j]$, where $i\in I$ and $j\in J$. It is

 understood that scalar objects being 0-dimensional need no subscripts.

 \subsection{Structure of model description}

 It is sometimes desirable to write a model which, at various points,

 may require different data for each problem instance to be solved using

 that model. For this reason in MathProg the model description consists

 of two parts: the {\it model section} and the {\it data section}.

 The model section is a main part of the model description that contains

 declarations of model objects and is common for all problems based on

 the corresponding model.

 The data section is an optional part of the model description that

 contains data specific for a particular problem instance.

 Depending on what is more convenient the model and data sections can be

 placed either in one file or in two separate files. The latter feature

 allows having arbitrary number of different data sections to be used

 with the same model section.

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 \newpage

 \section{Coding model description}

 \label{coding}

 The model description is coded in plain text format using ASCII

 character set. Characters valid in the model description are the

 following:

 \begin{itemize}

 \item alphabetic characters:\\

 \verb|A B C D E F G H I J K L M N O P Q R S T U V W X Y Z|\\

 \verb|a b c d e f g h i j k l m n o p q r s t u v w x y z _|

 \item numeric characters:\\

 \verb|0 1 2 3 4 5 6 7 8 9|

 \item special characters:\\

 \verb?! " # & ' ( ) * + , - . / : ; < = > [ ] ^ { | }?

 \item white-space characters:\\

 \verb|SP HT CR NL VT FF|

 \end{itemize}

 Within string literals and comments any ASCII characters (except

 control characters) are valid.

 White-space characters are non-significant. They can be used freely

 between lexical units to improve readability of the model description.

 They are also used to separate lexical units from each other if there

 is no other way to do that.

 Syntactically model description is a sequence of lexical units in the

 following categories:

 \begin{itemize}

 \item symbolic names;

 \item numeric literals;

 \item string literals;

 \item keywords;

 \item delimiters;

 \item comments.

 \end{itemize}

 The lexical units of the language are discussed below.

 \subsection{Symbolic names}

 A {\it symbolic name} consists of alphabetic and numeric characters,

 the first of which must be alphabetic. All symbolic names are distinct

 (case sensitive).

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent\verb|alpha123|

 \noindent\verb|This_is_a_name|

 \noindent\verb|_P123_abc_321|

 \newpage

 Symbolic names are used to identify model objects (sets, parameters,

 variables, constraints, objectives) and dummy indices.

 All symbolic names (except names of dummy indices) must be unique, i.e.

 the model description must have no objects with identical names.

 Symbolic names of dummy indices must be unique within the scope, where

 they are valid.

 \subsection{Numeric literals}

 A {\it numeric literal} has the form {\it xx}{\tt E}{\it syy}, where

 {\it xx} is a number with optional decimal point, {\it s} is the sign

 {\tt+} or {\tt-}, {\it yy} is a decimal exponent. The letter {\tt E} is

 case insensitive and can be coded as {\tt e}.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent\verb|123|

 \noindent\verb|3.14159|

 \noindent\verb|56.E+5|

 \noindent\verb|.78|

 \noindent\verb|123.456e-7|

 \medskip

 Numeric literals are used to represent numeric quantities. They have

 obvious fixed meaning.

 \subsection{String literals}

 A {\it string literal} is a sequence of arbitrary characters enclosed

 either in single quotes or in double quotes. Both these forms are

 equivalent.

 If the single quote is part of a string literal enclosed in single

 quotes, it must be coded twice. Analogously, if the double quote is

 part of a string literal enclosed in double quotes, it must be coded

 twice.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent\verb|'This is a string'|

 \noindent\verb|"This is another string"|

 \noindent\verb|'1 + 2 = 3'|

 \noindent\verb|'That''s all'|

 \noindent\verb|"She said: ""No"""|

 \medskip

 String literals are used to represent symbolic quantities.

 \subsection{Keywords}

 A {\it keyword} is a sequence of alphabetic characters and possibly

 some special characters.

 All keywords fall into two categories: {\it reserved keywords}, which

 cannot be used as symbolic names, and {\it non-reserved keywords},

 which being recognized by context can be used as symbolic names.

 \newpage

 The reserved keywords are the following:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}p{.7in}p{.7in}p{.7in}p{.7in}@{}}

 {\tt and}&{\tt else}&{\tt mod}&{\tt union}\\

 {\tt by}&{\tt if}&{\tt not}&{\tt within}\\

 {\tt cross}&{\tt in}&{\tt or}\\

 {\tt diff}&{\tt inter}&{\tt symdiff}\\

 {\tt div}&{\tt less}&{\tt then}\\

 \end{tabular}

 \medskip

 Non-reserved keywords are described in following sections.

 All the keywords have fixed meaning, which will be explained on

 discussion of corresponding syntactic constructions, where the keywords

 are used.

 \subsection{Delimiters}

 A {\it delimiter} is either a single special character or a sequence of

 two special characters as follows:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}p{.3in}p{.3in}p{.3in}p{.3in}p{.3in}p{.3in}@{}}

 {\tt+}&{\tt\textasciicircum}&{\tt==}&{\tt!}&{\tt:}&{\tt)}\\

 {\tt-}&{\tt\&}&{\tt>=}&{\tt\&\&}&{\tt;}&{\tt[}\\

 {\tt*}&{\tt<}&{\tt>}&{\tt||}&{\tt:=}&{\tt|}\\

 {\tt/}&{\tt<=}&{\tt<>}&{\tt.}&{\tt..}&{\tt\{}\\

 {\tt**}&{\tt=}&{\tt!=}&{\tt,}&{\tt(}&{\tt\}}\\

 \end{tabular}

 \medskip

 If the delimiter consists of two characters, there must be no spaces

 between the characters.

 All the delimiters have fixed meaning, which will be explained on

 discussion corresponding syntactic constructions, where the delimiters

 are used.

 \subsection{Comments}

 For documenting purposes the model description can be provided with

 {\it comments}, which may have two different forms. The first form is

 a {\it single-line comment}, which begins with the character {\tt\#}

 and extends until end of line. The second form is a {\it comment

 sequence}, which is a sequence of any characters enclosed within

 {\tt/*} and {\tt*/}.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent\verb|param n := 10; # This is a comment|

 \noindent\verb|/* This is another comment */|

 \medskip

 Comments are ignored by the model translator and can appear anywhere in

 the model description, where white-space characters are allowed.

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 \newpage

 \section{Expressions}

 An {\it expression} is a rule for computing a value. In model

 description expressions are used as constituents of certain statements.

 In general case expressions consist of operands and operators.

 Depending on the type of the resultant value all expressions fall into

 the following categories:

 \begin{itemize}

 \item numeric expressions;

 \item symbolic expressions;

 \item indexing expressions;

 \item set expressions;

 \item logical expressions;

 \item linear expressions.

 \end{itemize}

 \subsection{Numeric expressions}

 A {\it numeric expression} is a rule for computing a single numeric

 value represented as a floating-point number.

 The primary numeric expression may be a numeric literal, dummy index,

 unsubscripted parameter, subscripted parameter, built-in function

 reference, iterated numeric expression, conditional numeric expression,

 or another numeric expression enclosed in parentheses.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent

 \begin{tabular}{@{}ll@{}}

 \verb|1.23|&(numeric literal)\\

 \verb|j|&(dummy index)\\

 \verb|time|&(unsubscripted parameter)\\

 \verb|a['May 2003',j+1]|&(subscripted parameter)\\

 \verb|abs(b[i,j])|&(function reference)\\

 \verb|sum{i in S diff T} alpha[i] * b[i,j]|&(iterated expression)\\

 \verb|if i in I then 2 * p else q[i+1]|&(conditional expression)\\

 \verb|(b[i,j] + .5 * c)|&(parenthesized expression)\\

 \end{tabular}

 \medskip

 More general numeric expressions containing two or more primary numeric

 expressions may be constructed by using certain arithmetic operators.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent\verb|j+1|

 \noindent\verb|2 * a[i-1,j+1] - b[i,j]|

 \noindent\verb|sum{j in J} a[i,j] * x[j] + sum{k in K} b[i,k] * x[k]|

 \noindent\verb|(if i in I then 2 * p else q[i+1]) / (a[i,j] + 1.5)|

 \subsubsection{Numeric literals}

 If the primary numeric expression is a numeric literal, the resultant

 value is obvious.

 \subsubsection{Dummy indices}

 If the primary numeric expression is a dummy index, the resultant value

 is current value assigned to that dummy index.

 \subsubsection{Unsubscripted parameters}

 If the primary numeric expression is an unsubscripted parameter (which

 must be 0-dimensional), the resultant value is the value of that

 parameter.

 \subsubsection{Subscripted parameters}

 The primary numeric expression, which refers to a subscripted parameter,

 has the following syntactic form:

 \medskip

 \noindent\hfil

 {\it name}{\tt[}$i_1${\tt,} $i_2${\tt,} \dots{\tt,} $i_n${\tt]}

 \medskip

 \noindent where {\it name} is the symbolic name of the parameter,

 $i_1$, $i_2$, \dots, $i_n$ are subscripts.

 Each subscript must be a numeric or symbolic expression. The number of

 subscripts in the subscript list must be the same as the dimension of

 the parameter with which the subscript list is associated.

 Actual values of subscript expressions are used to identify

 a particular member of the parameter that determines the resultant

 value of the primary expression.

 \subsubsection{Function references}

 In MathProg there exist the following built-in functions which may be

 used in numeric expressions:

 \medskip

 \begin{tabular}{@{}p{96pt}p{222pt}@{}}

 {\tt abs(}$x${\tt)}&$|x|$, absolute value of $x$\\

 {\tt atan(}$x${\tt)}&$\arctan x$, principal value of the arc tangent of

 $x$ (in radians)\\

 {\tt atan(}$y${\tt,} $x${\tt)}&$\arctan y/x$, principal value of the

 arc tangent of $y/x$ (in radians). In this case the signs of both

 arguments $y$ and $x$ are used to determine the quadrant of the

 resultant value\\

 {\tt card(}$X${\tt)}&$|X|$, cardinality (the number of elements) of

 set $X$\\

 {\tt ceil(}$x${\tt)}&$\lceil x\rceil$, smallest integer not less than

 $x$ (``ceiling of $x$'')\\

 {\tt cos(}$x${\tt)}&$\cos x$, cosine of $x$ (in radians)\\

 {\tt exp(}$x${\tt)}&$e^x$, base-$e$ exponential of $x$\\

 {\tt floor(}$x${\tt)}&$\lfloor x\rfloor$, largest integer not greater

 than $x$ (``floor of $x$'')\\

 \end{tabular}

 \begin{tabular}{@{}p{96pt}p{222pt}@{}}

 {\tt gmtime()}&the number of seconds elapsed since 00:00:00~Jan~1, 1970,

 Coordinated Universal Time (for details see Subsection \ref{gmtime},

 page \pageref{gmtime})\\

 {\tt length(}$s${\tt)}&$|s|$, length of character string $s$\\

 {\tt log(}$x${\tt)}&$\log x$, natural logarithm of $x$\\

 {\tt log10(}$x${\tt)}&$\log_{10}x$, common (decimal) logarithm of $x$\\

 {\tt max(}$x_1${\tt,} $x_2${\tt,} \dots{\tt,} $x_n${\tt)}&the largest

 of values $x_1$, $x_2$, \dots, $x_n$\\

 {\tt min(}$x_1${\tt,} $x_2${\tt,} \dots{\tt,} $x_n${\tt)}&the smallest

 of values $x_1$, $x_2$, \dots, $x_n$\\

 {\tt round(}$x${\tt)}&rounding $x$ to nearest integer\\

 {\tt round(}$x${\tt,} $n${\tt)}&rounding $x$ to $n$ fractional decimal

 digits\\

 {\tt sin(}$x${\tt)}&$\sin x$, sine of $x$ (in radians)\\

 {\tt sqrt(}$x${\tt)}&$\sqrt{x}$, non-negative square root of $x$\\

 {\tt str2time(}$s${\tt,} $f${\tt)}&converting character string $s$ to

 calendar time (for details see Subsection \ref{str2time}, page

 \pageref{str2time})\\

 {\tt trunc(}$x${\tt)}&truncating $x$ to nearest integer\\

 {\tt trunc(}$x${\tt,} $n${\tt)}&truncating $x$ to $n$ fractional

 decimal digits\\

 {\tt Irand224()}&generating pseudo-random integer uniformly distributed

 in $[0,2^{24})$\\

 {\tt Uniform01()}&generating pseudo-random number uniformly distributed

 in $[0,1)$\\

 {\tt Uniform(}$a${\tt,} $b${\tt)}&generating pseudo-random number

 uniformly distributed in $[a,b)$\\

 {\tt Normal01()}&generating Gaussian pseudo-random variate with

 $\mu=0$ and $\sigma=1$\\

 {\tt Normal(}$\mu${\tt,} $\sigma${\tt)}&generating Gaussian

 pseudo-random variate with given $\mu$ and $\sigma$\\

 \end{tabular}

 \medskip

 Arguments of all built-in functions, except {\tt card}, {\tt length},

 and {\tt str2time}, must be numeric expressions. The argument of

 {\tt card} must be a set expression. The argument of {\tt length} and

 both arguments of {\tt str2time} must be symbolic expressions.

 The resultant value of the numeric expression, which is a function

 reference, is the result of applying the function to its argument(s).

 Note that each pseudo-random generator function has a latent argument

 (i.e. some internal state), which is changed whenever the function has

 been applied. Thus, if the function is applied repeatedly even to

 identical arguments, due to the side effect different resultant values

 are always produced.

 \subsubsection{Iterated expressions}

 \label{itexpr}

 An {\it iterated numeric expression} is a primary numeric expression,

 which has the following syntactic form:

 \medskip

 \noindent\hfil

 {\it iterated-operator indexing-expression integrand}

 \medskip

 \noindent where {\it iterated-operator} is the symbolic name of the

 iterated operator to be performed (see below), {\it indexing-expression}

 is an indexing expression which introduces dummy indices and controls

 iterating, {\it integrand} is a numeric expression that participates in

 the operation.

 In MathProg there exist four iterated operators, which may be used in

 numeric expressions:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}lll@{}}

 {\tt sum}&summation&$\displaystyle\sum_{(i_1,\dots,i_n)\in\Delta}

 f(i_1,\dots,i_n)$\\

 {\tt prod}&production&$\displaystyle\prod_{(i_1,\dots,i_n)\in\Delta}

 f(i_1,\dots,i_n)$\\

 {\tt min}&minimum&$\displaystyle\min_{(i_1,\dots,i_n)\in\Delta}

 f(i_1,\dots,i_n)$\\

 {\tt max}&maximum&$\displaystyle\max_{(i_1,\dots,i_n)\in\Delta}

 f(i_1,\dots,i_n)$\\

 \end{tabular}

 \medskip

 \noindent where $i_1$, \dots, $i_n$ are dummy indices introduced in

 the indexing expression, $\Delta$ is the domain, a set of $n$-tuples

 specified by the indexing expression which defines particular values

 assigned to the dummy indices on performing the iterated operation,

 $f(i_1,\dots,i_n)$ is the integrand, a numeric expression whose

 resultant value depends on the dummy indices.

 The resultant value of an iterated numeric expression is the result of

 applying of the iterated operator to its integrand over all $n$-tuples

 contained in the domain.

 \subsubsection{Conditional expressions}

 \label{ifthen}

 A {\it conditional numeric expression} is a primary numeric expression,

 which has one of the following two syntactic forms:

 \medskip

 \noindent\hfil

 {\tt if} $b$ {\tt then} $x$ {\tt else} $y$

 \medskip

 \noindent\hspace{126.5pt}

 {\tt if} $b$ {\tt then} $x$

 \medskip

 \noindent where $b$ is an logical expression, $x$ and $y$ are numeric

 expressions.

 The resultant value of the conditional expression depends on the value

 of the logical expression that follows the keyword {\tt if}. If it

 takes on the value {\it true}, the value of the conditional expression

 is the value of the expression that follows the keyword {\tt then}.

 Otherwise, if the logical expression takes on the value {\it false},

 the value of the conditional expression is the value of the expression

 that follows the keyword {\it else}. If the second, reduced form of the

 conditional expression is used and the logical expression takes on the

 value {\it false}, the resultant value of the conditional expression is

 zero.

 \subsubsection{Parenthesized expressions}

 Any numeric expression may be enclosed in parentheses that

 syntactically makes it a primary numeric expression.

 Parentheses may be used in numeric expressions, as in algebra, to

 specify the desired order in which operations are to be performed.

 Where parentheses are used, the expression within the parentheses is

 evaluated before the resultant value is used.

 The resultant value of the parenthesized expression is the same as the

 value of the expression enclosed within parentheses.

 \subsubsection{Arithmetic operators}

 In MathProg there exist the following arithmetic operators, which may

 be used in numeric expressions:

 \medskip

 \begin{tabular}{@{}p{96pt}p{222pt}@{}}

 {\tt +} $x$&unary plus\\

 {\tt -} $x$&unary minus\\

 $x$ {\tt +} $y$&addition\\

 $x$ {\tt -} $y$&subtraction\\

 $x$ {\tt less} $y$&positive difference (if $x<y$ then 0 else $x-y$)\\

 $x$ {\tt *} $y$&multiplication\\

 $x$ {\tt /} $y$&division\\

 $x$ {\tt div} $y$&quotient of exact division\\

 $x$ {\tt mod} $y$&remainder of exact division\\

 $x$ {\tt **} $y$, $x$ {\tt\textasciicircum} $y$&exponentiation (raising

 to power)\\

 \end{tabular}

 \medskip

 \noindent where $x$ and $y$ are numeric expressions.

 If the expression includes more than one arithmetic operator, all

 operators are performed from left to right according to the hierarchy

 of operations (see below) with the only exception that the

 exponentiaion operators are performed from right to left.

 The resultant value of the expression, which contains arithmetic

 operators, is the result of applying the operators to their operands.

 \subsubsection{Hierarchy of operations}

 \label{hierarchy}

 The following list shows the hierarchy of operations in numeric

 expressions:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}ll@{}}

 Operation&Hierarchy\\

 \hline

 Evaluation of functions ({\tt abs}, {\tt ceil}, etc.)&1st\\

 Exponentiation ({\tt**}, {\tt\textasciicircum})&2nd\\

 Unary plus and minus ({\tt+}, {\tt-})&3rd\\

 Multiplication and division ({\tt*}, {\tt/}, {\tt div}, {\tt mod})&4th\\

 Iterated operations ({\tt sum}, {\tt prod}, {\tt min}, {\tt max})&5th\\

 Addition and subtraction ({\tt+}, {\tt-}, {\tt less})&6th\\

 Conditional evaluation ({\tt if} \dots {\tt then} \dots {\tt else})&

 7th\\

 \end{tabular}

 \medskip

 This hierarchy is used to determine which of two consecutive operations

 is performed first. If the first operator is higher than or equal to

 the second, the first operation is performed. If it is not, the second

 operator is compared to the third, etc. When the end of the expression

 is reached, all of the remaining operations are performed in the

 reverse order.

 \newpage

 \subsection{Symbolic expressions}

 A {\it symbolic expression} is a rule for computing a single symbolic

 value represented as a character string.

 The primary symbolic expression may be a string literal, dummy index,

 unsubscripted parameter, subscripted parameter, built-in function

 reference, conditional symbolic expression, or another symbolic

 expression enclosed in parentheses.

 It is also allowed to use a numeric expression as the primary symbolic

 expression, in which case the resultant value of the numeric expression

 is automatically converted to the symbolic type.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent

 \begin{tabular}{@{}ll@{}}

 \verb|'May 2003'|&(string literal)\\

 \verb|j|&(dummy index)\\

 \verb|p|&(unsubscripted parameter)\\

 \verb|s['abc',j+1]|&(subscripted parameter)\\

 \verb|substr(name[i],k+1,3)|&(function reference)\\

 \verb|if i in I then s[i,j] else t[i+1]|&(conditional expression)\\

 \verb|((10 * b[i,j]) & '.bis')|&(parenthesized expression)\\

 \end{tabular}

 \medskip

 More general symbolic expressions containing two or more primary

 symbolic expressions may be constructed by using the concatenation

 operator.

 \medskip

 \noindent{\bf Examples}

 \medskip

 \noindent\verb|'abc[' & i & ',' & j & ']'|

 \noindent\verb|"from " & city[i] & " to " & city[j]|

 \medskip

 The principles of evaluation of symbolic expressions are completely

 analogous to the ones given for numeric expressions (see above).

 \subsubsection{Function references}

 In MathProg there exist the following built-in functions which may be

 used in symbolic expressions:

 \medskip

 \begin{tabular}{@{}p{96pt}p{222pt}@{}}

 {\tt substr(}$s${\tt,} $x${\tt)}&substring of $s$ starting from

 position $x$\\

 {\tt substr(}$s${\tt,} $x${\tt,} $y${\tt)}&substring of $s$ starting

 from position $x$ and having length $y$\\

 {\tt time2str(}$t${\tt,} $f${\tt)}&converting calendar time to

 character string (for details see Subsection \ref{time2str}, page

 \pageref{time2str})\\

 \end{tabular}

 \medskip

 The first argument of {\tt substr} must be a symbolic expression while

 its second and optional third arguments must be numeric expressions.

 The first argument of {\tt time2str} must be a numeric expression, and

 its second argument must be a symbolic expression.

 The resultant value of the symbolic expression, which is a function

 reference, is the result of applying the function to its arguments.

 \subsubsection{Symbolic operators}

 Currently in MathProg there exists the only symbolic operator:

 \medskip

 \noindent\hfil

 {\tt s \& t}

 \medskip

 \noindent where $s$ and $t$ are symbolic expressions. This operator

 means concatenation of its two symbolic operands, which are character

 strings.

 \subsubsection{Hierarchy of operations}

 The following list shows the hierarchy of operations in symbolic

 expressions:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}ll@{}}

 Operation&Hierarchy\\

 \hline

 Evaluation of numeric operations&1st-7th\\

 Concatenation ({\tt\&})&8th\\

 Conditional evaluation ({\tt if} \dots {\tt then} \dots {\tt else})&

 7th\\

 \end{tabular}

 \medskip

 This hierarchy has the same meaning as was explained above for numeric

 expressions (see Subsection \ref{hierarchy}, page \pageref{hierarchy}).

 \subsection{Indexing expressions and dummy indices}

 \label{indexing}

 An {\it indexing expression} is an auxiliary construction, which

 specifies a plain set of $n$-tuples and introduces dummy indices. It

 has two syntactic forms:

 \medskip

 \noindent\hspace{73.5pt}

 {\tt\{} {\it entry}$_1${\tt,} {\it entry}$_2${\tt,} \dots{\tt,}

 {\it entry}$_m$ {\tt\}}

 \medskip

 \noindent\hfil

 {\tt\{} {\it entry}$_1${\tt,} {\it entry}$_2${\tt,} \dots{\tt,}

 {\it entry}$_m$ {\tt:} {\it predicate} {\tt\}}

 \medskip

 \noindent where {\it entry}{$_1$}, {\it entry}{$_2$}, \dots,

 {\it entry}{$_m$} are indexing entries, {\it predicate} is a logical

 expression that specifies an optional predicate (logical condition).

 Each {\it indexing entry} in the indexing expression has one of the

 following three forms:

 \medskip

 \noindent\hspace{123pt}

 $i$ {\tt in} $S$

 \medskip

 \noindent\hfil

 {\tt(}$i_1${\tt,} $i_2${\tt,} \dots{\tt,}$i_n${\tt)} {\tt in} $S$

 \medskip

 \noindent\hspace{123pt}

 $S$

 \medskip

 \noindent where $i_1$, $i_2$, \dots, $i_n$ are indices, $S$ is a set

 expression (discussed in the next section) that specifies the basic set.

 The number of indices in the indexing entry must be the same as the

 dimension of the basic set $S$, i.e. if $S$ consists of 1-tuples, the

 first form must be used, and if $S$ consists of $n$-tuples, where

 $n>1$, the second form must be used.

 If the first form of the indexing entry is used, the index $i$ can be

 a dummy index only (see below). If the second form is used, the indices

 $i_1$, $i_2$, \dots, $i_n$ can be either dummy indices or some numeric

 or symbolic expressions, where at least one index must be a dummy index.

 The third, reduced form of the indexing entry has the same effect as if

 there were $i$ (if $S$ is 1-dimensional) or $i_1$, $i_2$, \dots, $i_n$

 (if $S$ is $n$-dimensional) all specified as dummy indices.

 A {\it dummy index} is an auxiliary model object, which acts like an

 individual variable. Values assigned to dummy indices are components of

 $n$-tuples from basic sets, i.e. some numeric and symbolic quantities.

 For referencing purposes dummy indices can be provided with symbolic

 names. However, unlike other model objects (sets, parameters, etc.)

 dummy indices need not be explicitly declared. Each {\it undeclared}

 symbolic name being used in the indexing position of an indexing entry

 is recognized as the symbolic name of corresponding dummy index.

 Symbolic names of dummy indices are valid only within the scope of the

 indexing expression, where the dummy indices were introduced. Beyond

 the scope the dummy indices are completely inaccessible, so the same

 symbolic names may be used for other purposes, in particular, to

 represent dummy indices in other indexing expressions.

 The scope of indexing expression, where implicit declarations of dummy

 indices are valid, depends on the context, in which the indexing

 expression is used:

 \begin{enumerate}

 \item If the indexing expression is used in iterated operator, its

 scope extends until the end of the integrand.

 \item If the indexing expression is used as a primary set expression,

 its scope extends until the end of that indexing expression.

 \item If the indexing expression is used to define the subscript domain

 in declarations of some model objects, its scope extends until the end

 of the corresponding statement.

 \end{enumerate}

 The indexing mechanism implemented by means of indexing expressions is

 best explained by some examples discussed below.

 Let there be given three sets:

 \medskip

 \noindent\hspace{33.5pt}

 $A=\{4,7,9\}$,

 \medskip

 \noindent\hfil

 $B=\{(1,Jan),(1,Feb),(2,Mar),(2,Apr),(3,May),(3,Jun)\}$,

 \medskip

 \noindent\hspace{33.5pt}

 $C=\{a,b,c\}$,

 \medskip

 \noindent where $A$ and $C$ consist of 1-tuples (singlets), $B$

 consists of 2-tuples (doublets). Consider the following indexing

 expression:

 \medskip

 \noindent\hfil

 {\tt\{i in A, (j,k) in B, l in C\}}

 \medskip

 \noindent where {\tt i}, {\tt j}, {\tt k}, and {\tt l} are dummy

 indices.

 Although MathProg is not a procedural language, for any indexing

 expression an equivalent algorithmic description can be given. In

 particular, the algorithmic description of the indexing expression

 above could look like follows:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}l@{}}

 {\bf for all} $i\in A$ {\bf do}\\

 \hspace{12pt}{\bf for all} $(j,k)\in B$ {\bf do}\\

 \hspace{24pt}{\bf for all} $l\in C$ {\bf do}\\

 \hspace{36pt}{\it action};\\

 \end{tabular}

 \newpage

 \noindent where the dummy indices $i$, $j$, $k$, $l$ are consecutively

 assigned corresponding components of $n$-tuples from the basic sets $A$,

 $B$, $C$, and {\it action} is some action that depends on the context,

 where the indexing expression is used. For example, if the action were

 printing current values of dummy indices, the printout would look like

 follows:

 \medskip

 \noindent\hfil

 \begin{tabular}{@{}llll@{}}

 $i=4$&$j=1$&$k=Jan$&$l=a$\\

 $i=4$&$j=1$&$k=Jan$&$l=b$\\

 $i=4$&$j=1$&$k=Jan$&$l=c$\\

 $i=4$&$j=1$&$k=Feb$&$l=a$\\

 $i=4$&$j=1$&$k=Feb$&$l=b$\\

 \multicolumn{4}{c}{.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .}\\

 $i=9$&$j=3$&$k=Jun$&$l=b$\\

 $i=9$&$j=3$&$k=Jun$&$l=c$\\

 \end{tabular}

 \medskip

 Let the example indexing expression be used in the following iterated

 operation:

 \medskip

 \noindent\hfil

 {\tt sum\{i in A, (j,k) in B, l in C\} p[i,j,k,l]}

 \medskip

 \noindent where {\tt p} is a 4-dimensional numeric parameter or some

 numeric expression whose resultant value depends on {\tt i}, {\tt j},

 {\tt k}, and {\tt l}. In this case the action is summation, so the

 resultant value of the primary numeric expression is:

 $$\sum_{i\in A,(j,k)\in B,l\in C}(p_{ijkl}).$$

 Now let the example indexing expression be used as a primary set

 expression. In this case the action is gathering all 4-tuples

 (quadruplets) of the form $(i,j,k,l)$ in one set, so the resultant

 value of such operation is simply the Cartesian product of the basic

 sets:

 $$A\times B\times C=\{(i,j,k,l):i\in A,(j,k)\in B,l\in C\}.$$

 Note that in this case the same indexing expression might be written in

 the reduced form:

 \medskip

 \noindent\hfil

 {\tt\{A, B, C\}}

 \medskip

 \noindent because the dummy indices $i$, $j$, $k$, and $l$ are not

 referenced and therefore their symbolic names need not be specified.

 Finally, let the example indexing expression be used as the subscript

 domain in the declaration of a 4-dimensional model object, say,

 a numeric parameter: