1 /* $Id$
2 *
3 * Name: conv-exprAbs.cpp
4 * Author: Pietro Belotti
5 * Purpose: convexification methods for |f(x)|
6 *
7 * (C) Carnegie-Mellon University, 2006-10.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "CouenneCutGenerator.hpp"
12
13 #include "OsiSolverInterface.hpp"
14 #include "CouenneTypes.hpp"
15 #include "CouenneProblem.hpp"
16 #include "CouenneExprAbs.hpp"
17 #include "CouenneExprAux.hpp"
18
19 using namespace Couenne;
20
21 // generate convexification cut for constraint w = |x|
22
generateCuts(expression * w,OsiCuts & cs,const CouenneCutGenerator * cg,t_chg_bounds * chg,int wind,CouNumber lbw,CouNumber ubw)23 void exprAbs::generateCuts (expression *w,
24 OsiCuts &cs, const CouenneCutGenerator *cg,
25 t_chg_bounds *chg, int wind,
26 CouNumber lbw, CouNumber ubw) {
27
28 int w_ind = w -> Index (),
29 x_ind = argument_ -> Index ();
30
31 CouNumber l, u;
32 argument_ -> getBounds (l, u);
33
34 enum auxSign sign = cg -> Problem () -> Var (w_ind) -> sign ();
35
36 bool
37 cbase = !chg || cg -> isFirst (),
38 cLeft = cbase || (chg [x_ind].lower() != t_chg_bounds::UNCHANGED),
39 cRight = cbase || (chg [x_ind].upper() != t_chg_bounds::UNCHANGED);
40
41 // if l, u have the same sign, then w = x (l >= 0) or w = -x (u <= 0)
42
43 if (l >= -0) {if (cLeft) cg -> createCut (cs, 0., sign, w_ind, 1., x_ind, -1.);}
44 else if (u <= 0) {if (cRight) cg -> createCut (cs, 0., sign, w_ind, 1., x_ind, +1.);}
45 else {
46
47 // add two global cuts: w >= x and w >= -x
48 if (cg -> isFirst () && sign != expression::AUX_LEQ) {
49 cg -> createCut (cs, 0., +1, w_ind, 1., x_ind, -1.);
50 cg -> createCut (cs, 0., +1, w_ind, 1., x_ind, 1.);
51 }
52
53 // otherwise check if at most one of the bounds is infinite: even
54 // so, we can still add a plane, whose slope is 1 (x unbounded
55 // from above) or -1 (from below)
56
57 if (sign != expression::AUX_GEQ) {
58
59 if (l > - COUENNE_INFINITY) {
60 if (u < COUENNE_INFINITY) { // the upper approximation has slope other than -1, 1
61
62 CouNumber slope = (u+l) / (u-l); // should be stable, l < 0 < u
63
64 // add an upper segment, which depends on the lower/upper bounds
65 if (cLeft || cRight)
66 cg -> createCut (cs, -l*(slope+1.), -1, w_ind, 1., x_ind, -slope);
67 }
68 else // slope = 1
69 if (cLeft) cg -> createCut (cs, -2*l, -1, w_ind, 1., x_ind, -1.);
70 }
71 else if (u < COUENNE_INFINITY) // slope = -1
72 if (cRight) cg -> createCut (cs, 2*u, -1, w_ind, 1., x_ind, 1.);
73 }
74 }
75 }
76