/home/coin/SVN-release/OS-2.4.2/Couenne/src/branch/BranchCore.cpp

Go to the documentation of this file.
00001 /* $Id: BranchCore.cpp 694 2011-06-18 20:13:17Z stefan $
00002  *
00003  * Name:    BranchCore.cpp
00004  * Authors: Jim Ostrowski
00005  * Purpose: Branching step with symmetry
00006  * Date:    October 13, 2010
00007  *
00008  * This file is licensed under the Eclipse Public License (EPL)
00009  */
00010 
00011 #include "CouenneObject.hpp"
00012 #include "CouenneBranchingObject.hpp"
00013 #include "CouenneProblem.hpp"
00014 
00015 extern int nOrbBr;
00016 
00017 using namespace Ipopt;
00018 using namespace Couenne;
00019 
00024 void CouenneBranchingObject::branchCore (OsiSolverInterface *solver, int indVar, int way, bool integer, double brpt,
00025                                          t_chg_bounds *&chg_bds) {
00026 
00031 
00032   if ((doFBBT_ && problem_ -> doFBBT ()) ||
00033       (doConvCuts_ && simulate_ && cutGen_))
00034     chg_bds = new t_chg_bounds [problem_ -> nVars ()];
00035 
00036 #ifdef COIN_HAS_NTY
00037 
00038   if (problem_ -> orbitalBranching ()) {
00039 
00040     std::vector< int > *branch_orbit = problem_ -> Find_Orbit (indVar);
00041 
00042     // if(branch_orbit -> size() >= 2){
00043     //   printf("branching on orbit of size %i \n", branch_orbit -> size());
00044     //   problem_ -> Print_Orbits();
00045     // }
00046 
00047     if (!way) {
00048 
00049       // DOWN BRANCH: xi <= brpt
00050 
00051       if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
00052 
00053         printf ("Branch: x%d <= %g [%g,%g]\n", 
00054                 indVar, 
00055                 integer ? floor (brpt) : brpt,
00056                 solver -> getColLower () [indVar], 
00057                 solver -> getColUpper () [indVar]);
00058 
00059         if (problem_ -> bestSol ()) {
00060 
00061           if ((solver  -> getColUpper () [indVar] > problem_ -> bestSol () [indVar]) &&
00062               (brpt                               < problem_ -> bestSol () [indVar]))
00063 
00064             printf ("Branching rule EXCLUDES optimal solution\n");
00065           else
00066             for (int i=0; i<problem_ -> nVars (); i++)
00067 
00068               if ((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
00069                   (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
00070 
00071                 {printf ("This node does not include optimal solution\n"); break;}
00072         }
00073       }
00074 
00075       // BRANCHING RULE -------------------------------------------------------------------------
00076 
00077       solver -> setColUpper (indVar, integer ? floor (brpt) : brpt); // down branch, x [indVar] <= brpt
00078       if (chg_bds) chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
00079 
00080     } else {
00081 
00082       // UP BRANCH: xi >= brpt for all i in symmetry group
00083 
00084       jnlst_ -> Printf (J_ERROR, J_BRANCHING, "Branch Symm (%d vars):", branch_orbit -> size ());
00085 
00086       if (branch_orbit -> size () > 1)
00087         nOrbBr ++;
00088 
00089       bool 
00090         brExclude   = false, 
00091         nodeExclude = false;
00092 
00093       for (std::vector<int>::iterator it = branch_orbit -> begin (); it != branch_orbit -> end (); ++it)  {
00094 
00095         assert (*it < problem_ -> nVars ());
00096 
00097         //if (*it >= problem_ -> nVars ()) 
00098         //continue;
00099 
00100         if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
00101           printf (" x%d>%g [%g,%g]", 
00102                   *it, 
00103                   integer ? ceil (brpt) : brpt,
00104                   solver -> getColLower () [*it], 
00105                   solver -> getColUpper () [*it]);
00106 
00107           if (problem_ -> bestSol () &&
00108               (solver  -> getColLower () [*it] < problem_ -> bestSol () [*it]) &&
00109               (brpt                            > problem_ -> bestSol () [*it]) && !brExclude)
00110 
00111             brExclude = true;
00112 
00113           if (problem_ -> bestSol ()) {
00114 
00115             for (int i=0; i<problem_ -> nVars (); i++)
00116 
00117               if (((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
00118                    (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))) {
00119 
00120                 nodeExclude = true;
00121                 break;
00122               }
00123           }
00124         }
00125 
00126         // BRANCHING RULE -------------------------------------------------------------------------
00127         if ((integer ? ceil  (brpt) : brpt) > solver -> getColLower () [*it]) {
00128 
00129           solver -> setColLower (*it, integer ? ceil  (brpt) : brpt); // up branch, x [indVar] >= brpt
00130           if (chg_bds) chg_bds [*it].setLower (t_chg_bounds::CHANGED);
00131         }
00132       }
00133 
00134       if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
00135         if (brExclude)   printf (" (Branching EXCLUDES optimal solution)");
00136         if (nodeExclude) printf (" (This node does not contain optimal solution)");
00137         printf ("\n");
00138       }
00139     }
00140 
00141     return;
00142   }
00143 
00144 #endif
00145 
00147 
00148   if (!way) {
00149 
00150     if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
00151       printf ("Branch: x%d <= %g [%g,%g]\n", 
00152               indVar, 
00153               integer ? floor (brpt) : brpt,
00154               solver -> getColLower () [indVar], 
00155               solver -> getColUpper () [indVar]);
00156 
00157       if (problem_ -> bestSol ()) {
00158 
00159         if ((solver  -> getColUpper () [indVar] > problem_ -> bestSol () [indVar]) &&
00160             (brpt                               < problem_ -> bestSol () [indVar]))
00161 
00162           printf ("Branching EXCLUDES optimal solution\n");
00163         else
00164           for (int i=0; i<problem_ -> nVars (); i++)
00165 
00166             if ((solver -> getColLower () [i] > problem_ -> bestSol () [i] + COUENNE_EPS) ||
00167                 (solver -> getColUpper () [i] < problem_ -> bestSol () [i] - COUENNE_EPS))
00168 
00169               {printf ("This node does not contain optimal solution\n"); break;}
00170       }
00171     }
00172 
00173     // BRANCHING RULE -------------------------------------------------------------------------
00174     solver -> setColUpper (indVar, integer ? floor (brpt) : brpt); // down branch, x [indVar] <= brpt
00175     if (chg_bds) chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
00176 
00177   } else {
00178 
00179     if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
00180 
00181       printf (" x%d >= %g [%g,%g]; ", 
00182               indVar, 
00183               integer ? ceil (brpt) : brpt,
00184               solver -> getColLower () [indVar], 
00185               solver -> getColUpper () [indVar]);
00186 
00187       if (problem_ -> bestSol ()) {
00188 
00189         if ((solver  -> getColLower () [indVar] < problem_ -> bestSol () [indVar]) &&
00190             (brpt                               > problem_ -> bestSol () [indVar]))
00191 
00192           printf ("Branching EXCLUDES optimal solution\n");
00193 
00194         else
00195           for (int i=0; i<problem_ -> nVars (); i++)
00196 
00197             if ((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
00198                 (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
00199 
00200               {printf ("This node does not contain optimal solution\n"); break;}
00201       }
00202     }
00203 
00204     // BRANCHING RULE -------------------------------------------------------------------------
00205     solver -> setColLower (indVar, integer ? ceil (brpt) : brpt); // up branch, x [indVar] >= brpt
00206     if (chg_bds) chg_bds [indVar].setLower (t_chg_bounds::CHANGED);
00207   }
00208 }

Generated on Wed Nov 30 03:03:57 2011 by  doxygen 1.4.7