/home/coin/SVN-release/OS-2.4.2/Couenne/src/convex/operators/conv-exprAbs.cpp

Go to the documentation of this file.
00001 /* $Id: conv-exprAbs.cpp 490 2011-01-14 16:07:12Z pbelotti $
00002  *
00003  * Name:    conv-exprAbs.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: convexification methods for |f(x)|
00006  *
00007  * (C) Carnegie-Mellon University, 2006-10.
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include "CouenneCutGenerator.hpp"
00012 
00013 #include "OsiSolverInterface.hpp"
00014 #include "CouenneTypes.hpp"
00015 #include "CouenneProblem.hpp"
00016 #include "CouenneExprAbs.hpp"
00017 #include "CouenneExprAux.hpp"
00018 
00019 using namespace Couenne;
00020 
00021 // generate convexification cut for constraint w = |x|
00022 
00023 void exprAbs::generateCuts (expression *w, 
00024                             OsiCuts &cs, const CouenneCutGenerator *cg, 
00025                             t_chg_bounds *chg, int wind, 
00026                             CouNumber lbw, CouNumber ubw) {
00027 
00028   int w_ind = w         -> Index (),
00029       x_ind = argument_ -> Index ();
00030 
00031   CouNumber l, u;
00032   argument_ -> getBounds (l, u);
00033 
00034   enum auxSign sign = cg -> Problem () -> Var (w_ind) -> sign ();
00035 
00036   bool
00037     cbase  = !chg || cg -> isFirst (),
00038     cLeft  = cbase || (chg [x_ind].lower() != t_chg_bounds::UNCHANGED),
00039     cRight = cbase || (chg [x_ind].upper() != t_chg_bounds::UNCHANGED);
00040 
00041   // if l, u have the same sign, then w = x (l >= 0) or w = -x (u <= 0)
00042 
00043   if      (l >= -0) {if (cLeft)  cg -> createCut (cs, 0., sign, w_ind, 1., x_ind, -1.);}
00044   else if (u <=  0) {if (cRight) cg -> createCut (cs, 0., sign, w_ind, 1., x_ind, +1.);}
00045   else {
00046 
00047     // add two global cuts: w >= x and w >= -x
00048     if (cg -> isFirst () && sign != expression::AUX_LEQ) {
00049       cg -> createCut (cs, 0., +1, w_ind, 1., x_ind, -1.);
00050       cg -> createCut (cs, 0., +1, w_ind, 1., x_ind,  1.);
00051     }
00052 
00053     // otherwise check if at most one of the bounds is infinite: even
00054     // so, we can still add a plane, whose slope is 1 (x unbounded
00055     // from above) or -1 (from below)
00056 
00057     if (sign != expression::AUX_GEQ) {
00058 
00059       if (l > - COUENNE_INFINITY) {
00060         if (u < COUENNE_INFINITY) { // the upper approximation has slope other than -1, 1
00061 
00062           CouNumber slope = (u+l) / (u-l); // should be stable, l < 0 < u
00063 
00064           // add an upper segment, which depends on the lower/upper bounds
00065           if (cLeft || cRight) 
00066             cg -> createCut (cs, -l*(slope+1.), -1, w_ind, 1., x_ind, -slope);
00067         }
00068         else // slope = 1
00069           if (cLeft) cg -> createCut (cs, -2*l, -1, w_ind, 1., x_ind, -1.);
00070       }
00071       else if (u < COUENNE_INFINITY) // slope = -1
00072         if (cRight) cg -> createCut (cs, 2*u, -1, w_ind, 1., x_ind, 1.);
00073     }
00074   }
00075 }

Generated on Wed Nov 30 03:03:58 2011 by  doxygen 1.4.7