gmpl.texi

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

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

@noindent
where @i{p}[@i{i}, @i{j}, @i{k}, @i{l}] may be a 4-dimensional numeric
parameter or some numeric expression whose resultant value depends on
@i{i}, @i{j}, @i{k}, and @i{l}. In this case the action is summation,
so the resultant value of the primary numeric expression
@iftex
is:

@quotation
@math{@displaystyle@sum_{i@in A,(j,k)@in B,l@in C}(p_{ijkl}).}
@end quotation
@end iftex
@ifnottex
is the sum of @i{p}[@i{i}, @i{j}, @i{k}, @i{l}], where summation is
performed over all @i{i}@tie{}in@tie{}@i{A},
(@i{j},@i{k})@tie{}in@tie{}@i{B}, and @i{l}@tie{}in@tie{}@i{C}.
@end ifnottex

Now let the example indexing expression be used as a primary set
expression. In this case the action is gathering all 4-tuples
(quadruples) of the form (@i{i}, @i{j}, @i{k}, @i{l}) in one set, so the
resultant value of such operation is simply the Cartesian product of the
basic sets:

@iftex
@quotation
@math{A@times B@times C=@{(i,j,k,l):i@in A,(j,k)@in B,l@in C@}.}
@end quotation
@end iftex

@ifnottex
@quotation
@i{A} x @i{B} x @i{C} = @{(@i{i},@i{j},@i{k},@i{l}) :
@i{i}@tie{}in@tie{}@i{A}, (@i{j},@i{k})@tie{}in@tie{}@i{B},
@i{l}@tie{}in@tie{}@i{C}@}
@end quotation
@end ifnottex

@noindent
Note that in this case the same indexing expression might be written
in the reduced form:

@example
@{A, B, C@}
@end example

@noindent
because the dummy indices @i{i}, @i{j}, @i{k}, and @i{l} are not
referenced and therefore their symbolic names are not needed.

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:

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

@noindent
In this case the action is generating the parameter members, where each
member has the form @i{p}[@i{i},@tie{}@i{j},@tie{}@i{k},@tie{}@i{l}].

As was said above, some indices in the second form of indexing entries
may be numeric or symbolic expressions, not only dummy indices. In this
case resultant values of such expressions play role of some logical
conditions to select only that @i{n}-tuples from the Cartesian product
of basic sets, which satisfy these conditions.

Consider, for example, the following indexing expression:

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

@noindent
where @i{i}, @i{k}, @i{l} are dummy indices, and @i{i}@minus{}1 is
a numeric expression. The algorithmic decsription of this indexing
expression is the following:

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

@ @ @ @b{for all} @math{(j,k)@in B} @b{and} @math{j=i-1} @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 and j = i-1 do
      for all l in C do
         action;
@end example
@end ifnottex

@noindent
Thus, if this indexing expression were used as a primary set expression,
the resultant set would be the following:

@quotation
@{(4,@i{May},@i{a}), (4,@i{May},@i{b}), (4,@i{May},@i{c}),
(4,@i{Jun},@i{a}), (4,@i{Jun},@i{b}), (4,@i{Jun},@i{c})@}.
@end quotation

@noindent
Should note that in this case the resultant set consists of 3-tuples,
not of 4-tuples, because in the indexing expression there is no dummy
index that corresponds to the first component of 2-tuples from the set
@i{B}.

The general rule is: the number of components of @i{n}-tuples defined
by an indexing expression is the same as the number of dummy indices in
that indexing expression, where the correspondence between dummy indices
and components on @math{n}-tuples in the resultant set is positional,
i.e. the first dummy index corresponds to the first component, the
second dummy index corresponds to the second component, etc.

In many cases it is needed to select a subset from the Cartesian
product of some sets. This may be attained by using an optional logical
predicate, which is specified in indexing expression after the last or
the only indexing entry.

Consider, for another example, the following indexing expression:

@example
@{i in A, (j,k) in B, l in C: i <= 5 and k <> 'Mar'@}
@end example

@noindent
where the logical expression following the colon is a predicate. The
algorithmic description of this indexing expression 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}

@ @ @ @ @ @ @ @ @ @b{if} @math{i@leq 5} @b{and} @math{k@neq} `@i{Mar}'
@b{then}

@ @ @ @ @ @ @ @ @ @ @ @ @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
         if i <= 5 and k != 'Mar' then
            action;
@end example
@end ifnottex

@noindent
Thus, if this indexing expression were used as a primary set expression,
the resultant set would be the following:

@quotation
@{(4,1,@i{Jan},@i{a}), (4,1,@i{Feb},@i{a}), (4,2,@i{Apr},@i{a}),
@dots{}, (4,3,@i{Jun},@i{c})@}.
@end quotation

If no predicate is specified in the indexing expression, the one, which
takes on the value @i{true}, is assumed.

@node Set expressions
@section Set expressions

@dfn{Set expression} is a rule for computing an elemental set, i.e.
a collection of @i{n}-tuples, where components of @i{n}-tuples are
numeric and symbolic quantities.

The primary set expression may be a literal set, unsubscripted set,
subscripted set, ``arithmetic'' set, indexing expression, iterated set
expression, conditional set expression, or another set expression
enclosed in parentheses.

@strong{Examples}

@quotation
@multitable @columnfractions .60 .40
@item @verb{|{(123,'aa'), (i,'bb'), (j-1,'cc')}|} @tab (literal set)
@item @verb{|I|} @tab (unsubscripted set)
@item @verb{|S[i-1,j+1]|} @tab (subscripted set)
@item @verb{|1..t-1 by 2|} @tab (``arithmetic'' set)
@item @verb{|{t in 1..T, (t+1,j) in S: (t,j) in F}|} @tab (indexing
expression)
@item @verb{|setof{i in I, j in J}(i+1,j-1)|} @tab (iterated expression)
@item @verb{|if i < j then S[i] else F diff S[j]|} @tab (conditional
expression)
@item @verb{|(1..10 union 21..30)|} @tab (parenthesized expression)
@end multitable
@end quotation

More general set expressions containing two or more primary set
expressions may be constructed by using certain set operators.

@strong{Examples}

@example
(A union B) inter (I cross J)
1..10 cross (if i < j then @{'a', 'b', 'c'@} else @{'d', 'e', 'f'@})
@end example

@subheading Literal sets

Literal set is a primary set expression, which has the following two
syntactic forms:

@iftex
@quotation
@math{@{e_1,e_2,@dots,e_m@}}

@math{@{(e_{11},@dots,e_{1n}),(e_{21},@dots,e_{2n}),@dots,(e_{m1},@dots,
e_{mn})@}}
@end quotation

@noindent
where @math{e_1}, @dots, @math{e_m}, @math{e_{11}}, @dots, @math{e_{mn}}
are numeric or symbolic expressions.
@end iftex

@ifnottex
@quotation
@{@i{e}1, @i{e}2, @dots{}, @i{em}@}

@{(@i{e}11, @dots{}, @i{e}1@i{n}), (@i{e}21, @dots{}, @i{e}2@i{n}),
@dots{}, (@i{em}1, @dots{}, @i{emn})@}
@end quotation

@noindent
where @i{e}1, @dots{}, @i{em}, @i{e}11, @dots{}, @i{emn} are numeric or
symbolic expressions.
@end ifnottex

If the first form is used, the resultant set consists of 1-tuples
(singles) enumerated within the curly braces. It is allowed to specify
an empty set, which has no 1-tuples.

If the second form is used, the resultant set consists of @i{n}-tuples
enumerated within the curly braces, where a particular @i{n}-tuple
consists of corresponding components enumerated within the parentheses.
All @i{n}-tuples must have the same number of components.

@subheading Unsubscripted sets

If the primary set expression is an unsubscripted set (which must be
0-dimensional), the resultant set is an elemental set associated with
the corresponding set object.

@subheading Subscripted sets

The primary set expression, which refers to a subscripted set, has the
following syntactic form:

@iftex
@quotation
@math{name[i_1,i_2,@dots,i_n],}
@end quotation

@noindent
where @math{name} is the symbolic name of the set object, @math{i_1},
@math{i_2}, @dots, @math{i_n} are subscripts.
@end iftex

@ifnottex
@quotation
@i{name}[@i{i}1, @i{i}2, @dots{}, @i{in}],
@end quotation

@noindent
where @i{name} is the symbolic name of the set object, @i{i}1, @i{i}2,
@dots{}, @i{in} are subscripts.
@end ifnottex

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 set object with which the subscript list is associated.

Actual values of subscript expressions are used to identify a particular
member of the set object that determines the resultant set.

@subheading ``Arithmetic'' set

The primary set expression, which is an ``arithmetic'' set, has the
following two syntactic forms:

@iftex
@quotation
@math{t_0} @verb{|..|} @math{t_f} @verb{|by|} @math{@delta t}

@math{t_0} @verb{|..|} @math{t_f}
@end quotation

@noindent
where @math{t_0}, @math{t_1}, and @math{@delta t} are numeric
expressions (the value of @math{@delta t} must not be zero). The second
form is equivalent to the first form, where @math{@delta t=1}.

If @math{@delta t>0}, the resultant set is determined as follows:

@quotation
@math{@{t:@exists k@in{@cal Z}(t=t_0+k@delta t,@ t_0@leq t@leq t_f)@}}
@end quotation

@noindent
Otherwise, if @math{@delta t<0}, the resultant set is determined as
follows:

@quotation
@math{@{t:@exists k@in{@cal Z}(t=t_0+k@delta t,@ t_f@leq t@leq t_0)@}}
@end quotation
@end iftex

@ifnottex
@quotation
@i{t}0 @verb{|..|} @i{tf} @verb{|by|} @i{dt}

@i{t}0 @verb{|..|} @i{tf}
@end quotation

@noindent
where @i{t}0, @i{t}1, and @i{dt} are numeric expressions (the value of
@i{dt} must not be zero). The second form is equivalent to the first
form, where @i{dt}@tie{}=@tie{}1.

If @i{dt}@tie{}>@tie{}0, the resultant set is determined as follows:

@quotation
@{@i{t}: exists @i{k} in Z (@i{t} = @i{t}0 + @i{k} @i{dt}, @i{t}0 <=
@i{t} <= @i{tf})@}
@end quotation

@noindent
Otherwise, if @i{dt}@tie{}<@tie{}0, the resultant set is determined as
follows:

@quotation
@{@i{t}: exists @i{k} in Z (@i{t} = @i{t}0 + @i{k} @i{dt}, @i{tf} <=
@i{t} <= @i{t}0)@}
@end quotation
@end ifnottex

@subheading Indexing expressions

If the primary set expression is an indexing expression, the resultant
set is determined as described in Section ``Indexing expressions and
dummy indices'' (see above).

@subheading Iterated expressions

Iterated set expression is a primary set expression, which has the
following syntactic form:

@quotation
@verb{|setof|} @var{indexing-expression} @var{integrand}
@end quotation

@noindent
where @var{indexing-expression} is an indexing expression which
introduces dummy indices and controls iterating, @var{integrand} is
either a single numeric or symbolic expression or a list of numeric and
symbolic expressions separated by commae and enclosed in parentheses.

If the integrand is a single numeric or symbolic expression, the
resultant set consists of 1-tuples and is determined as follows:

@iftex
@quotation
@math{@{x:(i_1,@dots,i_n)@in@Delta@},}
@end quotation

@noindent
where @math{x} is a value of the integrand, @math{i_1}, @dots,
@math{i_n} are dummy indices introduced in the indexing expression,
@math{@Delta}
@end iftex
@ifnottex
@quotation
@{@i{x}: (@i{i}1, @dots{}, @i{in}) in D@},
@end quotation

@noindent
where @i{x} is a value of the integrand, @i{i1}, @dots{}, @i{in} are
dummy indices introduced in the indexing expression, D
@end ifnottex
is the domain, a set of @i{n}-tuples specified by the indexing
expression which defines particular values assigned to the dummy indices
on performing the iterated operation.

If the integrand is a list containing @i{m} numeric and symbolic
expressions, the resultant set consists of @i{m}-tuples and is
determined as follows:

@iftex
@quotation
@math{@{(x_1,@dots,x_m):(i_1,@dots,i_n)@in@Delta@},}
@end quotation

@noindent
where @math{x_1}, @dots, @math{x_m} are values of the expressions in the
integrand list, @math{i_1}, @dots, @math{i_n} and @math{@Delta}
@end iftex
@ifnottex
@quotation
@{(@i{x}1, @dots{}, @i{xm}): (@i{i}1, @dots{}, @i{in}) in D@},
@end quotation

@noindent
where @i{x}1, @dots{}, @i{xm} are values of the expressions in the
integrand list, @i{i}1, @dots{}, @i{in} and D
@end ifnottex
have the same meaning as above.

@subheading Conditional expressions