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

[Brady Hunsaker]

I accidentally replied to the sender instead of to the list.  The email
is included below.

Brady

-----Forwarded Message-----
From: Brady Hunsaker <address@hidden>
To: Din Rao <address@hidden>
Subject: Re: [Help-glpk] FW: trying to stop solver
Date: Mon, 03 May 2004 15:11:28 -0400

On Thu, 2004-04-29 at 15:53, Din Rao wrote:
> Dear glpk help,
> 
> Here is the screenshot of glpsol trying to solve an LP (no binary or
> integer variables are present):
> 
> lpt_read_prob: reading LP data from `lpoct9_noint.txt'...
> lpt_read_prob: 186719 variables, 58727 constraints
> lpt_read_prob: 93665 lines were read
> lpx_simplex: original LP has 58727 rows, 186719 columns, 476946
> non-zeros
> lpx_simplex: presolved LP has 56188 rows, 157793 columns, 417847
> non-zeros
> lpx_adv_basis: size of triangular part = 56163
>       0:   objval =  -1.882780893e+05   infeas =   1.000000000e+00 (0)
>     200:   objval =  -8.302602730e+04   infeas =   9.287234663e-01 (0)
>     400:   objval =  -5.596677665e+04   infeas =   9.188069813e-01 (0)
>     600:   objval =  -5.005017544e+04   infeas =   7.717075583e-01 (0)
>     800:   objval =  -2.835981613e+04   infeas =   7.477124460e-01 (0)
>    1000:   objval =  -2.822934262e+04   infeas =   7.320822590e-01 (0)
> -----------------------------------------------------------------------------------------------------------------------------------------------
>  
> This process goes on and on and on..................
>  
> Please advise as to how to stop the solver from making NEGLIGIBLE
> progress AFTER the infeasibilities have reached 0.
>  
> I have noticed that the "objval" gets only less then 1% better after
> every 200 iterations AFTER the infeasibility has reached 0.
>  
> Notice that the LP is not exactly large and our UNIX server comparable
> to 800 MHz
> (Only 476,946 vars and 58,727 constraints) 
>  
> Thank you,
> Regards
>  
> Din Rao
> Senior Engineer
> Concerto Software
> Bethesda, MD 20171
> (301) 272-2251
> www.cforcetech.com
> 

Note that your infeasibilities are not zero in the lines posted.  At the
1000th pivot, the infeasibility is 0.732.  So GLPK is having trouble
finding a feasible solution.  As Robert Horvath pointed out, GLPK is in
phase 1 of the 2-phase simplex method.

So the questions I would consider are
1. What about this problem makes finding a feasible solution difficult?
2. Is a "near-feasible" solution acceptable or not?

The first question is highly dependent on the structure of the problem. 
Perhaps changing your formulation would allow for an easier solution,
but this depends very much on the problem.

If the answer to the second question is that a "near-feasible" solution
is acceptable, then you may consider Robert Horvath's suggestion of
adjusting the feasibility tolerance.  In general I would discourage
this, however, since it is compromising your constraints in an
unpredictable way.  Certainly any results found in this way should be
checked by a human to make sure that the violations are acceptable.

Rather than change the parameter, I would recommend adjusting your
model.  If you can "loosen" the appropriate constraints, you may be able
to find a model that gets an optimal solution in a reasonable amount of
time.  In this case you'll know exactly what constraints were
compromised to get the solution.  The main way to do this is to think
about the model and then do some trial-and-error of loosening suspected
constraints.  Then again, it may not work well even then.

Good luck,

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