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

Go to the documentation of this file.
00001 /* $Id: constrStandardize.cpp 154 2009-06-16 18:52:53Z pbelotti $ */
00002 /*
00003  * Name:    constrStandardize.cpp
00004  * Author:  Pietro Belotti
00005  * Purpose: standardization of constraints
00006  *
00007  * (C) Carnegie-Mellon University, 2007-09. 
00008  * This file is licensed under the Common Public License (CPL)
00009  */
00010 
00011 #include "CouenneProblemElem.hpp"
00012 #include "CouenneProblem.hpp"
00013 
00014 #include "exprAux.hpp"
00015 #include "depGraph.hpp"
00016 
00017 //#define DEBUG
00018 
00020 
00021 exprAux *CouenneConstraint::standardize (CouenneProblem *p) {
00022 
00023   // spot an auxiliary variable in constraint's body w - f(x) and move
00024   // the explicit w into the vector of auxiliary variables
00025   //
00026   // do it only if this is an equality constraint and there is at
00027   // least one variable that did not show up so far (need a problem
00028   // structure)
00029 
00030 #ifdef DEBUG
00031   printf ("################################\nStandardizing constraint: "); print ();
00032 
00033   printf (" ["); fflush (stdout); lb_ -> print ();
00034   printf (","); fflush (stdout);  ub_ -> print (); fflush (stdout);
00035   /*  printf ("] {with auxset = ");
00036   for (std::set <exprAux *, compExpr>::iterator i = p -> AuxSet () -> begin ();
00037        i != p -> AuxSet () -> end (); i++) {
00038     printf ("<"); (*i) -> print (); 
00039     printf (","); (*i) -> Image () -> print (); printf ("> ");
00040     }*/
00041   printf ("]\n");
00042 #endif
00043 
00044   if (compareExpr (&lb_, &ub_) == 0) {
00045 
00046     // this is an equality constraint, and could be the definition of
00047     // an auxiliary
00048 
00049     expression *rest;
00050 
00051     // split w from f(x)
00052     int wind = p -> splitAux ((*lb_) (), body_, rest, p -> Commuted ());
00053 
00054     if (wind >= 0) { // this IS the definition of an auxiliary variable w = f(x)
00055 
00056       // first, simplify expression (you never know)
00057 
00058       expression *restSimple = rest -> simplify ();
00059 
00060       if (restSimple) {
00061         delete rest;
00062         rest = restSimple;
00063       }
00064 
00065       // second, if this is a constraint of the form x=k, reset x's
00066       // bounds and do nothing else
00067 
00068       if (rest -> code () == COU_EXPRCONST) {
00069 
00070         p -> Var (wind) -> lb () = 
00071         p -> Var (wind) -> ub () = rest -> Value ();
00072 
00073         delete rest;
00074         return NULL;
00075       }
00076 
00077       // now assign a new auxiliary variable (with the same index,
00078       // "wind", as the old original variable) to the expression
00079       // contained in "rest"
00080 
00081       p -> Commuted () [wind] = true;
00082 
00083 #ifdef DEBUG
00084       printf ("---> %d & ", wind); fflush (stdout);
00085       rest -> print (); printf ("\n");
00086 #endif
00087 
00088       assert (p -> Var (wind) -> Type () == VAR);
00089 
00090       // create new variable, it has to be integer if original variable was integer
00091       exprAux *w = new exprAux (rest, wind, 1 + rest -> rank (),
00092                                 p -> Var (wind) -> isInteger () ? 
00093                                 exprAux::Integer : exprAux::Continuous,
00094                                 p -> domain ());
00095 
00096       std::set <exprAux *, compExpr>::iterator i = p -> AuxSet () -> find (w);
00097 
00098       // no such expression found in the set:
00099       if (i == p -> AuxSet () -> end ()) {
00100 
00101         p -> AuxSet      () -> insert (w); // 1) beware of useless copies
00102         p -> getDepGraph () -> insert (w); // 2) introduce it in acyclic structure
00103 
00104 #ifdef DEBUG
00105         printf ("now replacing x [%d] with ", wind);
00106         w -> print (); printf (" := ");
00107         w -> Image () -> print (); printf ("\n");
00108 #endif
00109 
00110         // replace ALL occurrences of original variable (with index
00111         // wind) with newly created auxiliary
00112         p -> auxiliarize (w);
00113       } 
00114 
00115 #ifdef DEBUG
00116       else {
00117         printf ("found aux occurrence of "); 
00118         w -> print (); printf (" := ");
00119         w -> Image () -> print (); printf (" ... ");
00120         (*i) -> print (); printf (" := ");
00121         (*i) -> Image () -> print (); printf ("\n");
00122       }
00123 #endif
00124 
00125       return NULL;
00126     }
00127   }
00128 
00129 #ifdef DEBUG
00130   printf ("\nnormal\n-----------------\n");
00131 #endif
00132 
00133   return body_ -> standardize (p);
00134 }

Generated on Thu Oct 8 03:02:57 2009 by  doxygen 1.4.7