1 /* $Id$
2 *
3 * Name: conv-exprLog.cpp
4 * Author: Pietro Belotti
5 * Purpose: convexification and bounding methods for the logarithm operator
6 *
7 * (C) Carnegie-Mellon University, 2006-09.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "CouenneCutGenerator.hpp"
12
13 #include "CouenneTypes.hpp"
14 #include "CouenneExprLog.hpp"
15 #include "CouenneExprPow.hpp"
16 #include "CouenneExprAux.hpp"
17
18 #include "CouenneProblem.hpp"
19
20 using namespace Couenne;
21
22 #define LOG_STEP 10
23 #define LOG_MININF 1e-50
24
25 // generate convexification cut for constraint w = this
26
generateCuts(expression * aux,OsiCuts & cs,const CouenneCutGenerator * cg,t_chg_bounds * chg,int wind,CouNumber lbw,CouNumber ubw)27 void exprLog::generateCuts (expression *aux, //const OsiSolverInterface &si,
28 OsiCuts &cs, const CouenneCutGenerator *cg,
29 t_chg_bounds *chg, int wind,
30 CouNumber lbw, CouNumber ubw) {
31 int
32 w_ind = aux -> Index (), // dependent variable's index
33 x_ind = argument_ -> Index (); // independent variable's index
34
35 bool changed =
36 !chg || (cg -> isFirst ()) ||
37 (chg [x_ind].lower() != t_chg_bounds::UNCHANGED) ||
38 (chg [x_ind].upper() != t_chg_bounds::UNCHANGED);
39
40 CouNumber l, u;
41 argument_ -> getBounds (l, u);
42
43 enum auxSign sign = cg -> Problem () -> Var (w_ind) -> sign ();
44
45 // if bounds are very close, convexify with a single line
46 if ((fabs (u - l) < COUENNE_EPS) && (l > COUENNE_EPS)) {
47
48 CouNumber x0 = 0.5 * (u+l);
49 if (changed) cg -> createCut (cs, log (x0) - 1, sign, w_ind, 1., x_ind, - 1/x0);
50 return;
51 }
52
53 // fix lower bound
54 if (l < LOG_MININF) l = LOG_MININF;
55 else // lower segment (if l is far from zero and u finite)
56 if ((u < COUENNE_INFINITY) && changed && sign != expression::AUX_LEQ) {
57
58 CouNumber dx = u-l;
59 CouNumber logu = log (u);
60 CouNumber dw = logu - log (l);
61
62 cg -> createCut (cs, dx*logu - u*dw, +1, w_ind, dx, x_ind, -dw);
63 }
64
65 // no need to continue if auxiliary is defined as w >= log (x)
66 if (sign == expression::AUX_GEQ)
67 return;
68
69 // pick tangent point closest to current point (x0,y0)
70 CouNumber x = (cg -> isFirst ()) ?
71 1 : powNewton ((*argument_) (), (*aux) (), log, inv, oppInvSqr);
72
73 // check if outside interval
74 if (x < l) x = l;
75 else if (x > u) x = u;
76
77 // fix bound interval (unless you like infinite coefficients)
78 if (u > 1e5 * log (COUENNE_INFINITY) - 1)
79 u = x + (LOG_STEP << cg -> nSamples ());
80
81 // add upper envelope
82 cg -> addEnvelope (cs, -1, log, inv, w_ind, x_ind, x, l, u, chg, true);
83 }
84