Scippy

UG

Ubiquity Generator framework

scipParaObjNodesel.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and software framework */
4 /* UG --- Ubquity Generator Framework */
5 /* */
6 /* Copyright Written by Yuji Shinano <shinano@zib.de>, */
7 /* Copyright (C) 2021 by Zuse Institute Berlin, */
8 /* licensed under LGPL version 3 or later. */
9 /* Commercial licenses are available through <licenses@zib.de> */
10 /* */
11 /* This code is free software; you can redistribute it and/or */
12 /* modify it under the terms of the GNU Lesser General Public License */
13 /* as published by the Free Software Foundation; either version 3 */
14 /* of the License, or (at your option) any later version. */
15 /* */
16 /* This program is distributed in the hope that it will be useful, */
17 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
18 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
19 /* GNU Lesser General Public License for more details. */
20 /* */
21 /* You should have received a copy of the GNU Lesser General Public License */
22 /* along with this program. If not, see <http://www.gnu.org/licenses/>. */
23 /* */
24 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
25 
26 /**@file objnodesel.cpp
27  * @brief C++ wrapper for node selectors
28  * @author Yuji Shinano
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #include <cassert>
34 #include "scipParaObjNodesel.h"
35 
36 using namespace ParaSCIP;
37 
38 /** node selection method of node selector */
39 SCIP_DECL_NODESELSELECT(ScipParaObjNodesel::scip_select)
40 { /*lint --e{715}*/
41  // SCIP_NODESELDATA* nodeseldata;
42 
43  assert(nodesel != NULL);
44  assert(strcmp(SCIPnodeselGetName(nodesel), "ScipParaObjNodesel") == 0);
45  assert(scip != NULL);
46  assert(selnode != NULL);
47 
48  *selnode = NULL;
49 
50  /* get node selector user data */
51  // nodeseldata = SCIPnodeselGetData(nodesel);
52  // assert(nodeseldata != NULL);
53 
54  SCIP_NODE* node;
55 
56  /* we want to plunge again: prefer children over siblings, and siblings over leaves,
57  * but only select a child or sibling, if its dual bound is small enough;
58  * prefer using nodes with higher node selection priority assigned by the branching rule
59  */
60  node = SCIPgetPrioChild(scip);
61  if( node != NULL )
62  {
63  *selnode = node;
64  SCIPdebugMessage(" -> selected prio child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
65  }
66  else
67  {
68  node = SCIPgetBestChild(scip);
69  if( node != NULL )
70  {
71  *selnode = node;
72  SCIPdebugMessage(" -> selected best child: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
73  }
74  else
75  {
76  node = SCIPgetPrioSibling(scip);
77  if( node != NULL )
78  {
79  *selnode = node;
80  SCIPdebugMessage(" -> selected prio sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
81  }
82  else
83  {
84  node = SCIPgetBestSibling(scip);
85  if( node != NULL )
86  {
87  *selnode = node;
88  SCIPdebugMessage(" -> selected best sibling: lower=%g\n", SCIPnodeGetLowerbound(*selnode));
89  }
90  else
91  {
92  *selnode = SCIPgetBestNode(scip);
93  SCIPdebugMessage(" -> selected best leaf: lower=%g\n",
94  *selnode != NULL ? SCIPnodeGetLowerbound(*selnode) : SCIPinfinity(scip));
95  }
96  }
97  }
98  }
99 
100  return SCIP_OKAY;
101 }
102 
103 
104 /** node comparison method of node selector */
105 SCIP_DECL_NODESELCOMP(ScipParaObjNodesel::scip_comp)
106 {
107 
108  SCIP_Real lowerbound1;
109  SCIP_Real lowerbound2;
110 
111  assert(nodesel != NULL);
112  assert(strcmp(SCIPnodeselGetName(nodesel), "ScipParaObjNodesel") == 0);
113  assert(scip != NULL);
114 
115  lowerbound1 = SCIPnodeGetLowerbound(node1);
116  lowerbound2 = SCIPnodeGetLowerbound(node2);
117  if( SCIPisLT(scip, lowerbound1, lowerbound2) )
118  return -1;
119  else if( SCIPisGT(scip, lowerbound1, lowerbound2) )
120  return +1;
121  else
122  {
123  int nBranchVars1 = getNBoundChanges(node1);
124  int nBranchVars2 = getNBoundChanges(node2);
125  if( nBranchVars1 < nBranchVars2 )
126  return -1;
127  else if( nBranchVars1 > nBranchVars2 )
128  return +1;
129  else
130  {
131  /** worse one might be better to transfer */
132  SCIP_Real estimate1;
133  SCIP_Real estimate2;
134 
135  estimate1 = SCIPnodeGetEstimate(node1);
136  estimate2 = SCIPnodeGetEstimate(node2);
137  if( (SCIPisInfinity(scip, estimate1) && SCIPisInfinity(scip, estimate2)) ||
138  (SCIPisInfinity(scip, -estimate1) && SCIPisInfinity(scip, -estimate2)) ||
139  SCIPisEQ(scip, estimate1, estimate2) )
140  {
141  SCIP_NODETYPE nodetype1;
142  SCIP_NODETYPE nodetype2;
143 
144  nodetype1 = SCIPnodeGetType(node1);
145  nodetype2 = SCIPnodeGetType(node2);
146  if( nodetype1 == SCIP_NODETYPE_CHILD && nodetype2 != SCIP_NODETYPE_CHILD )
147  return +1;
148  else if( nodetype1 != SCIP_NODETYPE_CHILD && nodetype2 == SCIP_NODETYPE_CHILD )
149  return -1;
150  else if( nodetype1 == SCIP_NODETYPE_SIBLING && nodetype2 != SCIP_NODETYPE_SIBLING )
151  return +1;
152  else if( nodetype1 != SCIP_NODETYPE_SIBLING && nodetype2 == SCIP_NODETYPE_SIBLING )
153  return -1;
154  else
155  {
156  int depth1;
157  int depth2;
158 
159  depth1 = SCIPnodeGetDepth(node1);
160  depth2 = SCIPnodeGetDepth(node2);
161  if( depth1 < depth2 )
162  return +1;
163  else if( depth1 > depth2 )
164  return -1;
165  else
166  return 0;
167  }
168  }
169  if( SCIPisLT(scip, estimate1, estimate2) )
170  return +1;
171 
172  assert(SCIPisGT(scip, estimate1, estimate2));
173  return -1;
174  }
175  }
176 }
177 
178 int
179 ScipParaObjNodesel::getNBoundChanges(
180  SCIP_NODE* node
181  )
182 {
183  SCIP *scip = scipParaSolver->getScip();
184  int depth = SCIPnodeGetDepth( node );
185  SCIP_VAR **branchVars = new SCIP_VAR*[depth];
186  SCIP_Real *branchBounds = new SCIP_Real[depth];
187  SCIP_BOUNDTYPE *boundTypes = new SCIP_BOUNDTYPE[depth];
188  int nBranchVars;
189  SCIPnodeGetAncestorBranchings( node, branchVars, branchBounds, boundTypes, &nBranchVars, depth );
190  if( nBranchVars > depth ) // did not have enough memory, then reallocate
191  {
192  delete [] branchVars;
193  delete [] branchBounds;
194  delete [] boundTypes;
195  branchVars = new SCIP_VAR*[nBranchVars];
196  branchBounds = new SCIP_Real[nBranchVars];
197  boundTypes = new SCIP_BOUNDTYPE[nBranchVars];
198  SCIPnodeGetAncestorBranchings( node, branchVars, branchBounds, boundTypes, &nBranchVars, nBranchVars );
199  }
200 
201  if( scipParaSolver->getParaParamSet()->getBoolParamValue(UG::AllBoundChangesTransfer) &&
202  !( scipParaSolver->getParaParamSet()->getBoolParamValue(UG::NoAllBoundChangesTransferInRacing) &&
203  scipParaSolver->isRacingStage() ) )
204  {
205  int nVars = SCIPgetNVars(scip);
206  SCIP_VAR **vars = SCIPgetVars(scip);
207  int *iBranchVars = new int[nBranchVars];
208  /* create the variable mapping hash map */
209  SCIP_HASHMAP* varmapLb;
210  SCIP_HASHMAP* varmapUb;
211  SCIP_CALL_ABORT( SCIPhashmapCreate(&varmapLb, SCIPblkmem(scip), nVars) );
212  SCIP_CALL_ABORT( SCIPhashmapCreate(&varmapUb, SCIPblkmem(scip), nVars) );
213  for( int i = 0; i < nBranchVars; i++ )
214  {
215  iBranchVars[i] = i;
216  if( boundTypes[i] == SCIP_BOUNDTYPE_LOWER )
217  {
218  if( !SCIPhashmapGetImage(varmapLb, branchVars[i]) )
219  {
220  SCIP_CALL_ABORT( SCIPhashmapInsert(varmapLb, branchVars[i], &iBranchVars[i] ) );
221  }
222  }
223  else
224  {
225  if( !SCIPhashmapGetImage(varmapUb, branchVars[i]) )
226  {
227  SCIP_CALL_ABORT( SCIPhashmapInsert(varmapUb, branchVars[i], &iBranchVars[i] ) );
228  }
229  }
230  }
231  SCIP_VAR **preBranchVars = branchVars;
232  SCIP_Real *preBranchBounds = branchBounds;
233  SCIP_BOUNDTYPE *preBboundTypes = boundTypes;
234  branchVars = new SCIP_VAR*[nBranchVars+nVars*2];
235  branchBounds = new SCIP_Real[nBranchVars+nVars*2];
236  boundTypes = new SCIP_BOUNDTYPE[nBranchVars+nVars*2];
237  for( int i = 0; i < nBranchVars; i++ )
238  {
239  branchVars[i] = preBranchVars[i];
240  branchBounds[i] = preBranchBounds[i];
241  boundTypes[i] = preBboundTypes[i];
242  }
243  int *iBranchVar = NULL;
244  for( int i = 0; i < nVars; i++ )
245  {
246  iBranchVar = (int *)SCIPhashmapGetImage(varmapLb, vars[i]);
247  if( iBranchVar )
248  {
249  // assert( EPSGE(preBranchBounds[*iBranchVar], SCIPvarGetLbLocal(vars[i]) ,DEFAULT_NUM_EPSILON ) );
250  if( EPSLT(preBranchBounds[*iBranchVar], SCIPvarGetLbLocal(vars[i]) ,DEFAULT_NUM_EPSILON ) )
251  {
252  branchBounds[*iBranchVar] = SCIPvarGetLbLocal(vars[i]); // node is current node
253  // if ( EPSGT(branchBounds[*iBranchVar], SCIPvarGetUbGlobal(vars[i]), DEFAULT_NUM_EPSILON) ) abort();
254  }
255  }
256  else
257  {
258  if( EPSGT( SCIPvarGetLbLocal(vars[i]), SCIPvarGetLbGlobal(vars[i]), MINEPSILON ) )
259  {
260  branchVars[nBranchVars] = vars[i];
261  branchBounds[nBranchVars] = SCIPvarGetLbLocal(vars[i]);
262  boundTypes[nBranchVars] = SCIP_BOUNDTYPE_LOWER;
263  // if ( EPSGT(branchBounds[nBranchVars], SCIPvarGetUbGlobal(vars[i]), DEFAULT_NUM_EPSILON) ) abort();
264  nBranchVars++;
265  }
266  }
267  iBranchVar = (int *)SCIPhashmapGetImage(varmapUb, vars[i]);
268  if( iBranchVar )
269  {
270  // assert( EPSLE(preBranchBounds[*iBranchVar], SCIPvarGetUbLocal(vars[i]) ,DEFAULT_NUM_EPSILON ) );
271  if( EPSGT(preBranchBounds[*iBranchVar], SCIPvarGetUbLocal(vars[i]) ,DEFAULT_NUM_EPSILON ) )
272  {
273  branchBounds[*iBranchVar] = SCIPvarGetUbLocal(vars[i]); // node is current node
274  if ( EPSLT(branchBounds[*iBranchVar], SCIPvarGetLbGlobal(vars[i]),DEFAULT_NUM_EPSILON) ) abort();
275  }
276  }
277  else
278  {
279  if( EPSLT( SCIPvarGetUbLocal(vars[i]), SCIPvarGetUbGlobal(vars[i]), MINEPSILON ) )
280  {
281  branchVars[nBranchVars] = vars[i];
282  branchBounds[nBranchVars] = SCIPvarGetUbLocal(vars[i]);
283  boundTypes[nBranchVars] = SCIP_BOUNDTYPE_UPPER;
284  if ( EPSLT(branchBounds[nBranchVars], SCIPvarGetLbGlobal(vars[i]),DEFAULT_NUM_EPSILON) ) abort();
285  nBranchVars++;
286  }
287  }
288  }
289  SCIPhashmapFree(&varmapLb);
290  SCIPhashmapFree(&varmapUb);
291  delete [] preBranchVars;
292  delete [] preBranchBounds;
293  delete [] preBboundTypes;
294  delete [] iBranchVars;
295  }
296 
297  /** check root node solvability */
298  delete [] branchVars;
299  delete [] branchBounds;
300  delete [] boundTypes;
301 
302  return nBranchVars;;
303 }
DEFAULT_NUM_EPSILON
#define DEFAULT_NUM_EPSILON
Definition: paraDef.h:49
UG::BbParaSolver::isRacingStage
bool isRacingStage()
check if Solver is in racing stage or not
Definition: bbParaSolver.h:1363
SCIP_DECL_NODESELCOMP
SCIP_DECL_NODESELCOMP(ScipParaObjNodesel::scip_comp)
Definition: scipParaObjNodesel.cpp:105
EPSLT
#define EPSLT(x, y, eps)
Definition: paraDef.h:167
UG::NoAllBoundChangesTransferInRacing
static const int NoAllBoundChangesTransferInRacing
Definition: bbParaParamSet.h:94
EPSGT
#define EPSGT(x, y, eps)
Definition: paraDef.h:169
SCIP_DECL_NODESELSELECT
SCIP_DECL_NODESELSELECT(ScipParaObjNodesel::scip_select)
Definition: scipParaObjNodesel.cpp:39
MINEPSILON
#define MINEPSILON
Definition: paraDef.h:50
UG::BbParaSolver::getParaParamSet
ParaParamSet * getParaParamSet()
get ParaParamSet object
Definition: bbParaSolver.h:1001
UG::AllBoundChangesTransfer
static const int AllBoundChangesTransfer
Definition: bbParaParamSet.h:93
ParaSCIP::ScipParaObjNodesel::getNBoundChanges
int getNBoundChanges(SCIP_NODE *node)
Definition: scipParaObjNodesel.cpp:179
UG::ParaParamSet::getBoolParamValue
bool getBoolParamValue(int param)
for bool parameters
Definition: paraParamSet.cpp:174