[m-dev.] For review: mercury linear inequation solver/termination analysis mods.

[Christopher Rodd SPEIRS]

Hi,
	I have just got a few points to make.  Firstly, i was wondering
if it is reasonable for the return value of the solver to differentiate
between infeasible sets of constraints, and sets of constraints where
the value of the objective function is unbounded.  Although the
difference is not used by termination analysis, it would be nice to be
able to differentiate between the two.

> %
> % file: lp.m
> % main author: conway,	Oct 1997
> %
> % 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 alll the numbers are floats.
s/alll/all/

Also, is it possible to have an inequality of the form
	a1.x1 + a2.x2 + a3.x1 + a4.x2 ... 
(ie where one variable occurs in the one inequality multiple times)?
If so, could you document it.

The next couple of things i bring up because lp_solve handled them
badly, and i needed to add workarounds to the termination analysis code
to ensure that these situations did not occur.  If your solver can
handle these situations, then perhaps you could remove the parts of the
analysis which avoid these situations occuring.  If you dont have
time/cant find them could you just add an XXX reminder.

Basically the only complications occur when you have inequalities of the
form 
	a1.x1 + a2.x2 + a3.x1 + a4.x2 ... 
One thing which lp_solve barfs on is if the inequality is
	1.x1 + -1.x1 {=<,=,>=} b
Clearly this is not really the worlds friendliest equation, but
unfortinatly it comes up rather easily in termination analysis.

The other problem were equations where one variable was multiplied by
zero
	0.x1 + 1.x2 >= 3

In terms of where to look for the lp_solve workarounds, see
proc_inequalities_scc_remove_useless_offsets in term_pass1.m

In case you were interested, lp_solve also had a problem with
inequalities which contained no variables, (eg 0 >= 1 constraints), but
this will not be a problem for your system, as it does not allow
constants on the left hand side of the [in]equation.

Chris