gmpl.texi

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

by the indexing expression which defines particular values assigned to
the dummy indices on performing the iterated operation,
@i{x}(@i{i}1,@tie{}@dots{},@tie{}@i{in}) is the integrand, a numeric
expression whose resultant value depends on the dummy indices.
@end ifnottex

The resultant value of an iterated numeric expression is the result of
applying of the iterated operator to its integrand over all @i{n}-tuples
contained in the domain.

@subheading Conditional expressions

Conditional numeric expression is a primary numeric expression, which
has one of the following two syntactic forms:

@quotation
@verb{|if|} @i{b} @verb{|then|} @i{x} @verb{|else|} @i{y}

@verb{|if|} @i{b} @verb{|then|} @i{x}
@end quotation

@noindent
where @i{b} is an logical expression, @i{x} and @i{y} are numeric
expressions.

The resultant value of the conditional expression depends on the value
of the logical expression that follows the keyword @code{if}. If it
takes on the value @i{true}, the value of the conditional expression is
the value of the expression that follows the keyword @code{then}.
Otherwise, if the logical expression takes on the value @i{false}, the
value of the conditional expression is the value of the expression that
follows the keyword @code{else}. If the reduced form of the conditional
expression is used and the logical expression takes on the value
@i{false}, the resultant value of the conditional expression is zero.

@subheading Parenthesized expressions

Any numeric expression may be enclosed in parentheses that syntactically
makes it 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.

@subheading Arithmetic operators

In MathProg there are the following arithmetic operators, which may be
used in numeric expressions:

@quotation
@multitable @columnfractions .25 .75
@item @verb{|+|} @i{x} @tab unary plus
@item @verb{|-|} @i{x} @tab unary minus
@item @i{x} @verb{|+|} @i{y} @tab addition
@item @i{x} @verb{|-|} @i{y} @tab subtraction
@item @i{x} @verb{|less|} @i{y} @tab positive difference (if
@i{x}@tie{}<@tie{}@i{y} then 0 else @i{x}@tie{}@minus{}@tie{}@i{y})
@item @i{x} @verb{|*|} @i{y} @tab multiplication
@item @i{x} @verb{|/|} @i{y} @tab division
@item @i{x} @verb{|div|} @i{y} @tab quotient of exact division
@item @i{x} @verb{|mod|} @i{y} @tab remainder of exact division
@item @i{x} @verb{|**|} @i{y}, @i{x} @verb{|^|} @i{y} @tab
exponentiation (raise to power)
@end multitable
@end quotation

@noindent
where @i{x} and @i{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.

@subheading Hierarchy of operations

The following list shows the hierarchy of operations in numeric
expressions:

@quotation
@multitable @columnfractions .70 .30
@item @i{Operation} @tab @i{Hierarchy}
@item Evaluation of functions (@verb{|abs|}, @verb{|ceil|}, etc.) @tab
1st
@item Exponentiation (@verb{|**|}, @verb{|^|}) @tab 2nd
@item Unary plus and minus (@verb{|+|}, @verb{|-|}) @tab 3rd
@item Multiplication and division (@verb{|*|}, @verb{|/|}, @verb{|div|},
@verb{|mod|}) @tab 4th
@item Iterated operations (@verb{|sum|}, @verb{|prod|}, @verb{|min|},
@verb{|max|}) @tab 5th
@item Addition and subtraction (@verb{|+|}, @verb{|-|}, @verb{|less|})
@tab 6th
@item Conditional evaluation (@verb{|if|} @dots{} @verb{|then|} @dots{}
@verb{|else|}) @tab 7th
@end multitable
@end quotation

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.

@node Symbolic expressions
@section Symbolic expressions

@dfn{Symbolic expression} is a rule for computing a single symbolic
value represented in the form of 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.

@strong{Examples}

@quotation
@multitable @columnfractions .60 .40
@item @verb{|'May 2003'|} @tab (string literal)
@item @verb{|j|} @tab (dummy index)
@item @verb{|p|} @tab (unsubscripted parameter)
@item @verb{|s['abc',j+1]|} @tab (subscripted parameter)
@item @verb{|substr(name[i],k+1,3)|} @tab (function reference)
@item @verb{|if i in I then s[i,j] else t[i+1]|} @tab (conditional
expression)
@item @verb{|((10 * b[i,j]) & '.bis')|} @tab (parenthesized expression)
@end multitable
@end quotation

More general symbolic expressions containing two or more primary
symbolic expressions may be constructed by using the concatenation
operator.

@strong{Examples}

@example
'abc[' & i & ',' & j & ']'
"from " & city[i] & " to " & city[j]
@end example

The principles of evaluation of symbolic expressions are completely
analogous to that ones given for numeric expressions (see above).

@subheading Function references

In MathProg there are the following built-in functions which may be used
in symbolic expressions:

@quotation
@multitable @columnfractions .25 .75
@item @verb{|substr|}(@i{x},@tie{}@i{y}) @tab substring of @i{x}
starting from position @i{y}
@item @verb{|substr|}(@i{x}, @i{y}, @i{z}) @tab substring of @i{x}
starting from position @i{y} and having length @i{z}
@item @verb{|time2str|}(@i{t}, @i{f}) @tab converting calendar time to
character string@footnote{For details see @xref{Converting calendar time
to character string}.}
@end multitable
@end quotation

The first argument of @code{substr} must be a symbolic expression while
its second and optional third arguments must be numeric expressions.

The first argument of @code{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.

@subheading Symbolic operators

Currently in MathProg there is the only symbolic operator:

@quotation
@i{x} @verb{|&|} @i{y}
@end quotation

@noindent
where @i{x} and @i{y} are symbolic expressions. This operator means
concatenation of its two symbolic operands, which are character strings.

@subheading Hierarchy of operations

The following list shows the hierarchy of operations in symbolic
expressions:

@quotation
@multitable @columnfractions .70 .30
@item @i{Operation} @tab @i{Hierarchy}
@item Evaluation of numeric operations @tab 1st-7th
@item Concatenation (@verb{|&|}) @tab 8th
@item Conditional evaluation (@verb{|if|} @dots{} @verb{|then|} @dots{}
@verb{|else|}) @tab 9th
@end multitable
@end quotation

This hierarchy has the same meaning as explained in Section ``Numeric
expressions''.

@node Indexing expressions and dummy indices
@section Indexing expressions and dummy indices

@dfn{Indexing expression} is an auxiliary construction, which specifies
a plain set of @math{n}-tuples and introduces dummy indices. It has two
syntactic forms:

@iftex
@quotation
@verb{|{|} @math{entry_1,entry_2,@dots,entry_m} @verb{|}|}

@verb{|{|} @math{entry_1,entry_2,@dots,entry_m} : @math{predicate}
@verb{|}|}
@end quotation

@noindent
where @math{entry_1,entry_2,@dots,entry_m} are indexing entries,
@math{predicate} is a logical expression which specifies an optional
predicate.
@end iftex

@ifnottex
@quotation
@verb{|{|} @var{entry}-1, @var{entry}-2, @dots{}, @var{entry}-@i{m}
@verb{|}|}

@verb{|{|} @var{entry}-1, @var{entry}-2, @dots{}, @var{entry}-@i{m} :
@var{predicate} @verb{|}|}
@end quotation

@noindent
where @var{entry}-1, @var{entry}-2, @dots{}, @var{entry}-@i{m} are
indexing entries, @var{predicate} is a logical expression which
specifies an optional predicate.
@end ifnottex

Each indexing entry in the indexing expression has one of the following
three forms:

@quotation
@i{t} @verb{|in|} @i{S}

@iftex
@math{(t_1,t_2,@dots,t_k)} @verb{|in|} @math{S}
@end iftex

@ifnottex
(@i{t}1, @i{t}2, @dots{}, @i{tk}) @verb{|in|} @math{S}
@end ifnottex

@i{S}
@end quotation

@noindent
where
@iftex
@math{t_1,t_2,@dots,t_k}
@end iftex
@ifnottex
@i{t}1, @i{t}2, @dots{}, @i{tk}
@end ifnottex
are indices, @i{S} is a set expression (discussed in the next section),
which specifies the basic set.

The number of indices in the indexing entry must be the same as the
dimension of the basic set @i{S}, i.e. if @i{S} consists of 1-tuples,
the first form must be used, and if @i{S} consists of @i{n}-tuples,
where @i{n}@tie{}>@tie{}1, the second form must be used.

If the first form of the indexing entry is used, the index @i{t} can
be a dummy index only. If the second form is used, the indices
@iftex
@math{t_1,t_2,@dots,t_k}
@end iftex
@ifnottex
@i{t}1, @i{t}2, @dots{}, @i{tk}
@end ifnottex
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{t}
(if @i{S} is 1-dimensional) or
@iftex
@math{t_1,t_2,@dots,t_k}
@end iftex
@ifnottex
@i{t}1, @i{t}2, @dots{}, @i{tk}
@end ifnottex
(if @math{S} is @math{n}-dimensional) all specified as dummy indices.

@dfn{Dummy index} is an auxiliary model object, which acts like an
individual variable. Values assigned to dummy indices are components
of @i{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 do not need to be explicitly declared. Each
@emph{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:

@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 this 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 three sets:

@quotation
@i{A} = @{4, 7, 9@}

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

@i{C} = @{@i{a}, @i{b}, @i{c}@}
@end quotation

@noindent
where @i{A} and @i{C} consist of 1-tuples (singles), @i{B} consists of
2-tuples (doubles). And consider the following indexing expression:

@example
@{i in A, (j,k) in B, l in C@}
@end example

@noindent
where @i{i}, @i{j}, @i{k}, and @i{l} are dummy indices.

Although MathProg is not a procedural language, for any indexing
expression an equivalent algorithmic description could be given. In
particular, the algorithmic description of the indexing expression
above is the following:

@iftex
@quotation
@b{for all} @math{i@in A} @b{do}

@ @ @ @b{for all} @math{(j,k)@in B} @b{do}

@ @ @ @ @ @ @b{for all} @math{l@in C} @b{do}

@ @ @ @ @ @ @ @ @ @i{action};
@end quotation
@end iftex

@ifnottex
@example
for all i in A do
   for all (j,k) in B do
      for all l in C do
         action;
@end example
@end ifnottex

@noindent
where the dummy indices @i{i}, @i{j}, @i{k}, @i{l} are consecutively
assigned corresponding components of @i{n}-tuples from the basic sets
@i{A}, @i{B}, @i{C}, and @code{action} is some action that depends on
the context, where the indexing expression is used. For example, if the
@code{action} were printing current values of dummy indices, the output
would look like follows:

@iftex
@quotation
@tex
$\matrix{
i = 4 & j = 1 & k = Jan & l = a \cr
i = 4 & j = 1 & k = Jan & l = b \cr
i = 4 & j = 1 & k = Jan & l = c \cr
i = 4 & j = 1 & k = Feb & l = a \cr
i = 4 & j = 1 & k = Feb & l = b \cr
\dots & \dots & \dots   & \dots \cr
i = 9 & j = 3 & k = Jun & l = b \cr
i = 9 & j = 3 & k = Jun & l = c \cr
}$
@end tex
@end quotation
@end iftex

@ifnottex
@quotation
@multitable @columnfractions .15 .15 .15 .15
@item @i{i} = 4 @tab @i{j} = 1 @tab @i{k} = @i{Jan} @tab @i{l} = @i{a}
@item @i{i} = 4 @tab @i{j} = 1 @tab @i{k} = @i{Jan} @tab @i{l} = @i{b}
@item @i{i} = 4 @tab @i{j} = 1 @tab @i{k} = @i{Jan} @tab @i{l} = @i{c}
@item @i{i} = 4 @tab @i{j} = 1 @tab @i{k} = @i{Feb} @tab @i{l} = @i{a}
@item @i{i} = 4 @tab @i{j} = 1 @tab @i{k} = @i{Feb} @tab @i{l} = @i{b}
@item @dots{} @tab @dots{} @tab @dots{} @tab @dots{}
@item @i{i} = 9 @tab @i{j} = 3 @tab @i{k} = @i{Jun} @tab @i{l} = @i{b}
@item @i{i} = 9 @tab @i{j} = 3 @tab @i{k} = @i{Jun} @tab @i{l} = @i{c}
@end multitable
@end quotation
@end ifnottex

@page

Let the example indexing expression be used in the following iterated
operation: