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

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

Generated on Tue Mar 30 03:04:36 2010 by  doxygen 1.4.7