/home/coin/SVN-release/OS-2.4.1/Couenne/src/bound_tightening/operators/impliedBounds-sum.cpp

Go to the documentation of this file.
00001 /* $Id: impliedBounds-sum.cpp 490 2011-01-14 16:07:12Z pbelotti $
00002  *
00003  * Name:    impliedBounds-sum.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: inferring bounds on monomials in a sum
00006  *
00007  * (C) Carnegie-Mellon University, 2006-10.
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include <vector>
00012 
00013 #include "CoinHelperFunctions.hpp"
00014 #include "CouenneExprSum.hpp"
00015 
00016 using namespace Couenne;
00017 
00018 #define ALMOST_INF (1e-5 * COUENNE_INFINITY)
00019 
00020 int exprSum::impliedBoundSum (CouNumber wl, 
00021                               CouNumber wu, 
00022                               std::vector <CouNumber> &xl,
00023                               std::vector <CouNumber> &xu,
00024                               std::vector <std::pair <int, CouNumber> > &nl,
00025                               std::vector <std::pair <int, CouNumber> > &nu) {
00026   CouNumber 
00027     sumLB = 0,
00028     sumUB = 0;
00029 
00030   int 
00031     nImpr = 0,
00032     n     = xl.size (), 
00033     infLo = -1, 
00034     infUp = -1;
00035 
00036   // check lower bounds
00037   for (int i=0; i<n; i++) {
00038     CouNumber l = xl [i];
00039     if (l < -ALMOST_INF) 
00040       if (infLo >= 0) {infLo = -2; break;}
00041       else infLo = i;
00042     else sumLB += l;
00043   }
00044 
00045   // check upper bounds
00046   for (int i=0; i<n; i++) {
00047     CouNumber u = xu [i];
00048     if (u > ALMOST_INF) 
00049       if (infUp >= 0) {infUp = -2; break;}
00050       else infUp = i;
00051     else sumUB += u;
00052   }
00053 
00054   // if more than two unbounded quantities on both sides, bail out
00055   if ((infUp == -2) && 
00056       (infLo == -2)) 
00057     return 0;
00058 
00059   // new lower bounds ////////////////////////////////////////////////////
00060 
00061   if (infLo == -1) { // none of the "first" components is unbounded from below
00062 
00063     for (int i=0; i<n; i++) {
00064 
00065       CouNumber nb = wu - sumLB + xl [i];
00066       if (nb < xu [i]) {
00067         nu.push_back (std::pair <int, CouNumber> (i, nb));
00068         nImpr ++;
00069       }
00070     }   
00071 
00072   } else if (infLo >= 0) { // exactly one of them is, can improve bound on that one only
00073   
00074     CouNumber nb = wu - sumLB;
00075     if (nb < xu [infLo]) {
00076       nu.push_back (std::pair <int, CouNumber> (infLo, nb));
00077       nImpr ++;
00078     }
00079   }
00080 
00081   // new upper bounds ////////////////////////////////////////////////////
00082  
00083   if (infUp == -1) { // none of the "first" components is unbounded from below
00084 
00085     for (int i=0; i<n; i++) {
00086 
00087       CouNumber nb = wl - sumUB + xu [i];
00088       if (nb > xl [i]) {
00089         nl.push_back (std::pair <int, CouNumber> (i, nb));
00090         nImpr ++;
00091       }
00092     }   
00093 
00094   } else if (infUp >= 0) { // exactly one of them is, can improve bound on that one only
00095   
00096     CouNumber nb = wl - sumUB;
00097     if (nb < xl [infLo]) {
00098       nl.push_back (std::pair <int, CouNumber> (infUp, nb));
00099       nImpr ++;
00100     }
00101   }
00102 
00103   return nImpr;
00104 }

Generated on Thu Nov 10 03:05:42 2011 by  doxygen 1.4.7