/home/coin/SVN-release/OS-2.4.1/Couenne/src/branch/CouenneOrbitObj.cpp

Go to the documentation of this file.
00001 /* $Id: CouenneOrbitObj.cpp 490 2011-01-14 16:07:12Z pbelotti $
00002  *
00003  * Name:    CouenneOrbitObj.cpp
00004  * Authors: Jim Ostrowski, University of Waterloo
00005  *          Pietro Belotti, Lehigh University
00006  * Purpose: Base object for variables (to be used in branching)
00007  *
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 /*
00012 #include "CoinHelperFunctions.hpp"
00013 #include "CoinFinite.hpp"
00014 
00015 #include "CouenneProblem.hpp"
00016 #include "CouenneOrbitObj.hpp"
00017 #include "CouenneBranchingObject.hpp"
00018 
00019 #include "CouenneExprGroup.hpp"
00020 using namespace Couenne;
00021 
00022 void Node::node(int i, double c , double l, double u, int cod){
00023   index = i;
00024   coeff = c;
00025   lb = l;
00026   ub = u;
00027   color = -1;
00028   code = cod;
00029 }
00030 void Node::color_vertex(int k){
00031   color = k;
00032   }
00033  
00034 bool compare (Node a, Node b){
00035   if(a.get_code() == b.get_code() )
00036     if(a.get_coeff() == b.get_coeff() )
00037       if(a.get_lb() == b.get_lb())
00038         if(a.get_ub() == b.get_ub())
00039             return 1;
00040   return 0;   
00041   }
00042 
00043 bool node_sort (Node a, Node b){
00044   bool is_less = 0;
00045   
00046   if(a.get_code() < b.get_code() )
00047     is_less = 1;
00048   else if(a.get_code() == b.get_code() )
00049       if(a.get_coeff() < b.get_coeff() )
00050         is_less = 1;
00051       else if(a.get_coeff() ==  b.get_coeff() )
00052           if(a.get_lb() < b.get_lb()) 
00053             is_less = 1;
00054           else if(a.get_lb() == b.get_lb())
00055               if(a.get_ub() < b.get_ub())
00056                 is_less = 1;
00057               else if(a.get_index() < b.get_index())
00058                   is_less = 1;
00059   
00060   return is_less;   
00061 }
00062 bool index_sort (Node a, Node b){
00063   return (a.get_index() < b.get_index() );
00064 }
00065 
00066 
00067 
00068 
00069 
00071 CouenneOrbitObj::CouenneOrbitObj ():
00072 
00073   CouenneObject () {}
00074 
00075 CouenneOrbitObj::CouenneOrbitObj (CouenneCutGenerator *cutgen,
00076                                   CouenneProblem *p, 
00077                                   exprVar *ref, 
00078                                   Bonmin::BabSetupBase *base, 
00079                                   JnlstPtr jnlst):
00080   CouenneObject (cutgen, p, ref, base, jnlst){
00081 
00082 //  // Find Coefficients
00083 
00085 
00086   int num_affine = 0;
00087 
00088   for (std::vector <exprVar *>:: iterator i = p -> Variables (). begin (); 
00089        i != p -> Variables (). end (); ++i) {
00090     
00091     if ((*i) -> Type () == AUX) {
00092       if ((*i) -> Image () -> code () != COU_EXPRGROUP) {
00093         if ((*i) -> Image () -> Type () == N_ARY) {
00094           for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
00095             expression *arg = (*i) -> Image () -> ArgList () [a];
00096             
00097             if (arg -> Type () == CONST) {
00098               num_affine ++;
00099                 
00100             }
00101           }
00102         }
00103       }
00104       if ((*i) -> Image () -> code () == COU_EXPRGROUP) {      
00105         
00106         exprGroup *e = dynamic_cast <exprGroup *> ((*i) -> Image ());
00107         
00108         // add a node for e -> getC0 ();
00109         if (e -> getc0 () != 0 ){
00110           num_affine ++;
00111         }
00112         
00113         // for each term add nodes for their non-one coefficients and their variable
00114         
00115         for (exprGroup::lincoeff::iterator el = e ->lcoeff().begin (); el != e -> lcoeff ().end (); ++el) {
00116           if ( el -> second !=1){
00117             num_affine ++;
00118           }
00119         }
00120       }
00121     }
00122   }
00123  
00124 
00125 
00126 
00127 
00128   
00129   // Create global Nauty object
00130 
00131  int nc = num_affine + p-> nVars ();
00132  printf (" There are   %d  coefficient vertices in the graph \n", num_affine);
00133  printf (" Graph has    %d  vertices \n", nc);
00134 
00135 
00136  nauty_info = new Nauty(nc);
00137 
00138   // create graph
00139 
00140  int coef_count= p-> nVars ();
00141  for (std::vector <exprVar *>:: iterator i = p -> Variables (). begin (); 
00142        i != p -> Variables (). end (); ++i) {
00143 
00144     //    printf ("I have code %d \n",  (*i) ->  Image() -> code() );
00145 
00146 
00147     
00148     if ((*i) -> Type () == AUX) {
00149       printf ("aux is %d with code %d \n", (*i) -> Index (), (*i) -> Image () -> code() );
00150       // this is an auxiliary variable
00151       
00152       Node vertex;
00153       vertex.node( (*i) -> Index () , 0.0 , (*i) -> lb () , (*i) -> ub () ,  (*i) -> Image () -> code() );
00154       node_info.push_back( vertex);
00155                 
00156       // add node in nauty graph for its index, (*i) -> Index ()
00157 
00158       if ((*i) -> Image () -> Type () == N_ARY) {
00159         
00160         if ((*i) -> Image () -> code () != COU_EXPRGROUP) {
00161           
00162           for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
00163             expression *arg = (*i) -> Image () -> ArgList () [a];
00164             
00165             if (arg -> Type () != CONST) {
00166               printf (" add edge  %d , %d\n", (*i) -> Index (),  arg -> Index ());
00167               nauty_info->addElement((*i) -> Index (),  arg -> Index ());
00168               nauty_info->addElement( arg -> Index (), (*i) -> Index ());
00169             }
00170 
00171             else{
00172               
00173               assert (arg -> Type () == CONST); 
00174 
00175               printf (" add new vertex to graph, coef # %d, value %g \n", coef_count, arg -> Value() );
00176               printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (),  coef_count);
00177               nauty_info->addElement((*i) -> Index (),  coef_count);
00178               nauty_info->addElement( coef_count, (*i) -> Index ());
00179               
00180 
00181               Node coef_vertex;
00182               coef_vertex.node( coef_count, arg -> Value(), arg -> Value() , arg -> Value(), -2 );
00183               node_info.push_back(coef_vertex);
00184               coef_count ++;          
00185             }
00186             
00187           }
00188         }
00189         
00190         
00191         if ((*i) -> Image () -> code () == COU_EXPRGROUP) {
00192 
00193           // dynamic_cast it to an exprGroup
00194 
00195           exprGroup *e = dynamic_cast <exprGroup *> ((*i) -> Image ());
00196 
00197           // add a node for e -> getC0 ();
00198           if (e -> getc0 () != 0 ){
00199             Node coef_vertex;
00200             coef_vertex.node( coef_count, e -> getc0(), e -> getc0() , e -> getc0(), -2 );
00201             node_info.push_back(coef_vertex);
00202 
00203             printf ("Add coef vertex to graph (coef value   %f) \n", e -> getc0 () );
00204             printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (), coef_count);
00205             nauty_info->addElement((*i) -> Index (),  coef_count);
00206             nauty_info->addElement( coef_count, (*i) -> Index ());
00207 
00208 
00209             coef_count ++;
00210           }
00211           
00212           // for each term add nodes for their non-one coefficients and their variable
00213 
00214           for (exprGroup::lincoeff::iterator el = e ->lcoeff().begin (); el != e -> lcoeff ().end (); ++el) {
00215 
00216             if ( el -> second ==1){ 
00217               printf (" add edge index %d ,  index %d\n", (*i) -> Index (), el -> first -> Index()    );
00218               nauty_info->addElement((*i) -> Index (),  el -> first -> Index());
00219               nauty_info->addElement( el -> first -> Index (), (*i) -> Index ());
00220             }
00221             else{
00222               printf (" add new vertex to graph, coef # %d with coef %f \n", coef_count, el -> second);
00223               Node coef_vertex;
00224               coef_vertex.node( coef_count, el -> second, el -> second, el -> second, -2 );
00225               node_info.push_back(coef_vertex);
00226 
00227               printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (), coef_count);
00228               nauty_info->addElement((*i) -> Index (),  coef_count);
00229               nauty_info->addElement( coef_count, (*i) -> Index ());
00230               
00231               printf (" add edge coef index %d ,  2nd index %d\n", coef_count,  el -> first -> Index()  );
00232               nauty_info->addElement(coef_count,  el -> first -> Index());
00233               nauty_info->addElement( el -> first -> Index (), coef_count);
00234               coef_count ++;
00235             }
00236             // coefficient = el -> second
00237             
00238             // variable index is el -> first -> Index ()
00239           }
00240           
00241         }
00242 
00243       } else if ((*i) -> Image () -> Type () == UNARY) {
00244 
00245       }
00246 
00247     } else {
00248       //  printf ("variable is %d\n", (*i) -> Index ());
00249       Node var_vertex;
00250       var_vertex.node( (*i) -> Index () , 0 , (*i) -> lb () , (*i) -> ub () ,  -1 );
00251       //      printf( "var info index %d, coef %f, lb %f, ub %f, code %d \n", var_vertex.get_index() , var_vertex.get_coeff() , var_vertex.get_lb() , var_vertex.get_ub() ,  var_vertex.get_code() );
00252       node_info.push_back(var_vertex);
00253        // this is an original variable
00254       
00255     }
00256   }
00257 
00258 }
00259 
00260 
00262 CouenneOrbitObj::CouenneOrbitObj (exprVar *ref, 
00263                                   Bonmin::BabSetupBase *base, 
00264                                   JnlstPtr jnlst):
00265 
00266   CouenneObject (ref, base, jnlst) {}
00267 
00268 
00270 CouenneOrbitObj::CouenneOrbitObj (const CouenneOrbitObj &src):
00271   CouenneObject       (src) {}
00272 
00273 
00275 OsiBranchingObject *CouenneOrbitObj::createBranch (OsiSolverInterface *si,
00276                                                    const OsiBranchingInformation *info,
00277                                                    int way) const {
00278 
00279   return NULL;
00280 }
00281 
00282 
00283 
00284 
00285 
00286 // set point at current LP solution
00287 double CouenneOrbitObj::feasibleRegion (OsiSolverInterface*, const OsiBranchingInformation*) const {
00288   return 0;
00289 }
00290 
00291 
00292 
00294 double CouenneOrbitObj::infeasibility (const OsiBranchingInformation *info, int &way) const {
00295 
00296   return 0;
00297 }
00298 
00299 
00303 double CouenneOrbitObj::checkInfeasibility (const OsiBranchingInformation *info) const {
00304 
00305   return 0;
00306 
00307 }
00308 
00309 void CouenneOrbitObj::Compute_Symmetry(){
00310   sort(node_info. begin (), node_info. end (), node_sort);
00311   
00312   int color = 1;
00313   for (std::vector <Node>:: iterator i = node_info. begin (); 
00314        i != node_info. end (); ++i) {
00315     if( (*i).get_color() == -1){
00316       (*i).color_vertex(color);
00317       printf ("Graph vertex %d is given color %d\n", (*i).get_index(), color);
00318       nauty_info -> color_node((*i).get_index(), color);
00319       for (std::vector <Node>:: iterator j = i+1; j <= node_info. end (); ++j) 
00320         if( compare( (*i) , (*j) ) ==1){
00321           (*j).color_vertex(color);
00322           nauty_info -> color_node((*j).get_index(),color);
00323           printf ("Graph vertex %d is given color %d, the same as vertex %d\n", (*j).get_index(), color, (*i).get_index());
00324         }
00325       //       else
00326       // j = node_info. end();
00327       color++;
00328       
00329     }
00330   }
00331   
00332   nauty_info -> computeAuto();
00333 }
00334 
00335 void CouenneOrbitObj::Print_Orbits(){
00336 
00337   printf("num gens = %d, num orbits = %d \n", nauty_info -> getNumGenerators(), nauty_info -> getNumOrbits() );
00338   
00339   std::vector<std::vector<int> > new_orbits = nauty_info->getOrbits();
00340   
00341   printf("There were %d orbits and %d generators\n",
00342          nauty_info->getNumOrbits(),
00343          nauty_info->getNumGenerators());
00344   
00345   for (unsigned int i = 0; i < new_orbits.size(); i++) {
00346     printf( "Orbit %d [", i);
00347     copy(new_orbits[i].begin(), new_orbits[i].end(),
00348          std::ostream_iterator<int>(std::cout, " "));
00349     printf("] \n");
00350   }
00351   
00352   
00353   
00354 }
00355 
00356 
00357   
00358 void CouenneOrbitObj::ChangeBounds (CouenneProblem  * p ){
00359   sort(node_info. begin (), node_info. end (), index_sort);
00360  
00361   for (std::vector <exprVar *>:: iterator i =  p->Variables (). begin (); 
00362        i !=  p->Variables (). end (); ++i) {
00363     node_info[(*i)->Index() ].bounds ( (*i) -> lb () , (*i) -> ub () );
00364 
00365   }
00366 
00367   
00368 }
00369 */

Generated on Thu Nov 10 03:05:42 2011 by  doxygen 1.4.7