BranchCore.cpp
Go to the documentation of this file.
1 /* $Id: BranchCore.cpp 925 2012-11-27 19:11:04Z stefan $
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 
15 using namespace Ipopt;
16 using namespace Couenne;
17 
18 // FIXME: horrible global variables. Brrr.
19 int CouenneBranchingObject::nOrbBr = 0;
20 int CouenneBranchingObject::maxDepthOrbBranch = -1;
21 int CouenneBranchingObject::nSGcomputations = 0;
22 
23 #define OB_WEIGHT 0.6
24 
29 void CouenneBranchingObject::branchCore (OsiSolverInterface *solver, int indVar, int way, bool integer, double brpt,
30  t_chg_bounds *&chg_bds) {
35  // printf("branchCore \n");
36 
37  if ((doFBBT_ && problem_ -> doFBBT ()) ||
38  (doConvCuts_ && simulate_ && cutGen_))
39  chg_bds = new t_chg_bounds [problem_ -> nVars ()];
40 
41 #ifdef COIN_HAS_NTY
42 
43  if (problem_ -> orbitalBranching ()) {
44 
45  //problem_ -> Print_Orbits ();
46 
47  // if(branch_orbit -> size() >= 2){
48  // printf("branching on orbit of size %i \n", branch_orbit -> size());
49  // problem_ -> Print_Orbits();
50  // }
51 
52  if (!way) {
53 
54  // DOWN BRANCH: xi <= brpt
55 
56  std::vector< int > *branch_orbit = problem_ -> Find_Orbit (indVar);
57 
58  double
59  lb = solver -> getColLower () [indVar],
60  ub = solver -> getColUpper () [indVar],
61  ob_brpt = lb + (ub-lb) / (branch_orbit -> size () + 1),
62  OB_weight = OB_WEIGHT;
63 
64  brpt = OB_weight * ob_brpt + (1-OB_weight) * brpt;
65 
66  if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
67 
68  printf ("Branch: x%d <= %g [%g,%g]\n",
69  indVar,
70  integer ? floor (brpt) : brpt,
71  solver -> getColLower () [indVar],
72  solver -> getColUpper () [indVar]);
73 
74  if (problem_ -> bestSol ()) {
75 
76  if ((solver -> getColUpper () [indVar] > problem_ -> bestSol () [indVar]) &&
77  (brpt < problem_ -> bestSol () [indVar]))
78 
79  printf ("Branching rule EXCLUDES optimal solution\n");
80  else
81  for (int i=0; i<problem_ -> nVars (); i++)
82 
83  if ((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
84  (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
85 
86  {printf ("This node does not include optimal solution\n"); break;}
87  }
88  }
89 
90  // BRANCHING RULE -------------------------------------------------------------------------
91 
92  // change branching point to reflect unbalancedness of BB subtrees.
93 
94  solver -> setColUpper (indVar, integer ? floor (brpt) : brpt); // down branch, x [indVar] <= brpt
95 
96  if (!simulate_ && (problem_ -> orbitalBranching ())){
97 
98  //printf ("LEFT BRANCH: x10 in [%g,%g]\n", solver -> getColLower() [10], solver -> getColUpper() [10]);
99 
100  problem_ -> ChangeBounds (solver -> getColLower (),
101  solver -> getColUpper (),
102  problem_ -> nVars ());
103 
104  problem_ -> Compute_Symmetry ();
105  //problem_ -> Print_Orbits ();
106  }
107 
108  if (chg_bds) chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
109  /*
110  for (int jj = 0; jj < problem_ -> nVars (); jj++)
111  printf ("Branch: x%d [%g,%g]\n",
112  jj,
113  solver -> getColLower () [jj],
114  solver -> getColUpper () [jj]);
115  */
116  }
117  else {
118 
119  // UP BRANCH: xi >= brpt for all i in symmetry group
120 
121  if (!simulate_ && (problem_ -> orbitalBranching ())){
122 
123  problem_ -> ChangeBounds (solver -> getColLower (),
124  solver -> getColUpper (),
125  problem_ -> nVars ());
126 
127  problem_ -> Compute_Symmetry ();
128  //problem_ -> Print_Orbits ();
129  }
130 
131  std::vector< int > *branch_orbit = problem_ -> Find_Orbit (indVar);
132 
133  jnlst_ -> Printf (J_ERROR, J_BRANCHING, "Branch Symm (%d vars):", branch_orbit -> size ());
134 
135  if (!simulate_ && (branch_orbit -> size () > 1))
136  nOrbBr ++;
137 
138  bool
139  brExclude = false,
140  nodeExclude = false;
141 
142  double
143  lb = solver -> getColLower () [indVar],
144  ub = solver -> getColUpper () [indVar],
145  ob_brpt = lb + (ub-lb) / ((double) branch_orbit -> size () + 1),
146  OB_weight = OB_WEIGHT;
147 
148  // change branching point to reflect unbalancedness of BB subtrees.
149 
150  brpt = OB_weight * ob_brpt + (1-OB_weight) * brpt;
151 
152  for (std::vector<int>::iterator it = branch_orbit -> begin (); it != branch_orbit -> end (); ++it) {
153  assert (*it < problem_ -> nVars ());
154  //if (*it >= problem_ -> nVars ())
155  //continue;
156 
157  if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
158  printf (" x%d>%g [%g,%g]",
159  *it,
160  integer ? ceil (brpt) : brpt,
161  solver -> getColLower () [*it],
162  solver -> getColUpper () [*it]);
163 
164  if (problem_ -> bestSol () &&
165  (solver -> getColLower () [*it] < problem_ -> bestSol () [*it]) &&
166  (brpt > problem_ -> bestSol () [*it]) && !brExclude)
167 
168  brExclude = true;
169 
170  if (problem_ -> bestSol ()) {
171 
172  for (int i=0; i<problem_ -> nVars (); i++)
173 
174  if (((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
175  (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))) {
176 
177  nodeExclude = true;
178  break;
179  }
180  }
181  }
182 
183  // BRANCHING RULE -------------------------------------------------------------------------
184  if ((integer ? ceil (brpt) : brpt) > solver -> getColLower () [*it]) {
185 
186  solver -> setColLower (*it, integer ? ceil (brpt) : brpt); // up branch, x [indVar] >= brpt
187  if (chg_bds) chg_bds [*it].setLower (t_chg_bounds::CHANGED);
188  }
189  }
190 
191  if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
192  if (brExclude) printf (" (Branching EXCLUDES optimal solution)");
193  if (nodeExclude) printf (" (This node does not contain optimal solution)");
194  printf ("\n");
195  }
196 
197  delete branch_orbit;
198  }
199  /*
200  for (int jj = 0; jj < problem_ -> nVars (); jj++)
201  printf ("Branch: x%d [%g,%g]\n",
202  jj,
203  solver -> getColLower () [jj],
204  solver -> getColUpper () [jj]);*/
205 
206  return;
207  }
208 
209 #endif
210 
212 
213  if (!way) {
214 
215  if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
216 
217  printf ("Branch: x%d <= %g [%g,%g] (opt %g)\n",
218  indVar,
219  integer ? floor (brpt) : brpt,
220  solver -> getColLower () [indVar],
221  solver -> getColUpper () [indVar],
222  problem_ -> bestSol () ? problem_ -> bestSol () [indVar] : 0.);
223 
224  if (problem_ -> bestSol ()) {
225 
226  if ((solver -> getColUpper () [indVar] >= problem_ -> bestSol () [indVar]) &&
227  (brpt < problem_ -> bestSol () [indVar]))
228 
229  printf ("Branching EXCLUDES optimal solution\n");
230  else
231  for (int i=0; i<problem_ -> nVars (); i++)
232 
233  if ((solver -> getColLower () [i] > problem_ -> bestSol () [i] + COUENNE_EPS) ||
234  (solver -> getColUpper () [i] < problem_ -> bestSol () [i] - COUENNE_EPS))
235 
236  {printf ("This node does not contain optimal solution: x%d in [%g,%g] (%g)\n",
237  i, solver -> getColLower () [i], solver -> getColUpper () [i], problem_ -> bestSol () [i]); break;}
238  }
239  }
240 
241  // BRANCHING RULE -------------------------------------------------------------------------
242  solver -> setColUpper (indVar, integer ? floor (brpt + COUENNE_EPS) : brpt); // down branch, x [indVar] <= brpt
243  assert (solver -> getColUpper () [indVar] <= brpt + COUENNE_EPS);
244  if (chg_bds) chg_bds [indVar].setUpper (t_chg_bounds::CHANGED);
245 
246  } else {
247 
248  if (jnlst_ -> ProduceOutput (J_ERROR, J_BRANCHING)) {
249 
250  printf ("Branch: x%d >= %g [%g,%g] (opt %g)\n",
251  indVar,
252  integer ? ceil (brpt) : brpt,
253  solver -> getColLower () [indVar],
254  solver -> getColUpper () [indVar],
255  problem_ -> bestSol () ? problem_ -> bestSol () [indVar] : 0.);
256 
257  if (problem_ -> bestSol ()) {
258 
259  if ((solver -> getColLower () [indVar] <= problem_ -> bestSol () [indVar]) &&
260  (brpt > problem_ -> bestSol () [indVar]))
261 
262  printf ("Branching EXCLUDES optimal solution\n");
263 
264  else
265  for (int i=0; i<problem_ -> nVars (); i++)
266 
267  if ((solver -> getColLower () [indVar] > problem_ -> bestSol () [indVar] + COUENNE_EPS) ||
268  (solver -> getColUpper () [indVar] < problem_ -> bestSol () [indVar] - COUENNE_EPS))
269 
270  {printf ("This node does not contain optimal solution: x%d in [%g,%g] (%g)\n",
271  i, solver -> getColLower () [i], solver -> getColUpper () [i], problem_ -> bestSol () [i]); break;}
272  }
273  }
274 
275  // BRANCHING RULE -------------------------------------------------------------------------
276  solver -> setColLower (indVar, integer ? ceil (brpt - COUENNE_EPS) : brpt); // up branch, x [indVar] >= brpt
277  if (chg_bds) chg_bds [indVar].setLower (t_chg_bounds::CHANGED);
278  }
279 }
Couenne::t_chg_bounds
status of lower/upper bound of a variable, to be checked/modified in bound tightening ...
Definition: CouenneTypes.hpp:66
Couenne::t_chg_bounds::setLower
void setLower(ChangeStatus lower)
Definition: CouenneTypes.hpp:85
CouenneObject.hpp
Couenne::J_BRANCHING
const Ipopt::EJournalCategory J_BRANCHING(Ipopt::J_USER1)
Couenne::t_chg_bounds::setUpper
void setUpper(ChangeStatus upper)
Definition: CouenneTypes.hpp:86
end
fint end
Definition: BonFilterSolver.cpp:135
COUENNE_EPS
#define COUENNE_EPS
Definition: CouennePrecisions.hpp:19
CouenneProblem.hpp
OB_WEIGHT
#define OB_WEIGHT
Definition: BranchCore.cpp:23
CouenneBranchingObject.hpp
Generated by   doxygen 1.8.5