gmpl.texi

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

%* gmpl.texi *%

\input texinfo @c -*-texinfo-*-
@c %**start of header
@setfilename gmpl.info
@settitle Modeling Language GNU MathProg
@c %**end of header

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

Copyright @copyright{} 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007,
2008, 2009 Andrew Makhorin, Department for Applied Informatics, Moscow
Aviation Institute, Moscow, Russia. All rights reserved.

Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
02110-1301, USA.

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.

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.

Permission is granted to copy and distribute translations of this manual
into another language, under the above conditions for modified versions.
@end copying

@dircategory Scientific software
@direntry
* gmpl: (gmpl).                 GNU MathProg Language Reference
@end direntry

@titlepage
@title Modeling Language GNU MathProg
@subtitle Language Reference
@subtitle Draft Edition, for GLPK Version 4.34
@subtitle December 2008
@author Andrew Makhorin
Moscow Aviation Institute, Moscow, Russia
@page
@vskip 0pt plus 1filll
@insertcopying
@end titlepage

@contents

@ifnottex
@node Top
@top GNU MathProg Language Reference
@end ifnottex

@menu
* Introduction::
* Coding model description::
* Expressions::
* Statements::
* Model data::
* Date and time functions::
* Solving models with glpsol::
* Example model description::
* Acknowledgements::
@end menu

@node Introduction
@chapter Introduction

@menu
* Linear programming problem::
* Model objects::
* Structure of model description::
@end menu

@dfn{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: @emph{Robert@tie{}Fourer}, @emph{David@tie{}M.@tie{}Gay},
and @emph{Brian@tie{}W.@tie{}Kernighan}, ``A Modeling Language for
Mathematical Programming.'' @emph{Management Science} 36 (1990)
pp.@tie{}519-54.}

@indent
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 translation, a program called the 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 solver
to obtain numeric solution of the problem.

@node Linear programming problem
@section Linear programming problem

In MathProg it is assumed that the linear programming (LP) problem has
the following statement:

@iftex
@quotation
@quotation
@quotation
minimize (or maximize)
@tex
$$z=c_1x_1+c_2x_2+\dots+c_nx_n+c_0\eqno(1)$$
@end tex
subject to linear constraints
@tex
$$\matrix{
L_1\leq a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n\leq U_1\cr
L_2\leq a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n\leq U_2\cr
.\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\ \ .\cr
L_m\leq a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n\leq U_m\cr
}\eqno(2)$$
@end tex
and bounds of variables
@tex
$$\matrix{
l_1\leq x_1\leq u_1\cr
l_2\leq x_2\leq u_2\cr
.\ \ .\ \ .\ \ .\cr
l_n\leq x_n\leq u_n\cr
}\eqno(3)$$
@end tex
@end quotation
@end quotation
@end quotation

@noindent
where:
@multitable @columnfractions .20 .80
@item @math{x_1}, @math{x_2}, @dots, @math{x_n} @tab are variables;
@item @math{z} @tab is the objective function;
@item @math{c_1}, @math{c_2}, @dots, @math{c_n} @tab are coefficients of
the objective function;
@item @math{c_0} @tab is the constant term (``shift'') of the objective
function;
@item @math{a_{11}}, @math{a_{12}}, @dots, @math{a_{mn}} @tab are
constraint coefficients;
@item @math{L_1}, @math{L_2}, @dots, @math{L_m} @tab are lower
constraint bounds;
@item @math{U_1}, @math{U_2}, @dots, @math{U_m} @tab are upper
constraint bounds;
@item @math{l_1}, @math{l_2}, @dots, @math{l_n} @tab are lower bounds of
variables;
@item @math{u_1}, @math{u_2}, @dots, @math{u_n} @tab are upper bounds of
variables.
@end multitable
@end iftex

@ifnottex
@quotation
Minimize (or maximize)

@quotation
@i{z} = @i{c}1 @i{x}1 + @i{c}2 @i{x}2 + @dots{} + @i{cn xn} + @i{c}0
@end quotation

subject to linear constraints

@quotation
@i{L}1 <= @i{a}11 @i{x}1 + @i{a}12 @i{x}2 + @dots{} + @i{a}1@i{n} @i{xn}
<= @i{U}1 @*
@i{L}2 <= @i{a}21 @i{x}1 + @i{a}22 @i{x}2 + @dots{} + @i{a}2@i{n} @i{xn}
<= @i{U}2 @*
. . . . . @*
@i{Lm} <= @i{am}1 @i{x}1 + @i{am}2 @i{x}2 + @dots{} + @i{amn} @i{xn} <=
@i{Um}
@end quotation

and bounds of variables

@quotation
@i{l}1 <= @i{x}1 <= @i{u}1 @*
@i{l}2 <= @i{x}2 <= @i{u}2 @*
. . . . . @*
@i{ln} <= @i{xn} <= @i{un}
@end quotation
@end quotation

@multitable @columnfractions .30 .70
@item where:
@item @i{x}1, @i{x}2, @dots{}, @i{xn} @tab are variables;
@item @i{z} @tab is the objective function;
@item @i{c}1, @i{c}2, @dots{}, @i{cn} @tab are coefficients of the
objective function;
@item @i{c}0 @tab is the constant term (``shift'') of the objective
function;
@item @i{a}11, @i{a}12, @dots{}, @i{amn} @tab are constraint
coefficients;
@item @i{L}1, @i{L}2, @dots{}, @i{Lm} @tab are lower constraint bounds;
@item @i{U}1, @i{U}2, @dots{}, @i{Um} @tab are upper constraint bounds;
@item @i{l}1, @i{l}2, @dots{}, @i{ln} @tab are lower bounds of
variables;
@item @i{u}1, @i{u}2, @dots{}, @i{un} @tab are upper bounds of
variables.
@end multitable
@end ifnottex

@page

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:

@iftex
@quotation
@multitable @columnfractions .25 .75
@item @math{-@infty<x<+@infty} @tab Free (unbounded) variable
@item @math{x@geq l} @tab Variable with lower bound
@item @math{x@leq u} @tab Variable with upper bound
@item @math{l@leq x@leq u} @tab Double-bounded variable
@item @math{x=l@ (=u)} @tab Fixed variable
@end multitable

@multitable @columnfractions .25 .75
@item @math{-@infty<@sum a_jx_j<+@infty} @tab Free (unbounded) linear
form
@item @math{@sum a_jx_j@geq L} @tab Inequality constraint ``greater than
or equal to''
@item @math{@sum a_jx_j@leq U} @tab Inequality constraint ``less than or
equal to''
@item @math{L@leq@sum a_jx_j@leq U} @tab Double-bounded inequality
constraint
@item @math{@sum a_jx_j=L@ (=U)} @tab Equality constraint
@end multitable
@end quotation
@end iftex

@ifnottex
@quotation
@multitable @columnfractions .40 .60
@item @minus{}inf < @i{x} < +inf @tab Free (unbounded) variable
@item @i{x} >= @i{l} @tab Variable with lower bound
@item @i{x} <= @i{u} @tab Variable with upper bound
@item @i{l} <= @i{x} <= @i{u} @tab Double-bounded variable
@item @i{x} = @i{l} (= @i{u}) @tab Fixed variable
@item @tab
@item @minus{}inf < sum @i{aj} @i{xj} < +inf @tab Free (unbounded)
linear form
@item sum @i{aj} @i{xj} >= @i{L} @tab Inequality constraint ``greater
than or equal to''
@item sum @i{aj} @i{xj} <= @i{U} @tab Inequality constraint ``less than
or equal to''
@item @i{L} <= sum @i{aj} @i{xj} <= @i{U} @tab Double-bounded inequality
constraint
@item sum @i{aj} @i{xj} = @i{L} (= @i{U}) @tab Equality constraint
@end multitable
@end quotation
@end ifnottex

In addition to pure LP problems MathProg allows mixed integer linear
programming (MIP) problems, where some (or all) structural variables are
restricted to be integer.

@node Model objects
@section Model objects

In MathProg the model is described in terms of sets, parameters,
variables, constraints, and objectives, which are called @dfn{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, @i{n}-dimensional array @i{A} is the
mapping:
@iftex
@tex
$$A:\Delta\rightarrow\Xi,\eqno(4)$$
@end tex
where @math{@Delta@subseteq S_1@times S_2@times@dots@times S_n} is a
subset of the Cartesian product of indexing sets, @math{@Xi} is a set of
the array members. In MathProg the set @math{@Delta} is called
@dfn{subscript domain}. Its members are @math{n}-tuples
@math{(i_1,i_2,@dots,i_n)}, where @math{i_1@in S_1}, @math{i_2@in S_2},
@dots, @math{i_n@in S_n}.
@end iftex

@ifnottex
@quotation
@i{A} : D @minus{}> X,
@end quotation

@noindent
where D within
@i{S}1@tie{}x@tie{}@i{S}2@tie{}x@tie{}@dots{}@tie{}x@tie{}@i{Sn} is a
subset of the Cartesian product of indexing sets, X is a set of the
array members. In MathProg the set D is called @dfn{subscript domain}.
Its members are @i{n}-tuples
(@i{i}1,@tie{}@i{i}2,@tie{}@dots{},@tie{}@i{in}), where
@i{i}1@tie{}in@tie{}@i{S}1, @i{i}2@tie{}in@tie{}@i{S}2, @dots{},
@i{in}@tie{}in@tie{}@i{Sn}.
@end ifnottex

If @i{n} = 0, the Cartesian product above has exactly one element
(namely, 0-tuple), so it is convenient to think scalar objects as
0-dimensional arrays which have one member.

The type of array members is determined by the type of corresponding
model object as follows:

@quotation
@multitable @columnfractions .20 .80
@item @i{Model object} @tab @i{Array member}
@item Set @tab Elemental plain set
@item Parameter @tab Number or symbol
@item Variable @tab Elemental variable
@item Constraint @tab Elemental constraint
@item Objective @tab Elemental objective
@end multitable
@end quotation

In order to refer to a particular object member the object should be
provided with subscripts. For example, if @i{a} is 2-dimensional
parameter built over
@iftex
@math{I@times J},
@end iftex
@ifnottex
@i{I}@tie{}x@tie{}@i{J},
@end ifnottex
a reference to its particular
member can be written as @i{a}[@i{i},@tie{}@i{j}], where
@iftex
@math{i@in I} and @math{j@in J}.
@end iftex
@ifnottex
@i{i}@tie{}in@tie{}@i{I} and @i{j}@tie{}in@tie{}@i{J}.
@end ifnottex
It is understood that scalar objects being 0-dimensional need no
subscripts.

@node Structure of model description
@section Structure of model description

It is sometimes desirable to write a model which, at various points,
may require different data for each problem to be solved using that
model. For this reason in MathProg the model description consists of
two parts: model section and data section.

@dfn{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.

@dfn{Data section} is an optional part of the model description that
contains data specific for a particular problem.

Depending on what is more convenient model and data sections can be
placed either in one file or in two separate files. The latter feature
allows to have arbitrary number of different data sections to be used
with the same model section.

@node Coding model description
@chapter Coding model description

@menu
* Symbolic names::
* Numeric literals::
* String literals::
* Keywords::
* Delimiters::
* Comments::
@end menu

Model description is coded in plain text format using ASCII character
set. Valid characters acceptable in the model description are the
following:

@itemize @bullet
@item alphabetic characters:

@quotation
@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 _|}
@end quotation

@item numeric characters:

@quotation
@verb{|0 1 2 3 4 5 6 7 8 9|}
@end quotation

@item special characters:

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

@item white-space characters:

@quotation
@verb{|SP HT CR NL VT FF|}
@end quotation
@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:

@itemize @bullet
@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.

@node Symbolic names
@section Symbolic names