Scippy

UG

Ubiquity Generator framework

bbParaNodesMerger.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 bbParaNodesMerger.cpp
27 * @brief Nodes Merger.
28 * @author Yuji Shinano
29 *
30 *
31 *
32 */
33
34/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36#include "bbParaParamSet.h"
37#include "bbParaNodesMerger.h"
38#include "bbParaNode.h"
39#include "bbParaNodePool.h"
40#include "bbParaDiffSubproblem.h"
41
42using namespace UG;
43
44void
45BbParaNodesMerger::addNodeToMergeNodeStructs(
46 BbParaNode *node
47 )
48{
49 // Mergeing nodes look better to be restricted. It has to be tested
50 if( nBoundChangesOfBestNode < 0 )
51 {
52 nBoundChangesOfBestNode = dynamic_cast<BbParaDiffSubproblem *>(node->getDiffSubproblem())->getNBoundChanges();
53 }
54 if( nBoundChangesOfBestNode > 0 &&
55 node->getDiffSubproblem() && dynamic_cast<BbParaDiffSubproblem *>(node->getDiffSubproblem())->getNBoundChanges() <= nBoundChangesOfBestNode )
56 {
57 /*
58 if( logSolvingStatusFlag )
59 {
60 *osLogSolvingStatus << paraTimer->getElapsedTime()
61 << " The node " << node->toSimpleString() << " is out of merge candidates."
62 << std::endl;
63 }
64 */
65 return; // prohibit to generate the same merging node twice
66 }
67 /*
68 if( node->getMergingStatus() == 1 )
69 {
70 if( logSolvingStatusFlag )
71 {
72 *osLogSolvingStatus << paraTimer->getElapsedTime()
73 << " The node " << node->toSimpleString() << " is out of merge candidates."
74 << std::endl;
75 }
76 return; // prohibit to generate the same merging node twice
77 }
78 */
79
80 double startTime = paraTimer->getElapsedTime();
81 //
82 // create mergeNodeInfo and linked to paraNode
83 //
84 BbParaMergeNodeInfo *mNode = new BbParaMergeNodeInfo();
85 mNode->status = BbParaMergeNodeInfo::PARA_MERGING;
86 mNode->nSameValueVariables = -1;
87 mNode->nMergedNodes = -1;
88 mNode->keyIndex = -1;
89 mNode->nFixedVariables = 0;
90 mNode->fixedVariables = 0;
91 mNode->mergedTo = 0;
92 mNode->paraNode = node;
93 mNode->origDiffSubproblem = 0;
94 mNode->mergedDiffSubproblem = 0;
95 mNode->next = 0;
96 node->setMergingStatus(0); // checking
97 node->setMergeNodeInfo(mNode); // set merge node info.
98
99 //
100 // make the same value fixed variables links
101 //
102 /* get fixed variables array */
103 if( node->getDiffSubproblem() )
104 {
105 mNode->nFixedVariables = dynamic_cast<BbParaDiffSubproblem *>(node->getDiffSubproblem())->getFixedVariables(
106 instance,
107 &(mNode->fixedVariables));
108 }
109 else
110 {
111 mNode->nFixedVariables = 0;
112 }
113 if( mNode->nFixedVariables == 0 ) // cannot merge!
114 {
115 delete mNode;
116 dynamic_cast<BbParaNode *>(node)->setMergingStatus(3); // cannot be merged
117 dynamic_cast<BbParaNode *>(node)->setMergeNodeInfo(0);
118 addingNodeToMergeStructTime += paraTimer->getElapsedTime() - startTime;
119 return;
120 }
121
122 //
123 // add mergeNode to mergeNodeInfo list
124 //
125 if( mergeInfoTail == 0 )
126 {
127 mergeInfoTail = mNode;
128 mergeInfoHead = mNode;
129 }
130 else
131 {
132 mergeInfoTail->next = mNode;
133 mergeInfoTail = mNode;
134 }
135
136 for( int i = 0; i < mNode->nFixedVariables; i++ )
137 {
138 mNode->fixedVariables[i].mnode = mNode;
139 BbParaFixedValue *fixedValue = 0;
140 if( varIndexTable[mNode->fixedVariables[i].index] == 0 )
141 {
142 fixedValue = new BbParaFixedValue();
143 fixedValue->value = mNode->fixedVariables[i].value;
144 fixedValue->head = 0;
145 fixedValue->tail = 0;
146 fixedValue->next = 0;
147 varIndexTable[mNode->fixedVariables[i].index] = fixedValue;
148 }
149 else
150 {
151 BbParaFixedValue *prev = varIndexTable[mNode->fixedVariables[i].index];
152 for( fixedValue = varIndexTable[mNode->fixedVariables[i].index];
153 fixedValue != 0 && !EPSEQ( fixedValue->value, mNode->fixedVariables[i].value, DEFAULT_NUM_EPSILON );
154 fixedValue = fixedValue->next )
155 {
156 prev = fixedValue;
157 }
158 if( fixedValue == 0 )
159 {
160 fixedValue = new BbParaFixedValue();
161 fixedValue->value = mNode->fixedVariables[i].value;
162 fixedValue->head = 0;
163 fixedValue->tail = 0;
164 fixedValue->next = 0;
165 prev->next = fixedValue;
166 }
167 }
168 assert( fixedValue );
169 if( fixedValue->tail == 0 )
170 {
171 fixedValue->head = &(mNode->fixedVariables[i]);
172 fixedValue->tail = &(mNode->fixedVariables[i]);
173 }
174 else
175 {
176 fixedValue->tail->next = &(mNode->fixedVariables[i]);
177 fixedValue->tail->next->prev = fixedValue->tail;
178 fixedValue->tail = &(mNode->fixedVariables[i]);
179 }
180 for( BbParaFixedVariable *p = fixedValue->head; p != fixedValue->tail; p = p->next )
181 {
182 (p->nSameValue)++;
183 }
184 }
185
186 addingNodeToMergeStructTime += paraTimer->getElapsedTime() - startTime;
187
188}
189
190void
191BbParaNodesMerger::generateMergeNodesCandidates(
192 ParaComm *paraComm,
193 ParaInitiator *paraInitiator
194 )
195{
196 double startTime = paraTimer->getElapsedTime();
197
198 BbParaMergeNodeInfo *mPre = mergeInfoHead;
199 BbParaMergeNodeInfo *mNode = mergeInfoHead;
200 mNode = mergeInfoHead;
201 while( mNode )
202 {
203 assert( mNode->paraNode->getMergeNodeInfo() == mNode );
204 if( mNode->status == BbParaMergeNodeInfo::PARA_MERGING && mNode->nMergedNodes < 0 )
205 {
206 // make sorted variables list
207 std::multimap<int, BbParaSortedVariable, std::greater<int> > descendent;
208 for( int i = 0; i < mNode->nFixedVariables; i++ )
209 {
210 BbParaSortedVariable sortedVar;
211 sortedVar.idxInFixedVariabes = i;
212 sortedVar.fixedVariable = &(mNode->fixedVariables[i]);
213 descendent.insert(std::make_pair(mNode->fixedVariables[i].nSameValue, sortedVar));
214
215 }
216 //
217 // try to make merge candidates
218 //
219 std::multimap<int, BbParaSortedVariable, std::greater<int> >::iterator pos;
220 pos = descendent.begin();
221 mNode->keyIndex = pos->second.idxInFixedVariabes;
222 mNode->nSameValueVariables = 1;
223 BbParaFixedVariable *traverse = mNode->fixedVariables[mNode->keyIndex].next;
224 int nmNodes = 0;
225 for( ;
226 traverse;
227 traverse = traverse->next )
228 {
229 if( traverse->mnode->status == BbParaMergeNodeInfo::PARA_MERGING && traverse->mnode->nMergedNodes < 0 )
230 {
231 assert( traverse->mnode != mNode );
232 traverse->mnode->mergedTo = mNode;
233 traverse->mnode->nMergedNodes = 0;
234 traverse->mnode->nSameValueVariables = 1;
235 nmNodes++;
236 }
237 }
238 ++pos;
239 for( ; pos != descendent.end(); ++pos )
240 {
241 // check if there are merged nodes in case adding one more variable
242 for( traverse = mNode->fixedVariables[pos->second.idxInFixedVariabes].next;
243 traverse;
244 traverse = traverse->next )
245 {
246 if( traverse->mnode->nMergedNodes == 0 && traverse->mnode->mergedTo == mNode )
247 {
248 if( traverse->mnode->nSameValueVariables == mNode->nSameValueVariables )
249 {
250 break; // at least one node can be merged
251 }
252 }
253 }
254 if( traverse == 0 ) // cannot merge any nodes
255 {
256 break;
257 }
258
259 // merge nodes
260 mNode->nSameValueVariables++;
261 for( traverse = mNode->fixedVariables[pos->second.idxInFixedVariabes].next;
262 traverse;
263 traverse = traverse->next )
264 {
265 if( traverse->mnode->nMergedNodes == 0 && traverse->mnode->mergedTo == mNode )
266 {
267 if( traverse->mnode->nSameValueVariables == (mNode->nSameValueVariables - 1) )
268 {
269 traverse->mnode->nSameValueVariables++;
270 }
271 }
272 }
273 }
274
275 // if the number of fixed variables is too small, then the merged node is not created
276 if( nmNodes < 2 || // no merging nodes
277 static_cast<int>((mNode->nFixedVariables)*paraParamSet->getRealParamValue(FixedVariablesRatioInMerging)) < 1 || // 0 same value variables are not allowed
278 mNode->nSameValueVariables < (mNode->nFixedVariables)*paraParamSet->getRealParamValue(FixedVariablesRatioInMerging) ||
279 ( nBoundChangesOfBestNode > 0 && mNode->nSameValueVariables <= nBoundChangesOfBestNode )
280 )
281 {
282 for( BbParaFixedVariable *cleanup = mNode->fixedVariables[mNode->keyIndex].next;
283 cleanup;
284 cleanup = cleanup->next )
285 {
286 if( cleanup->mnode->mergedTo == mNode )
287 {
288 cleanup->mnode->nSameValueVariables = -1;
289 cleanup->mnode->nMergedNodes = -1;
290 cleanup->mnode->keyIndex = -1;
291 cleanup->mnode->mergedTo = 0;
292 assert( cleanup->mnode->status == BbParaMergeNodeInfo::PARA_MERGING );
293 }
294 }
295 assert( !(mNode->origDiffSubproblem) );
296 assert( !(mNode->mergedDiffSubproblem) );
297 mNode->paraNode->setMergeNodeInfo(0);
298 mNode->paraNode->setMergingStatus(3); // cannot merged
299 BbParaMergeNodeInfo *doomed = mNode;
300 if( mNode == mergeInfoHead )
301 {
302 mergeInfoHead = mNode->next;
303 mPre = mergeInfoHead;
304 mNode = mergeInfoHead;
305 }
306 else
307 {
308 mPre->next = mNode->next;
309 mNode = mNode->next;
310 }
311 if( mNode == mergeInfoTail )
312 {
313 mergeInfoTail = mPre;
314 }
315 deleteMergeNodeInfo(doomed);
316 }
317 else // cleanup and merge nodes
318 {
319 int nMergedNodes = 0;
320 for( BbParaFixedVariable *cleanup = mNode->fixedVariables[mNode->keyIndex].next;
321 cleanup;
322 cleanup = cleanup->next )
323 {
324 if( cleanup->mnode->mergedTo == mNode )
325 {
326 if( mNode->nSameValueVariables == cleanup->mnode->nSameValueVariables )
327 {
328 nMergedNodes++;
329 cleanup->mnode->status = BbParaMergeNodeInfo::PARA_MERGE_CHECKING_TO_OTHER_NODE;
330 }
331 else
332 {
333 assert( cleanup->mnode->status == BbParaMergeNodeInfo::PARA_MERGING );
334 cleanup->mnode->nSameValueVariables = -1;
335 cleanup->mnode->nMergedNodes = -1;
336 cleanup->mnode->keyIndex = -1;
337 cleanup->mnode->mergedTo = 0;
338 }
339 }
340 }
341 mNode->nMergedNodes = nMergedNodes;
342 assert(nMergedNodes > 0);
343 int n = 0;
344 BbParaFixedVariable *fixedVariables = new BbParaFixedVariable[mNode->nSameValueVariables];
345 for( pos = descendent.begin(); pos != descendent.end(); ++pos )
346 {
347 fixedVariables[n] = *(pos->second.fixedVariable);
348 n++;
349 if( n == mNode->nSameValueVariables ) break;
350 }
351 mNode->origDiffSubproblem = mNode->paraNode->getDiffSubproblem();
352 mNode->mergedDiffSubproblem = mNode->origDiffSubproblem->createDiffSubproblem(paraComm, paraInitiator, n, fixedVariables );
353 delete [] fixedVariables;
354 mNode->paraNode->setDiffSubproblem(mNode->mergedDiffSubproblem);
355 mNode->status = BbParaMergeNodeInfo::PARA_MERGED_RPRESENTATIVE;
356 assert( mNode->mergedTo == 0 );
357 mPre = mNode;
358 mNode = mNode->next;
359 }
360 }
361 else
362 {
363 mPre = mNode;
364 mNode = mNode->next;
365 }
366 }
367
368 // remove data which are not used anymore.
369 if( varIndexTable )
370 {
371 for( int i = 0; i < instance->getVarIndexRange(); i++ )
372 {
373 if( varIndexTable[i] )
374 {
375 while ( varIndexTable[i] )
376 {
377 BbParaFixedValue *del = varIndexTable[i];
378 varIndexTable[i] = varIndexTable[i]->next;
379 delete del;
380 }
381 }
382 }
383 delete [] varIndexTable;
384 varIndexTable = 0;
385 }
386
387 generateMergeNodesCandidatesTime += paraTimer->getElapsedTime() - startTime;
388}
389
390void
391BbParaNodesMerger::regenerateMergeNodesCandidates(
392 BbParaNode *node,
393 ParaComm *paraComm,
394 ParaInitiator *paraInitiator
395 )
396{
397 double startTime = paraTimer->getElapsedTime();
398
399 BbParaMergeNodeInfo *mNode = dynamic_cast<BbParaNode *>(node)->getMergeNodeInfo();
400 assert(mNode);
401 assert(mNode->paraNode == node);
402 assert(mNode->status == BbParaMergeNodeInfo::PARA_MERGED_RPRESENTATIVE);
403 assert(mNode->mergedTo == 0);
404 dynamic_cast<BbParaNode *>(node)->setMergeNodeInfo(0);
405 dynamic_cast<BbParaNode *>(node)->resetDualBoundValue();
406 node->setDiffSubproblem(mNode->origDiffSubproblem);
407 delete mNode->mergedDiffSubproblem;
408 mNode->mergedDiffSubproblem = 0;
409 assert( mNode->status != BbParaMergeNodeInfo::PARA_MERGING );
410 // set new range
411 mergeInfoHead = 0;
412 mergeInfoTail = 0;
413 BbParaMergeNodeInfo *mPrev = 0;
414 for( BbParaFixedVariable *traverse = mNode->fixedVariables[mNode->keyIndex].next;
415 traverse;
416 traverse = traverse->next )
417 {
418 if( mergeInfoTail )
419 {
420 mPrev->next = traverse->mnode;
421 mergeInfoTail = traverse->mnode;
422 mPrev = traverse->mnode;
423 }
424 if( mNode == traverse->mnode->mergedTo )
425 {
426 if( !mergeInfoHead )
427 {
428 mergeInfoHead = traverse->mnode;
429 mergeInfoTail = traverse->mnode;
430 mPrev = traverse->mnode;
431 }
432 assert( traverse->mnode->status == BbParaMergeNodeInfo::PARA_MERGE_CHECKING_TO_OTHER_NODE );
433 }
434 }
435 if( mergeInfoHead )
436 {
437 assert(mergeInfoTail);
438 mergeInfoTail->next = 0;
439 }
440
441 // remove mnode
442 mNode->paraNode->setMergingStatus(-1); // no merging node
443 deleteMergeNodeInfo(mNode);
444 if( mergeInfoHead )
445 {
446 generateMergeNodesCandidates(paraComm, paraInitiator);
447 }
448
449 regenerateMergeNodesCandidatesTime += paraTimer->getElapsedTime() - startTime;
450}
451
452void
453BbParaNodesMerger::deleteMergeNodeInfo(
454 BbParaMergeNodeInfo *mNode
455 )
456{
457
458 if( mNode->nMergedNodes == 0 && mNode->mergedTo )
459 {
460 assert(mNode->status == BbParaMergeNodeInfo::PARA_MERGE_CHECKING_TO_OTHER_NODE);
461 assert(mNode->mergedTo->status == BbParaMergeNodeInfo::PARA_MERGED_RPRESENTATIVE);
462 assert(mNode->mergedTo->mergedTo == 0);
463 mNode->mergedTo->nMergedNodes--;
464 if( mNode->mergedTo->nMergedNodes == 0 && mNode->mergedTo->paraNode->getMergeNodeInfo() )
465 {
466 assert(mNode->mergedTo == mNode->mergedTo->paraNode->getMergeNodeInfo() );
467 mNode->mergedTo->paraNode->setDiffSubproblem(mNode->mergedTo->origDiffSubproblem);
468 mNode->mergedTo->paraNode->setMergeNodeInfo(0);
469 mNode->mergedTo->paraNode->setMergingStatus(-1);
470 delete mNode->mergedTo->mergedDiffSubproblem;
471 mNode->mergedTo->mergedDiffSubproblem = 0;
472 mNode->mergedTo->origDiffSubproblem = 0;
473 deleteMergeNodeInfo(mNode->mergedTo);
474 }
475 mNode->mergedTo = 0;
476
477 }
478
479 if( mNode->status == BbParaMergeNodeInfo::PARA_MERGED_RPRESENTATIVE)
480 {
481 assert( mNode->mergedTo == 0 );
482 if( mNode->paraNode->getMergingStatus() == -1 ) // merging failed
483 {
484 for( BbParaFixedVariable *traverse = mNode->fixedVariables[mNode->keyIndex].next;
485 traverse;
486 traverse = traverse->next )
487 {
488 if( traverse->mnode->nMergedNodes == 0 && mNode == traverse->mnode->mergedTo )
489 {
490 traverse->mnode->mergedTo->nMergedNodes--;
491 if( traverse->mnode->mergedTo->nMergedNodes == 0 && traverse->mnode->mergedTo->paraNode->getMergeNodeInfo() )
492 {
493 // NOTE; mNode == traverse->mnode->mergedTo:
494 traverse->mnode->mergedTo->paraNode->setDiffSubproblem(traverse->mnode->mergedTo->origDiffSubproblem);
495 traverse->mnode->mergedTo->paraNode->setMergeNodeInfo(0);
496 traverse->mnode->mergedTo->paraNode->setMergingStatus(-1);
497 delete traverse->mnode->mergedTo->mergedDiffSubproblem;
498 traverse->mnode->mergedTo->mergedDiffSubproblem = 0;
499 traverse->mnode->mergedTo->origDiffSubproblem = 0;
500 assert( traverse->mnode->mergedTo->mergedTo == 0);
501 deleteMergeNodeInfo(traverse->mnode->mergedTo);
502 }
503 traverse->mnode->mergedTo = 0;
504 traverse->mnode->paraNode->setMergingStatus(0);
505 traverse->mnode->status = BbParaMergeNodeInfo::PARA_MERGING;
506 traverse->mnode->nMergedNodes = -1;
507 traverse->mnode->nSameValueVariables = -1;
508 traverse->mnode->keyIndex = -1;
509 }
510 }
511 }
512 else
513 {
514 for( BbParaFixedVariable *traverse = mNode->fixedVariables[mNode->keyIndex].next;
515 traverse;
516 traverse = traverse->next )
517 {
518 if( traverse->mnode->nMergedNodes == 0 && mNode == traverse->mnode->mergedTo )
519 {
520 traverse->mnode->mergedTo->nMergedNodes--;
521 if( traverse->mnode->mergedTo->nMergedNodes == 0 && traverse->mnode->mergedTo->paraNode->getMergeNodeInfo() )
522 {
523 // NOTE; mNode == traverse->mnode->mergedTo:
524 traverse->mnode->mergedTo->paraNode->setDiffSubproblem(traverse->mnode->mergedTo->origDiffSubproblem);
525 traverse->mnode->mergedTo->paraNode->setMergeNodeInfo(0);
526 traverse->mnode->mergedTo->paraNode->setMergingStatus(-1);
527 delete traverse->mnode->mergedDiffSubproblem;
528 traverse->mnode->mergedTo->mergedDiffSubproblem = 0;
529 traverse->mnode->mergedTo->origDiffSubproblem = 0;
530 assert( traverse->mnode->mergedTo->mergedTo == 0);
531 deleteMergeNodeInfo(traverse->mnode->mergedTo);
532 }
533 traverse->mnode->mergedTo = 0;
534 if( traverse->mnode->paraNode->getDualBoundValue() < mNode->paraNode->getDualBoundValue() )
535 {
536 traverse->mnode->paraNode->setMergingStatus(0);
537 traverse->mnode->status = BbParaMergeNodeInfo::PARA_MERGING;
538 traverse->mnode->nMergedNodes = -1;
539 traverse->mnode->nSameValueVariables = -1;
540 traverse->mnode->keyIndex = -1;
541 }
542 else
543 {
544 traverse->mnode->paraNode->setMergingStatus(4); // merging representative was deleted -> this node should be deleted
545 traverse->mnode->status = BbParaMergeNodeInfo::PARA_DELETED;
546 traverse->mnode->nMergedNodes = -1;
547 traverse->mnode->nSameValueVariables = -1;
548 traverse->mnode->keyIndex = -1;
549 }
550 }
551 }
552 }
553 }
554
555 if( mNode->fixedVariables )
556 {
557 for( int i = 0; i < mNode->nFixedVariables; i++ )
558 {
559 for( BbParaFixedVariable *traverse = mNode->fixedVariables[i].prev;
560 traverse;
561 traverse = traverse->prev
562 )
563 {
564 traverse->nSameValue--;
565 }
566 if( mNode->fixedVariables[i].prev )
567 {
568 mNode->fixedVariables[i].prev->next = mNode->fixedVariables[i].next;
569 if( mNode->fixedVariables[i].next )
570 {
571 mNode->fixedVariables[i].next->prev = mNode->fixedVariables[i].prev;
572 }
573 else
574 {
575 mNode->fixedVariables[i].prev->next = 0;
576 }
577 }
578 else // prev == 0
579 {
580 if( mNode->fixedVariables[i].next )
581 {
582 mNode->fixedVariables[i].next->prev = 0;
583 }
584 }
585
586 }
587 delete [] mNode->fixedVariables;
588 }
589 delete mNode;
590}
591
592int
593BbParaNodesMerger::mergeNodes(
594 BbParaNode *node,
595 BbParaNodePool *paraNodePool
596 )
597{
598 double startTime = paraTimer->getElapsedTime();
599
600 BbParaMergeNodeInfo *mNode = dynamic_cast<BbParaNode *>(node)->getMergeNodeInfo();
601 assert( mNode->status == BbParaMergeNodeInfo::PARA_MERGED_RPRESENTATIVE );
602 assert( mNode->mergedTo == 0 );
603 BbParaMergedNodeListElement *head = 0;
604 BbParaMergedNodeListElement *cur = 0;
605 int nMerged = 0;
606 for( BbParaFixedVariable *traverse = mNode->fixedVariables[mNode->keyIndex].next;
607 traverse;
608 traverse = traverse->next )
609 {
610 if( traverse->mnode->nMergedNodes == 0 && mNode == traverse->mnode->mergedTo )
611 {
612 if( head == 0 )
613 {
614 head = cur = new BbParaMergedNodeListElement();
615 }
616 else
617 {
618 cur->next = new BbParaMergedNodeListElement();
619 cur = cur->next;
620 }
621 cur->node = traverse->mnode->paraNode;
622 dynamic_cast<BbParaNode *>(cur->node)->setMergingStatus(2);
623 cur->next = 0;
624 nMerged++;
625#ifdef UG_DEBUG_SOLUTION
626 if( cur->node->getDiffSubproblem() && cur->node->getDiffSubproblem()->isOptimalSolIncluded() )
627 {
628 assert(node->getDiffSubproblem());
629 node->getDiffSubproblem()->setOptimalSolIndicator(1);
630 }
631#endif
632 }
633 }
634 assert( mNode->nMergedNodes == nMerged);
635 int delNodes = 0;
636 if ( head )
637 {
638 delNodes = paraNodePool->removeMergedNodes(head);
639 }
640 assert( delNodes == nMerged );
641 if( delNodes != nMerged )
642 {
643 THROW_LOGICAL_ERROR4("delNodes != nMerged, delNodes = ", delNodes, ", nMerged = ", nMerged );
644 }
645 node->setDiffSubproblem(mNode->mergedDiffSubproblem);
646 delete mNode->origDiffSubproblem;
647 dynamic_cast<BbParaNode *>(node)->setMergeNodeInfo(0);
648 dynamic_cast<BbParaNode *>(node)->setMergingStatus(1);
649 assert(mNode->mergedTo == 0);
650 mNode->mergedDiffSubproblem = 0;
651 mNode->origDiffSubproblem = 0;
652 deleteMergeNodeInfo(mNode);
653// lcts.nDeletedByMerging += nMerged;
654// if( logSolvingStatusFlag )
655// {
656// *osLogSolvingStatus << (nMerged + 1) <<
657// " nodes are merged at " <<
658// paraTimer->getElapsedTime() << " seconds."
659// << "Dual bound: " << dynamic_cast<BbParaInitiator *>(paraInitiator)->convertToExternalValue(
660// dynamic_cast<BbParaNode *>(node)->getDualBoundValue() )
661// << std::endl;
662// }
663
664 mergeNodeTime += paraTimer->getElapsedTime() - startTime;
665
666 return nMerged;
667
668}
bbParaDiffSubproblem.h
Base class for a container which has difference between instance and subproblem.
bbParaNodePool.h
BbParaNode Pool.
bbParaNode.h
Base class for BbParaNode.
bbParaNodesMerger.h
Structs used for merging nodes.
bbParaParamSet.h
Parameter set for UG framework.
UG::BbParaDiffSubproblem
Class for the difference between instance and subproblem.
Definition: bbParaDiffSubproblem.h:68
UG::BbParaDiffSubproblem::createDiffSubproblem
virtual BbParaDiffSubproblem * createDiffSubproblem(ParaComm *comm, ParaInitiator *initiator, int n, BbParaFixedVariable *fixedVars)=0
create new BbParaDiffSubproblem object using fixed variables information
UG::BbParaInstance::getVarIndexRange
virtual int getVarIndexRange()=0
get variable index range TODO: this function should be in inherited class
UG::BbParaNodePool
class BbParaNodePool
Definition: bbParaNodePool.h:109
UG::BbParaNodePool::removeMergedNodes
virtual int removeMergedNodes(BbParaMergedNodeListElement *head)=0
remove merged BbParaNodes from this pool
UG::BbParaNode
class BbParaNode
Definition: bbParaNode.h:62
UG::BbParaNode::getMergingStatus
int getMergingStatus()
get merging status
Definition: bbParaNode.h:678
UG::BbParaNode::getMergeNodeInfo
BbParaMergeNodeInfo * getMergeNodeInfo()
get merge node information struct
Definition: bbParaNode.h:658
UG::BbParaNode::setDiffSubproblem
void setDiffSubproblem(BbParaDiffSubproblem *inDiffSubproblem)
setter of diffSubproblem *‍/
Definition: bbParaNode.h:362
UG::BbParaNode::getDiffSubproblem
BbParaDiffSubproblem * getDiffSubproblem()
getter of diffSubproblem
Definition: bbParaNode.h:353
UG::BbParaNode::setMergeNodeInfo
void setMergeNodeInfo(BbParaMergeNodeInfo *mNode)
set merge node information to this BbParaNode object
Definition: bbParaNode.h:646
UG::BbParaNode::setMergingStatus
void setMergingStatus(int status)
set merging status
Definition: bbParaNode.h:667
UG::BbParaNode::getDualBoundValue
double getDualBoundValue()
getter of dual bound value
Definition: bbParaNode.h:303
UG::BbParaNodesMerger::mergeNodeTime
double mergeNodeTime
accumulate time to make a merged node
Definition: bbParaNodesMerger.h:139
UG::BbParaNodesMerger::generateMergeNodesCandidatesTime
double generateMergeNodesCandidatesTime
accumulate time to generate merge nodes candidates
Definition: bbParaNodesMerger.h:137
UG::BbParaNodesMerger::mergeInfoHead
BbParaMergeNodeInfo * mergeInfoHead
head of BbParaMergeNodeInfo list
Definition: bbParaNodesMerger.h:133
UG::BbParaNodesMerger::nBoundChangesOfBestNode
int nBoundChangesOfBestNode
bound changes of the best node
Definition: bbParaNodesMerger.h:128
UG::BbParaNodesMerger::deleteMergeNodeInfo
void deleteMergeNodeInfo(BbParaMergeNodeInfo *mNode)
delete merge node info
Definition: bbParaNodesMerger.cpp:453
UG::BbParaNodesMerger::mergeNodes
int mergeNodes(BbParaNode *node, BbParaNodePool *paraNodePool)
make a merge node
Definition: bbParaNodesMerger.cpp:593
UG::BbParaNodesMerger::paraParamSet
ParaParamSet * paraParamSet
pointer to ParaParamSet object
Definition: bbParaNodesMerger.h:131
UG::BbParaNodesMerger::mergeInfoTail
BbParaMergeNodeInfo * mergeInfoTail
tail of BbParaMergeNodeInfo list times
Definition: bbParaNodesMerger.h:134
UG::BbParaNodesMerger::varIndexTable
BbParaFixedValue ** varIndexTable
variable indices table.
Definition: bbParaNodesMerger.h:132
UG::BbParaNodesMerger::regenerateMergeNodesCandidatesTime
double regenerateMergeNodesCandidatesTime
accumulate time to regenerate merge nodes candidates
Definition: bbParaNodesMerger.h:138
UG::BbParaNodesMerger::generateMergeNodesCandidates
void generateMergeNodesCandidates(ParaComm *paraComm, ParaInitiator *paraInitiator)
generate merge nodes candidates
Definition: bbParaNodesMerger.cpp:191
UG::BbParaNodesMerger::instance
BbParaInstance * instance
pointer to ParaInstance object
Definition: bbParaNodesMerger.h:130
UG::BbParaNodesMerger::paraTimer
ParaTimer * paraTimer
normal timer used
Definition: bbParaNodesMerger.h:129
UG::BbParaNodesMerger::addingNodeToMergeStructTime
double addingNodeToMergeStructTime
accumulate time to add Node to merge struct
Definition: bbParaNodesMerger.h:136
UG::BbParaNodesMerger::regenerateMergeNodesCandidates
void regenerateMergeNodesCandidates(BbParaNode *node, ParaComm *paraComm, ParaInitiator *paraInitiator)
regenerate merge nodes candidates
Definition: bbParaNodesMerger.cpp:391
UG::ParaComm
Base class of communicator object.
Definition: paraComm.h:102
UG::ParaInitiator
Class for initiator.
Definition: paraInitiator.h:63
UG::ParaParamSet::getRealParamValue
double getRealParamValue(int param)
get real parameter value
Definition: paraParamSet.cpp:336
UG::ParaTimer::getElapsedTime
virtual double getElapsedTime()=0
get elapsed time
paraInitiator
static ScipParaInitiator * paraInitiator
Definition: fscip.cpp:76
UG::BbParaFixedValue
struct BbParaFixedValue_ BbParaFixedValue
Definition: bbParaNodesMerger.h:53
UG::BbParaMergedNodeListElement
struct BbParaMergedNodeListElement_ BbParaMergedNodeListElement
Definition: bbParaNodesMerger.h:58
UG::BbParaMergeNodeInfo
struct BbParaMergeNodeInfo_ BbParaMergeNodeInfo
Definition: bbParaNodesMerger.h:54
UG::FixedVariablesRatioInMerging
static const int FixedVariablesRatioInMerging
Definition: bbParaParamSet.h:186
DEFAULT_NUM_EPSILON
#define DEFAULT_NUM_EPSILON
Definition: paraDef.h:49
THROW_LOGICAL_ERROR4
#define THROW_LOGICAL_ERROR4(msg1, msg2, msg3, msg4)
Definition: paraDef.h:103
EPSEQ
#define EPSEQ(x, y, eps)
Definition: paraDef.h:166
UG::BbParaFixedValue_
Fixed value struct.
Definition: bbParaNodesMerger.h:63
UG::BbParaFixedValue_::next
BbParaFixedValue * next
point next ParaFixedValue struct
Definition: bbParaNodesMerger.h:67
UG::BbParaFixedValue_::head
BbParaFixedVariable * head
point the head of the ParaFixedVariable
Definition: bbParaNodesMerger.h:65
UG::BbParaFixedValue_::tail
BbParaFixedVariable * tail
point the tail of the ParaFixedVarialbe
Definition: bbParaNodesMerger.h:66
UG::BbParaFixedValue_::value
double value
value for a fixed variable
Definition: bbParaNodesMerger.h:64
UG::BbParaFixedVariable_
Fixed variable struct.
Definition: bbParaNodesMerger.h:101
UG::BbParaFixedVariable_::mnode
BbParaMergeNodeInfo * mnode
pointer to merge node info struct to which this info is belonging
Definition: bbParaNodesMerger.h:105
UG::BbParaFixedVariable_::prev
BbParaFixedVariable * prev
pointer to the previous node which has the same fixed value
Definition: bbParaNodesMerger.h:107
UG::BbParaFixedVariable_::next
BbParaFixedVariable * next
pointer to the next node which has the same fixed value
Definition: bbParaNodesMerger.h:106
UG::BbParaFixedVariable_::index
int index
index of the variable among all solvers
Definition: bbParaNodesMerger.h:103
UG::BbParaFixedVariable_::nSameValue
int nSameValue
the number of same value fixed variables in the following nodes
Definition: bbParaNodesMerger.h:102
UG::BbParaFixedVariable_::value
double value
fixed value
Definition: bbParaNodesMerger.h:104
UG::BbParaMergeNodeInfo_
Merge node information struct.
Definition: bbParaNodesMerger.h:73
UG::BbParaMergeNodeInfo_::PARA_MERGE_CHECKING_TO_OTHER_NODE
@ PARA_MERGE_CHECKING_TO_OTHER_NODE
checking possibility to merge with the other nodes
Definition: bbParaNodesMerger.h:77
UG::BbParaMergeNodeInfo_::PARA_DELETED
@ PARA_DELETED
this node is deleted
Definition: bbParaNodesMerger.h:80
UG::BbParaMergeNodeInfo_::PARA_MERGED_RPRESENTATIVE
@ PARA_MERGED_RPRESENTATIVE
representative node for merging
Definition: bbParaNodesMerger.h:76
UG::BbParaMergeNodeInfo_::PARA_MERGING
@ PARA_MERGING
in merging process
Definition: bbParaNodesMerger.h:75
UG::BbParaMergeNodeInfo_::mergedDiffSubproblem
BbParaDiffSubproblem * mergedDiffSubproblem
merged DiffSubproblem, in case this node is merged and this is the head *‍/
Definition: bbParaNodesMerger.h:94
UG::BbParaMergeNodeInfo_::mergedTo
BbParaMergeNodeInfo * mergedTo
pointer to merge node info to which this node is merged *‍/
Definition: bbParaNodesMerger.h:91
UG::BbParaMergeNodeInfo_::nMergedNodes
int nMergedNodes
the number of merged nodes with this node.
Definition: bbParaNodesMerger.h:84
UG::BbParaMergeNodeInfo_::origDiffSubproblem
BbParaDiffSubproblem * origDiffSubproblem
original DiffSubproblem *‍/
Definition: bbParaNodesMerger.h:93
UG::BbParaMergeNodeInfo_::keyIndex
int keyIndex
The fixedVar of this index can reach all merging nodes.
Definition: bbParaNodesMerger.h:88
UG::BbParaMergeNodeInfo_::paraNode
BbParaNode * paraNode
BbParaNode corresponding to this ParaMergeModeInfo *‍/.
Definition: bbParaNodesMerger.h:92
UG::BbParaMergeNodeInfo_::next
BbParaMergeNodeInfo * next
pointer to the next ParaMergeNodeInfo *‍/
Definition: bbParaNodesMerger.h:95
UG::BbParaMergeNodeInfo_::fixedVariables
BbParaFixedVariable * fixedVariables
array of fixed variable info
Definition: bbParaNodesMerger.h:90
UG::BbParaMergeNodeInfo_::nSameValueVariables
int nSameValueVariables
the number of fixed values which are the same as those of the merged node
Definition: bbParaNodesMerger.h:82
UG::BbParaMergeNodeInfo_::status
enum UG::BbParaMergeNodeInfo_::@0 status
status of this ParaMargeNodeInfo
UG::BbParaMergeNodeInfo_::nFixedVariables
int nFixedVariables
the number of fixed variables
Definition: bbParaNodesMerger.h:89
UG::BbParaMergedNodeListElement_
merged node list element stract
Definition: bbParaNodesMerger.h:120
UG::BbParaMergedNodeListElement_::next
BbParaMergedNodeListElement * next
pointer to the next ParaMergedNodeListElement
Definition: bbParaNodesMerger.h:122
UG::BbParaMergedNodeListElement_::node
BbParaNode * node
pointer to BbParaNode object
Definition: bbParaNodesMerger.h:121
UG::BbParaSortedVariable_
Sorted variable struct.
Definition: bbParaNodesMerger.h:113
UG::BbParaSortedVariable_::idxInFixedVariabes
int idxInFixedVariabes
index in the fixedVariables array
Definition: bbParaNodesMerger.h:114
UG::BbParaSortedVariable_::fixedVariable
BbParaFixedVariable * fixedVariable
pointer to the fixedVariable
Definition: bbParaNodesMerger.h:115