[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] RE: glpk 4.4 Question

From: Robert Horvath
Subject: [Help-glpk] RE: glpk 4.4 Question
Date: Tue, 20 Apr 2004 10:05:41 +0200

> 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
> for the solution


PS: Please send your questions to the address@hidden list as well to help
others too.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]