Changeset 409


Ignore:
Timestamp:
Oct 13, 2010 4:26:33 PM (11 years ago)
Author:
jim_ostrowski
Message:

Adding orbital branching features to Couenne

Location:
trunk/Couenne/src
Files:
19 edited

Legend:

Unmodified
Added
Removed

  • trunk/Couenne/src/Makefile.am

    r393 r409  
    140140        heuristics/BonNlpHeuristic.hpp \
    141141        heuristics/BonInitHeuristic.hpp \
     142        branch/Nauty.h \       
    142143        heuristics/CouenneFeasPump.hpp \
    143144        branch/CouenneObject.hpp \

  • trunk/Couenne/src/Makefile.in

    r393 r409  
    410410        heuristics/BonNlpHeuristic.hpp \
    411411        heuristics/BonInitHeuristic.hpp \
     412        branch/Nauty.h \
    412413        heuristics/CouenneFeasPump.hpp \
    413414        branch/CouenneObject.hpp \

  • trunk/Couenne/src/bound_tightening/Makefile.am

    r402 r409  
    6666        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/main` \
    6767        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression` \
     68        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/branch`\
    6869        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression/operators`
    6970endif

  • trunk/Couenne/src/bound_tightening/Makefile.in

    r402 r409  
    4949@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/main` \
    5050@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression` \
     51@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/branch`\
    5152@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression/operators`
    5253

  • trunk/Couenne/src/bound_tightening/boundTightening.cpp

    r397 r409  
    211211  return btCore (chg_bds);
    212212
     213  //Tighten bounds
     214  /* 
     215  std::vector<std::vector<int> > new_orbits = nauty_info->getOrbits();
     216 
     217  for (int i=0; i <  nauty_info -> getNumOrbits(); i++){
     218    int ll =-COUENNE_INFINITY;
     219    int uu =COUENNE_INFINITY;
     220    for(int j = 0; j < new_orbits[i].size(); j++){
     221      if(Lb( new_orbits[i][j]) > ll)
     222        ll = Lb( new_orbits[i][j]);
     223      if(Ub( new_orbits[i][j]) < uu)
     224        uu = Ub( new_orbits[i][j]);
     225    }
     226    for(int j = 0; j < new_orbits[i].size(); j++){
     227      Lb( new_orbits[i][j]) = ll;
     228      Ub( new_orbits[i][j]) = uu;
     229    }
     230  }
     231
     232  */
     233 
    213234  //printf ("Total cpu time = %e\n", CoinCpuTime () - startTime);
    214235  //exit (-1);
    … …  
    220241int CouenneProblem::redCostBT (const OsiSolverInterface *psi,
    221242                               t_chg_bounds *chg_bds) const {
     243
     244  //Compute symmetry group
     245  //  ChangeBounds( psi -> getColLower (),  psi -> getColUpper (), psi -> getNumCols ());
     246  //Compute_Symmetry();
     247
     248 
     249 
    222250  int
    223251    nchanges = 0,

  • trunk/Couenne/src/branch/CouenneBranchingObject.cpp

    r349 r409  
    148148  */
    149149
     150
     151  //_______ Jim's adding stuff ________
     152
     153  problem_ -> ChangeBounds( solver -> getColLower (),  solver -> getColUpper (), solver -> getNumCols ());
     154  problem_ -> Compute_Symmetry();
     155
     156 
     157  std::vector< int > branch_orbit;
     158  //  problem_ -> Print_Orbits();
     159  //printf("branching on var %i \n", index);
     160  branch_orbit = problem_ -> Find_Orbit(index);
     161  /*
     162  if(branch_orbit.size() >= 2){
     163    printf("branching on orbit of size %i \n", branch_orbit.size());
     164    problem_ -> Print_Orbits();
     165  }
     166  */
    150167  if (!way) solver -> setColUpper (index, integer ? floor (brpt) : brpt); // down branch
    151   else      solver -> setColLower (index, integer ? ceil  (brpt) : brpt); // up   branch
    152 
     168  else {
     169    for (std::vector<int>::iterator it = branch_orbit.begin(); it!=branch_orbit.end(); ++it)
     170      solver -> setColLower (*it, integer ? ceil  (brpt) : brpt); // up   branch
     171   
     172  }
     173 
     174 
     175 
    153176  //CouenneSolverInterface *couenneSolver = dynamic_cast <CouenneSolverInterface *> (solver);
    154177  //CouenneProblem *p = cutGen_ -> Problem ();

  • trunk/Couenne/src/branch/CouenneOrbitObj.cpp

    r349 r409  
    99 */
    1010
     11/*
    1112#include "CoinHelperFunctions.hpp"
    1213#include "CoinFinite.hpp"
    … …  
    1718
    1819#include "CouenneExprGroup.hpp"
    19 
    2020using namespace Couenne;
     21
     22void Node::node(int i, double c , double l, double u, int cod){
     23  index = i;
     24  coeff = c;
     25  lb = l;
     26  ub = u;
     27  color = -1;
     28  code = cod;
     29}
     30void Node::color_vertex(int k){
     31  color = k;
     32  }
     33 
     34bool compare (Node a, Node b){
     35  if(a.get_code() == b.get_code() )
     36    if(a.get_coeff() == b.get_coeff() )
     37      if(a.get_lb() == b.get_lb())
     38        if(a.get_ub() == b.get_ub())
     39            return 1;
     40  return 0;   
     41  }
     42
     43bool node_sort (Node a, Node b){
     44  bool is_less = 0;
     45 
     46  if(a.get_code() < b.get_code() )
     47    is_less = 1;
     48  else if(a.get_code() == b.get_code() )
     49      if(a.get_coeff() < b.get_coeff() )
     50        is_less = 1;
     51      else if(a.get_coeff() ==  b.get_coeff() )
     52          if(a.get_lb() < b.get_lb())
     53            is_less = 1;
     54          else if(a.get_lb() == b.get_lb())
     55              if(a.get_ub() < b.get_ub())
     56                is_less = 1;
     57              else if(a.get_index() < b.get_index())
     58                  is_less = 1;
     59 
     60  return is_less;   
     61}
     62bool index_sort (Node a, Node b){
     63  return (a.get_index() < b.get_index() );
     64}
     65
     66
     67
     68
    2169
    2270/// Empty constructor
    … …  
    2573  CouenneObject () {}
    2674
    27 
    28 /// Constructor with information for branching point selection strategy
    2975CouenneOrbitObj::CouenneOrbitObj (CouenneCutGenerator *cutgen,
    3076                                  CouenneProblem *p,
    … …  
    3278                                  Bonmin::BabSetupBase *base,
    3379                                  JnlstPtr jnlst):
    34   CouenneObject (cutgen, p, ref, base, jnlst) {
    35 
    36   // nautyGraph_ = createNautyGraph (p);
    37 
    38   // create graph
    39 
    40   // create p -> nVars () nodes for (aux+orig) variables.
    41 
    42 
    43   // join them
     80  CouenneObject (cutgen, p, ref, base, jnlst){
     81
     82//  // Find Coefficients
     83
     84/// initialize nauty
     85
     86  int num_affine = 0;
    4487
    4588  for (std::vector <exprVar *>:: iterator i = p -> Variables (). begin ();
    4689       i != p -> Variables (). end (); ++i) {
    47 
     90   
    4891    if ((*i) -> Type () == AUX) {
    49 
     92      if ((*i) -> Image () -> code () != COU_EXPRGROUP) {
     93        if ((*i) -> Image () -> Type () == N_ARY) {
     94          for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
     95            expression *arg = (*i) -> Image () -> ArgList () [a];
     96           
     97            if (arg -> Type () == CONST) {
     98              num_affine ++;
     99               
     100            }
     101          }
     102        }
     103      }
     104      if ((*i) -> Image () -> code () == COU_EXPRGROUP) {     
     105       
     106        exprGroup *e = dynamic_cast <exprGroup *> ((*i) -> Image ());
     107       
     108        // add a node for e -> getC0 ();
     109        if (e -> getc0 () != 0 ){
     110          num_affine ++;
     111        }
     112       
     113        // for each term add nodes for their non-one coefficients and their variable
     114       
     115        for (exprGroup::lincoeff::iterator el = e ->lcoeff().begin (); el != e -> lcoeff ().end (); ++el) {
     116          if ( el -> second !=1){
     117            num_affine ++;
     118          }
     119        }
     120      }
     121    }
     122  }
     123 
     124
     125
     126
     127
     128 
     129  // Create global Nauty object
     130
     131 int nc = num_affine + p-> nVars ();
     132 printf (" There are   %d  coefficient vertices in the graph \n", num_affine);
     133 printf (" Graph has    %d  vertices \n", nc);
     134
     135
     136 nauty_info = new Nauty(nc);
     137
     138  // create graph
     139
     140 int coef_count= p-> nVars ();
     141 for (std::vector <exprVar *>:: iterator i = p -> Variables (). begin ();
     142       i != p -> Variables (). end (); ++i) {
     143
     144    //    printf ("I have code %d \n",  (*i) ->  Image() -> code() );
     145
     146
     147   
     148    if ((*i) -> Type () == AUX) {
     149      printf ("aux is %d with code %d \n", (*i) -> Index (), (*i) -> Image () -> code() );
    50150      // this is an auxiliary variable
    51 
     151     
     152      Node vertex;
     153      vertex.node( (*i) -> Index () , 0.0 , (*i) -> lb () , (*i) -> ub () ,  (*i) -> Image () -> code() );
     154      node_info.push_back( vertex);
     155               
    52156      // add node in nauty graph for its index, (*i) -> Index ()
    53157
    54       if        ((*i) -> Image () -> Type () == N_ARY) {
    55 
    56         for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
    57 
    58           expression *arg = (*i) -> Image () -> ArgList () [a];
    59 
    60           if (arg -> Type () == AUX) {
    61 
    62             // a-th argument is an auxiliary variable
    63 
    64           } else if (arg -> Type () == VAR) {
    65 
    66             CouNumber lb, ub;
    67 
    68             arg -> getBounds (lb, ub);
    69 
    70             // a-th argument is an original variable
    71 
    72           } else {
    73 
    74             assert (arg -> Type () == CONST);
    75 
    76             // this is a constant.
    77 
    78           }
    79         }
    80 
    81 
     158      if ((*i) -> Image () -> Type () == N_ARY) {
     159       
     160        if ((*i) -> Image () -> code () != COU_EXPRGROUP) {
     161         
     162          for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
     163            expression *arg = (*i) -> Image () -> ArgList () [a];
     164           
     165            if (arg -> Type () != CONST) {
     166              printf (" add edge  %d , %d\n", (*i) -> Index (),  arg -> Index ());
     167              nauty_info->addElement((*i) -> Index (),  arg -> Index ());
     168              nauty_info->addElement( arg -> Index (), (*i) -> Index ());
     169            }
     170
     171            else{
     172             
     173              assert (arg -> Type () == CONST);
     174
     175              printf (" add new vertex to graph, coef # %d, value %g \n", coef_count, arg -> Value() );
     176              printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (),  coef_count);
     177              nauty_info->addElement((*i) -> Index (),  coef_count);
     178              nauty_info->addElement( coef_count, (*i) -> Index ());
     179             
     180
     181              Node coef_vertex;
     182              coef_vertex.node( coef_count, arg -> Value(), arg -> Value() , arg -> Value(), -2 );
     183              node_info.push_back(coef_vertex);
     184              coef_count ++;         
     185            }
     186           
     187          }
     188        }
     189       
     190       
    82191        if ((*i) -> Image () -> code () == COU_EXPRGROUP) {
    83192
    … …  
    87196
    88197          // add a node for e -> getC0 ();
    89 
     198          if (e -> getc0 () != 0 ){
     199            Node coef_vertex;
     200            coef_vertex.node( coef_count, e -> getc0(), e -> getc0() , e -> getc0(), -2 );
     201            node_info.push_back(coef_vertex);
     202
     203            printf ("Add coef vertex to graph (coef value   %f) \n", e -> getc0 () );
     204            printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (), coef_count);
     205            nauty_info->addElement((*i) -> Index (),  coef_count);
     206            nauty_info->addElement( coef_count, (*i) -> Index ());
     207
     208
     209            coef_count ++;
     210          }
     211         
    90212          // for each term add nodes for their non-one coefficients and their variable
    91213
    92214          for (exprGroup::lincoeff::iterator el = e ->lcoeff().begin (); el != e -> lcoeff ().end (); ++el) {
    93215
     216            if ( el -> second ==1){
     217              printf (" add edge index %d ,  index %d\n", (*i) -> Index (), el -> first -> Index()    );
     218              nauty_info->addElement((*i) -> Index (),  el -> first -> Index());
     219              nauty_info->addElement( el -> first -> Index (), (*i) -> Index ());
     220            }
     221            else{
     222              printf (" add new vertex to graph, coef # %d with coef %f \n", coef_count, el -> second);
     223              Node coef_vertex;
     224              coef_vertex.node( coef_count, el -> second, el -> second, el -> second, -2 );
     225              node_info.push_back(coef_vertex);
     226
     227              printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (), coef_count);
     228              nauty_info->addElement((*i) -> Index (),  coef_count);
     229              nauty_info->addElement( coef_count, (*i) -> Index ());
     230             
     231              printf (" add edge coef index %d ,  2nd index %d\n", coef_count,  el -> first -> Index()  );
     232              nauty_info->addElement(coef_count,  el -> first -> Index());
     233              nauty_info->addElement( el -> first -> Index (), coef_count);
     234              coef_count ++;
     235            }
    94236            // coefficient = el -> second
    95 
     237           
    96238            // variable index is el -> first -> Index ()
    97239          }
    … …  
    104246
    105247    } else {
    106 
    107       // this is an original variable
    108 
     248      //  printf ("variable is %d\n", (*i) -> Index ());
     249      Node var_vertex;
     250      var_vertex.node( (*i) -> Index () , 0 , (*i) -> lb () , (*i) -> ub () ,  -1 );
     251      //      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() );
     252      node_info.push_back(var_vertex);
     253       // this is an original variable
     254     
    109255    }
    110256  }
    111257
    112   // create partitions for log only
    113 
    114   for (std::vector <exprVar *>:: iterator i = p -> Variables (). begin ();
    115        i != p -> Variables (). end (); ++i) {
    116 
    117     if ((*i) -> Type () == AUX) {
    118 
    119       // this is an auxiliary variable
    120 
    121       if ((*i) -> Image () -> code () == COU_EXPRLOG) {
    122         printf ("log is %d\n", (*i) -> Index ());
    123       }
    124 
    125     } else {
    126 
    127       // this is an original variable
    128 
    129     }
    130   }
    131258}
    132259
    … …  
    154281
    155282
     283
     284
     285
    156286// set point at current LP solution
    157287double CouenneOrbitObj::feasibleRegion (OsiSolverInterface*, const OsiBranchingInformation*) const {
    … …  
    176306
    177307}
     308
     309void CouenneOrbitObj::Compute_Symmetry(){
     310  sort(node_info. begin (), node_info. end (), node_sort);
     311 
     312  int color = 1;
     313  for (std::vector <Node>:: iterator i = node_info. begin ();
     314       i != node_info. end (); ++i) {
     315    if( (*i).get_color() == -1){
     316      (*i).color_vertex(color);
     317      printf ("Graph vertex %d is given color %d\n", (*i).get_index(), color);
     318      nauty_info -> color_node((*i).get_index(), color);
     319      for (std::vector <Node>:: iterator j = i+1; j <= node_info. end (); ++j)
     320        if( compare( (*i) , (*j) ) ==1){
     321          (*j).color_vertex(color);
     322          nauty_info -> color_node((*j).get_index(),color);
     323          printf ("Graph vertex %d is given color %d, the same as vertex %d\n", (*j).get_index(), color, (*i).get_index());
     324        }
     325      //       else
     326      // j = node_info. end();
     327      color++;
     328     
     329    }
     330  }
     331 
     332  nauty_info -> computeAuto();
     333}
     334
     335void CouenneOrbitObj::Print_Orbits(){
     336
     337  printf("num gens = %d, num orbits = %d \n", nauty_info -> getNumGenerators(), nauty_info -> getNumOrbits() );
     338 
     339  std::vector<std::vector<int> > new_orbits = nauty_info->getOrbits();
     340 
     341  printf("There were %d orbits and %d generators\n",
     342         nauty_info->getNumOrbits(),
     343         nauty_info->getNumGenerators());
     344 
     345  for (unsigned int i = 0; i < new_orbits.size(); i++) {
     346    printf( "Orbit %d [", i);
     347    copy(new_orbits[i].begin(), new_orbits[i].end(),
     348         std::ostream_iterator<int>(std::cout, " "));
     349    printf("] \n");
     350  }
     351 
     352 
     353 
     354}
     355
     356
     357 
     358void CouenneOrbitObj::ChangeBounds (CouenneProblem  * p ){
     359  sort(node_info. begin (), node_info. end (), index_sort);
     360 
     361  for (std::vector <exprVar *>:: iterator i =  p->Variables (). begin ();
     362       i !=  p->Variables (). end (); ++i) {
     363    node_info[(*i)->Index() ].bounds ( (*i) -> lb () , (*i) -> ub () );
     364
     365  }
     366
     367 
     368}
     369*/

  • trunk/Couenne/src/branch/CouenneOrbitObj.hpp

    r349 r409  
    88 * This file is licensed under the Common Public License (CPL)
    99 */
    10 
     10/*
    1111#ifndef COUENNEORBITOBJ_HPP
    1212#define COUENNEORBITOBJ_HPP
    … …  
    1818#include "CouenneJournalist.hpp"
    1919#include "OsiBranchingObject.hpp"
    20 
    2120#include "CouenneObject.hpp"
     21#include "Nauty.h"
    2222
    2323namespace Couenne {
    2424
     25class Node{
     26  int index;
     27  double coeff;
     28  double lb;
     29  double ub;
     30  int color;
     31  int code;
     32public:
     33  void node(int, double, double, double, int);
     34  void color_vertex(int);
     35  int get_index () {return index;
     36  };
     37  double get_coeff () {return coeff;     
     38  };
     39  double get_lb () {return lb;     
     40  };
     41  double get_ub () {return ub ;     
     42  };
     43  int get_color () {return color;     
     44  };
     45  int get_code () {return code;     
     46  };
     47  void bounds( double a, double b){ lb = a; ub = b;
     48  };
     49};
     50
     51  bool compare (  Node a, Node b);
     52  bool node_sort (  Node a, Node b);
     53  bool index_sort (  Node a, Node b);
     54
     55
    2556/// OsiObject for Orbital Branching
    26 
    2757class CouenneOrbitObj: public CouenneObject {
    2858
    … …  
    3666                   CouenneProblem *p,
    3767                   exprVar *ref, Bonmin::BabSetupBase *base, JnlstPtr jnlst);
     68
     69
     70                   
    3871
    3972  /// Constructor with lesser information, used for infeasibility only
    … …  
    5083  {return new CouenneOrbitObj (*this);}
    5184
     85
     86 
    5287  /// set object parameters by reading from command line
    5388  void setParameters (Bonmin::BabSetupBase *base);
    54 
    5589  /// compute infeasibility of this variable, |w - f(x)| (where w is
    5690  /// the auxiliary variable defined as w = f(x)
    … …  
    66100  /// create CouenneBranchingObject or CouenneThreeWayBranchObj based
    67101  /// on this object
    68   virtual OsiBranchingObject *createBranch (OsiSolverInterface*,
    69                                             const OsiBranchingInformation*, int) const;
     102  virtual OsiBranchingObject *createBranch (OsiSolverInterface*,const OsiBranchingInformation*, int) const;
    70103
     104
     105 
     106  void Compute_Symmetry();
     107  void Print_Orbits();
     108  void ChangeBounds (CouenneProblem *p);
     109   
     110
     111  std::vector<Node> node_info;
     112 
     113  Nauty *nauty_info;
     114 
    71115protected:
    72116
    … …  
    76120
    77121#endif
     122*/

  • trunk/Couenne/src/branch/Makefile.am

    r322 r409  
    1111# List all source files for this library, including headers
    1212libCouenneBranch_la_SOURCES = \
     13        Nauty.cpp\
    1314        CouenneThreeWayBranchObj.cpp \
    1415        CouenneBranchingObject.cpp \

  • trunk/Couenne/src/branch/Makefile.in

    r336 r409  
    6767LTLIBRARIES = $(noinst_LTLIBRARIES)
    6868libCouenneBranch_la_LIBADD =
    69 am_libCouenneBranch_la_OBJECTS = CouenneThreeWayBranchObj.lo \
     69am_libCouenneBranch_la_OBJECTS = Nauty.lo CouenneThreeWayBranchObj.lo \
    7070        CouenneBranchingObject.lo CouenneObject.lo CouenneVarObject.lo \
    7171        CouenneChooseVariable.lo CouenneChooseStrong.lo \
    … …  
    305305# List all source files for this library, including headers
    306306libCouenneBranch_la_SOURCES = \
     307        Nauty.cpp\
    307308        CouenneThreeWayBranchObj.cpp \
    308309        CouenneBranchingObject.cpp \
    … …  
    418419@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CouenneThreeWayBranchObj.Plo@am__quote@
    419420@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/CouenneVarObject.Plo@am__quote@
     421@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/Nauty.Plo@am__quote@
    420422@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/doStrongBranching.Plo@am__quote@
    421423@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/feasibleRegion.Plo@am__quote@

  • trunk/Couenne/src/couenne.opt

    r16 r409  
    4242boundtightening_print_level 0 # Output level for bound tightening code in Couenne
    4343convexifying_print_level    0 # Output level for convexifying code in Couenne
    44 problem_print_level         4 # Output level for problem manipulation code in Couenne
     44problem_print_level         7 # Output level for problem manipulation code in Couenne
    4545                              # (4 prints out original problem)
    4646nlpheur_print_level         0 # Output level for NLP heuristic in Couenne
    4747#disjcuts_print_level       0 # Output level for disjunctive cuts in Couenne - disabled for now
    4848
    49 
     49orbital_branching yes
    5050
    5151#

  • trunk/Couenne/src/main/BonCouenneSetup.cpp

    r407 r409  
    402402  }
    403403
    404   // Experimental: orbital branching //////////////////////////////////////////////
    405   options () -> GetStringValue ("orbital_branching", s, "couenne.");
     404    // Experimental: orbital branching //////////////////////////////////////////////
     405    /*
     406    options () -> GetStringValue ("orbital_branching", s, "couenne.");
    406407
    407408  if (s == "yes") {
    … …  
    410411    objects [nobj++] -> setPriority (contObjPriority);
    411412  }
    412 
     413    */
    413414  // Add objects /////////////////////////////////
    414415

  • trunk/Couenne/src/problem/CouenneProblem.cpp

    r407 r409  
    281281
    282282
     283//Symmetry Stuff --------------------------------------------------------------------
     284
     285
     286void Node::node(int i, double c , double l, double u, int cod){
     287  index = i;
     288  coeff = c;
     289  lb = l;
     290  ub = u;
     291  color = -1;
     292  code = cod;
     293}
     294void Node::color_vertex(int k){
     295  color = k;
     296}
     297
     298bool CouenneProblem::compare ( Node a, Node b) const{
     299  if(a.get_code() == b.get_code() )
     300    if(a.get_coeff() == b.get_coeff() )
     301      if( fabs ( a.get_lb() - b.get_lb() ) <= COUENNE_EPS )
     302        if( fabs ( a.get_ub() - b.get_ub() ) <= COUENNE_EPS )
     303          return 1;
     304  return 0;
     305}
     306
     307/*
     308bool CouenneProblem::node_sort (Node a, Node  b){
     309  bool is_less = 0;
     310
     311  if(a.get_code() < b.get_code() )
     312    is_less = 1;
     313  else {
     314    if(a.get_code() == b.get_code() )
     315      if(a.get_coeff() < b.get_coeff() )
     316        is_less = 1;
     317      else{
     318        if(a.get_coeff() ==  b.get_coeff() )
     319          if(a.get_lb() < b.get_lb())
     320            is_less = 1;
     321          else{
     322            if(a.get_lb() == b.get_lb())
     323              if(a.get_ub() < b.get_ub())
     324                is_less = 1;
     325              else{
     326                if(a.get_index() < b.get_index())
     327                  is_less = 1;
     328              }
     329          }
     330      }
     331  }
     332  return is_less;
     333}
     334bool CouenneProblem::index_sort (Node a, Node b){
     335  return (a.get_index() < b.get_index() );
     336}
     337*/
     338
     339void CouenneProblem::sym_setup (){
     340
     341  //  // Find Coefficients
     342
     343  /// initialize nauty
     344
     345  int num_affine = 0;
     346
     347  for (std::vector <exprVar *>:: iterator i = Variables (). begin ();
     348       i != Variables (). end (); ++i) {
     349
     350    if ((*i) -> Type () == AUX) {
     351      if ((*i) -> Image () -> code () != COU_EXPRGROUP) {
     352        if ((*i) -> Image () -> Type () == N_ARY) {
     353          for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
     354            expression *arg = (*i) -> Image () -> ArgList () [a];
     355
     356            if (arg -> Type () == CONST) {
     357              num_affine ++;
     358
     359            }
     360          }
     361        }
     362      }
     363      if ((*i) -> Image () -> code () == COU_EXPRGROUP) {
     364
     365        exprGroup *e = dynamic_cast <exprGroup *> ((*i) -> Image ());
     366
     367        // add a node for e -> getC0 ();
     368        if (e -> getc0 () != 0 ){
     369          num_affine ++;
     370        }
     371
     372        // for each term add nodes for their non-one coefficients and their variable
     373
     374        for (exprGroup::lincoeff::iterator el = e ->lcoeff().begin (); el != e -> lcoeff ().end (); ++el) {
     375          if ( el -> second !=1){
     376            num_affine ++;
     377          }
     378        }
     379      }
     380    }
     381  }
     382
     383
     384
     385
     386
     387
     388  // Create global Nauty object
     389
     390  int nc = num_affine + nVars ();
     391  // printf (" There are   %d  coefficient vertices in the graph \n", num_affine);
     392  //printf (" Graph has    %d  vertices \n", nc);
     393
     394
     395  nauty_info = new Nauty(nc);
     396  // create graph
     397
     398  int coef_count= nVars ();
     399  for (std::vector <exprVar *>:: iterator i =  Variables (). begin ();
     400       i != Variables (). end (); ++i) {
     401
     402    //    printf ("I have code %d \n",  (*i) ->  Image() -> code() );
     403
     404
     405
     406    if ((*i) -> Type () == AUX) {
     407      // printf ("aux is %d with code %d \n", (*i) -> Index (), (*i) -> Image () -> code() );
     408      // this is an auxiliary variable
     409
     410      Node vertex;
     411      vertex.node( (*i) -> Index () , 0.0 , (*i) -> lb () , (*i) -> ub () ,  (*i) -> Image () -> code() );
     412      node_info.push_back( vertex);
     413
     414      // add node in nauty graph for its index, (*i) -> Index ()
     415
     416      if ((*i) -> Image () -> Type () == N_ARY) {
     417
     418        if ((*i) -> Image () -> code () != COU_EXPRGROUP) {
     419
     420          for (int a=0; a < (*i) -> Image () -> nArgs(); a++) {
     421            expression *arg = (*i) -> Image () -> ArgList () [a];
     422
     423            if (arg -> Type () != CONST) {
     424              //printf (" add edge  %d , %d\n", (*i) -> Index (),  arg -> Index ());
     425              nauty_info->addElement((*i) -> Index (),  arg -> Index ());
     426              nauty_info->addElement( arg -> Index (), (*i) -> Index ());
     427            }
     428
     429            else{
     430
     431              assert (arg -> Type () == CONST);
     432
     433              //printf (" add new vertex to graph, coef # %d, value %g \n", coef_count, arg -> Value() );
     434              //printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (),  coef_count);
     435              nauty_info->addElement((*i) -> Index (),  coef_count);
     436              nauty_info->addElement( coef_count, (*i) -> Index ());
     437
     438
     439              Node coef_vertex;
     440              coef_vertex.node( coef_count, arg -> Value(), arg -> Value() , arg -> Value(), -2 );
     441              node_info.push_back(coef_vertex);
     442              coef_count ++;
     443            }
     444
     445          }
     446        }
     447
     448
     449        if ((*i) -> Image () -> code () == COU_EXPRGROUP) {
     450
     451          // dynamic_cast it to an exprGroup
     452          exprGroup *e = dynamic_cast <exprGroup *> ((*i) -> Image ());
     453
     454          // add a node for e -> getC0 ();
     455          if (e -> getc0 () != 0 ){
     456            Node coef_vertex;
     457            coef_vertex.node( coef_count, e -> getc0(), e -> getc0() , e -> getc0(), -2 );
     458            node_info.push_back(coef_vertex);
     459
     460            // printf ("Add coef vertex to graph (coef value   %f) \n", e -> getc0 () );
     461            //printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (), coef_count);
     462            nauty_info->addElement((*i) -> Index (),  coef_count);
     463            nauty_info->addElement( coef_count, (*i) -> Index ());
     464
     465
     466            coef_count ++;
     467          }
     468
     469          // for each term add nodes for their non-one coefficients and their variable
     470
     471          for (exprGroup::lincoeff::iterator el = e ->lcoeff().begin (); el != e -> lcoeff ().end (); ++el) {
     472
     473            if ( el -> second ==1){
     474              //printf (" add edge index %d ,  index %d\n", (*i) -> Index (), el -> first -> Index()    );
     475              nauty_info->addElement((*i) -> Index (),  el -> first -> Index());
     476              nauty_info->addElement( el -> first -> Index (), (*i) -> Index ());
     477            }
     478            else{
     479              //printf (" add new vertex to graph, coef # %d with coef %f \n", coef_count, el -> second);
     480              Node coef_vertex;
     481              coef_vertex.node( coef_count, el -> second, el -> second, el -> second, -2 );
     482              node_info.push_back(coef_vertex);
     483
     484              //printf (" add edge aux index %d ,  coef index %d\n", (*i) -> Index (), coef_count);
     485              nauty_info->addElement((*i) -> Index (),  coef_count);
     486              nauty_info->addElement( coef_count, (*i) -> Index ());
     487
     488              // printf (" add edge coef index %d ,  2nd index %d\n", coef_count,  el -> first -> Index()  );
     489              nauty_info->addElement(coef_count,  el -> first -> Index());
     490              nauty_info->addElement( el -> first -> Index (), coef_count);
     491              coef_count ++;
     492            }
     493            // coefficient = el -> second
     494
     495            // variable index is el -> first -> Index ()
     496          }
     497
     498        }
     499
     500      } else if ((*i) -> Image () -> Type () == UNARY) {
     501
     502      }
     503
     504    } else {
     505      //  printf ("variable is %d\n", (*i) -> Index ());
     506      Node var_vertex;
     507      var_vertex.node( (*i) -> Index () , 0 , (*i) -> lb () , (*i) -> ub () ,  -1 );
     508      //      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() );
     509      node_info.push_back(var_vertex);
     510      // this is an original variable
     511
     512    }
     513  }
     514
     515}
     516
     517
     518void CouenneProblem::Compute_Symmetry() const{
     519  //printf("Computing Symmetry\n");
     520  std::sort(node_info. begin (), node_info. end (), node_sort);
     521
     522  for (std::vector <Node>:: iterator i = node_info. begin ();
     523       i != node_info. end (); ++i)
     524    (*i).color_vertex(-1);
     525 
     526  int color = 1;
     527  for (std::vector <Node>:: iterator i = node_info. begin ();
     528       i != node_info. end (); ++i) {
     529    if( (*i).get_color() == -1){
     530      (*i).color_vertex(color);
     531      // printf ("Graph vertex %d is given color %d\n", (*i).get_index(), color);
     532      nauty_info -> color_node((*i).get_index(), color);
     533      for (std::vector <Node>:: iterator j = i+1; j <= node_info. end (); ++j)
     534        if( compare( (*i) , (*j) ) ==1){
     535          (*j).color_vertex(color);
     536          nauty_info -> color_node((*j).get_index(),color);
     537          //      printf ("Graph vertex %d is given color %d, the same as vertex %d\n", (*j).get_index(), color, (*i).get_index());
     538        }
     539      //       else
     540      // j = node_info. end();
     541      color++;
     542
     543    }
     544  }
     545
     546  nauty_info -> computeAuto();
     547}
     548 
     549void CouenneProblem::Print_Orbits(){
     550
     551  printf("num gens = %d, num orbits = %d \n", nauty_info -> getNumGenerators(), nauty_info -> getNumOrbits() );
     552
     553  std::vector<std::vector<int> > new_orbits = nauty_info->getOrbits();
     554
     555  printf("There were %d orbits and %d generators\n",
     556         nauty_info->getNumOrbits(),
     557         nauty_info->getNumGenerators());
     558
     559  for (unsigned int i = 0; i < new_orbits.size(); i++) {
     560    printf( "Orbit %d [", i);
     561    copy(new_orbits[i].begin(), new_orbits[i].end(),
     562         std::ostream_iterator<int>(std::cout, " "));
     563    printf("] \n");
     564  }
     565}
     566std::vector<int>  CouenneProblem::Find_Orbit(int index){
     567
     568  std::vector<int> orbit;
     569  int which_orbit = -1;
     570  std::vector<std::vector<int> > new_orbits = nauty_info->getOrbits();
     571
     572  for (unsigned int i = 0; i < new_orbits.size(); i++) {
     573    for (unsigned int j = 0; j < new_orbits[i].size(); j++) {
     574      //   for (std::vector <int>:: iterator j = new_orbits[i].begin(); new_orbits[i].end(); ++j){
     575      if( new_orbits[i][j] ==  index)
     576        which_orbit = i;
     577    }
     578  }
     579 
     580  //  for (std::vector <int>:: iterator j = new_orbits[which_orbit].begin(); new_orbits[which_orbit].end(), ++j)
     581  for (unsigned int j = 0; j < new_orbits[which_orbit].size(); j++)
     582    orbit.push_back(new_orbits[which_orbit][j]);
     583   
     584  return orbit;
     585}
     586
     587   
     588
     589
     590void CouenneProblem::ChangeBounds (const double * new_lb, const double * new_ub, int num_cols) const {
     591  assert (num_cols == Variables().size());
     592  std::sort(node_info. begin (), node_info. end (), index_sort);
     593
     594  for (int  i = 0; i < num_cols; i++) {
     595    //   printf("Var %d  lower bound: %f   upper bound %f \n", i, new_lb[i], new_ub[i]);
     596   
     597    assert (node_info[i].index == i);
     598    node_info[i ].bounds ( new_lb[i] , new_ub[i] );
     599    // printf("Var %d  INPUT lower bound: %f   upper bound %f \n", i, node_info[i].get_lb(), node_info[i].get_ub());
     600  }
     601 
     602
     603}
     604
     605
     606
    283607/// Get cutoff
    284608CouNumber CouenneProblem::getCutOff () const
    … …  
    289613CouNumber *CouenneProblem::getCutOffSol () const
    290614{return pcutoff_ -> getCutOffSol ();}
     615

  • trunk/Couenne/src/problem/CouenneProblem.hpp

    r407 r409  
    1818#include "CouenneTypes.hpp"
    1919#include "CouenneExpression.hpp"
     20//#include "CouenneOrbitObj.hpp"
     21#include "Nauty.h"
    2022#include "CouenneJournalist.hpp"
    2123#include "CouenneDomain.hpp"
    2224
     25/*
     26extern "C" {
     27#include <nauty.h>
     28}
     29*/
    2330using namespace Ipopt;
    2431
    … …  
    4451class OsiObject;
    4552class CoinWarmStart;
     53//class Nauty;
     54
     55
     56  class Node{
     57    int index;
     58    double coeff;
     59    double lb;
     60    double ub;
     61    int color;
     62    int code;
     63  public:
     64    void node(int, double, double, double, int);
     65    void color_vertex(int);
     66    int get_index () {return index;
     67    };
     68    double get_coeff () {return coeff;
     69    };
     70    double get_lb () {return lb;
     71    };
     72    double get_ub () {return ub ;
     73    };
     74    int get_color () {return color;
     75    };
     76    int get_code () {return code;
     77    };
     78    void bounds( double a, double b){ lb = a; ub = b;
     79    };
     80  };
     81 
     82
     83
     84  struct myclass0 {
     85    bool operator() (Node a, Node b) {
     86      bool is_less = 0;
     87     
     88      if(a.get_code() < b.get_code() )
     89        is_less = 1;
     90      else {
     91        if(a.get_code() == b.get_code() )
     92          if(a.get_coeff() < b.get_coeff() )
     93            is_less = 1;
     94          else{
     95            if(a.get_coeff() ==  b.get_coeff() )
     96              if(a.get_lb() < b.get_lb())
     97                is_less = 1;
     98              else{
     99                if(a.get_lb() == b.get_lb())
     100                  if(a.get_ub() < b.get_ub())
     101                    is_less = 1;
     102                  else{
     103                    if(a.get_index() < b.get_index())
     104                      is_less = 1;
     105                  }
     106              }
     107          }
     108      }
     109    return is_less;
     110    }
     111  } ;
     112   
     113     
     114  struct myclass {
     115    bool operator() (Node a, Node b) {
     116      return (a.get_index() < b.get_index() );
     117    }
     118  };
     119
     120
    46121
    47122namespace Couenne {
    … …  
    61136  struct compExpr;
    62137
     138
    63139// default tolerance for checking feasibility (and integrality) of NLP solutions
    64140const CouNumber feas_tolerance_default = 1e-5;
    … …  
    243319  void setNDefVars(int ndefined__) { ndefined_ = ndefined__; }
    244320
     321 
     322
     323
     324  // Symmetry Info
     325 
     326  std::vector<int>  Find_Orbit(int);
     327  mutable std::vector<Node> node_info;
     328  mutable Nauty *nauty_info;
     329
     330  myclass0  node_sort;
     331  myclass index_sort;
     332
     333  void sym_setup();
     334  void Compute_Symmetry() const;
     335  void Print_Orbits();
     336  void ChangeBounds (const double * , const double *, int ) const;
     337  bool compare (  Node a, Node b) const;
     338  // bool node_sort (  Node  a, Node  b);
     339  // bool index_sort (  Node  a, Node  b);
     340 
     341
     342 
     343 
    245344  /// get evaluation order index
    246345  inline int evalOrder (int i) const

  • trunk/Couenne/src/problem/reformulate.cpp

    r365 r409  
    2727/// preprocess problem in order to extract linear relaxations etc.
    2828void CouenneProblem::reformulate (CouenneCutGenerator *cg) {
    29 
     29 
    3030  double now = CoinCpuTime ();
    3131
    … …  
    148148  createUnusedOriginals ();
    149149
     150  sym_setup();
     151  Compute_Symmetry();
     152  Print_Orbits();
    150153  //writeAMPL ("extended-aw.mod", true);
    151154  //writeAMPL ("original.mod", false);

  • trunk/Couenne/src/standardize/Makefile.am

    r394 r409  
    4646        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression` \
    4747        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression/operators` \
    48         -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/problem/depGraph`
     48        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/branch` \
     49        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/problem/depGraph`
    4950endif
    5051

  • trunk/Couenne/src/standardize/Makefile.in

    r394 r409  
    4747@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression` \
    4848@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression/operators` \
    49 @COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/problem/depGraph`
     49@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/branch` \
     50@COIN_HAS_COUENNE_TRUE@         -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/problem/depGraph`
    5051
    5152@COIN_HAS_NTY_TRUE@am__append_2 = \

  • trunk/Couenne/src/two_implied_bt/Makefile.am

    r403 r409  
    4141  AM_CPPFLAGS += \
    4242        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/problem` \
    43         -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression` \
     43        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression`\
     44        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/branch`\
    4445        -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/bound_tightening`
    4546endif
     47
    4648
    4749if COIN_HAS_NTY

  • trunk/Couenne/src/two_implied_bt/Makefile.in

    r404 r409  
    4747@COIN_HAS_COUENNE_TRUE@am__append_1 = \
    4848@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/problem` \
    49 @COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression` \
     49@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/expression`\
     50@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/branch`\
    5051@COIN_HAS_COUENNE_TRUE@ -I`$(CYGPATH_W) $(COUENNESRCDIR)/src/bound_tightening`
    5152
Note: See TracChangeset for help on using the changeset viewer.