/home/coin/SVN-release/OS-2.1.1/Couenne/src/branch/operators/branchExprQuad.cpp

Go to the documentation of this file.
00001 /* $Id: branchExprQuad.cpp 141 2009-06-03 04:19:19Z pbelotti $ */
00002 /*
00003  * Name:    branchExprQuad.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: return branch data for quadratic forms
00006  *
00007  * (C) Carnegie-Mellon University, 2007-08.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CoinHelperFunctions.hpp"
00012 
00013 #include "exprQuad.hpp"
00014 #include "CouenneObject.hpp"
00015 #include "CouenneBranchingObject.hpp"
00016 
00017 //#define DEBUG
00018 
00021 CouNumber exprQuad::selectBranch (const CouenneObject *obj, 
00022                                   const OsiBranchingInformation *info,
00023                                   expression *&var, 
00024                                   double * &brpts, 
00025                                   double * &brDist, // distance of current LP
00026                                                     // point to new convexifications
00027                                   int &way) {
00028   int ind = -1;
00029 
00030   // use a combination of eigenvectors and bounds
00031 
00032   CouNumber delta = (*(obj -> Reference ())) () - (*this) ();
00033 
00034   /*printf ("infeasibility: ");
00035   obj -> Reference () -> print (); 
00036   printf (" [%g=%g] := ", 
00037           (*(obj -> Reference ())) (), info -> solution_ [obj -> Reference () -> Index ()]);
00038           print (); printf (" [%g]\n", (*this) ());*/
00039 
00040   brpts  = (double *) realloc (brpts,    sizeof (double));
00041   brDist = (double *) realloc (brDist, 2*sizeof (double));
00042 
00043   way = TWO_RAND;
00044 
00045   // depending on where the current point is w.r.t. the curve,
00046   // branching is done on the eigenvector corresponding to the minimum
00047   // or maximum eigenvalue
00048 
00049   std::vector <std::pair <CouNumber, 
00050     std::vector <std::pair <exprVar *, CouNumber> > > >::iterator         fi = eigen_.begin ();
00051 
00052   std::vector <std::pair <CouNumber, 
00053     std::vector <std::pair <exprVar *, CouNumber> > > >::reverse_iterator ri = eigen_.rbegin ();
00054 
00055   CouNumber max_span = -COUENNE_INFINITY;
00056 
00057   bool changed_sign = false;
00058 
00060 
00061   for (;((delta < 0.) && (fi != eigen_. end  ()) || // && (fi -> first < 0.) ||
00062          (delta > 0.) && (ri != eigen_. rend ()));  // && (ri -> first > 0.));
00063        ++fi, ++ri) {
00064 
00065     std::vector <std::pair <exprVar *, CouNumber> > &ev = 
00066       (delta < 0.) ? fi -> second : ri -> second;
00067 
00068     if ((delta < 0.) && (fi -> first > 0.) ||
00069         (delta > 0.) && (ri -> first < 0.)) {
00070 
00071       if (max_span > 0.) break; // if found a variable already, return
00072       changed_sign = true;      // otherwise, keep in mind we are on
00073                                 // the wrong eigenvalues' sign
00074     }
00075 
00076     for (std::vector <std::pair <exprVar *, CouNumber> >::iterator j = ev.begin ();
00077          j != ev.end (); ++j) {
00078 
00079       int index = j -> first -> Index ();
00080 
00081       CouNumber 
00082         lb = info -> lower_ [index],
00083         ub = info -> upper_ [index];
00084 
00085       // only accept variable if not fixed
00086       if (fabs (ub-lb) > COUENNE_EPS) {
00087 
00088           // no variable was found but the eigenvalue is already
00089           // positive (negative)
00090           //      changed_sign &&
00091           //      (max_span < 0.))
00092 
00093         CouNumber span = -1;
00094 
00095         if ((lb < -COUENNE_INFINITY) ||
00096             (ub >  COUENNE_INFINITY) ||
00097             ((span = (ub-lb) * fabs (j -> second)) > max_span + COUENNE_EPS)) {
00098 
00099           ind = index;
00100           var = j -> first;
00101 
00102           *brpts = obj -> midInterval (info -> solution_ [index], lb, ub);
00103 
00104           if (changed_sign) 
00105             break;
00106 
00107           if (span >= 0) max_span = span; // finite, keep searching
00108           else break;                     // span unbounded, stop searching
00109         }
00110       }
00111     }
00112   }
00113 
00114   if ((eigen_.size () == 0) // if no eigenvalue has been computed yet
00115       || (ind < 0)) {       // or no index was found, pick largest interval
00116 
00117     CouNumber max_span = -COUENNE_INFINITY;
00118 
00119     for (std::map <exprVar *, std::pair <CouNumber, CouNumber> >::iterator i = bounds_. begin ();
00120          i != bounds_. end (); ++i) {
00121 
00122       CouNumber
00123         lb = i -> second.first,
00124         ub = i -> second.second,
00125         span = ub - lb;
00126 
00127       if ((span > COUENNE_EPS) && 
00128           (span > max_span)) {
00129 
00130         var = i -> first;
00131         ind = var -> Index ();
00132       }
00133     }
00134 
00135     if (ind < 0) {
00136 
00137       var = obj -> Reference ();
00138       ind = var -> Index ();
00139 
00140       *brpts = obj -> midInterval (info -> solution_ [ind],
00141                                    info -> lower_ [ind],
00142                                    info -> upper_ [ind]);
00143     }
00144     else *brpts = obj -> midInterval (info -> solution_ [ind], 
00145                                       info -> lower_ [ind],
00146                                       info -> upper_ [ind]);      
00147     //return fabs (delta);
00148   }
00149 
00150   return (brDist [0] = brDist [1] = fabs (delta));
00151 }

Generated on Mon May 3 03:05:19 2010 by  doxygen 1.4.7