Changeset 539


Ignore:
Timestamp:
May 19, 2007 1:06:40 PM (12 years ago)
Author:
pbelotti
Message:

updating 3way branching

Location:
branches/Couenne/Couenne
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • branches/Couenne/Couenne/TODO

    r537 r539  
     1- Bilinear cuts
     2- trisection
     3- extended formulation
     4- variable lhs/rhs of bounds containing expression defining aux vars
     5- OBBT
     6
     7
    18- cut currValue_ from expressions
    29- documentation
  • branches/Couenne/Couenne/src/branch/CouenneBranchingObject.cpp

    r537 r539  
    134134  // TODO: apply bound tightening
    135135
    136   /*if (0) {
     136  if (0) {
    137137
    138     printf (" --> [%.6e,%.6e]\n", l, u);
     138    //    printf (" --> [%.6e,%.6e]\n", l, u);
    139139    printf ("### Branch: x%d %c= %.12f\n",
    140140            index_, way ? '>' : '<', value_);
    141 
    142     for (int i=0; i < solver -> getNumCols(); i++)
     141           
     142    /*for (int i=0; i < solver -> getNumCols(); i++)
    143143      printf (" %3d [%.3e,%.3e]\n", i, solver -> getColLower () [i],
    144144      solver -> getColUpper () [i]);
    145145      }*/
     146  }
    146147
    147148  branchIndex_++;
  • branches/Couenne/Couenne/src/branch/CouenneObject.cpp

    r537 r539  
    4747
    4848  //expression::Variable (reference_ -> Index ());
    49   /* if (0) {
     49 if (0) {
    5050
    5151    printf ("Inf: = |%.6e - %.6e| = %.6e  ",  ////[%.2f,%.2f]
     
    5656    reference_             -> print (std::cout); std::cout << " = ";
    5757    reference_ -> Image () -> print (std::cout); printf ("\n");
    58   }  */
     58  }
    5959
    6060  CouNumber delta = fabs (var - expr);
     
    198198  bool isint = reference_ -> isInteger ();
    199199
     200  if (0)
    200201  if (brVarInd_ >= 0)
    201202    switch (way) {
     
    214215    }
    215216
    216   /*if (0) {
     217  if (0) {
    217218    printf ("CO::createBranch: ");
    218219    reference_ -> print (std::cout);
     
    222223    reference_ -> Image () -> getFixVar () -> print (std::cout);
    223224    printf ("\n");
    224     }*/
     225    }
    225226
    226227  // constructor uses actual values of variables and bounds, update them
     
    287288        || (fabs (ur-xr) < COUENNE_EPS)
    288289        || (fabs (ur-lr) < COUENNE_EPS))
    289       return new CouenneBranchingObject (index, TWO_RAND, x, depvar -> isInteger ());
    290   }
    291 
    292   return new CouenneBranchingObject (ref_ind, TWO_RAND, xr, reference_ -> isInteger ());
     290      return new CouenneBranchingObject (index, TWO_LEFT, x, depvar -> isInteger ());
     291  }
     292
     293  return new CouenneBranchingObject (ref_ind, TWO_LEFT, xr, reference_ -> isInteger ());
    293294}
  • branches/Couenne/Couenne/src/convex/CouenneCutGenerator.cpp

    r521 r539  
    5555
    5656  now = CoinCpuTime ();
    57   //problem_ -> print (std::cout);
    58   //printf ("======================================\n");
     57  problem_ -> print (std::cout);
     58  printf ("======================================\n");
    5959  problem_ -> standardize ();
    6060
     
    6464  septime_ = now;
    6565
    66   //problem_ -> print (std::cout);
     66  problem_ -> print (std::cout);
    6767  //  printf ("======================================\n");
    6868  //  problem_ -> writeMod ("extended.mod");
  • branches/Couenne/Couenne/src/convex/boundTightening.cpp

    r537 r539  
    2323
    2424  int objInd = problem_ -> Obj (0) -> Body () -> Index ();
     25
     26  /////////////////////// MIP bound management /////////////////////////////////
     27
     28  if (objInd < 0) objInd = 0;
     29
     30  if (babInfo && (babInfo -> babPtr ())) {
     31
     32    CouNumber primal  = babInfo  -> babPtr () -> model (). getObjValue(),
     33              dual    = babInfo  -> babPtr () -> model (). getBestPossibleObjValue (),
     34              primal0 = problem_ -> Ub (objInd),
     35              dual0   = problem_ -> Lb (objInd);
     36
     37    // Bonmin assumes minimization. Hence, primal (dual) is an UPPER
     38    // (LOWER) bound.
     39
     40    if ((primal <   COUENNE_INFINITY - 1) && (primal < primal0)) { // update primal bound (MIP)
     41      problem_ -> Ub (objInd) = primal;
     42      chg_bds [objInd] = 1;
     43    }
     44
     45    if ((dual   > - COUENNE_INFINITY + 1) && (dual   > dual0)) { // update dual bound
     46      problem_ -> Lb (objInd) = dual;
     47      chg_bds [objInd] = 1;
     48    }
     49  }
    2550
    2651  //////////////////////// Reduced cost bound tightening //////////////////////
     
    5277        }
    5378      }
    54     }
    55   }
    56 
    57   /////////////////////// MIP bound management /////////////////////////////////
    58 
    59   if (objInd < 0) objInd = 0;
    60 
    61   if (babInfo && (babInfo -> babPtr ())) {
    62 
    63     CouNumber primal  = babInfo  -> babPtr () -> model (). getObjValue(),
    64               dual    = babInfo  -> babPtr () -> model (). getBestPossibleObjValue (),
    65               primal0 = problem_ -> Ub (objInd),
    66               dual0   = problem_ -> Lb (objInd);
    67 
    68     // Bonmin assumes minimization. Hence, primal (dual) is an UPPER
    69     // (LOWER) bound.
    70 
    71     if ((primal <   COUENNE_INFINITY - 1) && (primal < primal0)) { // update primal bound (MIP)
    72       problem_ -> Ub (objInd) = primal;
    73       chg_bds [objInd] = 1;
    74     }
    75 
    76     if ((dual   > - COUENNE_INFINITY + 1) && (dual   > dual0)) { // update dual bound
    77       problem_ -> Lb (objInd) = dual;
    78       chg_bds [objInd] = 1;
    7979    }
    8080  }
     
    121121      return false;
    122122    }
    123   } while (ntightened || nbwtightened && (niter++ < 10));
     123
     124#define MAX_BT_ITER 10
     125
     126  } while (ntightened || nbwtightened && (niter++ < MAX_BT_ITER));
    124127  // need to check if EITHER procedures gave results, as expression
    125128  // structure is not a tree any longer.
  • branches/Couenne/Couenne/src/convex/generateCuts.cpp

    r537 r539  
    2323 
    2424  /*printf (":::::::::::::::::::::::: level = %d, pass = %d, intree=%d\n Bounds:\n",
    25           info.level, info.pass, info.inTree);
     25    info.level, info.pass, info.inTree);*/
    2626
    2727  for (int i=0; i < si. getNumCols(); i++)
    2828      printf (" %3d [%.3e,%.3e]\n", i, si. getColLower () [i],
    29       si. getColUpper () [i]);*/
     29      si. getColUpper () [i]);
    3030
    3131  Bonmin::BabInfo * babInfo = dynamic_cast <Bonmin::BabInfo *> (si.getAuxiliaryInfo ());
     
    137137  //////////////////////// Bound tightening ///////////////////////////////////////////
    138138
    139   if (! boundTightening (si, cs, chg_bds, babInfo))
     139  //  for (int i=0; i<problem_ -> nAuxs () + problem_ -> nVars (); i++ )
     140  //    printf ("%d: [%.4f %.4f]\n", i, problem_ -> Lb (i), problem_ -> Ub (i));
     141
     142  if (! boundTightening (si, cs, chg_bds, babInfo)) {
     143
     144    printf ("INFEASIBLE\n");
     145    //    for (int i=0; i<problem_ -> nAuxs () + problem_ -> nVars (); i++ )
     146    //      printf ("%d: [%.4f %.4f]\n", i, problem_ -> Lb (i), problem_ -> Ub (i));
     147
    140148    goto end_genCuts;
     149  }
     150
     151  //  for (int i=0; i<problem_ -> nAuxs () + problem_ -> nVars (); i++ )
     152  //    printf ("%d: [%.4f %.4f]\n", i, problem_ -> Lb (i), problem_ -> Ub (i));
    141153
    142154  //////////////////////// GENERATE CONVEXIFICATION CUTS //////////////////////////////
  • branches/Couenne/Couenne/src/problem/impliedBounds.cpp

    r525 r539  
    2424  for (int i=nAuxs (); i--;) {
    2525
     26    //    for (int j=0; j<nAuxs () + nVars (); j++ )
     27    //      printf ("--- %d: [%.4f %.4f]\n", j, lb_ [j], ub_ [j]);
     28
    2629    if (lb_ [nvar+i] > ub_ [nvar+i] + COUENNE_EPS) {
    27       /*printf ("w_%d has infeasible bounds [%g,%g]\n",
    28         i+nvar, lb_ [nvar+i], ub_ [nvar+i]);*/
     30      //      printf ("w_%d has infeasible bounds [%g,%g]\n",
     31      //        i+nvar, lb_ [nvar+i], ub_ [nvar+i]);
    2932      return -1;
    3033    }
     
    3639              u0 = ub_ [nvar+i];
    3740
    38     if (auxiliaries_ [i] -> Image () -> impliedBound (nvar+i, lb_, ub_, chg_bds) > COUENNE_EPS) {
    39       /*printf ("implied: [%g,%g] -> [%g,%g] ", l0, u0, lb_ [nvar+i], ub_ [nvar+i]);
    40       auxiliaries_ [i] -> print (std::cout); printf (" := ");
    41       auxiliaries_ [i] -> Image () -> print (std::cout); printf ("\n");*/
     41   if (auxiliaries_ [i] -> Image () -> impliedBound (nvar+i, lb_, ub_, chg_bds) > COUENNE_EPS) {
     42    //      printf ("implied: [%g,%g] -> [%g,%g]", l0, u0, lb_ [nvar+i], ub_ [nvar+i]);
     43
     44
     45    //      auxiliaries_ [i] -> print (std::cout); printf (" := ");
     46    //      auxiliaries_ [i] -> Image () -> print (std::cout); printf ("\n");
    4247      nchg++;
    4348    }
  • branches/Couenne/Couenne/src/problem/tightenBounds.cpp

    r525 r539  
    3838       j < naux; j++) {
    3939
     40    //    for (int j=0; j<nAuxs () + nVars (); j++ )
     41    //      printf ("+++ %d: [%.4f %.4f]\n", j, lb_ [j], ub_ [j]);
     42
    4043    /*    printf ("w_%d [%g, %g] ", i+j,
    4144            expression::Lbound (i+j),
     
    5356
    5457    if (ll > uu + COUENNE_EPS) {
    55       /*printf ("w_%d has infeasible bounds [%g,%g]: ", i+j, ll, uu);
    56       Aux (j) -> Lb () -> print (std::cout); printf (" - ");
    57       Aux (j) -> Ub () -> print (std::cout); printf ("\n");*/
     58
     59      //      printf ("w_%d has infeasible bounds [%g,%g]: ", i+j, ll, uu);
     60      //      Aux (j) -> Lb () -> print (std::cout); printf (" - ");
     61      //      Aux (j) -> Ub () -> print (std::cout); printf ("\n");
    5862
    5963      return -1; // declare this node infeasible
     
    7175        i+j, ll, lb_ [i+j]);*/
    7276
    73       /*printf (" propaga: [%g,(%g)] -> [%g,(%g)] ", lb_ [i+j], ub_ [i+j], ll, uu);
    74       Aux (j)             -> print (std::cout); printf (" := ");
    75       Aux (j) -> Image () -> print (std::cout); printf ("\n");*/
     77      //      printf (" propaga: [%g,(%g)] -> [%g,(%g)] ", lb_ [i+j], ub_ [i+j], ll, uu);
     78      //      Aux (j)             -> print (std::cout); printf (" := ");
     79      //      Aux (j) -> Image () -> print (std::cout); printf ("\n");
    7680
    7781      lb_ [i+j] = ll;
     
    8791        i+j, uu, ub_ [i+j]);*/
    8892
    89       /*printf (" propaga: [(%g),%g] -> [(%g),%g] ", lb_ [i+j], ub_ [i+j], ll, uu);
    90       Aux (j)             -> print (std::cout); printf (" := ");
    91       Aux (j) -> Image () -> print (std::cout); printf ("\n");*/
     93      //      printf (" propaga: [(%g),%g] -> [(%g),%g] ", lb_ [i+j], ub_ [i+j], ll, uu);
     94      //      Aux (j)             -> print (std::cout); printf (" := ");
     95      //      Aux (j) -> Image () -> print (std::cout); printf ("\n");
    9296
    9397      ub_ [i+j] = uu;
Note: See TracChangeset for help on using the changeset viewer.