/home/coin/SVN-release/OS-2.2.0/Couenne/src/standardize/constrStandardize.cpp

Go to the documentation of this file.
00001 /* $Id: constrStandardize.cpp 340 2010-05-16 17:05:54Z pbelotti $
00002  *
00003  * Name:    constrStandardize.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: standardization of constraints
00006  *
00007  * (C) Carnegie-Mellon University, 2007-10.
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CouenneProblemElem.hpp"
00012 #include "CouenneProblem.hpp"
00013 
00014 #include "exprClone.hpp"
00015 #include "exprAux.hpp"
00016 #include "exprIVar.hpp"
00017 #include "depGraph.hpp"
00018 
00019 //#define DEBUG
00020 
00021 // replace a variable
00022 void replace (CouenneProblem *p, int wind, int xind);
00023 
00024 
00026 exprAux *CouenneConstraint::standardize (CouenneProblem *p) {
00027 
00028   // spot an auxiliary variable in constraint's body w - f(x) and move
00029   // the explicit w into the vector of auxiliary variables
00030   //
00031   // do it only if this is an equality constraint and there is at
00032   // least one variable that did not show up so far (need a problem
00033   // structure)
00034 
00035 #ifdef DEBUG
00036   printf ("################################\nStandardizing constraint: "); print ();
00037 
00038   printf (" ["); fflush (stdout); lb_ -> print ();
00039   printf (","); fflush (stdout);  ub_ -> print (); fflush (stdout);
00040   /*  printf ("] {with auxset = ");
00041   for (std::set <exprAux *, compExpr>::iterator i = p -> AuxSet () -> begin ();
00042        i != p -> AuxSet () -> end (); i++) {
00043     printf ("<"); (*i) -> print (); 
00044     printf (","); (*i) -> Image () -> print (); printf ("> ");
00045     }*/
00046   printf ("]\n");
00047 #endif
00048 
00049   if (compareExpr (&lb_, &ub_) == 0) {
00050 
00051     // this is an equality constraint, and could be the definition of
00052     // an auxiliary
00053 
00054     expression *rest;
00055 
00056     // split w from f(x)
00057     int wind = p -> splitAux ((*lb_) (), body_, rest, p -> Commuted ());
00058 
00059     if (wind >= 0) { // this IS the definition of an auxiliary variable w = f(x)
00060 
00061       // first, simplify expression (you never know)
00062 
00063       expression *restSimple = rest -> simplify ();
00064 
00065       if (restSimple) {
00066         delete rest;
00067         rest = restSimple;
00068       }
00069 
00070       // second, if this is a constraint of the form x=k, reset x's
00071       // bounds and do nothing else
00072 
00073       if (rest -> code () == COU_EXPRCONST) {
00074 
00075         p -> Var (wind) -> lb () = 
00076         p -> Var (wind) -> ub () = rest -> Value ();
00077 
00078         delete rest;
00079         return NULL;
00080       }
00081 
00082       // now assign a new auxiliary variable (with the same index,
00083       // "wind", as the old original variable) to the expression
00084       // contained in "rest"
00085 
00086       p -> Commuted () [wind] = true;
00087 
00088 #ifdef DEBUG
00089       printf ("---> %d & ", wind); fflush (stdout);
00090       rest -> print (); printf ("\n");
00091 #endif
00092 
00093       assert (p -> Var (wind) -> Type () == VAR);
00094 
00095       // check if constraint now reduces to w_k = x_h, and if so
00096       // replace all occurrences of x_k with x_h
00097 
00098       int xind = rest -> Index ();
00099 
00100       if (xind >= 0) {
00101 
00102         // create new variable, it has to be integer if original variable was integer
00103         exprAux *w = new exprAux (new exprClone (p -> Var (xind)), wind, 1 + p -> Var (xind) -> rank (),
00104                                   p -> Var (wind) -> isInteger () ?
00105                                   exprAux::Integer : exprAux::Continuous,
00106                                   p -> domain ());
00107         p -> auxiliarize (w);
00108         w -> zeroMult ();
00109         
00110         replace (p, wind, xind);
00111 
00112         p -> auxiliarize (p -> Var (wind), p -> Var (xind));
00113         //p -> Var (wind) -> zeroMult (); // redundant variable is neutralized
00114 
00115 
00116         //      //replace (p, wind, xind);
00117 
00118         //      p -> auxiliarize (p -> Var (wind), p -> Var (xind));
00119         //      p -> Var (wind) -> zeroMult (); // redundant variable is neutralized
00120 
00121       } else {
00122 
00123         // create new variable, it has to be integer if original variable was integer
00124         exprAux *w = new exprAux (rest, wind, 1 + rest -> rank (),
00125                                   p -> Var (wind) -> isInteger () ? 
00126                                   exprAux::Integer : exprAux::Continuous,
00127                                   p -> domain ());
00128 
00129         std::set <exprAux *, compExpr>::iterator i = p -> AuxSet () -> find (w);
00130 
00131         // no such expression found in the set:
00132         if (i == p -> AuxSet () -> end ()) {
00133 
00134           p -> AuxSet      () -> insert (w); // 1) beware of useless copies
00135           p -> getDepGraph () -> insert (w); // 2) introduce it in acyclic structure
00136 
00137 #ifdef DEBUG
00138           printf ("now replacing x [%d] with ", wind); fflush (stdout);
00139           w -> print (); printf (" := ");
00140           w -> Image () -> print (); printf ("\n");
00141 #endif
00142 
00143           // replace ALL occurrences of original variable (with index
00144           // wind) with newly created auxiliary
00145           p -> auxiliarize (w);
00146         } 
00147 
00148         else {
00149 
00150 #ifdef DEBUG
00151           printf ("found aux occurrence of "); fflush (stdout);
00152           w -> print (); printf (" := ");
00153           w -> Image () -> print (); printf (" ... ");
00154           (*i) -> print (); printf (" := ");
00155           (*i) -> Image () -> print (); printf ("\n");
00156 #endif
00157 
00158           // if this is an original variable and is competing with an
00159           // auxiliary variable, or at least this has a lower index,
00160           // we better replace it throughout and eliminate that
00161           // aux. See globallib/st_glmp_fp3 for an example where this
00162           // otherwise would be a bug (x_1 unlinked from x2-x3 and
00163           // leading to unbounded)
00164           
00165           int xind = (*i) -> Index (), iMax, iMin;
00166 
00167           if (xind < wind) {
00168             iMax = wind;
00169             iMin = xind;
00170           } else {
00171             iMax = xind;
00172             iMin = wind;
00173           }
00174 
00175           replace (p, iMax, iMin);
00176 
00177           p -> auxiliarize (p -> Var (iMax), p -> Var (iMin));
00178           p -> Var (iMax) -> zeroMult (); // redundant variable is neutralized
00179           p -> auxiliarize (w);
00180         }
00181       }
00182 
00183       return NULL;
00184     }
00185   }
00186 
00187 #ifdef DEBUG
00188   printf ("\nnormal\n-----------------\n");
00189 #endif
00190 
00191   return body_ -> standardize (p);
00192 }
00193 
00194 
00195 // Replace a variable ////////////////////////////////
00196 void replace (CouenneProblem *p, int wind, int xind) {
00197 
00198   exprVar 
00199     *varLeaves = p -> Variables () [wind],
00200     *varStays  = p -> Variables () [xind];
00201 
00202   // intersect features of the two variables (integrality, bounds)
00203 
00204   varStays -> lb () = varLeaves -> lb () = CoinMax (varStays -> lb (), varLeaves -> lb ());
00205   varStays -> ub () = varLeaves -> ub () = CoinMin (varStays -> ub (), varLeaves -> ub ());
00206 
00207   if (varStays  -> isInteger () ||
00208       varLeaves -> isInteger ()) {
00209 
00210     varStays -> lb () = ceil  (varStays -> lb ());
00211     varStays -> ub () = floor (varStays -> ub ());
00212 
00213     if (varStays -> Type () == AUX)
00214       varStays -> setInteger (true);
00215     else {
00216       //expression *old = varStays; // !!! leak
00217       p -> Variables () [xind] = varStays = new exprIVar (xind, p -> domain ());
00218       p -> auxiliarize (varStays); // replace it everywhere in the problem
00219       //delete old;
00220     }
00221   }
00222 }

Generated on Thu Aug 5 03:02:57 2010 by  doxygen 1.4.7