|
From: | Robert Horvath |
Subject: | RE: [Help-glpk] FW: trying to stop solver |
Date: | Fri, 30 Apr 2004 11:00:39 +0200 |
I got good news! The problem is that you try
to solve a way too big problem, and glpsol is invented for smaller scale ones
by default. However if you read the
mail I just sent to a guy, you will be able to solve your problem, since he had
the same. > > Dear Robert: > > I have a
questions regarding the stand alone solver "glpsol" > > I am running
a large MIP (120 binary vars) and the following >
characteristics: > > lpx_simplex:
original LP has 58727 rows, 186719 columns, 476946 > non-zeros > lpx_simplex:
presolved LP has 56188 rows, 157793 columns, 417847 > non-zeros > > When I run
this, I currently see the following output: > > 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) > 1200: objval
= 1.069233214e+04 infeas = 7.167442459e-01 (0) > 1400:
objval = 1.741619443e+05 infeas = 6.993087736e-01 (0) > > My questions
to you are: > > - What is
this infeasibilities column and how is it related to Branch > & Bound?
(I have forgotten from my student days) In this case
infeasibilities column has nothing to do with Branch and Bound!! In this case
glpk tries to give you the relaxation of the problem. (Finding the solution of
the lp problem.) And whats more it is in phase I, that means that glpk tries to
find values for variables that comply to the set of constraints you made. The
infeasibilities column gives the sum of the difference of all those structural
and auxiliary variables that are out of their bounds. For example If the
constraints have a line like: 1 >= x10 <= 15, and in the current
iteration x10 has a value of 16, then x10 is greater than its upper bound, and
it vould add 1 ( abs(15-16) ) to the infeasibilities. > > - Is there
anyway to make the precision lower while solving MIPs? > You have two
options: use lpx_set_real_parm to set the LPX_K_TOLBND parameter from the
default 1e-7 to bigger (eg. 1e-2), since this is the number to which glpk
compares the infeasibility. Or if you use glpsol: You have to hack
code: in src\glplpx3.c you need to edit line 51 that is like this:
lp->tol_bnd = 1e-7; to set to the
value you chose. > - In other
words, is there an option that would make the solver to > recognize
whether or not a variable is "good enough" to be considered > a ZERO or a
ONE for the solution Regards Robert PS: Please send your
questions to the address@hidden list as well to help others too. From:
address@hidden
[mailto:address@hidden On Behalf Of Din Rao Dear glpk help,
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 -----Original
Message----- |
[Prev in Thread] | Current Thread | [Next in Thread] |