(5)Applying Constraint Logic Programming Languages for Modelling Multi-objective Decision Making under Uncertainty

[Software Functions]

This software distribution represents the revised prototype of solvers 
for integer programming (IP) problems from specification to
solution. It includes three representative systems: TIP, a
logic modelling tool for IP, MGBAS, an IP solver based on 
  Minimised Geometric Buchberger Algorithm (MGBA), and SIPS, a
stochastic IP solver based on MGBA.

1. TIP

TIP (Transformation of IP) is a tool on Mathematica for
modelling IP with logic. It is based on our research for modelling IP
with logic: language and implementation. In this research,
we propose a language L+ for IP, in which we write logical
specification of an IP problem. L+ is a language based on the
predicate logic, but is extended with meta predicates such as
at_least(m,S), where m is a non-negative integer, meaning that at
least m predicates in the set S of formulas hold. The meta
predicates are introduced to facilitate reasoning about a model of 
an IP problem rigorously and logically. L+ is executable in the sense 
that formulas in L+ are mechanically translated into a set of 
mathematical formulas, called IP formulas, which most of existing 
IP solvers accept. We give a systematic method for translating formulas 
in L+ to IP formulas. The translation is rigorously defined, verified 
and implemented in Mathematica 3.0.

TIP consists of the functions GenIP[spec_,decl_,opts___]}, 
RRC[spec_], RuleE[spec_], RuleT[spec_], RuleN[spec_], 
RuleF[spec_] and RuleR[spec_]. RRC[spec_] (Remove
Redundant Constraints) checks whether a given constraint is redundant
and outputs empty set {} if redundant or else a simplified
constraint after substituting the value of the bounds. 
RuleE[spec_] to RuleR[spec_] define the transformation
rules E to R respectively. GenIP[spec_,decl_,opts___]
is the main function which is called with a logical specification 
spec, a list of propositional variables and integer variables with
their bounds decl and an option opts. If user want to
simplify the generated IP-formulas, they can input 
IPFormSimplify->True as an option, otherwise they input
nothing. TIP first checks each variable in the logic
specification spec whether it is declared in decl and
outputs an error message if some variables are not declared or 
else outputs the generated IP-formulas. Please see the whole program of
TIP and some examples in detail.

2. MGBAS

MGBAS is a generic symbolic IP solver based on Minimised
Geometric Buchberger Algorithm (MGBA). Algorithm MGBA is the
result of the joint work with Yike and Prof. John Darlington. Recently,
various algebraic IP solvers have been proposed based on the theory
of Groebner bases. The key idea is to encode an IP problem
IP{A,C} into a special ideal associated with the constraint
matrix A and the cost (object) function C. An important property
of such an encoding is that its Groebner basis corresponds
directly to the test set of the IP problem. The main difficulty of
these new methods is the size of the Groebner bases generated. In
the proposed algorithms, large Groebner bases are caused by
either introducing additional variables or by considering the
generic IP problem IP{A,C}. Based on these analyses,  
we propose a new algebraic algorithm MGBA which
combines various recently developed symbolic IP solvers such as Hosten
and Sturmfel's method(GRIN) and Thomas's truncated GBA to achieve a
very efficient and general IP solver.

MGBAS includes two parts: one is to compute the 
reduced Groebner basis i.e. the test set for IP problem; the other
is to find a feasible solution and derive an optimal solution by using 
the test set to reduce the feasible solution. For any standard
formulation of IP problems like as
 Min {Cx : Ax=b, x in N^n}
if you input the objective function Cx and constraints Ax=b, you
can get an optimal solution for the IP problems directly by running
MGBAS. Please see the whole program of MGBAS and some examples in details.

3. SIPS

SIPS is a stochastic IP solver based on MGBA. A stochastic
IP problem is an IP problem with uncertain parameters describing 
optimisation problems with uncertainty. The applications of IP
range from future productivity in a production problem to a 
hydro-electric power station to demands at various nodes in a 
transportation network. We consider a class of stochastic IP called 
chance constrained IP (CIP) P0:

    Min h(x) subject to
    Prob{Tx<= $\xi$}>=$\gamma$
    Ax=b
    x in N^n, $\xi$ is a vector of random variables.\\

Model P0 has two properties: (1) The probabilistic constraint is
not separable and (2) integer variables are required to model setup decisions.
The available techniques for stochastic programming do not provide a 
satisfactory solution for models that have integer
variables and nonseparable chance (probabilistic) constraints arising
from nonnormal distributions.

Based on MGBA, SIPS solve the above model successfully. We also applied 
SIPS to a job scheduling problem. Users can input some The
preliminary experiments indicate that this method provides a realistic
solution for the challenge of stochastic IP.

[Necessary Environments]

Currently the only environment necessary for running the denoted software
is the computer algebra system Mathematica(tm) 3.0 from Wolfram
Research. Mathematica is available for all major Unix platforms including
Linux, for Windows NT/95, and for MacOS. For further information on
Mathematica, see http://www.wolfram.com

[Quantity of the software and file configuration]

The package is currently 6.3 MB in size (gzipped tar file) and structured
as follows:

    Readme-E        ... document for explaining the structure of the package
    doct            ... this file 
    TIP/            ... Transformation of IP
     README-TIP
     TIP.nb
    MGBAS/          ... Minimised Geometric Buchberger Solver for IP
     README-MGBA
     Example-MGBA
     mgba.c
     mgba
    SIPS/           ... Stochastic IP Solver  
     README-SIPS
     Example-SIPS
     sips.c
     sips

[FTP]

• README
• Program and Documents [43K]