source: trunk/Couenne/src/branch/BranchCore.cpp @ 541

Last change on this file since 541 was 541, checked in by pbelotti, 9 years ago

merged bugfixes from strong branching and variable priorities

  • Property svn:keywords set to Author Date Id Revision
File size: 6.2 KB
Line 
1/* $Id: BranchCore.cpp 541 2011-03-17 20:34:26Z pbelotti $
2 *
3 * Name:    BranchCore.cpp
4 * Authors: Jim Ostrowski
5 * Purpose: Branching step with symmetry
6 * Date:    October 13, 2010
7 *
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11#include "CouenneObject.hpp"
12#include "CouenneBranchingObject.hpp"
13#include "CouenneProblem.hpp"
14
15extern int nOrbBr;
16
17using namespace Couenne;
18
19/** \brief Execute the core of the branch --- need to separate code
20    because of include conflicts with other packages' config_*.h
21 */
22
23void CouenneBranchingObject::branchCore (OsiSolverInterface *solver, int indVar, int way, bool integer, double brpt,
24                                         t_chg_bounds *&chg_bds) {
25
26  /// only perform orbital branching if
27  ///
28  /// 1) Nauty has been made available through configure
29  /// 2) The orbital_branching option has been set to yes
30
31  if ((doFBBT_ && problem_ -> doFBBT ()) ||
32      (doConvCuts_ && simulate_ && cutGen_))
33    chg_bds = new t_chg_bounds [problem_ -> nVars ()];
34
35#ifdef COIN_HAS_NTY
36
37  if (problem_ -> orbitalBranching ()) {
38
39    std::vector< int > *branch_orbit = problem_ -> Find_Orbit (indVar);
40
41    // if(branch_orbit -> size() >= 2){
42    //   printf("branching on orbit of size %i \n", branch_orbit -> size());
43    //   problem_ -> Print_Orbits();
44    // }
45
46    if (!way) {
47
48      // DOWN BRANCH: xi <= brpt
49
50      if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
51
52        printf ("Branch: x%d <= %g [%g,%g]\n", 
53                indVar, 
54                integer ? floor (brpt) : brpt,
55                solver -> getColLower () [indVar], 
56                solver -> getColUpper () [indVar]);
57
58        if (problem_ -> bestSol ()) {
59
60          if ((solver  -> getColUpper () [indVar] > problem_ -> bestSol () [indVar]) &&
61              (brpt                               < problem_ -> bestSol () [indVar]))
62
63            printf ("Branching EXCLUDES optimal solution\n");
64          else
65            for (int i=0; i<problem_ -> nVars (); i++)
66
67              if ((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
68                  (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
69
70                {printf ("This node EXCLUDES optimal solution\n"); break;}
71        }
72      }
73
74      // BRANCHING RULE -------------------------------------------------------------------------
75
76      solver -> setColUpper (indVar, integer ? floor (brpt) : brpt); // down branch, x [indVar] <= brpt
77      if (chg_bds) chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
78
79    } else {
80
81      // UP BRANCH: xi >= brpt for all i in symmetry group
82
83      jnlst_ -> Printf (J_ERROR, J_BRANCHING, "Branch Symm (%d vars):", branch_orbit -> size ());
84
85      if (branch_orbit -> size () > 1)
86        nOrbBr ++;
87
88      bool 
89        brExclude   = false, 
90        nodeExclude = false;
91
92      for (std::vector<int>::iterator it = branch_orbit -> begin (); it != branch_orbit -> end (); ++it)  {
93
94        assert (*it < problem_ -> nVars ());
95
96        //if (*it >= problem_ -> nVars ())
97        //continue;
98
99        if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
100          printf (" x%d>%g [%g,%g]", 
101                  *it, 
102                  integer ? ceil (brpt) : brpt,
103                  solver -> getColLower () [*it], 
104                  solver -> getColUpper () [*it]);
105
106          if (problem_ -> bestSol () &&
107              (solver  -> getColLower () [*it] < problem_ -> bestSol () [*it]) &&
108              (brpt                            > problem_ -> bestSol () [*it]) && !brExclude)
109
110            brExclude = true;
111
112          if (problem_ -> bestSol ()) {
113
114            for (int i=0; i<problem_ -> nVars (); i++)
115
116              if (((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
117                   (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))) {
118
119                nodeExclude = true;
120                break;
121              }
122          }
123        }
124
125        // BRANCHING RULE -------------------------------------------------------------------------
126        if ((integer ? ceil  (brpt) : brpt) > solver -> getColLower () [*it]) {
127
128          solver -> setColLower (*it, integer ? ceil  (brpt) : brpt); // up branch, x [indVar] >= brpt
129          if (chg_bds) chg_bds [*it].setLower (t_chg_bounds::CHANGED);
130        }
131      }
132
133      if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
134        if (brExclude)   printf (" (Branching EXCLUDES optimal solution)");
135        if (nodeExclude) printf (" (This node EXCLUDES optimal solution)");
136        printf ("\n");
137      }
138    }
139
140    return;
141  }
142
143#endif
144
145  /// plain (non-orbital) branching
146
147  if (!way) {
148
149    if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
150      printf ("Branch: x%d <= %g [%g,%g]\n", 
151              indVar, 
152              integer ? floor (brpt) : brpt,
153              solver -> getColLower () [indVar], 
154              solver -> getColUpper () [indVar]);
155
156      if (problem_ -> bestSol ()) {
157
158        if ((solver  -> getColUpper () [indVar] > problem_ -> bestSol () [indVar]) &&
159            (brpt                               < problem_ -> bestSol () [indVar]))
160
161          printf ("Branching EXCLUDES optimal solution\n");
162        else
163          for (int i=0; i<problem_ -> nVars (); i++)
164
165            if ((solver -> getColLower () [i] > problem_ -> bestSol () [i] + COUENNE_EPS) ||
166                (solver -> getColUpper () [i] < problem_ -> bestSol () [i] - COUENNE_EPS))
167
168              {printf ("This node EXCLUDES optimal solution\n"); break;}
169      }
170    }
171
172    // BRANCHING RULE -------------------------------------------------------------------------
173    solver -> setColUpper (indVar, integer ? floor (brpt) : brpt); // down branch, x [indVar] <= brpt
174    if (chg_bds) chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
175
176  } else {
177
178    if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
179
180      printf (" x%d >= %g [%g,%g]; ", 
181              indVar, 
182              integer ? ceil (brpt) : brpt,
183              solver -> getColLower () [indVar], 
184              solver -> getColUpper () [indVar]);
185
186      if (problem_ -> bestSol ()) {
187
188        if ((solver  -> getColLower () [indVar] < problem_ -> bestSol () [indVar]) &&
189            (brpt                               > problem_ -> bestSol () [indVar]))
190
191          printf ("Branching EXCLUDES optimal solution\n");
192
193        else
194          for (int i=0; i<problem_ -> nVars (); i++)
195
196            if ((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
197                (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
198
199              {printf ("This node EXCLUDES optimal solution\n"); break;}
200      }
201    }
202
203    // BRANCHING RULE -------------------------------------------------------------------------
204    solver -> setColLower (indVar, integer ? ceil (brpt) : brpt); // up branch, x [indVar] >= brpt
205    if (chg_bds) chg_bds [indVar].setLower (t_chg_bounds::CHANGED);
206  }
207}
Note: See TracBrowser for help on using the repository browser.