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

Go to the documentation of this file.
00001 /*
00002  * $Id: standardize.cpp 274 2009-11-21 00:01:19Z 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   // CONSTRAINTS /////////////////////////////////////////////////////////////////////////////
00146 
00147   for (std::vector <CouenneConstraint *>::iterator i = constraints_.begin (); 
00148        i != constraints_.end (); ++i) {
00149 
00150 #ifdef DEBUG
00151     printf ("############# Constraint "); 
00152     (*i) -> print ();
00153 #endif
00154 
00155     exprAux *aux = (*i) -> standardize (this);
00156 
00157 #ifdef DEBUG
00158     printf (" ==> [%d] ", aux ? (aux -> Index ()) : -1); 
00159     (*i) -> print ();
00160 #endif
00161 
00162     if (aux) { // save if standardized
00163 
00164       // this is a top level auxiliary, i.e., an auxiliary whose node
00165       // in the DAG stands at the maximum level -- no other variable
00166       // depends on it as it is the lhs of a constraint.
00167       aux -> top_level () = true;
00168 
00169       //printf ("delete %x: ", ((*i) -> Body ())); ((*i) -> Body ()) -> print ();
00170       //printf ("\n"); 
00171       //delete ((*i) -> Body ());
00172       (*i) -> Body (new exprClone (aux));
00173       //      con2.push_back (*i);
00174     }
00175     else {
00176       CouNumber lb, ub;
00177       (*i) -> Body () -> getBounds (lb, ub);
00178       if ((((*((*i) -> Lb ())) ()) > ub) ||
00179           (((*((*i) -> Ub ())) ()) < lb)) {
00180         jnlst_ -> Printf (J_SUMMARY, J_PROBLEM, "found infeasible constraint [%g,%g]\n", lb, ub);
00181 #ifdef DEBUG
00182         (*i) -> print ();
00183 #endif
00184         retval = false;
00185       }
00186       iters2erase.push_back (i);
00187     }
00188 
00189     //(*i) -> Body () -> realign (this);
00190 
00191 #ifdef DEBUG
00192     printf (" --> ");
00193     (*i) -> print ();
00194     printf ("..............................................................\n");
00195     //print ();
00196 #endif
00197 
00198     /*printf ("=== "); fflush (stdout); 
00199     aux -> print (); printf (" := "); fflush (stdout);
00200     aux -> Image () -> print (); printf ("\n");*/
00201   }
00202 
00203   for (unsigned int i = iters2erase.size (); i--;)
00204     constraints_. erase (iters2erase [i]);
00205 
00206 #ifdef DEBUG 
00207   // Use with caution. Bounds on auxs are not defined yet, so valgrind complains
00208   printf ("done with standardization: (careful, bounds below can be nonsense)\n");
00209   print (); 
00210 #endif
00211 
00212   // Create evaluation order ////////////////////////////////////////////////////
00213 
00214   delete auxSet_;
00215 
00216   // reallocate space for enlarged set of variables
00217   domain_.current () -> resize (nVars ());
00218 
00219   //graph_ -> print ();
00220   graph_ -> createOrder ();
00221   //graph_ -> print ();
00222 
00223   assert (graph_ -> checkCycles () == false);
00224 
00225   // Fill numbering structure /////////////////////////////////////////////////
00226 
00227   int n = nVars ();
00228   numbering_ = new int [n];
00229   std::set <DepNode *, compNode> vertices = graph_ -> Vertices ();
00230 
00231   for (std::set <DepNode *, compNode>::iterator i = vertices.begin ();
00232        i != vertices.end (); ++i)
00233 
00234     numbering_ [(*i) -> Order ()] = (*i) -> Index (); 
00235 
00237 
00238   for (int i = 0; i < nVars (); i++) {
00239 
00240     int ord = numbering_ [i];
00241 
00242     if (variables_ [ord] -> Type () == AUX) {
00243 
00244       // initial auxiliary bounds are infinite (they are later changed
00245       // through branching)
00246 
00247       if (variables_ [ord] -> Index () >= nOrigVars_) { // and one that was not an original, originally...
00248 
00249         domain_.lb (ord) = -COIN_DBL_MAX;
00250         domain_.ub (ord) =  COIN_DBL_MAX;
00251       }
00252 
00253       //printf ("from "); variables_ [ord] -> Lb    () -> print (); 
00254 
00255       // tighten them with propagated bounds
00256       variables_ [ord] -> crossBounds ();
00257 
00258       //printf ("to "); variables_ [ord] -> Lb    () -> print (); printf (", now eval\n");
00259 
00260 #ifdef DEBUG
00261       printf (":::: %3d %10g [%10g, %10g]", 
00262               ord, domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00263 #endif
00264 
00265       // and evaluate them
00266       domain_.x  (ord) = (*(variables_ [ord] -> Image ())) ();
00267       domain_.lb (ord) = (*(variables_ [ord] -> Lb    ())) ();
00268       domain_.ub (ord) = (*(variables_ [ord] -> Ub    ())) ();
00269 
00270 #ifdef DEBUG
00271       printf (" --> %10g [%10g, %10g] [", 
00272               domain_.x (ord), domain_.lb (ord), domain_.ub (ord));
00273       variables_ [ord] -> Lb () -> print (); printf (",");
00274       variables_ [ord] -> Ub () -> print (); printf ("]\n");
00275 #endif
00276 
00277       bool integer = variables_ [ord] -> isInteger ();
00278 
00279       if (integer) {
00280         domain_.lb (ord) = ceil  (domain_.lb (ord) - COUENNE_EPS);
00281         domain_.ub (ord) = floor (domain_.ub (ord) + COUENNE_EPS);
00282       }
00283     }
00284   }
00285 
00286   // TODO: resolve duplicate index in exprQuad before restoring this
00287 
00288   std::string delete_redund;
00289   if (bonBase_)
00290     bonBase_ -> options () -> GetStringValue ("delete_redundant", delete_redund, "couenne."); 
00291   else
00292     delete_redund = "yes";
00293 
00294   if (delete_redund == "yes")
00295 
00296     // Look for auxiliaries of the form w:=x and replace each occurrence of w with x
00297     for (std::vector <exprVar *>::iterator i = variables_.begin (); 
00298        i != variables_.end (); ++i)
00299 
00300     if ((*i) -> Type () == AUX) {
00301 
00302       int type = (*i) -> Image () -> Type ();
00303 
00304       if ((type == VAR) || (type == AUX)) {
00305 
00306         // found w_k = x_h. 
00307         // 
00308         // Check if either is integer, the survivor will be integer too
00309         // Replace all occurrences of w_k with x_h
00310 
00311         /*printf ("redundancy: "); 
00312         (*i)             -> print (); printf (" := "); 
00313         (*i) -> Image () -> print (); printf ("\n");*/
00314 
00315         // use the info on the variable to be discarded: tighter
00316         // bounds and integrality that the replacement might not have.
00317 
00318         int 
00319           indStays  = (*i) -> Image () -> Index (), // index h
00320           indLeaves = (*i)             -> Index (); // index k
00321 
00322         if (indStays == indLeaves)  // very strange case, w_h = x_h
00323           continue;
00324 
00325         // do not swap! x_h could be in turn an auxiliary...
00326         //
00327         //if (indStays > indLeaves) 
00328         //{int swap = indStays; indStays = indLeaves; indLeaves = swap;} // swap
00329 
00330         exprVar 
00331           *varStays  = variables_ [indStays],
00332           *varLeaves = variables_ [indLeaves];
00333 
00334         // intersect features of the two variables (integrality, bounds)
00335 
00336         varStays -> lb () = varLeaves -> lb () = CoinMax (varStays -> lb (), varLeaves -> lb ());
00337         varStays -> ub () = varLeaves -> ub () = CoinMin (varStays -> ub (), varLeaves -> ub ());
00338 
00339         if (varStays  -> isInteger () ||
00340             varLeaves -> isInteger ()) {
00341 
00342           varStays -> lb () = ceil  (varStays -> lb ());
00343           varStays -> ub () = floor (varStays -> ub ());
00344 
00345           if (varStays -> Type () == AUX)
00346             varStays -> setInteger (true);
00347           else {
00348             //expression *old = varStays; // !!! leak
00349             variables_ [indStays] = varStays = new exprIVar (indStays, &domain_);
00350             auxiliarize (varStays); // replace it everywhere in the problem
00351             //delete old;
00352           }
00353         }
00354 
00355         auxiliarize (varLeaves, varStays); // now replace occurrences of w_k with x_h
00356 
00357         //if (varLeaves -> Index () >= nOrigVars_) // why check? It's not there anymore.
00358         varLeaves -> zeroMult (); // disable this variable
00359       }
00360     }
00361 
00367   for (int ii=0; ii < nVars (); ii++) {
00368 
00369     int i = numbering_ [ii];
00370 
00371     if ((Var (i) -> Multiplicity () > 0) &&
00372         (Var (i) -> Type () == AUX) &&
00373         (Var (i) -> Image () -> isInteger ()))
00374       Var (i) -> setInteger (true);
00375 
00376     //if (Var (i) -> Multiplicity () == 0)
00377     //Lb (i) = Ub (i) = 0.;
00378   }
00379 
00380   // TODO: re-compute ranks
00381 
00382   delete [] commuted_;  commuted_ = NULL;
00383   delete    graph_;     graph_    = NULL;
00384 
00385   return retval;
00386 }

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