RE: [Help-glpk] FW: trying to stop solver

[Brady Hunsaker]

On Tue, 2004-05-04 at 04:37, Robert Horvath wrote:
> I agree that accepting a non feasible solution for phase 2 is not a
> very good idea. But if you consider the problem that is to be solved
> it has 56188 auxiliary variables and 157793 structural ones, so it has
> about 213981 variables total. GLPK calculates the infeasibilities by
> adding all the infeasibilities found at each variable. Two things
> follow:
> 
> 1.   IF the infeasibilities are distributed evenly then
> .732/213981=3.42e-6 per one variable, which is acceptable I think.(I
> would really appreciate some remarks on that from Brady Hunsaker)
> 

GLPK reports the sum of infeasibilities in the output.  However, the
parameter LPX_K_TOLBND is not used against the sum of infeasibilities. 
It is used as a relative tolerance for each constraint individually. 
The feasibility check occurs in the function spx_check_bbar in file
glpspx1.c.  This function is called with the tolerance given as the
second parameter.

By changing the tolerance to 0.001, for example, then every constraint
can be violated by 0.1% of its right-hand-side.  Actually it's slightly
more complicated than that to deal with very small right-hand-sides; you
can check the code for the exact expression.

The point is that the tolerance is not really dependent on the number of
inequalities.

> 2.   If the infeasibilities are not distributed evenly, for example
> only a few variables are responsible for the infeasibilities found,
> then there is a problem, and the problem needs to be rearranged, or it
> just takes more time to calculate phase II.
> 
>  
> 
> Regards
> 
> Robert
> 
>  

An additional concern is that the tolerance is really meant to handle
numerical difficulties resulting from rounding and floating-point
arithmetic.  That is, GLPK doesn't "know" that it can take advantage of
an increased tolerance when looking for a feasible solution.  It still
does its best to satisfy the constraints.  When rounding errors
naturally occur, it doesn't discount the solution as quickly.  So in
this case we're relying on rounding errors to take advantage of the
increased tolerance.

That's why I think it is better to leave the tolerance at its default
value and try loosening some constraints instead.  With this approach,
GLPK knows to take advantage of the changes and we know exactly what
compromises we have made.

Brady

-- 
Brady Hunsaker
Assistant Professor
Industrial Engineering
University of Pittsburgh
http://www.engr.pitt.edu/hunsaker/