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

Go to the documentation of this file.
00001 /*
00002  * $Id: standardize.cpp 154 2009-06-16 18:52:53Z pbelotti $
00003  *
00004  * Name:    standardize.cpp
00005  * Author:  Pietro Belotti
00006  * Purpose: standardize all expressions in a problem
00007  *
00008  * (C) Carnegie-Mellon University, 2006-09.
00009  * This file is licensed under the Common Public License (CPL)
00010  */
00011 
00012 #include <vector>
00013 
00014 #include "CoinHelperFunctions.hpp"
00015 
00016 #include "CouenneTypes.hpp"
00017 #include "expression.hpp"
00018 #include "exprIVar.hpp"
00019 #include "exprClone.hpp"
00020 #include "CouenneProblem.hpp"
00021 #include "CouenneProblemElem.hpp"
00022 #include "depGraph.hpp"
00023 
00024 //#define DEBUG
00025 
00027 
00028 bool CouenneProblem::standardize () {
00029 
00030 #ifdef DEBUG
00031   printf ("START: current point: %d vars -------------------\n", 
00032           domain_.current () -> Dimension ());
00033   for (int i=0; i<domain_.current () -> Dimension (); i++)
00034     printf ("%3d %20g [%20g %20g]\n", i, domain_.x (i), domain_.lb (i), domain_.ub (i));
00035 #endif
00036 
00037   bool retval = true;
00038 
00039   // create dependence graph to assign an order to the evaluation (and
00040   // bound propagation, and -- in reverse direction -- implied bounds)
00041   graph_ = new DepGraph;
00042 
00043   for (std::vector <exprVar *>::iterator i = variables_ . begin ();
00044        i != variables_ . end (); ++i)
00045     graph_ -> insert (*i);
00046 
00047   // allocate space in auxiliaries_ from commonexprs_
00048 
00049   int initVar = variables_ . size () - commonexprs_ . size ();
00050 
00051   // Defined variables ///////////////////////////////////////////
00052 
00053   // standardize initial aux variables (aka defined variables, aka
00054   // common expression)
00055 
00056 #ifdef DEBUG
00057   if (commonexprs_.size ()) printf ("%d common exprs, initVar = %d = %d - %d\n", 
00058                                     commonexprs_.size (), 
00059                                     initVar, 
00060                                     variables_ . size (), 
00061                                     commonexprs_ . size ());
00062 #endif
00063 
00064   for (std::vector <expression *>::iterator i = commonexprs_ . begin ();
00065        i != commonexprs_ . end (); ++i) {
00066 
00067 #ifdef DEBUG
00068     printf ("-- stdz common expr [%d] :=", initVar); fflush (stdout);
00069     (*i) -> print (); printf ("\n"); fflush (stdout);
00070 #endif
00071 
00072     exprAux *naux = (*i) -> standardize (this, false);
00073 
00074     expression *img = naux -> Image ();
00075 
00076     // trick to obtain same index as common expression: create exprAux
00077     // with index initVar and replace occurrences with address of
00078     // newly created exprAux through auxiliarize()
00079 
00080     exprAux *newvar = new exprAux (img, initVar, 1 + img -> rank (), exprAux::Unset, &domain_);
00081     //img -> isInteger () ? exprAux::Integer : exprAux::Continuous);
00082 
00083     auxiliarize (newvar); // takes care of putting newvar at right position in variables_
00084 
00085     graph_ -> insert (newvar);
00086     graph_ -> erase (naux);
00087 
00088     //variables_ . erase (variables_ . end () - 1);
00089 
00090 #ifdef DEBUG
00091     if (naux) {
00092       printf ("done: "); fflush (stdout);
00093       naux -> print ();
00094       printf (" := "); fflush (stdout);
00095       naux -> Image () -> print (); printf ("\n..."); fflush (stdout);
00096     } else if (*i) {
00097       (*i) -> print ();
00098       //printf (" := "); fflush (stdout);
00099       //aux -> Image () -> print (); 
00100       printf ("\n");
00101     } else printf ("[n]aux NULL!\n");
00102 #endif
00103 
00104     initVar++;
00105   }
00106 
00107   // OBJECTIVES //////////////////////////////////////////////////////////////////////////////
00108 
00109   for (std::vector <CouenneObjective *>::iterator i = objectives_.begin ();
00110        i != objectives_.end (); ++i) {
00111 
00112 #ifdef DEBUG
00113     printf ("Objective [code: %d]", (*i) -> Body () -> code ()); (*i) -> print ();
00114 #endif
00115 
00116     exprAux *aux = (*i) -> standardize (this);
00117 
00118 #ifdef DEBUG
00119     printf ("      --> "); (*i) -> print (); 
00120     if (aux) {printf (" -- aux is "); aux -> print (); printf ("\n");}
00121 #endif
00122 
00123     if (aux) {
00124       //delete ((*i) -> Body ());
00125       (*i) -> Body (new exprClone (aux));
00126     }
00127 
00128 #ifdef DEBUG
00129     printf ("      --> "); (*i) -> print (); printf ("...................\n");
00130 #endif
00131   }
00132 
00133   // commuted_ is an array with a flag for each original variable,
00134   // which is true at position i if initially original variable x_i
00135   // went auxiliary
00136 
00137   commuted_ = new bool [nVars ()];
00138   for (int i = nVars (); i--;)
00139     *commuted_++ = false;
00140   commuted_ -= nVars ();
00141 
00142   //  std::vector <CouenneConstraint *> con2;
00143   std::vector <std::vector <CouenneConstraint *>::iterator> iters2erase;
00144 
00145 
00146   // CONSTRAINTS /////////////////////////////////////////////////////////////////////////////
00147 
00148   for (std::vector <CouenneConstraint *>::iterator i = constraints_.begin (); 
00149        i != constraints_.end (); ++i) {
00150 
00151 #ifdef DEBUG
00152     printf ("############# Constraint "); 
00153     (*i) -> print ();
00154 #endif
00155 
00156     exprAux *aux = (*i) -> standardize (this);
00157 
00158 #ifdef DEBUG
00159     printf (" ==> [%d] ", aux ? (aux -> Index ()) : -1); 
00160     (*i) -> print ();
00161 #endif
00162 
00163     if (aux) { // save if standardized
00164       //delete ((*i) -> Body ());
00165       (*i) -> Body (new exprClone (aux));
00166       //      con2.push_back (*i);
00167     }
00168     else {
00169       CouNumber lb, ub;
00170       (*i) -> Body () -> getBounds (lb, ub);
00171       if ((((*((*i) -> Lb ())) ()) > ub) ||
00172           (((*((*i) -> Ub ())) ()) < lb)) {
00173 #ifdef DEBUG
00174         printf ("found infeasible constraint [%g,%g]\n", lb, ub);
00175         (*i) -> print ();
00176 #endif
00177         retval = false;
00178       }
00179       iters2erase.push_back (i);
00180     }
00181 
00182     //(*i) -> Body () -> realign (this);
00183 
00184 #ifdef DEBUG
00185     printf (" --> ");
00186     (*i) -> print ();
00187     printf ("..............................................................\n");
00188     //print ();
00189 #endif
00190 
00191     /*printf ("=== "); fflush (stdout); 
00192     aux -> print (); printf (" := "); fflush (stdout);
00193     aux -> Image () -> print (); printf ("\n");*/
00194   }
00195 
00196   for (unsigned int i = iters2erase.size (); i--;)
00197     constraints_. erase (iters2erase [i]);
00198 
00199 #ifdef DEBUG 
00200   // Use with caution. Bounds on auxs are not defined yet, so valgrind complains
00201   printf ("done with standardization: (careful, bounds below can be nonsense)\n");
00202   print (); 
00203 #endif
00204 
00205   // Create evaluation order ////////////////////////////////////////////////////
00206 
00207   delete auxSet_;
00208 
00209   // reallocate space for enlarged set of variables
00210   domain_.current () -> resize (nVars ());
00211 
00212   //graph_ -> print ();
00213   graph_ -> createOrder ();
00214   //graph_ -> print ();
00215 
00216   assert (graph_ -> checkCycles () == false);
00217 
00218   // Fill numbering structure /////////////////////////////////////////////////
00219 
00220   int n = nVars ();
00221   numbering_ = new int [n];
00222   std::set <DepNode *, compNode> vertices = graph_ -> Vertices ();
00223 
00224   for (std::set <DepNode *, compNode>::iterator i = vertices.begin ();
00225        i != vertices.end (); ++i)
00226 
00227     numbering_ [(*i) -> Order ()] = (*i) -> Index (); 
00228 
00230 
00231   for (int i = 0; i < nVars (); i++) {
00232 
00233     int ord = numbering_ [i];
00234 
00235     if (variables_ [ord] -> Type () == AUX) {
00236 
00237       // initial auxiliary bounds are infinite (they are later changed
00238       // through branching)
00239 
00240       if (variables_ [ord] -> Index () >= nOrigVars_) { // and one that was not an original, originally...
00241 
00242         domain_.lb (ord) = -COIN_DBL_MAX;
00243         domain_.ub (ord) =  COIN_DBL_MAX;
00244       }
00245 
00246       //printf ("from "); variables_ [ord] -> Lb    () -> print (); 
00247 
00248       // tighten them with propagated bounds
00249       variables_ [ord] -> crossBounds ();
00250 
00251       //printf ("to "); variables_ [ord] -> Lb    () -> print (); printf (", now eval\n");
00252 
00253 #ifdef DEBUG
00254       printf (":::: %3d %10g [%10g, %10g]", 
00255               ord, domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00256 #endif
00257 
00258       // and evaluate them
00259       domain_.x  (ord) = (*(variables_ [ord] -> Image ())) ();
00260       domain_.lb (ord) = (*(variables_ [ord] -> Lb    ())) ();
00261       domain_.ub (ord) = (*(variables_ [ord] -> Ub    ())) ();
00262 
00263 #ifdef DEBUG
00264       printf (" --> %10g [%10g, %10g] [", 
00265               domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00266       variables_ [ord] -> Lb () -> print (); printf (",");
00267       variables_ [ord] -> Ub () -> print (); printf ("]\n");
00268 #endif
00269 
00270       bool integer = variables_ [ord] -> isInteger ();
00271 
00272       if (integer) {
00273         domain_.lb (ord) = ceil  (domain_.lb (ord) - COUENNE_EPS);
00274         domain_.ub (ord) = floor (domain_.ub (ord) + COUENNE_EPS);
00275       }
00276     }
00277   }
00278 
00279   // TODO: resolve duplicate index in exprQuad before restoring this
00280 
00281   std::string delete_redund;
00282   if (bonBase_)
00283     bonBase_ -> options () -> GetStringValue ("delete_redundant", delete_redund, "couenne."); 
00284   else
00285     delete_redund = "yes";
00286 
00287   if (delete_redund == "yes")
00288 
00289     // Look for auxiliaries of the form w:=x and replace each occurrence of w with x
00290     for (std::vector <exprVar *>::iterator i = variables_.begin (); 
00291        i != variables_.end (); ++i)
00292 
00293     if ((*i) -> Type () == AUX) {
00294 
00295       int type = (*i) -> Image () -> Type ();
00296 
00297       if ((type == VAR) || (type == AUX)) {
00298 
00299         // found w_k = x_h. 
00300         // 
00301         // Check if either is integer, the survivor will be integer too
00302         // Replace all occurrences of w_k with x_h
00303 
00304         /*printf ("redundancy: "); 
00305         (*i)             -> print (); printf (" := "); 
00306         (*i) -> Image () -> print (); printf ("\n");*/
00307 
00308         // use the info on the variable to be discarded: tighter
00309         // bounds and integrality that the replacement might not have.
00310 
00311         int 
00312           indStays  = (*i) -> Image () -> Index (), // index h
00313           indLeaves = (*i)             -> Index (); // index k
00314 
00315         if (indStays == indLeaves)  // very strange case, w_h = x_h
00316           continue;
00317 
00318         // do not swap! x_h could be in turn an auxiliary...
00319         //
00320         //if (indStays > indLeaves) 
00321         //{int swap = indStays; indStays = indLeaves; indLeaves = swap;} // swap
00322 
00323         exprVar 
00324           *varStays  = variables_ [indStays],
00325           *varLeaves = variables_ [indLeaves];
00326 
00327         // intersect features of the two variables (integrality, bounds)
00328 
00329         varStays -> lb () = varLeaves -> lb () = CoinMax (varStays -> lb (), varLeaves -> lb ());
00330         varStays -> ub () = varLeaves -> ub () = CoinMin (varStays -> ub (), varLeaves -> ub ());
00331 
00332         if (varStays  -> isInteger () ||
00333             varLeaves -> isInteger ()) {
00334 
00335           varStays -> lb () = ceil  (varStays -> lb ());
00336           varStays -> ub () = floor (varStays -> ub ());
00337 
00338           if (varStays -> Type () == AUX)
00339             varStays -> setInteger (true);
00340           else {
00341             //expression *old = varStays; // !!! leak
00342             variables_ [indStays] = varStays = new exprIVar (indStays, &domain_);
00343             auxiliarize (varStays); // replace it everywhere in the problem
00344             //delete old;
00345           }
00346         }
00347 
00348         auxiliarize (varLeaves, varStays); // now replace occurrences of w_k with x_h
00349 
00350         //if (varLeaves -> Index () >= nOrigVars_) // why check? It's not there anymore.
00351         varLeaves -> zeroMult (); // disable this variable
00352       }
00353     }
00354 
00360   for (int ii=0; ii < nVars (); ii++) {
00361 
00362     int i = numbering_ [ii];
00363 
00364     if ((Var (i) -> Multiplicity () > 0) &&
00365         (Var (i) -> Type () == AUX) &&
00366         (Var (i) -> Image () -> isInteger ()))
00367       Var (i) -> setInteger (true);
00368 
00369     //if (Var (i) -> Multiplicity () == 0)
00370     //Lb (i) = Ub (i) = 0.;
00371   }
00372 
00373   // TODO: re-compute ranks
00374 
00375   delete [] commuted_;  commuted_ = NULL;
00376   delete    graph_;     graph_    = NULL;
00377 
00378   return retval;
00379 }

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