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

[Thomas Charles CONWAY]

Chris writes:
> 
> 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.
> 

This can pretty easily be added. I won't do it now though - harald
is planning to hire a summer student to work in this area, so that
can be a job for them.

> > % The form of an [in]equation is
> > % 	a1.x1 + a2.x2 + ... + an.xn {=<,=,>=} b
> > % where alll the numbers are floats.
> s/alll/all/
> 

Fixed.

> 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 documentation now reads:

% The form of an [in]equation is
%       a1.x1 + a2.x2 + ... + an.xn {=<,=,>=} b
% where all the numbers are floats, a variable xn may occur multiple
% times in an equation (or the objective function) - the solver simplifies
% all the inequations.

> 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
> 

The solver trivially handles both situations.
Of course, an equation that has an overall coefficient of 0 for a
variable does no constrain that variable, so if it occurs in the
objective, then you may have a linear program that is unbounded.


Thomas