gmpl.texi

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

Conditional set expression is a primary set expression that has the
following syntactic form:

@quotation
@verb{|if|} @i{b} @verb{|then|} @i{X} @verb{|else|} @i{Y}
@end quotation

@noindent
where @i{b} is an logical expression, @i{X} and @i{Y} are set
expressions, which must define sets of the same dimension.

The resultant value of the conditional expression depends on the value
of the logical expression that follows the keyword @verb{|if|}. If it
takes on the value @i{true}, the resultant set is the value of the
expression that follows the keyword @verb{|then|}. Otherwise, if the
logical expression takes on the value @i{false}, the resultant set is
the value of the expression that follows the keyword @verb{|else|}.

@subheading Parenthesized expressions

Any set expression may be enclosed in parentheses that syntactically
makes it primary set expression.

Parentheses may be used in set 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 Set operators

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

@quotation
@multitable @columnfractions .20 .80
@item @i{X} @verb{|union|} @i{Y} @tab union
@iftex
@math{X@cup Y}
@end iftex
@item @i{X} @verb{|diff|} @i{Y} @tab difference
@iftex
@math{X@backslash Y}
@end iftex
@item @i{X} @verb{|symdiff|} @i{Y} @tab symmetric difference
@iftex
@math{X@oplus Y}
@end iftex
@item @i{X} @verb{|inter|} @i{Y} @tab intersection
@iftex
@math{X@cap Y}
@end iftex
@item @i{X} @verb{|cross|} @i{Y} @tab cross (Cartesian) product
@iftex
@math{X@times Y}
@end iftex
@end multitable
@end quotation

@noindent
where @i{X} and @i{Y} are set expressions, which must define sets of the
identical dimension (except for the Cartesian product).

If the expression includes more than one set operator, all operators are
performed from left to right according to the hierarchy of operations
(see below).

The resultant value of the expression, which contains set operators, is
the result of applying the operators to their operands.

The dimension of the resultant set, i.e. the dimension of @i{n}-tuples,
of which the resultant set consists of, is the same as the dimension of
the operands, except the Cartesian product, where the dimension of the
resultant set is the sum of dimensions of the operands.

@subheading Hierarchy of operations

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

@quotation
@multitable @columnfractions .70 .30
@item @i{Operation} @tab @i{Hierarchy}
@item Evaluation of numeric operations @tab 1st-7th
@item Evaluation of symbolic operations @tab 8th-9th
@item Evaluation of iterated or ``arithmetic'' set (@verb{|setof|},
@verb{|..|}) @tab 10th
@item Cartesian product (@verb{|cross|}) @tab 11th
@item Intersection (@verb{|inter|}) @tab 12th
@item Union and difference (@verb{|union|}, @verb{|diff|},
@verb{|symdiff|}) @tab 13th
@item Conditional evaluation (@verb{|if|} @dots{} @verb{|then|} @dots{}
@verb{|else|}) @tab 14th
@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 Logical expressions
@section Logical expressions

@dfn{Logical expression} is a rule for computing a single logical value,
which can be either @i{true} or @i{false}.

The primary logical expression may be a numeric expression, relational
expression, iterated logical expression, or another logical expression
enclosed in parentheses.

@strong{Examples}

@quotation
@multitable @columnfractions .60 .40
@item @verb{|i+1|} @tab (numeric expression)
@item @verb{|a[i,j] < 1.5|} @tab (relational expression)
@item @verb{|s[i+1,j-1] <> 'Mar' & year|} @tab (relational expression)
@item @verb{|(i+1,'Jan') not in I cross J|} @tab (relational expression)
@item @verb{|S union T within A[i] inter B[j]|} @tab (relational
expression)
@item @verb{|forall{i in I, j in J} a[i,j] < .5 * b|} @tab (iterated
expression)
@item @verb{|(a[i,j] < 1.5 or b[i] >= a[i,j])|} @tab (parenthesized
expression)
@end multitable
@end quotation

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

@strong{Examples}

@example
not (a[i,j] < 1.5 or b[i] >= a[i,j]) and (i,j) in S
(i,j) in S or (i,j) not in T diff U
@end example

@subheading Numeric expressions

The resultant value of the primary logical expression, which is a
numeric expression, is @i{true}, if the resultant value of the numeric
expression is non-zero. Otherwise the resultant value of the logical
expression is @i{false}.

@subheading Relational expressions

In MathProg there are the following relational operators, which may be
used in logical expressions:

@quotation
@multitable @columnfractions .50 .50
@item @i{x} @verb{|<|} @i{y} @tab test on @i{x} < @i{y}
@item @i{x} @verb{|<=|} @i{y} @tab test on
@iftex
@math{x@leq y}
@end iftex
@ifnottex
@i{x} <= @i{y}
@end ifnottex
@item @i{x} @verb{|=|} @i{y}, @i{x} @verb{|==|} @i{y} @tab test on
@i{x} = @i{y}
@item @i{x} @verb{|>=|} @i{y} @tab test on
@iftex
@math{x@geq y}
@end iftex
@ifnottex
@i{x} >= @i{y}
@end ifnottex
@item @i{x} @verb{|<>|} @i{y}, @i{x} @verb{|!=|} @i{y} @tab test on
@iftex
@math{x@neq y}
@end iftex
@ifnottex
@i{x} != @i{y}
@end ifnottex
@item @i{x} @verb{|in|} @i{Y} @tab test on
@iftex
@math{x@in Y}
@end iftex
@ifnottex
@i{x} in @i{Y}
@end ifnottex
@iftex
@item @math{(x_1,@dots,x_n)} @verb{|in|} @math{Y} @tab test on
@math{(x_1,@dots,x_n)@in Y}
@end iftex
@ifnottex
@item (@i{x}1,@dots{},@i{xn}) @verb{|in|} @i{Y} @tab test on
(@i{x}1,@dots{},@i{xn}) in @i{Y}
@end ifnottex
@item @i{x} @verb{|not in|} @i{Y}, @i{x} @verb{|!in|} @i{Y} @tab test on
@iftex
@math{x@not@in Y}
@end iftex
@ifnottex
@i{x} not in @i{Y}
@end ifnottex
@iftex
@item @math{(x_1,@dots,x_n)} @verb{|not in|} @math{Y},
@math{(x_1,@dots,x_n)} @verb{|!in|} @math{Y} @tab test on
@math{(x_1,@dots,x_n)@not@in Y}
@end iftex
@ifnottex
@item (@i{x}1,@dots{},@i{xn}) @verb{|not in|} @i{Y}, @tab
@item (@i{x}1,@dots{},@i{xn}) @verb{|!in|} @i{Y} @tab test on
(@i{x}1,@dots{},@i{xn}) not in @i{Y}
@end ifnottex
@item @i{X} @verb{|within|} @i{Y} @tab test on
@iftex
@math{X@subseteq Y}
@end iftex
@ifnottex
@i{X} within @i{Y}
@end ifnottex
@item @i{X} @verb{|not within|} @i{Y}, @i{X} @verb{|!within|} @i{Y}
@tab test on
@iftex
@math{X@not@subseteq Y}
@end iftex
@ifnottex
@i{X} not within @i{Y}
@end ifnottex
@end multitable
@end quotation

@noindent
where @i{x},
@iftex
@math{x_1}, @dots, @math{x_n},
@end iftex
@ifnottex
@i{x}1, @dots{}, @i{xn},
@end ifnottex
@i{y} are numeric or symbolic expressions, @i{X} and @i{Y} are set
expression.

@i{Note:}

@quotation
@enumerate
@item In the operations @verb{|in|}, @verb{|not in|}, and @verb{|!in|}
the number of components in the first operands must be the same as the
dimension of the second operand.
@item In the operations @verb{|within|}, @verb{|not within|}, and
@verb{|!within|} both operands must have identical dimension.
@end enumerate
@end quotation

All the relational operators listed above have their conventional
mathematical meaning. The resultant value is @i{true}, if the
corresponding relation is satisfied for its operands, otherwise
@i{false}. (Note that symbolic values are ordered lexicographically,
and any numeric value precedes any symbolic value.)

@subheading Iterated expressions

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

@quotation
@var{iterated-operator} @var{indexing-expression} @var{integrand}
@end quotation

@noindent
where @var{iterated-operator} is the symbolic name of the iterated
operator to be performed (see below), @var{indexing expression} is an
indexing expression which introduces dummy indices and controls
iterating, @var{integrand} is a logical expression that participates in
the operation.

In MathProg there are two iterated operators, which may be used in
logical expressions:

@iftex
@quotation
@multitable @columnfractions .10 .25 .65
@item @verb{|forall|} @tab @math{@forall}-quantification @tab
@math{@forall(i_1,@dots,i_n)_{@in@Delta}[x(i_1,@dots,i_n)]}
@item @verb{|exists|} @tab @math{@exists}-quantification @tab
@math{@exists(i_1,@dots,i_n)_{@in@Delta}[x(i_1,@dots,i_n)]}
@end multitable
@end quotation
@end iftex

@ifnottex
@quotation
@multitable @columnfractions .10 .25 .65
@item @verb{|forall|} @tab A-quantification @tab
for all (@i{i}1,@dots{},@i{in}) in D: @i{x}(@i{i}1,@dots{},@i{in})
@item @verb{|exists|} @tab E-quantification @tab
exists @ (@i{i}1,@dots{},@i{in}) in D: @i{x}(@i{i}1,@dots{},@i{in})
@end multitable
@end quotation
@end ifnottex

@noindent
where
@iftex
@math{i_1}, @dots, @math{i_n}
@end iftex
@ifnottex
@i{i}1, @dots{}, @i{in}
@end ifnottex
are dummy indices introduced in the
indexing expression,
@iftex
@math{@Delta}
@end iftex
@ifnottex
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,
@iftex
@math{x(i_1,@dots,i_n)}
@end iftex
@ifnottex
@i{x}(@i{i}1,@dots{},@i{in})
@end ifnottex
is the integrand, a logical expression whose resultant value depends on
the dummy indices.

For
@iftex
@math{@forall}-quantification
@end iftex
@ifnottex
A-quantification
@end ifnottex
the resultant value of the iterated logical expression is @i{true}, if
the value of the integrand is @i{true} for all @i{n}-tuples contained in
the domain, otherwise @i{false}.

For
@iftex
@math{@exists}-quantification
@end iftex
@ifnottex
E-quantification
@end ifnottex
the resultant value of the iterated logical expression is @i{false}, if
the value of the integrand is @i{false} for all @i{n}-tuples contained
in the domain, otherwise @i{true}.

@subheading Parenthesized expressions

Any logical expression may be enclosed in parentheses that syntactically
makes it primary logical expression.

Parentheses may be used in logical 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 Logical operators

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

@quotation
@multitable @columnfractions .30 .70
@item @verb{|not|} @i{x}, @verb{|!|} @i{x} @tab negation
@item @i{x} @verb{|and|} @i{y}, @i{x} @verb{|&&|} @i{y} @tab
conjunction (logical ``and'')
@item @i{x} @verb{|or|} @i{y}, @i{x} @verb{$||$} @i{y} @tab
disjunction (logical ``or'')
@end multitable
@end quotation

@noindent
where @i{x} and @i{y} are logical expressions.

If the expression includes more than one logical operator, all
operators are performed from left to right according to the hierarchy
of operations (see below).

The resultant value of the expression, which contains logical
operators, is the result of applying the operators to their operands.

@subheading Hierarchy of operations

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

@quotation
@multitable @columnfractions .70 .30
@item @i{Operation} @tab @i{Hierarchy}
@item Evaluation of numeric operations @tab 1st-7th
@item Evaluation of symbolic operations @tab 8th-9th
@item Evaluation of set operations @tab 10th-14th
@item Relational operations (@verb{|<|}, @verb{|<=|}, etc.) @tab 15th
@item Negation (@verb{|not|}, @verb{|!|}) @tab 16th
@item Conjunction (@verb{|and|}, @verb{|&&|}) @tab 17th
@item
@iftex
@math{@forall}- and @math{@exists}-quantification
@end iftex
@ifnottex
A- and E-quantification
@end ifnottex
(@verb{|forall|}, @verb{|exists|}) @tab 18th
@item Disjunction (@verb{|or|}, @verb{$||$}) @tab 19th
@end multitable
@end quotation

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

@node Linear expressions
@section Linear expressions

@dfn{Linear expression} is a rule for computing so called @dfn{linear
form} or simply @dfn{formula}, which is a linear (or affine) function of
elemental variables.

The primary linear expression may be an unsubscripted variable,
subscripted variable, iterated linear expression, conditional linear
expression