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

[Robert Horvath]

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)

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

 

> -----Original Message-----

> From: address@hidden [mailto:help-

> address@hidden On Behalf Of Brady

> Hunsaker

> Sent: Monday, May 03, 2004 9:13 PM

> To: address@hidden

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

>

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

>

>

>

>

> _______________________________________________

> Help-glpk mailing list

> address@hidden

> http://mail.gnu.org/mailman/listinfo/help-glpk