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-2024 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 scipParaObjNodesel.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
36using namespace ParaSCIP;
37
38/** node selection method of node selector */
39SCIP_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 */
105SCIP_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
178int
179ScipParaObjNodesel::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}
UG::BbParaSolver::getParaParamSet
ParaParamSet * getParaParamSet()
get ParaParamSet object
Definition: bbParaSolver.h:1001
UG::BbParaSolver::isRacingStage
bool isRacingStage()
check if Solver is in racing stage or not
Definition: bbParaSolver.h:1363
UG::ParaParamSet::getBoolParamValue
bool getBoolParamValue(int param)
get bool parameter value
Definition: paraParamSet.cpp:174
UG::NoAllBoundChangesTransferInRacing
static const int NoAllBoundChangesTransferInRacing
Definition: bbParaParamSet.h:94
UG::AllBoundChangesTransfer
static const int AllBoundChangesTransfer
Definition: bbParaParamSet.h:93
DEFAULT_NUM_EPSILON
#define DEFAULT_NUM_EPSILON
Definition: paraDef.h:49
EPSLT
#define EPSLT(x, y, eps)
Definition: paraDef.h:167
MINEPSILON
#define MINEPSILON
Definition: paraDef.h:50
EPSGT
#define EPSGT(x, y, eps)
Definition: paraDef.h:169
SCIP_DECL_NODESELSELECT
SCIP_DECL_NODESELSELECT(ScipParaObjNodesel::scip_select)
Definition: scipParaObjNodesel.cpp:39
SCIP_DECL_NODESELCOMP
SCIP_DECL_NODESELCOMP(ScipParaObjNodesel::scip_comp)
Definition: scipParaObjNodesel.cpp:105