/home/coin/SVN-release/OS-2.1.1/Couenne/src/convex/operators/conv-exprMul.cpp

Go to the documentation of this file.
00001 /* $Id: conv-exprMul.cpp 230 2009-07-18 11:42:59Z pbelotti $
00002  *
00003  * Name:    conv-exprMul.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: utility methods to convexify multiplications
00006  *
00007  * (C) Carnegie-Mellon University, 2006-08.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CouenneTypes.hpp"
00012 #include "exprMul.hpp"
00013 #include "exprBMul.hpp"
00014 #include "exprConst.hpp"
00015 #include "exprPow.hpp"
00016 #include "exprClone.hpp"
00017 #include "CouenneProblem.hpp"
00018 
00019 
00021 
00022 inline bool areSameVariables (expression *v1, expression *v2) {
00023 
00024   register int t1 = v1 -> Type (), t2;
00025   return (((t1 == VAR) || (t1 == AUX)) &&
00026           (((t2 = v2 -> Type ()) == VAR) || (t2 == AUX)) && 
00027           (v1 -> Index () == v2 -> Index ()));
00028 }
00029 
00030 
00032 
00033 exprAux *exprMul::standardize (CouenneProblem *p, bool addAux) {
00034 
00035   exprOp::standardize (p);
00036 
00037   if (nargs_ == 1)  // TODO: what happens really?
00038     return NULL;
00039   /* {
00040      exprAux *aux = arglist_ [0];
00041      arglist_ [0] = NULL;
00042      return aux;
00043      } */
00044 
00045   // check if it is a product of binary variables
00046   bool isBinProd = true;
00047   for (int i=nargs_; i--;) {
00048 
00049     expression *arg = arglist_ [i];
00050     if (arg -> isInteger ()) {
00051 
00052       CouNumber lb, ub;
00053       arg -> getBounds (lb, ub);
00054       if ((fabs (lb)      > 0.) ||
00055           (fabs (ub - 1.) > 0.)) { // if not all conditions hold, 
00056         isBinProd = false;
00057         break;
00058       }
00059     } else {
00060       isBinProd = false;
00061       break;
00062     }
00063   }
00064 
00065   if (isBinProd) {
00066 
00067     //printf ("found a BinProd!\n");
00068 
00069   }
00070 
00071   //expression *aux = arglist_ [0]; // why not this one?
00072   expression *aux = new exprClone (arglist_ [0]);
00073 
00074   for (int i = 1; i < nargs_ - 1; i++)
00075     aux = (areSameVariables (aux, arglist_ [i])) ? 
00076       (p -> addAuxiliary (new exprPow (new exprClone (aux), new exprConst (2.)))) : 
00077       (p -> addAuxiliary (new exprMul (new exprClone (aux), new exprClone (arglist_ [i]))));
00078 
00079   if (areSameVariables (aux, arglist_ [nargs_ - 1])) 
00080     aux    = new exprPow (new exprClone (aux), new exprConst (2.));
00081   else aux = new exprMul (new exprClone (aux), new exprClone (arglist_ [nargs_ - 1]));
00082 
00083   return (addAux ? (p -> addAuxiliary (aux)) : new exprAux (this, p -> domain ()));
00084 }
00085 
00086 
00088 
00089 void exprMul::getBounds (expression *&lb, expression *&ub) {
00090 
00091   int i;
00092 
00093   if ((arglist_ [i=0] -> Type () == CONST) ||
00094       (arglist_ [i=1] -> Type () == CONST)) {
00095 
00096     CouNumber c = arglist_ [i] -> Value ();
00097 
00098     if (!i && (arglist_ [1] -> Type () == CONST)) { 
00099 
00100       // !i means i==0, or the first is constant. If you are here,
00101       // both are constant, which should not happen...
00102 
00103       CouNumber prod = c * arglist_ [1] -> Value ();
00104 
00105       lb = new exprConst (prod);
00106       ub = new exprConst (prod);
00107 
00108       return;
00109     }
00110     else {
00111 
00112       // expression is of the type c*x
00113 
00114       expression *lbi, *ubi;
00115       arglist_ [1-i] -> getBounds (lbi, ubi);
00116 
00117       if (c >= 0) {
00118         lb = new exprMul (new exprConst (c), lbi);
00119         ub = new exprMul (new exprConst (c), ubi);
00120       } else {
00121         lb = new exprMul (new exprConst (c), ubi);
00122         ub = new exprMul (new exprConst (c), lbi);
00123       }
00124     }
00125   }
00126   else {
00127 
00128     // expression is of the type x*y
00129 
00130     expression **almin = new expression * [4];
00131     expression **almax = new expression * [4];
00132 
00133     arglist_ [0] -> getBounds (almin [0], almin [1]);
00134     arglist_ [1] -> getBounds (almin [2], almin [3]);
00135 
00136     almax [0] = new exprClone (almin [0]);
00137     almax [1] = new exprClone (almin [1]);
00138     almax [2] = new exprClone (almin [2]);
00139     almax [3] = new exprClone (almin [3]);
00140 
00141     lb = new exprLBMul (almin, 4);
00142     ub = new exprUBMul (almax, 4);
00143   }
00144 }
00145 
00146 
00148 
00149 void exprMul::getBounds (CouNumber &lb, CouNumber &ub) {
00150 
00151   CouNumber lb1, ub1, lb2, ub2;
00152 
00153   arglist_ [0] -> getBounds (lb1, ub1);
00154   arglist_ [1] -> getBounds (lb2, ub2);
00155 
00156   if (ub1 < 0) { // use lb1, dominant
00157     if      (ub2 < 0) {lb = safeProd(ub1,ub2); ub = safeProd(lb1,lb2);}
00158     else if (lb2 > 0) {lb = safeProd(lb1,ub2); ub = safeProd(ub1,lb2);}
00159     else              {lb = safeProd(lb1,ub2); ub = safeProd(lb1,lb2);}
00160   } else if (lb1 > 0) { // use ub1, dominant
00161     if      (ub2 < 0) {lb = safeProd(ub1,lb2); ub = safeProd(lb1,ub2);}
00162     else if (lb2 > 0) {lb = safeProd(lb1,lb2); ub = safeProd(ub1,ub2);}
00163     else              {lb = safeProd(ub1,lb2); ub = safeProd(ub1,ub2);}
00164   } else { // there is a zero to consider
00165     if      (ub2 < 0) {lb = safeProd(ub1,lb2); ub = safeProd(lb1,lb2);}
00166     else if (lb2 > 0) {lb = safeProd(lb1,ub2); ub = safeProd(ub1,ub2);}
00167     else              {lb = CoinMin (safeProd(lb1,ub2), safeProd(lb2,ub1));
00168                        ub = CoinMax (safeProd(lb1,lb2), safeProd(ub1,ub2));}
00169   }
00170 }

Generated on Mon May 3 03:05:19 2010 by  doxygen 1.4.7