00001 /* $Id: conv-exprPow-envelope.cpp 698 2011-06-20 13:36:43Z pbelotti $ 00002 * 00003 * Name: conv-exprPow-envelope.cpp 00004 * Author: Pietro Belotti 00005 * Purpose: methods of the expression class 00006 * 00007 * (C) Carnegie-Mellon University, 2006-11. 00008 * This file is licensed under the Eclipse Public License (EPL) 00009 */ 00010 00011 #include <math.h> 00012 00013 #include "CouenneCutGenerator.hpp" 00014 00015 #include "CouenneTypes.hpp" 00016 #include "CouenneRootQ.hpp" 00017 #include "CouenneExprPow.hpp" 00018 #include "CouennePrecisions.hpp" 00019 #include "CouenneProblem.hpp" 00020 #include "CouenneFunTriplets.hpp" 00021 00022 using namespace Couenne; 00023 00024 // adds convex (upper/lower) envelope to a power function 00025 00026 void Couenne::addPowEnvelope (const CouenneCutGenerator *cg, OsiCuts &cs, 00027 int wi, int xi, 00028 CouNumber x, CouNumber y, 00029 CouNumber k, 00030 CouNumber l, CouNumber u, 00031 int sign) { 00032 00033 // set x to get a deeper cut (so that we get a tangent which is 00034 // orthogonal with line through current- and tangent point) 00035 00036 powertriplet pt (k); 00037 00038 if (!(cg -> isFirst ())) 00039 x = powNewton (x, y, &pt); 00040 00041 if (x<l) x=l; 00042 else if (x>u) x=u; 00043 00044 // limit the bounds for the envelope 00045 00046 CouNumber powThres = (k<=1) ? COU_MAX_COEFF: pow (COU_MAX_COEFF, 1./k); 00047 //step = (1 + log (1. + (double) (cg -> nSamples ()))) * powThres / COU_MAX_COEFF; 00048 00049 // If the bounds are too large, the linearization cuts might have 00050 // large coefficients. To prevent that, Couenne used to set very 00051 // small fictitious bounds, resulting in 00052 // 00053 // 1) still valid cuts, but 00054 // 00055 // 2) a very abrupt change in their coefficients; 00056 // 00057 // 3) cuts that may result in an LP solution far away from x (this 00058 // behavior recalls that of bundle methods for NDO); 00059 // 00060 // 4) a non-exact linearization at the bounds (in theory, necessary 00061 // for convergence...). 00062 // 00063 // New values for l and u, if necessary, are therefore set to the 00064 // maximum bounds if l and/or u are beyond them. 00065 // 00066 // Thanks to Sergey for pointing this out. 00067 00068 if (l < - powThres + 1) { 00069 l = - powThres + 1; // keeps bounds reasonably large 00070 //l = x - step; 00071 if (u > powThres - 1) { 00072 u = powThres - 1; 00073 //u = x + step; 00074 } 00075 } else 00076 if (u > powThres - 1) { 00077 u = powThres - 1; 00078 //u = x + step; 00079 } 00080 00081 // convex envelope 00082 cg -> addEnvelope (cs, sign, &pt, 00083 wi, xi, x, l, u); 00084 }