[Help-glpk] Re: MIP rounding

[Andrew Makhorin]

Dear Prof. Fourer,

Thank you very much for your interest in glpk and for your comments.

I would like to note that the glpk b&b solver checks integrality
exactly in the same way as you explained for cplex (with exception that
the default tolerance used by glpk is 1e-6).

It seems to me that Jean's question concerns another issue. In the
question the variable c is binary, and its lower bound is exact zero,
i.e. it is not something close to zero being given with a finite
precision. On the other hand, fixing a variable at *exact* zero bound
is equivalent to removing it from the problem. So, fixing c at zero we
have the following lp problem:

min c (= 0)
s.t. x <= 0
     x >= 0.5

I think no one would say that this problem is feasible, because it is
infeasible. And in this context the answer x = 0.5, c = 0 really seems
a bit strange. So, Jean's suggestion to check feasibility whenever the
basic solution of some LP relaxation satisfies the integrality tolerance
seems to me very reasonable (at least to issue a warning message like
cplex does).

Andrew Makhorin


----- Original Message ----- 
From: Robert Fourer <address@hidden>
To: 'Andrew Makhorin' <address@hidden>; 'Jean-Sebastien Roy' <address@hidden>; 
<address@hidden>
Sent: Tuesday, July 08, 2003 1:06 AM
Subject: RE: [Help-glpk] Re: MIP rounding


> 
> Regarding the "MIP rounding" issue, I think what typically happens in this
> situation is that, given the problem
> 
>    min   c
>    st    x - 1000000 c <= 0
>          x >= 0.5
>          c in {0,1}
> 
> an branch-and-bound code for integer programming first solves the continuous
> relaxation of the problem,
> 
>    min   c
>    st    x - 1000000 c <= 0
>          x >= 0.5
>          0 <= c <= 1
> 
> to which the optimal solution is
> 
>    x = 0.5, c = 0.0000005
> 
> IP codes typically have an "integrality tolerance": if an integer variable 
> comes
> within this tolerance of an integer value, then it is considered to be 
> integer.
> This is necessary so that integer solutions found through continuous 
> relaxations
> will not be overlooked due to insignificant rounding errors.  In this case,
> however, if the integrality tolerance is 5e-7 or more, then the result will 
> be to
> return a solution of x = 0.5, c = 0.
> 
> CPLEX can be used to demonstrate this behavior, provided the "presolve" 
> option is
> disabled.  With the "round" option disabled and the "integrality" option
> (tolerance) left at its default value of 1e-5, I get the follwing results 
> (using
> AMPL to drive CPLEX):
> 
>    ampl: option solver cplex81;
>    ampl: var x >= 0.5;
>    ampl: var c binary;
>    ampl: minimize obj: c;
>    ampl: subj to con: x - 1000000 * c <= 0;
> 
>    ampl: option cplex_options 'round=0 presolve=0';
>    ampl: solve;
> 
>    CPLEX 8.1.0: optimal (non-)integer solution; objective 5e-07
>    0 MIP simplex iterations
>    0 branch-and-bound nodes
>    1 integer variables would be rounded (maxerr = 5e-07).
>    Assigning integrality = 1e-09 might help.
>    Currently integrality = 1e-05.
> 
>    ampl: display x,c;
>    x = 0.5
>    c = 5e-07
> 
> When I set the tolerance to 1e-7 instead, the "correct" solution is returned:
> 
>    ampl: option cplex_options 'integrality=1e-07 round=0 presolve=0';
>    ampl: solve;
>    CPLEX 8.1.0: integrality=1e-07
> 
>    CPLEX 8.1.0: optimal integer solution; objective 1
>    1 MIP simplex iterations
>    0 branch-and-bound nodes
> 
>    ampl: display x,c;
>    x = 0.5
>    c = 1
> 
> Going back to the default tolerance and the default setting of "round" (which
> causes all integer variables' values to be rounded before the solution is 
> returned)
> results in the "wrong" solution that prompted this query:
> 
>    ampl: option cplex_options 'presolve 0';
>    ampl: solve;
> 
>    CPLEX 8.1.0: optimal (non-)integer solution; objective 5e-07
>    1 MIP simplex iterations
>    0 branch-and-bound nodes
>    1 integer variables rounded (maxerr = 5e-07).
>    Assigning integrality = 1e-09 might help.
>    Currently integrality = 1e-05.
> 
>    ampl: display x,c;
>    x = 0.5
>    c = 0
> 
> Scaling the constraint won't help with this.  But changing the units of 
> measure of
> c so that, say, it is replaced by mc == 1000000 * c will remedy the problem.
> 
> Robert Fourer
> address@hidden
>