/home/coin/SVN-release/OS-2.4.0/Couenne/src/branch/operators/branchExprExp.cpp

Go to the documentation of this file.
00001 /* $Id: branchExprExp.cpp 708 2011-06-23 14:04:59Z pbelotti $
00002  *
00003  * Name:    branchExprExp.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: return branch gain and branch object for exponentials
00006  *
00007  * (C) Carnegie-Mellon University, 2006-10.
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include "CoinHelperFunctions.hpp"
00012 
00013 #include "CouenneExprExp.hpp"
00014 #include "CouenneObject.hpp"
00015 #include "CouenneBranchingObject.hpp"
00016 #include "CouenneProjections.hpp"
00017 #include "CouenneFunTriplets.hpp"
00018 
00019 using namespace Couenne;
00020 
00023 CouNumber exprExp::selectBranch (const CouenneObject *obj, 
00024                                  const OsiBranchingInformation *info,
00025                                  expression *&var, 
00026                                  double * &brpts, 
00027                                  double * &brDist, // distance of current LP
00028                                                    // point to new convexifications
00029                                  int &way) {
00030 
00031   // two cases: inside and outside the curve. 
00032   //
00033   // Inside: the distance depends on the projection of the current
00034   // point onto the would-be upper envelopes, which forces us to look
00035   // at it numerically. If both bounds are infinite, create a ThreeWay
00036   // branch.
00037   //
00038   // Outside: it suffices to project the current point on the line
00039   // (i.e. to get the closest point on the line) to get the maxi-min
00040   // displacement.
00041   //
00042   // As for all monotone functions, after choosing *brpts it is
00043   // equivalent to choose w's or x's index as ind, as the implied- and
00044   // propagated bounds will do the rest.
00045 
00046   var = argument_;
00047 
00048   brDist = (double *) realloc (brDist, 2 * sizeof (double));
00049   brpts  = (double *) realloc (brpts, sizeof (double));
00050 
00051   int
00052     ind = var -> Index (),
00053     wi  = obj -> Reference () -> Index ();
00054 
00055   assert ((ind >= 0) && (wi >= 0));
00056 
00057   CouNumber y0 = info -> solution_ [wi],
00058             x0 = info -> solution_ [ind],
00059             l  = info -> lower_    [ind],
00060             u  = info -> upper_    [ind];
00061 
00062   // Outside //////////////////////////////////////////////////////////////////
00063 
00064   if (y0 < exp (x0)) {
00065 
00066     // Look for point (x1,y1) on curve y=exp(x) closest to current
00067     // (x0,y0), branch at x1
00068 
00069     *brpts = obj -> midInterval (powNewton (x0, y0, exp, exp, exp), l, u, info);
00070 
00071     way = TWO_RAND;
00072 
00073     y0 -= exp (*brpts);
00074     x0 -= *brpts;
00075 
00076     return sqrt (brDist [0] = brDist [1] = sqrt (x0*x0 + y0*y0)); // exact distance
00077   }
00078 
00079   // Inside. Four cases: ///////////////////////////////////////////////////////
00080 
00081   if ((l < -COUENNE_INFINITY) && 
00082       (u >  COUENNE_INFINITY)) { // unbounded in both directions
00083 
00084     /*    // TODO: restore when we can do three-way branching
00085 #if 0
00086     brpts = (double *) realloc (brpts, 2 * sizeof (double));
00087     way = THREE_CENTER; // focus on central convexification first
00088     brpts [0] = x0;       // draw vertical   from (x0,y0) south to curve y=exp(x)
00089     brpts [1] = log (y0); //      horizontal              east
00090     CouNumber 
00091       a = y0 - exp (x0),  // sides of a triangle with (x0,y0)
00092       b = log (y0) - x0;  // as one of the vertices
00093     // exact distance from central interval, from others it's a and b
00094     return (a * cos (atan (a/b))); 
00095 #endif    */
00096 
00097     // follow South-East diagonal to find point on curve
00098     // so that current point is surely cut 
00099     *brpts = 0.5 * (x0 + log (y0)); 
00100     way = TWO_RAND;
00101 
00102     return CoinMin (brDist [0] = log (y0) - x0, 
00103                     brDist [1] = y0 - exp (x0));
00104   }
00105 
00106   // 2,3) at least one of them is finite
00107 
00108   if (l < - COUENNE_INFINITY) { // 2) unbounded from below --> break vertically
00109 
00110     *brpts = obj -> midInterval (x0, l, u, info);
00111 
00112     way = TWO_RIGHT;
00113     return CoinMin (brDist [0] = y0 - exp (x0), 
00114                     brDist [1] = projectSeg (x0, y0, *brpts, exp (*brpts), u, exp (u), -1));
00115   } 
00116 
00117   if (u > COUENNE_INFINITY) { // 3) unbounded from above -- break horizontally
00118 
00119     *brpts = obj -> midInterval (log (y0), l, u, info);
00120 
00121     way = TWO_LEFT;
00122     return CoinMin (brDist [0] = projectSeg (x0, y0, l, exp (l), *brpts, exp (*brpts), -1),
00123                     brDist [1] = log (y0) - x0);
00124                     
00125   }
00126 
00127   // 4) both are finite
00128 
00129   simpletriplet ft (exp, exp, exp, log);
00130   *brpts = obj -> getBrPoint (&ft, x0, l, u, info); // select based on strategy
00131 
00132   way = TWO_RAND;
00133 
00134   // exact distance
00135   return CoinMin (brDist [0] = projectSeg (x0, y0, l, exp (l), *brpts, exp (*brpts),             -1),
00136                   brDist [1] = projectSeg (x0, y0,             *brpts, exp (*brpts), u, exp (u), -1));
00137 }

Generated on Thu Sep 22 03:05:56 2011 by  doxygen 1.4.7