Changeset 581


Ignore:
Timestamp:
May 22, 2011 7:37:33 AM (9 years ago)
Author:
pbelotti
Message:

intInfeasibility() checks lower/upper bounds to avoid non-null infeasibility upon out-of-bounds values, which triggers infeasibility in Couenne but not in Cbc, and this in turn makes the BB loop

Location:
stable/0.3/Couenne/src/branch
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • stable/0.3/Couenne/src/branch/CouenneObject.cpp

    r524 r581  
    134134
    135135
     136/// integer infeasibility: min {value - floor(value), ceil(value) -
     137/// value}. Handle special cases so that Cbc and Couenne agree. Also,
     138/// check out-of-bounds values.
     139
     140double CouenneObject::intInfeasibility (double value, double lb, double ub) const {
     141
     142  if      (value < lb) value = lb;
     143  else if (value > ub) value = ub;
     144
     145  return CoinMin (value - floor (value + COUENNE_EPS),
     146                          ceil  (value - COUENNE_EPS) - value);
     147}
     148
     149
    136150/// apply the branching rule
    137151OsiBranchingObject *CouenneObject::createBranch (OsiSolverInterface *si,
     
    314328  problem_ -> domain () -> pop ();
    315329
     330  int refInd = reference_ -> Index ();
     331  double point = info -> solution_ [refInd];
     332
    316333  if (pseudoMultType_ == INFEASIBILITY) {
    317334
    318     double point = info -> solution_ [reference_ -> Index ()];
    319 
    320335    if (reference_ -> isInteger ()) {
    321       if (retval < intInfeasibility (point)) {
     336
     337      CouNumber intInfeas = intInfeasibility (point, info -> lower_ [refInd], info -> upper_ [refInd]);
     338
     339      if (retval < intInfeas) {
    322340        if (downEstimate_ <       point  - floor (point)) downEstimate_ =       point  - floor (point);
    323341        if (upEstimate_   < ceil (point) -        point)  upEstimate_   = ceil (point) -        point;
    324         retval = intInfeasibility (point);
     342        retval = intInfeas;
    325343      }
    326344    }
     
    330348
    331349  return (reference_ -> isInteger ()) ?
    332     CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
     350    CoinMax (retval, intInfeasibility (point, info -> lower_ [refInd], info -> upper_ [refInd])) :
    333351    retval;
    334352}
     
    340358double CouenneObject::checkInfeasibility (const OsiBranchingInformation *info) const {
    341359
     360  int refInd = reference_ -> Index (); 
     361
    342362  if (reference_ -> Type () == VAR)
    343363    return (reference_ -> isInteger ()) ?
    344       intInfeasibility (info -> solution_ [reference_ -> Index ()]) : 0.;
     364      intInfeasibility (info -> solution_ [refInd],
     365                        info -> lower_    [refInd],
     366                        info -> upper_    [refInd]) : 0.;
    345367
    346368  double
     
    387409
    388410  return (reference_ -> isInteger ()) ?
    389     CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
     411    CoinMax (retval, intInfeasibility (info -> solution_ [refInd],
     412                                       info -> lower_    [refInd],
     413                                       info -> upper_    [refInd])) :
    390414    retval;
    391415}
  • stable/0.3/Couenne/src/branch/CouenneObject.hpp

    r578 r581  
    157157
    158158  /// integer infeasibility: min {value - floor(value), ceil(value) - value}
    159   virtual double intInfeasibility (double value) const
    160   {return CoinMin (value - floor (value + COUENNE_EPS), ceil (value - COUENNE_EPS) - value);}
     159  virtual double intInfeasibility (double value, double lb, double ub) const;
    161160
    162161  /// Defines safe interval percentage for using LP point as a branching point
  • stable/0.3/Couenne/src/branch/infeasibility.cpp

    r569 r581  
    8484  problem_ -> domain () -> pop (); // domain not used below
    8585
     86  int refInd = reference_ -> Index (); 
     87
    8688  if (reference_ -> isInteger ()) {
    87     CouNumber intinfeas = intInfeasibility (info -> solution_ [reference_ -> Index ()]);
     89    CouNumber intinfeas = intInfeasibility (info -> solution_ [refInd],
     90                                            info -> lower_    [refInd],
     91                                            info -> upper_    [refInd]);
    8892    if (intinfeas > retval)
    8993      retval = intinfeas;
     
    9599  jnlst_ -> Printf (J_DETAILED, J_BRANCHING,
    96100                    "infVar x%d ==> returning %e\n", reference_ -> Index (), (reference_ -> isInteger ()) ?
    97                     CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
     101                    CoinMax (retval, intInfeasibility (info -> solution_ [refInd],
     102                                                       info -> lower_    [refInd],
     103                                                       info -> upper_    [refInd])) :
    98104                    retval);
    99105
  • stable/0.3/Couenne/src/branch/infeasibilityVT.cpp

    r259 r581  
    3131      if (downEstimate_ <       point  - floor (point)) downEstimate_ =       point  - floor (point);
    3232      if (upEstimate_   < ceil (point) -        point)  upEstimate_   = ceil (point) -        point;
    33       return intInfeasibility (point);
     33      return intInfeasibility (point,
     34                               info -> lower_ [indexVar],
     35                               info -> upper_ [indexVar]);
    3436    } else return (upEstimate_ = downEstimate_ = 0.);
    3537  }
     
    258260
    259261  return (reference_ -> isInteger ()) ?
    260     CoinMax (retval, intInfeasibility (info -> solution_ [reference_ -> Index ()])) :
     262    CoinMax (retval, intInfeasibility (info -> solution_ [indexVar],
     263                                       info -> lower_    [indexVar],
     264                                       info -> upper_    [indexVar])) :
    261265    retval;
    262266}
Note: See TracChangeset for help on using the changeset viewer.