[m-dev.] diff: lpQ - new module for linear programming over Q

[Thomas Charles CONWAY]

Vanessa Joy TEAGUE, you write:
> Hi Tom,
> 
> Could you review this please?
> 
> 
> Estimated hours taken: 240
> 
> Add some functions to lp and change number representation to rationals.
> 
> compiler/lpQ.m:
	...
> compiler/rat.m:

For consitency and clarity, it might be better to name lpQ.m lp_rational.m
and rat.m rational.m (yes I know I chose rat as a filename, but I doubt
the extra few keystrokes will kill anyone :-).

> %-----------------------------------------------------------------------------%
> % Copyright (C) 1997-1998 The University of Melbourne.
> % This file may only be copied under the terms of the GNU General
> % Public License - see the file COPYING in the Mercury distribution.
> %-----------------------------------------------------------------------------%
> %
> % file: lpQ.m
> % main author: conway,	Oct 1997
> % rewrite by vjteag, Feb 1998

the convention elsewhere is to simply put

% main autors: conway, vjteag

> %
> % This module implements:
> %
> % A linear constraint solver that finds an optimal solution to a set of 
> % linear [in]equalities with respect to some objective function. It does 
> % this using the simplex method.
> %
> % 	The form of an [in]equation is
> % 		a1.x1 + a2.x2 + ... + an.xn {=<,=,>=} b
> % 	where all the numbers are rats, a variable xn may occur multiple
> % 	times in an equation (or the objective function) - the solver simplifies
> % 	all the inequations.
> % 	By defaut, there is an additional constraint on each of the `xn's:
> %		xn >= 0
> % 	If you want xn to take on any value, you can include it in the list
> % 	of URS (UnRestricted in Sign) variables.
> %
> % 	The objective function is simply a weighted sum of the variables.
> %
> % 	The `x's are represented by `term__var's. The varset from which
> % 	they are allocated is passed to the solver because it needs to
> % 	introduce new variables as part of the solving algorithm.
> %
> %
> % Fourier-Motzkin elimination, which takes a polyhedron represented by 
> % a list of inequations (represented in the same way as in the 
> % constraint solver) and projects it onto a subset of the variables 
> % contained in the inequations. 
> %
> % 
> % A convex hull algorithm, which takes a list of polyhedrons (represented
> % by lists of inequations), and computes the smallest convex set which is 
> % a superset of all of them. 
> % For details of the algorithm, see Benoy and King.
> %
> %
> % A test for entailment of one constraint (a single inequality) by a
> % conjunction of other inequalities (a polyhedron).  This uses the constraint 
> % solver to find the point on the polyhedron closest to the boundary of the 
> % constraint, then checks whether it is on the correct side of the boundary.
> % It assumes that all variables are non-negative.

By "constraint solver" do you mean linear program optimizer?

Some comments about the following predicates and the intended
interpretation of their arguments would be helpful.

> :- pred project(equations, list(var), equations).
> :- mode project(in, in, out) is det.
> 
> :- pred convex_hull(list(equations), equations, varset, varset).
> :- mode convex_hull(in, out, in, out) is det.
> 
> :- pred widen(equations, equations, varset, equations).
> :- mode widen(in, in, in, out) is det.
> 
> :- pred entailed(equation, equations, varset).
> :- mode entailed(in, in, in) is semidet.
> 
> :- pred is_false(equation).
> :- mode is_false(in) is semidet.
> 
> :- pred false_eqn(equation).
> :- mode false_eqn(out) is det.
> 
> % Exported for testing purposes.
> :- pred eqns_to_vectors(equations, list(vector)).
> :- mode eqns_to_vectors(in, out) is det.
> 
> :- pred fm_standardize_equations(equations, equations).
> :- mode fm_standardize_equations(in, out) is det.
> 
> 
> 
> :- pred vectors_to_eqns(list(vector), equations).
> :- mode vectors_to_eqns(in, out) is det.
> vectors_to_eqns(Vectors, Equations) :-
> 	Vec_to_eqn = lambda([pair(Map,Rat)::in, Eqn::out] is det, (
> 		map__to_assoc_list(Map, List),
> 		Eqn = eqn(List, (=<), Rat)
> 	)),
> 	list__map(Vec_to_eqn, Vectors, Equations).	
> 		

Our convention elsewhere is to write

:- pred foo(...).
:- mode foo(...) is Det.
				<- blank line
foo(...) :-

> 
> gcd0(A, B) = (
> 		A = 1 -> 1
> 	;	B = 1 -> 1
> 	;	A = B -> A
> 	;	A > B -> gcd0(A - B, B)
> 	;	gcd0(B - A, A)
> 	).

There is a more efficient version which uses A mod B. Is there
any good reason not to use it?

Thomas
-- 
ZZ:wq!
^X^C
Thomas Conway               				      conway at cs.mu.oz.au
AD DEUM ET VINUM	  			   Nail here [] for new monitor.