RE: [Help-glpk] Re: MIP rounding

[Robert Fourer]

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


> -----Original Message-----
> From: address@hidden [mailto:help-glpk-
> address@hidden On Behalf Of Andrew Makhorin
> Sent: Monday, July 07, 2003 5:13 AM
> To: Jean-Sebastien Roy; address@hidden
> Cc: address@hidden
> Subject: [Help-glpk] Re: MIP rounding
>
> Thank you for your information.
>
> >I recently found a strange behavior in GLPK. When I input the following
> >problem :
> >
> >Minimize
> >obj: c
> >Subject To
> >cst: x - 1000000.0 c <= 0
> >Bounds
> >0.5 <= x
> >Binaries
> >c
> >End
> >
> >Whose solution is c = 1, x = 0.5. (min = 1)
> >GLPK is quite happy to answer c = 0, x = 0.5. (min = 0 !)
> >
> >I understand that the large (1e6) coefficient is the cause of the
> >problem (the relaxed having solution c=5e-7, x=0.5, and c being
> >assimilated as the integer 0), but a basic check for feasibility would
> >be nice (or trying to solve the LP with integer variables fixed to
> >their optimal values).
>
> This is a common difficulty that arises due to "big M". In fact, one
> could think that c = 0, x = 0.5 is wrong answer, because then the
> constraint x - 1e6 c <= 0 is violated with the absolute error 0.5.
> However, absolute error is not an adequate measure of infeasibility,
> because it can be made arbitrary small or large simply by scaling
> constraint coefficients. Thus, scaling the constraint in order to
> normalize constraint coefficients we have 1e-6 x - c <= 0, in which
> case the absolute error is 0.5e-6. Although in your case it is obvious
> how to obtain the answer which is mathematically correct, it is
> impossible in general case, if the problem is ill-conditioned and
> inexact arithmetic is used, because actually the solver finds the
> solution of some slightly perturbed problem, not the original one.
>
> >btw, when asked to output an MPS file for this problem, glpsol omits the
> >'RHS' part (which is empty) which is problem for some solvers (SBB,
> >LP_SOLVE).
>
> I consulted the "IBM Optimization Library Guide and Reference" (it is
> publically available on the internet). In the section "Passing your
> model using MPS format", subsection "Order of records" there is the
> phrase: "The RHS, RANGES, and BOUNDS sections are optional." (In fact,
> the RHS section was mandatory only in old versions of the MPS format
> where the BOUNDS section was not used, i.e. all structural variables
> could be only non-negative.)
>
> Andrew Makhorin
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/help-glpk