Scippy

SCIP

Solving Constraint Integer Programs

reduce_sol.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file reduce_sol.c
17  * @brief Reduction solution storage methods for Steiner problems
18  * @author Daniel Rehfeldt
19  *
20  * This file includes methods to save and retain solutions and sollocal bounds during the reduction
21  * process
22  *
23  * A list of all interface methods can be found in reduce.h.
24  *
25  */
26 
27 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
28 /*lint -esym(750,REDUCE_C) -esym(766,stdlib.h) -esym(766,string.h) */
29 //#define SCIP_DEBUG
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <assert.h>
33 #include "graph.h"
34 #include "reduce.h"
35 #include "heur_tm.h"
36 #include "solstp.h"
37 #include "scip/scip.h"
38 #include "portab.h"
39 #include "stpvector.h"
40 
41 
42 #define REDSOLVAL_UNSET (-FARAWAY)
43 
45 {
46  int* nodesol;
48  SCIP_Real offset; /**< offset NOTE: offset is only used within this structure! */
49  SCIP_Real primalbound; /**< best sollocal bound */
50  int nnodes;
53 };
54 
55 
56 /** single level representation (needed for decomposition of problem graph) */
58 {
59  REDSOLLOCAL* redsollocal; /**< local storage */
60  int* nodesol; /**< solution nodes marker */
61  int* nodesol_transfer; /**< only needed for decomposition */
62  SCIP_Real solval_postred; /**< value after reduction loop */
63  SCIP_Real solval_incomplete; /**< incomplete value (to be summed up during decomposition ) */
64  int nnodes;
67 } REDSOLLEVEL;
68 
69 
71 {
72  STP_Vectype(REDSOLLEVEL*) levels; /**< levels */
73  SCIP_Real offset; /**< offset */
76 };
77 
78 
79 
80 /*
81  * Local methods
82  */
83 
84 
85 /** updates node solution */
86 static
88  const GRAPH* g, /**< graph data structure */
89  int* nodesol /**< solution array to be filled */
90  )
91 {
92  const int nnodes = graph_get_nNodes(g);
93 
94  assert(nodesol);
95  assert(g->terms == 1);
96 
97  for( int i = 0; i < nnodes; i++ )
98  {
99  if( Is_term(g->term[i]) )
100  {
101  nodesol[i] = CONNECT;
102  }
103  else
104  {
105  nodesol[i] = UNKNOWN;
106  }
107  }
108 }
109 
110 
111 /** updates node solution */
112 static
114  SCIP* scip, /**< SCIP data structure */
115  GRAPH* g, /**< graph data structure */
116  SCIP_Real* solval, /**< FARAWAY if no valid solution build */
117  PATH* solpath, /**< path entry per node */
118  int* nodesol /**< solution array to be filled */
119  )
120 {
121  assert(graph_typeIsSpgLike(g) || graph_pc_isPcMw(g));
122 
123  if( graph_pc_isPcMw(g) )
124  SCIP_CALL( SCIPStpHeurTMBuildTreePcMw(scip, g, TRUE, solpath, g->cost, solval, nodesol) );
125  else
126  SCIPStpHeurTMBuildTree(scip, g, solpath, g->cost, solval, nodesol);
127 
128  return SCIP_OKAY;
129 }
130 
131 #ifdef SCIP_DEBUG
132 /** print node solution */
133 static
134 SCIP_RETCODE nodesolPrintStatus(
135  SCIP* scip, /**< SCIP data structure */
136  GRAPH* g,
137  const int* nodesol /**< solution array to be filled */
138  )
139 {
140  int* nodesol_copy;
141  PATH* solpath;
142  SCIP_Real solval;
143  const int nnodes = graph_get_nNodes(g);
144 
145  assert(scip && nodesol);
146 
147  SCIP_CALL( SCIPallocBufferArray(scip, &solpath, nnodes) );
148  SCIP_CALL( SCIPallocBufferArray(scip, &nodesol_copy, nnodes) );
149  BMScopyMemoryArray(nodesol_copy, nodesol, nnodes);
150 
151  SCIP_CALL( nodesolUpdate(scip, g, &solval, solpath, nodesol_copy) );
152 
154  printf("nodesol value=%f \n", solval);
155 
156  SCIPfreeBufferArray(scip, &nodesol_copy);
157  SCIPfreeBufferArray(scip, &solpath);
158 
159  return SCIP_OKAY;
160 }
161 #endif
162 
163 
164 /** initializes node solution */
165 static
167  SCIP* scip, /**< SCIP data structure */
168  int* nodesol_transfer, /**< solution to be moved or NULL */
169  REDSOLLOCAL* sollocal /**< solution */
170  )
171 {
172  assert(sollocal);
173  assert(!sollocal->nodesol);
174  assert(sollocal->nnodes > 0);
175  assert(!sollocal->nodesol_use);
176 
177  sollocal->nodesol_use = TRUE;
178  sollocal->nodesol_ub = REDSOLVAL_UNSET;
179 
180  if( nodesol_transfer )
181  {
182  sollocal->nodesol = nodesol_transfer;
183  }
184  else
185  {
186  const int nnodes = sollocal->nnodes;
187 
188  SCIP_CALL( SCIPallocMemoryArray(scip, &(sollocal->nodesol), nnodes) );
189 
190  for( int i = 0; i < nnodes; i++ )
191  {
192  sollocal->nodesol[i] = UNKNOWN;
193  }
194  }
195 
196  return SCIP_OKAY;
197 }
198 
199 
200 /** gets edge solution after nodesolUpdate call */
201 static
203  const GRAPH* graph, /**< graph */
204  const PATH* solpath, /**< stores solution */
205  int* edgesol /**< solution array to be filled */
206  )
207 {
208  const int nnodes = graph_get_nNodes(graph);
209  const int nedges = graph_get_nEdges(graph);
210 
211  for( int e = 0; e < nedges; e++ )
212  edgesol[e] = UNKNOWN;
213 
214  for( int k = 0; k < nnodes; k++ )
215  {
216  const int e = solpath[k].edge;
217 
218  if( e >= 0 )
219  edgesol[e] = CONNECT;
220  }
221 }
222 
223 
224 /** initializes */
225 static
227  SCIP* scip, /**< SCIP data structure */
228  int nnodes, /**< number of nodes */
229  REDSOLLEVEL** redlevel /**< to be initialized */
230  )
231 {
232  REDSOLLEVEL* rl;
233 
234  assert(scip);
235 
236  SCIP_CALL( SCIPallocMemory(scip, redlevel) );
237  rl = *redlevel;
238 
239  rl->redsollocal = NULL;
241  rl->solval_incomplete = 0.0;
242  rl->nnodes = nnodes;
243  rl->nodesol_use = TRUE;
245  rl->nodesol_transfer = NULL;
246  /* NOTE: will later be moved from sollocal*/
247  rl->nodesol = NULL;
248 
249  return SCIP_OKAY;
250 }
251 
252 
253 /** frees */
254 static
256  SCIP* scip, /**< SCIP data structure */
257  REDSOLLEVEL** redlevel /**< to be freed */
258  )
259 {
260  REDSOLLEVEL* rl;
261 
262  assert(scip && redlevel);
263  assert(*redlevel);
264 
265  rl = *redlevel;
266 
267  if( rl->redsollocal )
268  reduce_sollocalFree(scip, &(rl->redsollocal));
269 
270 
272  SCIPfreeMemoryArrayNull(scip, &(rl->nodesol));
273 
274  SCIPfreeMemory(scip, redlevel);
275 }
276 
277 
278 #ifndef NDEBUG
279 static
281  REDSOLLEVEL* redlevel /**< to be cleaned */
282  )
283 {
284  assert(redlevel);
285 
286  if( redlevel->redsollocal )
287  return FALSE;
288 
289  if( redlevel->nodesol )
290  return FALSE;
291 
292  if( !EQ(redlevel->solval_postred, REDSOLVAL_UNSET) )
293  return FALSE;
294 
295  if( !EQ(redlevel->solval_incomplete, 0.0) )
296  return FALSE;
297 
298  return TRUE;
299 }
300 #endif
301 
302 
303 /** cleans */
304 static
306  SCIP* scip, /**< SCIP data structure */
307  REDSOLLEVEL* redlevel /**< to be cleaned */
308  )
309 {
310  assert(redlevel);
311  assert(!redlevel->redsollocal);
312  assert(redlevel->nodesol || !redlevel->nodesol_use);
313 
314  SCIPfreeMemoryArrayNull(scip, &(redlevel->nodesol));
315 
316  redlevel->solval_postred = REDSOLVAL_UNSET;
317  redlevel->solval_incomplete = 0.0;
318 
319  assert(redlevelIsClean(redlevel));
320 }
321 
322 
323 /** gets node solution */
324 static
326  REDSOLLEVEL* redlevel /**< to be cleaned */
327  )
328 {
329  assert(redlevel);
330 
331  if( redlevel->nodesol )
332  return redlevel->nodesol;
333 
334  assert(redlevel->redsollocal);
335 
336  return reduce_sollocalGetSolnode(redlevel->redsollocal);
337 }
338 
339 
340 /** initializes incomplete info */
341 static
343  SCIP* scip, /**< SCIP data structure */
344  const REDSOL* redsol, /**< reduction solution */
345  REDSOLLEVEL* redlevel /**< to be initialized */
346  )
347 {
348  assert(scip && redlevel);
349  assert(redlevel->nnodes > 0);
350  assert(EQ(redlevel->solval_incomplete, 0.0));
351 
352  redlevel->solval_incomplete = redsol->offset;
353 
354  SCIPdebugMessage("setting initial solval_incomplete=%f \n", redsol->offset);
355 
356  return SCIP_OKAY;
357 }
358 
359 
360 /** adds local solution */
361 static
363  SCIP* scip, /**< SCIP data structure */
364  const GRAPH* g, /**< graph data structure */
365  REDSOLLEVEL* redlevel, /**< level */
366  REDSOLLOCAL** redsollocal_out /**< pointer to newly initialized local */
367  )
368 {
369  assert(scip && redlevel);
370  assert(!redlevel->redsollocal);
371  assert(redlevel->nnodes > 0);
372 
373  SCIP_CALL( reduce_sollocalInit(scip, g, &(redlevel->redsollocal)) );
374 
375  if( redlevel->nodesol_use )
376  {
377  if( redlevel->nodesol_transfer )
378  {
379  SCIP_CALL( sollocalInitNodesol(scip, redlevel->nodesol_transfer, redlevel->redsollocal) );
380  redlevel->nodesol_transfer = NULL;
381  }
382  else
383  {
384  SCIP_CALL( sollocalInitNodesol(scip, NULL, redlevel->redsollocal) );
385  }
386  }
387 
388  if( redsollocal_out )
389  {
390  *redsollocal_out = redlevel->redsollocal;
391  }
392 
393  return SCIP_OKAY;
394 }
395 
396 
397 /** gets number of levels */
398 static
400  const REDSOL* redsol /**< solution */
401  )
402 {
403  int levels;
404  assert(redsol);
405 
406  levels = StpVecGetSize(redsol->levels);
407  assert(levels > 0);
408 
409  return (levels);
410 }
411 
412 
413 /** gets top level */
414 static
416  const REDSOL* redsol /**< solution */
417  )
418 {
419  const int nlevels = redsolGetNlevels(redsol);
420  assert(nlevels >= 1);
421  assert(redsol->levels[nlevels - 1]);
422 
423  return (redsol->levels[nlevels - 1]);
424 }
425 
426 
427 /** gets parent of top level */
428 static
430  const REDSOL* redsol /**< solution */
431  )
432 {
433  const int nlevels = redsolGetNlevels(redsol);
434  assert(nlevels >= 2);
435  assert(redsol->levels[nlevels - 2]);
436 
437  return (redsol->levels[nlevels - 2]);
438 }
439 
440 
441 /*
442  * Interface methods
443  */
444 
445 
446 /** initializes */
448  SCIP* scip, /**< SCIP data structure */
449  const GRAPH* g, /**< graph data structure */
450  REDSOLLOCAL** sollocal /**< to initialize */
451  )
452 {
453  REDSOLLOCAL* rp;
454  assert(scip);
455 
456  SCIP_CALL( SCIPallocMemory(scip, sollocal) );
457  rp = *sollocal;
458 
459  rp->offset = 0.0;
460  rp->primalbound = FARAWAY;
461  rp->nnodes = graph_get_nNodes(g);
462  rp->nodesol = NULL;
463  rp->nodesol_use = FALSE;
465  rp->isPcMw = graph_pc_isPcMw(g);
466 
467  return SCIP_OKAY;
468 }
469 
470 
471 /** frees */
473  SCIP* scip, /**< SCIP data structure */
474  REDSOLLOCAL** sollocal /**< to free */
475  )
476 {
477  assert(scip && sollocal);
478  assert(*sollocal);
479 
480  SCIPfreeMemoryArrayNull(scip, &((*sollocal)->nodesol));
481  SCIPfreeMemory(scip, sollocal);
482 }
483 
484 
485 
486 /** sets offset
487  * NOTE: offset is only used within this structure! */
489  SCIP_Real offsetnew, /**< new offset */
490  REDSOLLOCAL* sollocal /**< sollocal */
491  )
492 {
493  assert(sollocal);
494  assert(GE(offsetnew, 0.0));
495 
496  if( sollocal->isPcMw && !EQ(sollocal->offset, offsetnew) )
497  {
498  SCIPdebugMessage("setting primalbound from %f to FARAWAY \n", sollocal->primalbound);
499  sollocal->primalbound = FARAWAY;
500  }
501 
502  sollocal->offset = offsetnew;
503 }
504 
505 
506 /** tries to rebuild solnode if possible and necessary */
508  SCIP* scip, /**< SCIP data structure */
509  GRAPH* g, /**< graph */
510  REDSOLLOCAL* sollocal /**< sollocal */
511  )
512 {
513  assert(g && sollocal);
514  assert(sollocal->nnodes == g->knots);
515  assert(graph_pc_isPcMw(g));
516 
517  if( GE(sollocal->primalbound, FARAWAY) && !EQ(sollocal->nodesol_ub, REDSOLVAL_UNSET) && g->terms > 2 )
518  {
519  PATH* solpath;
520  SCIP_Real solval;
521  SCIP_Real solval_total;
522  const SCIP_Real isOrg = !g->extended;
523 
524  if( isOrg )
525  graph_pc_2trans(scip, g);
526 
527  SCIP_CALL( SCIPallocBufferArray(scip, &solpath, sollocal->nnodes ) );
528  SCIP_CALL( nodesolUpdate(scip, g, &solval, solpath, sollocal->nodesol) );
529  SCIPfreeBufferArray(scip, &solpath);
530 
531  solval_total = solval + sollocal->offset;
532 
533  if( graph_pc_isPc(g) )
534  solval_total += graph_pc_getNonLeafTermOffset(scip, g);
535 
536  if( isOrg )
537  graph_pc_2org(scip, g);
538 
539  if( GT(solval_total, FARAWAY) )
540  solval_total = FARAWAY;
541 
542  SCIPdebugMessage("updating upper bound %f->%f \n", sollocal->primalbound, solval_total);
543  SCIPdebugMessage("without offset: %f \n", solval);
544 
545  sollocal->primalbound = solval_total;
546  sollocal->nodesol_ub = solval_total;
547  }
548 
549  return SCIP_OKAY;
550 }
551 
552 
553 /** updates */
555  const REDSOLLOCAL* sollocal /**< sollocal */
556  )
557 {
558  assert(sollocal);
559 
560  return sollocal->nodesol_use;
561 }
562 
563 
564 /** updates */
566  SCIP* scip, /**< SCIP data structure */
567  const int* edgesol, /**< incoming solution */
568  GRAPH* g, /**< graph data structure */
569  REDSOLLOCAL* sollocal /**< sollocal */
570  )
571 {
572  const int nnodes = graph_get_nNodes(g);
573 
574  assert(scip && edgesol && sollocal);
575  assert(reduce_sollocalUsesNodesol(sollocal));
576  assert(nnodes == sollocal->nnodes);
577  assert(solstp_isValid(scip, g, edgesol));
578 
579 
580  // printf("updating nodesol... \n");
581 
582  {
583  PATH* solpath;
584  const SCIP_Real solval_new = solstp_getObj(g, edgesol, 0.0);
585  SCIP_Real solval_old = FARAWAY;
586 
587  if( !EQ(sollocal->nodesol_ub, REDSOLVAL_UNSET) )
588  {
589  SCIP_CALL( SCIPallocBufferArray(scip, &solpath, nnodes) );
590  SCIP_CALL( nodesolUpdate(scip, g, &solval_old, solpath, sollocal->nodesol) );
591  SCIPfreeBufferArray(scip, &solpath);
592  }
593 
594  // printf("old vs new: %f vs %f \n", solval_old, solval_new);
595 
596  if( LT(solval_new, solval_old) )
597  {
598  // printf("updating! \n");
599 
600  solstp_setVertexFromEdgeConn(g, edgesol, sollocal->nodesol);
601  sollocal->nodesol_ub = solval_new;
602  }
603  }
604 
605  return SCIP_OKAY;
606 }
607 
608 
609 /** sets new sollocal bound if better than old one */
611  SCIP_Real ubnew, /**< new upper bound, not including offset! */
612  REDSOLLOCAL* sollocal /**< sollocal */
613  )
614 {
615  SCIP_Real ubnew_scaled;
616 
617  assert(sollocal);
618 
619  ubnew_scaled = ubnew + sollocal->offset;
620 
621  assert(GE(ubnew_scaled, 0.0));
622  assert(LE(ubnew_scaled, FARAWAY));
623 
624  if( ubnew_scaled < sollocal->primalbound )
625  {
626  SCIPdebugMessage("updating upper bound %f->%f \n", sollocal->primalbound, ubnew_scaled);
627  sollocal->primalbound = ubnew_scaled;
628  }
629 }
630 
631 
632 /** gets upper bound; not including (last set) offset */
634  const REDSOLLOCAL* sollocal /**< sollocal */
635  )
636 {
637  assert(sollocal);
638 
639  if( EQ(sollocal->primalbound, FARAWAY) )
640  return FARAWAY;
641 
642  assert(GE_FEAS(sollocal->primalbound, sollocal->offset));
643 
644  SCIPdebugMessage("returning best bound: %f (%f-%f) \n", sollocal->primalbound - sollocal->offset, sollocal->primalbound, sollocal->offset);
645  return MAX(sollocal->primalbound - sollocal->offset, 0.0);
646 }
647 
648 
649 
650 /** gets array */
652  REDSOLLOCAL* sollocal /**< sollocal */
653  )
654 {
655  assert(sollocal);
656  assert(reduce_sollocalUsesNodesol(sollocal) == (sollocal->nodesol != NULL));
657 
658  return sollocal->nodesol;
659 }
660 
661 
662 
663 /** gets upper bound; including (last set) offset */
665  const REDSOLLOCAL* sollocal /**< sollocal */
666  )
667 {
668  assert(sollocal);
669 
670  return (sollocal->primalbound);
671 }
672 
673 
674 /** do we have a (non-trivial) primal bound? */
676  const REDSOLLOCAL* sollocal /**< sollocal */
677  )
678 {
679  assert(sollocal);
680  assert(LE(sollocal->primalbound, FARAWAY));
681 
682  return !EQ(sollocal->primalbound, FARAWAY);
683 }
684 
685 
686 /** initializes */
688  SCIP* scip, /**< SCIP data structure */
689  const GRAPH* g, /**< graph data structure */
690  SCIP_Bool useNodeSol, /**< should solution be used? (additionally to solution value) */
691  REDSOL** redsol /**< to be initialized */
692  )
693 {
694  REDSOLLEVEL* redlevel;
695  REDSOL* rs;
696  assert(scip && g);
697 
698  SCIP_CALL( SCIPallocMemory(scip, redsol) );
699  rs = *redsol;
700 
701  rs->offset = 0.0;
702  rs->isPcMw = graph_pc_isPcMw(g);
703  rs->levels = NULL;
704  rs->nodesol_use = useNodeSol;
705 
706  SCIP_CALL( redlevelInit(scip, g->knots, &redlevel) );
707  StpVecPushBack(scip, rs->levels, redlevel);
708  redlevel->nodesol_use = useNodeSol;
709 
710  assert(redsolGetNlevels(rs) == 1);
711 
712  return SCIP_OKAY;
713 }
714 
715 
716 /** adds local for given level; call before reduction loop */
718  SCIP* scip, /**< SCIP data structure */
719  const GRAPH* g, /**< graph data structure */
720  REDSOL* redsol, /**< reduction solution */
721  REDSOLLOCAL** redsollocal_out /**< pointer to newly initialized local */
722  )
723 {
724  const int nlevels = redsolGetNlevels(redsol);
725  assert(redsol);
726  assert(nlevels >= 1);
727 
728  SCIP_CALL( redlevelAddLocal(scip, g, redsol->levels[nlevels - 1], redsollocal_out) );
729 
730  return SCIP_OKAY;
731 }
732 
733 
734 /** finalizes local for given level; call after reduction loop */
736  SCIP* scip, /**< SCIP data structure */
737  const GRAPH* g, /**< graph data structure */
738  REDSOL* redsol /**< reduction solution */
739  )
740 {
741  REDSOLLEVEL* toplevel = redsolGetTopLevel(redsol);
742  REDSOLLOCAL* redsollocal = toplevel->redsollocal;
743  const SCIP_Real offset = reduce_solGetOffset(redsol);
744 
745  assert(redsollocal);
746 
747  if( g->terms == 1 )
748  {
749  reduce_sollocalSetOffset(offset, redsollocal);
750  reduce_sollocalUpdateUpperBound(0.0, redsollocal);
751 
752  assert(redsol->nodesol_use == redsollocal->nodesol_use);
753 
754  if( redsol->nodesol_use )
755  {
756  nodesolSetTrivial(g, redsollocal->nodesol);
757  redsollocal->nodesol_ub = 0.0;
758  }
759  }
760 
761  assert(EQ(toplevel->solval_postred, REDSOLVAL_UNSET));
762 
763  if( reduce_sollocalHasUpperBound(redsollocal) )
765  else
766  toplevel->solval_postred = FARAWAY;
767 
768  assert(!toplevel->nodesol);
769 
770  if( redsol->nodesol_use )
771  {
772  toplevel->nodesol_ub = redsollocal->nodesol_ub;
773  toplevel->nodesol = redsollocal->nodesol;
774  redsollocal->nodesol = NULL;
775 
776 #ifdef SCIP_DEBUG
777  printf("level=%d have solution in finalize... \n", redsolGetNlevels(redsol) - 1);
778  SCIP_CALL_ABORT( nodesolPrintStatus(scip, (GRAPH*) g, toplevel->nodesol) );
779 #endif
780  }
781  else
782  {
783 #ifdef SCIP_DEBUG
784  printf("level=%d have NO solution in finalize \n", redsolGetNlevels(redsol) - 1);
785 #endif
786  }
787 
788  reduce_sollocalFree(scip, &(toplevel->redsollocal));
789 }
790 
791 
792 /** reinitalizes local after it has been finished */
794  const GRAPH* g, /**< graph data structure */
795  REDSOL* redsol /**< reduction solution */
796  )
797 {
798  REDSOLLEVEL* toplevel = redsolGetTopLevel(redsol);
799 
800  assert(g);
801  assert(toplevel->nnodes == g->knots);
802 
803  toplevel->solval_postred = REDSOLVAL_UNSET;
804  toplevel->nodesol_ub = REDSOLVAL_UNSET;
805 
806  if( redsol->nodesol_use )
807  {
808  assert(toplevel->nodesol);
809  assert(!toplevel->nodesol_transfer);
810 
811  toplevel->nodesol_transfer = toplevel->nodesol;
812  toplevel->nodesol = NULL;
813  }
814 }
815 
816 
817 /** frees */
819  SCIP* scip, /**< SCIP data structure */
820  REDSOL** redsol /**< to be freed */
821  )
822 {
823  REDSOL* rs;
824 
825  assert(scip && redsol);
826  assert(*redsol);
827 
828  rs = *redsol;
829  assert(!StpVecIsEmpty(rs->levels));
830 
831  while( !StpVecIsEmpty(rs->levels) )
832  {
833  const int size = StpVecGetSize(rs->levels);
834  assert(size >= 1);
835 
836  redlevelFree(scip, &(rs->levels[size - 1]));
837  StpVecPopBack(rs->levels);
838  }
839 
840  StpVecFree(scip, rs->levels);
841  SCIPfreeMemory(scip, redsol);
842 }
843 
844 
845 /** packs solution */
847  const GRAPH* g, /**< graph data structure */
848  const int* nodes_old2packed, /**< map to packed node IDs */
849  int nnodes_packed, /**< number of packed nodes */
850  REDSOL* redsol /**< sollocal */
851  )
852 {
853  REDSOLLEVEL* redlevel;
854  int* nodesol;
855  const int nnodes = graph_get_nNodes(g);
856 
857  assert(g && redsol && nodes_old2packed);
858 
859  redlevel = redsol->levels[0];
860  assert(redlevel);
861  assert(nnodes == redlevel->nnodes);
862  assert(1 <= nnodes_packed && nnodes_packed <= nnodes);
863 
864  redlevel->nnodes = nnodes_packed;
865 
866  if( !redsol->nodesol_use )
867  return;
868 
869  nodesol = redlevel->nodesol;
870 
871  // todo also implement for PcMw!
872  if( !nodesol )
873  {
874  assert(graph_pc_isPcMw(g));
875  return;
876  }
877 
878 
879  assert(nodesol);
880 
881  for( int i = 0; i < nnodes; i++ )
882  {
883  const int node_packed = nodes_old2packed[i];
884 
885  if( node_packed >= 0 )
886  {
887  assert(node_packed <= i);
888  assert(node_packed < nnodes_packed);
889 
890  nodesol[node_packed] = nodesol[i] ;
891  }
892  }
893 }
894 
895 
896 /** adds level */
898  SCIP* scip, /**< SCIP data structure */
899  const GRAPH* g, /**< graph data structure */
900  REDSOL* redsol /**< sollocal */
901  )
902 {
903  REDSOLLEVEL* redlevel_new;
904  REDSOLLEVEL* redlevel_top = redsolGetTopLevel(redsol);
905 
906  SCIPdebugMessage("adding level %d \n", redsolGetNlevels(redsol));
907 
908  assert(redsol);
909  assert(EQ(redsolGetTopLevel(redsol)->solval_incomplete, 0.0));
910 
911  SCIP_CALL( redlevelInitIncomplete(scip, redsol, redlevel_top) );
912 
913  SCIP_CALL( redlevelInit(scip, -1, &redlevel_new) );
914  StpVecPushBack(scip, redsol->levels, redlevel_new);
915  redlevel_new->nodesol_use = redsol->nodesol_use;
916 
917  return SCIP_OKAY;
918 }
919 
920 
921 /** initializes level with given (sub) graph */
923  SCIP* scip, /**< SCIP data structure */
924  const GRAPH* subgraph, /**< graph data structure */
925  REDSOL* redsol /**< reduction solution */
926  )
927 {
928  const int nnodes = graph_get_nNodes(subgraph);
929  REDSOLLEVEL* toplevel = redsolGetTopLevel(redsol);
930 
931  assert(redlevelIsClean(toplevel));
932 
933  toplevel->nnodes = nnodes;
934 
935  return SCIP_OKAY;
936 }
937 
938 
939 /** removes top level */
941  SCIP* scip, /**< SCIP data structure */
942  REDSOL* redsol /**< reduction solution */
943  )
944 {
945  const int nlevels = redsolGetNlevels(redsol);
946  assert(nlevels >= 2);
947 
948  redlevelFree(scip, &(redsol->levels[nlevels - 1]));
949  StpVecPopBack(redsol->levels);
950 
951  assert(redsolGetNlevels(redsol) == nlevels - 1);
952 }
953 
954 
955 /** finalizes top level; also removes the level! */
957  SCIP* scip, /**< SCIP data structure */
958  GRAPH* g, /**< graph data structure */
959  REDSOL* redsol /**< sollocal */
960  )
961 {
962  REDSOLLOCAL* redsollocal_top;
963  REDSOLLEVEL* redlevel_top;
964  const int nlevels = redsolGetNlevels(redsol);
965  assert(nlevels >= 2);
966 
967  redlevelFree(scip, &(redsol->levels[nlevels - 1]));
968  StpVecPopBack(redsol->levels);
969 
970  redlevel_top = redsolGetTopLevel(redsol);
971  redsollocal_top = redlevel_top->redsollocal;
972  assert(redsollocal_top);
973 
974  reduce_sollocalSetOffset(0.0, redsollocal_top);
975  reduce_sollocalUpdateUpperBound(redlevel_top->solval_incomplete, redsollocal_top);
976 
977  SCIPdebugMessage("FINALIZING top level %d; solval=%f offset=%f \n", nlevels - 1, redlevel_top->solval_incomplete, redsol->offset);
978 
979 /*
980  int* solnode = redsollocal_top->nodesol;
981 
982  if( solnode )
983  {
984 nodesolPrintStatus(scip, g, solnode);
985  }
986  else
987  {
988  printf("no solnode \n");
989 
990  }
991 */
992  assert(redsolGetNlevels(redsol) == nlevels - 1);
993 }
994 
995 
996 /** removes level */
998  SCIP* scip, /**< SCIP data structure */
999  REDSOL* redsol /**< sollocal */
1000  )
1001 {
1002  const int nlevels = redsolGetNlevels(redsol);
1003  assert(nlevels >= 1);
1004 
1005  redlevelClean(scip, redsol->levels[nlevels - 1]);
1006 }
1007 
1008 
1009 /** merges level up */
1011  const int* nodemap_subToOrg, /**< map */
1012  REDSOL* redsol /**< sollocal */
1013  )
1014 {
1015  REDSOLLOCAL* redsollocalParent;
1016  REDSOLLEVEL* const levelTop = redsolGetTopLevel(redsol);
1017  REDSOLLEVEL* const levelParent = redsolGetTopParentLevel(redsol);
1018 
1019  assert(nodemap_subToOrg);
1020  assert(!levelTop->redsollocal);
1021  assert(levelParent->redsollocal);
1022  assert(GE(levelTop->solval_postred, 0.0));
1023  assert(levelTop->nodesol_use == levelParent->nodesol_use);
1024 
1025  SCIPdebugMessage("merge levels %d->%d \n", redsolGetNlevels(redsol) - 1, redsolGetNlevels(redsol) - 2);
1026  SCIPdebugMessage("...update solval_incomplete: %f->%f \n", levelParent->solval_incomplete, levelParent->solval_incomplete + levelTop->solval_postred);
1027 
1028  levelParent->solval_incomplete += levelTop->solval_postred;
1029 
1030  if( GT(levelParent->solval_incomplete, FARAWAY) )
1031  levelParent->solval_incomplete = FARAWAY;
1032 
1033  /* is there a solution to merge back? */
1034  if( levelTop->nodesol_use )
1035  {
1036  const int nnodes_top = levelTop->nnodes;
1037  const int* const nodesol_top = redlevelGetNodesol(levelTop);
1038  int* const nodesol_parent = redlevelGetNodesol(levelParent);
1039 
1040  assert(nodesol_top && nodesol_parent);
1041 
1042  for( int i = 0; i < nnodes_top; i++ )
1043  {
1044  const int node_parent = nodemap_subToOrg[i];
1045  assert(0 <= node_parent && node_parent <= levelParent->nnodes);
1046  assert(nodesol_top[i] == CONNECT || nodesol_top[i] == UNKNOWN);
1047 
1048  nodesol_parent[node_parent] = nodesol_top[i];
1049  }
1050 
1051  assert(levelParent->redsollocal);
1052  redsollocalParent = levelParent->redsollocal;
1053 
1054  if( EQ(redsollocalParent->nodesol_ub, REDSOLVAL_UNSET) )
1055  {
1056  redsollocalParent->nodesol_ub = MAX(levelTop->nodesol_ub, 0.0);
1057  }
1058  else
1059  {
1060  redsollocalParent->nodesol_ub += MAX(levelTop->nodesol_ub, 0.0);
1061  }
1062  }
1063 }
1064 
1065 
1066 /** transfers solution from parent to top level */
1068  const int* nodemap_orgToTop, /**< map */
1069  REDSOL* redsol /**< sollocal */
1070  )
1071 {
1072  REDSOLLEVEL* const toplevel = redsolGetTopLevel(redsol);
1073  REDSOLLEVEL* const parentlevel = redsolGetTopParentLevel(redsol);
1074  const int nnodes_parent = parentlevel->nnodes;
1075  const int nnodes_top = toplevel->nnodes;
1076 
1077  assert(toplevel->nodesol_use == parentlevel->nodesol_use);
1078  assert(!toplevel->redsollocal);
1079  assert(nnodes_parent >= nnodes_top);
1080 
1081  if( toplevel->nodesol_use )
1082  {
1083  /* NOTE: we create a solution for the level that will later
1084  * be moved to the local solution */
1085  int* nodesol_transfer;
1086  const int* const nodesol_org = redlevelGetNodesol(parentlevel);
1087 
1088  assert(!toplevel->nodesol_transfer);
1089  assert(nodesol_org);
1090 
1091  SCIP_CALL( SCIPallocMemoryArray(scip, &nodesol_transfer, nnodes_top) );
1092 
1093 #ifndef NDEBUG
1094  for( int i = 0; i < nnodes_top; i++ )
1095  nodesol_transfer[i] = -2;
1096 #endif
1097 
1098  for( int i = 0; i < nnodes_parent; i++ )
1099  {
1100  const int node = nodemap_orgToTop[i];
1101 
1102  if( node < 0 )
1103  continue;
1104 
1105  assert(node < nnodes_top);
1106 
1107  // printf("map %d to %d %d \n", i, node, nodesol_org[i]);
1108  nodesol_transfer[node] = nodesol_org[i];
1109  }
1110 
1111 #ifndef NDEBUG
1112  for( int i = 0; i < nnodes_top; i++ )
1113  assert(nodesol_transfer[i] != -2);
1114 #endif
1115 
1116  toplevel->nodesol_transfer = nodesol_transfer;
1117  }
1118 
1119  return SCIP_OKAY;
1120 }
1121 
1122 
1123 /** sets offset */
1125  SCIP_Real offsetnew, /**< new offset */
1126  REDSOL* redsol /**< solution */
1127  )
1128 {
1129  assert(redsol);
1130  assert(GE(offsetnew, 0.0));
1131 
1132  redsol->offset = offsetnew;
1133 }
1134 
1135 
1136 /** gets */
1138  const REDSOL* redsol /**< solution */
1139  )
1140 {
1141  assert(redsol);
1142 
1143 
1144  return (redsol->offset);
1145 }
1146 
1147 
1148 
1149 /** adds (and possibly overwrites) nodesol */
1151  const GRAPH* g, /**< graph data structure */
1152  const int* nodesol, /**< incoming solution */
1153  REDSOL* redsol /**< solution */
1154  )
1155 {
1156  REDSOLLEVEL* level;
1157 
1158  assert(redsol && nodesol && g);
1159  assert(redsolGetNlevels(redsol) == 1);
1160  assert(redsol->nodesol_use);
1161 
1162  level = redsol->levels[0];
1163  assert(g->knots == level->nnodes);
1164  assert(!level->nodesol_transfer);
1165 
1166  SCIP_CALL( SCIPallocMemoryArray(scip, &(level->nodesol_transfer), g->knots) );
1167  level->nodesol_ub = 0.0;
1168 
1169  BMScopyMemoryArray(level->nodesol_transfer, nodesol, g->knots);
1170 
1171  return SCIP_OKAY;
1172 }
1173 
1174 
1175 /** gets */
1177  const GRAPH* g, /**< graph data structure */
1178  REDSOL* redsol, /**< solution */
1179  int* nodesol /**< solution array to be filled */
1180  )
1181 {
1182  REDSOLLEVEL* level;
1183 
1184  assert(redsol && nodesol && g);
1185  assert(redsolGetNlevels(redsol) == 1);
1186  assert(redsol->nodesol_use);
1187 
1188  level = redsol->levels[0];
1189  assert(g->knots == level->nnodes);
1190  assert(level->nodesol);
1191 
1192  BMScopyMemoryArray(nodesol, level->nodesol, g->knots);
1193 }
1194 
1195 
1196 /** gets edge solution, if available, and solution value */
1198  SCIP* scip, /**< SCIP data structure */
1199  GRAPH* g, /**< graph data structure */
1200  REDSOL* redsol, /**< solution */
1201  SCIP_Real* solval, /**< FARAWAY if no solution available */
1202  int* edgesol /**< solution array to be filled */
1203  )
1204 {
1205  REDSOLLEVEL* level;
1206 
1207  assert(scip && g && redsol && solval && edgesol);
1208 
1209  *solval = FARAWAY;
1210  level = redsol->levels[0];
1211  assert(level);
1212  assert(g->knots > 1);
1213 
1214  if( !redsol->nodesol_use )
1215  return SCIP_OKAY;
1216 
1217  if( LT(level->nodesol_ub, FARAWAY) )
1218  {
1219  PATH* solpath;
1220  const int nnodes = graph_get_nNodes(g);
1221 
1222  SCIP_CALL( SCIPallocBufferArray(scip, &solpath, nnodes) );
1223  SCIP_CALL( nodesolUpdate(scip, g, solval, solpath, level->nodesol) );
1224 
1225  if( LT(*solval, FARAWAY) )
1226  nodesolGetEdgeSol(g, solpath, edgesol);
1227 
1228  SCIPfreeBufferArray(scip, &solpath);
1229  }
1230 
1231  return SCIP_OKAY;
1232 }
1233 
1234 
1235 /** is node solution in use? */
1237  const REDSOL* redsol /**< solution */
1238  )
1239 {
1240 
1241  assert(redsol);
1242 
1243  return (redsol->nodesol_use);
1244 }
1245 
1246 
1247 /** gets */
1249  const REDSOL* redsol /**< solution */
1250  )
1251 {
1252  const REDSOLLEVEL* const level = redsolGetTopLevel(redsol);
1253 
1254  assert(reduce_solUsesNodesol(redsol));
1255  assert(redsolGetNlevels(redsol) == 1);
1256  assert(level->nodesol);
1257 
1258  return level->nodesol;
1259 }
1260 
1261 
1262 /** gets */
1264  const REDSOL* redsol /**< solution */
1265  )
1266 {
1267  REDSOLLEVEL* level;
1268  SCIP_Real ub;
1269 
1270  assert(redsol);
1271  assert(redsolGetNlevels(redsol) >= 1);
1272  assert(redsol->levels);
1273 
1274  level = redsol->levels[0];
1275  ub = level->solval_postred;
1276 
1277  if( EQ(ub, REDSOLVAL_UNSET) )
1278  return FARAWAY;
1279 
1280  return (ub);
1281 }
1282 
1283 
1284 /** gets */
1286  REDSOL* redsol /**< solution */
1287  )
1288 {
1289  assert(redsol);
1290 
1291 
1292  return &(redsol->offset);
1293 }
#define STP_Vectype(type)
Definition: stpvector.h:44
int graph_get_nEdges(const GRAPH *)
Definition: graph_stats.c:548
SCIP_Bool reduce_solUsesNodesol(const REDSOL *redsol)
Definition: reduce_sol.c:1236
#define StpVecGetSize(vec)
Definition: stpvector.h:139
SCIP_Real reduce_solGetUpperBoundWithOffset(const REDSOL *redsol)
Definition: reduce_sol.c:1263
SCIP_Real solval_incomplete
Definition: reduce_sol.c:63
SCIP_RETCODE reduce_solGetEdgesol(SCIP *scip, GRAPH *g, REDSOL *redsol, SCIP_Real *solval, int *edgesol)
Definition: reduce_sol.c:1197
void reduce_solFree(SCIP *scip, REDSOL **redsol)
Definition: reduce_sol.c:818
#define SCIPfreeMemoryArrayNull(scip, ptr)
Definition: scip_mem.h:72
#define Is_term(a)
Definition: graphdefs.h:102
SCIP_Real reduce_sollocalGetUpperBoundWithOffset(const REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:664
signed int edge
Definition: graphdefs.h:287
int terms
Definition: graphdefs.h:192
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
includes methods for Steiner tree problem solutions
static SCIP_RETCODE nodesolUpdate(SCIP *scip, GRAPH *g, SCIP_Real *solval, PATH *solpath, int *nodesol)
Definition: reduce_sol.c:113
#define GE_FEAS(a, b)
Definition: portab.h:72
void reduce_solLevelTopRemove(SCIP *scip, REDSOL *redsol)
Definition: reduce_sol.c:940
void graph_pc_2org(SCIP *, GRAPH *)
#define FALSE
Definition: def.h:87
void reduce_sollocalSetOffset(SCIP_Real offsetnew, REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:488
static SCIP_RETCODE redlevelAddLocal(SCIP *scip, const GRAPH *g, REDSOLLEVEL *redlevel, REDSOLLOCAL **redsollocal_out)
Definition: reduce_sol.c:362
static REDSOLLEVEL * redsolGetTopParentLevel(const REDSOL *redsol)
Definition: reduce_sol.c:429
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
includes various files containing graph methods used for Steiner tree problems
static void nodesolSetTrivial(const GRAPH *g, int *nodesol)
Definition: reduce_sol.c:87
#define StpVecPopBack(vec)
Definition: stpvector.h:178
SCIP_RETCODE reduce_solLevelTopUpdate(SCIP *scip, const GRAPH *subgraph, REDSOL *redsol)
Definition: reduce_sol.c:922
#define REDSOLVAL_UNSET
Definition: reduce_sol.c:42
#define SCIPdebugMessage
Definition: pub_message.h:87
#define FARAWAY
Definition: graphdefs.h:89
SCIP_Real graph_pc_getNonLeafTermOffset(SCIP *, const GRAPH *)
static SCIP_RETCODE redlevelInit(SCIP *scip, int nnodes, REDSOLLEVEL **redlevel)
Definition: reduce_sol.c:226
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
header only, simple implementation of an STL like vector
void reduce_solLevelTopFinalize(SCIP *scip, GRAPH *g, REDSOL *redsol)
Definition: reduce_sol.c:956
REDSOLLOCAL * redsollocal
Definition: reduce_sol.c:59
int * reduce_sollocalGetSolnode(REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:651
SCIP_RETCODE reduce_solInit(SCIP *scip, const GRAPH *g, SCIP_Bool useNodeSol, REDSOL **redsol)
Definition: reduce_sol.c:687
void reduce_solLevelTopClean(SCIP *scip, REDSOL *redsol)
Definition: reduce_sol.c:997
#define LE(a, b)
Definition: portab.h:83
const int * reduce_solGetNodesolPointer(const REDSOL *redsol)
Definition: reduce_sol.c:1248
#define GE(a, b)
Definition: portab.h:85
void graph_pc_2trans(SCIP *, GRAPH *)
SCIP_Bool extended
Definition: graphdefs.h:267
void reduce_sollocalUpdateUpperBound(SCIP_Real ubnew, REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:610
static SCIP_Bool redlevelIsClean(REDSOLLEVEL *redlevel)
Definition: reduce_sol.c:280
static void nodesolGetEdgeSol(const GRAPH *graph, const PATH *solpath, int *edgesol)
Definition: reduce_sol.c:202
void reduce_solGetNodesol(const GRAPH *g, REDSOL *redsol, int *nodesol)
Definition: reduce_sol.c:1176
void reduce_solFinalizeLocal(SCIP *scip, const GRAPH *g, REDSOL *redsol)
Definition: reduce_sol.c:735
#define NULL
Definition: lpi_spx1.cpp:155
struct reduction_solution_level REDSOLLEVEL
#define EQ(a, b)
Definition: portab.h:79
int knots
Definition: graphdefs.h:190
#define SCIP_CALL(x)
Definition: def.h:384
#define LT(a, b)
Definition: portab.h:81
void SCIPStpHeurTMBuildTree(SCIP *scip, GRAPH *g, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:2932
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
#define GT(a, b)
Definition: portab.h:84
SCIP_Bool reduce_sollocalUsesNodesol(const REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:554
#define SCIP_Bool
Definition: def.h:84
static SCIP_RETCODE sollocalInitNodesol(SCIP *scip, int *nodesol_transfer, REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:166
SCIP_Real reduce_sollocalGetUpperBound(const REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:633
static int redsolGetNlevels(const REDSOL *redsol)
Definition: reduce_sol.c:399
void reduce_solSetOffset(SCIP_Real offsetnew, REDSOL *redsol)
Definition: reduce_sol.c:1124
#define MAX(x, y)
Definition: tclique_def.h:83
void reduce_solLevelTopTransferSolBack(const int *nodemap_subToOrg, REDSOL *redsol)
Definition: reduce_sol.c:1010
static REDSOLLEVEL * redsolGetTopLevel(const REDSOL *redsol)
Definition: reduce_sol.c:415
static void redlevelFree(SCIP *scip, REDSOLLEVEL **redlevel)
Definition: reduce_sol.c:255
int *RESTRICT term
Definition: graphdefs.h:196
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
#define StpVecIsEmpty(vec)
Definition: stpvector.h:144
SCIP_Bool graph_pc_isPc(const GRAPH *)
#define CONNECT
Definition: graphdefs.h:87
SCIP_RETCODE reduce_solAddNodesol(const GRAPH *g, const int *nodesol, REDSOL *redsol)
Definition: reduce_sol.c:1150
Portable definitions.
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
SCIP_Bool reduce_sollocalHasUpperBound(const REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:675
void reduce_sollocalFree(SCIP *scip, REDSOLLOCAL **sollocal)
Definition: reduce_sol.c:472
SCIP_Real reduce_solGetOffset(const REDSOL *redsol)
Definition: reduce_sol.c:1137
SCIP_Real * cost
Definition: graphdefs.h:221
void solstp_setVertexFromEdgeConn(const GRAPH *g, const int *soledge, int *solnode)
Definition: solstp.c:2114
SCIP_RETCODE SCIPStpHeurTMBuildTreePcMw(SCIP *scip, const GRAPH *g, SCIP_Bool useRootSym, PATH *mst, const SCIP_Real *cost, SCIP_Real *objresult, int *connected)
Definition: heur_tm.c:3012
void reduce_solReInitLocal(const GRAPH *g, REDSOL *redsol)
Definition: reduce_sol.c:793
static int * redlevelGetNodesol(REDSOLLEVEL *redlevel)
Definition: reduce_sol.c:325
SCIP_Bool graph_pc_isPcMw(const GRAPH *)
SCIP_RETCODE reduce_sollocalInit(SCIP *scip, const GRAPH *g, REDSOLLOCAL **sollocal)
Definition: reduce_sol.c:447
#define SCIP_Real
Definition: def.h:177
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
SCIP_RETCODE reduce_sollocalRebuildTry(SCIP *scip, GRAPH *g, REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:507
shortest paths based primal heuristics for Steiner problems
void reduce_solPack(const GRAPH *g, const int *nodes_old2packed, int nnodes_packed, REDSOL *redsol)
Definition: reduce_sol.c:846
int graph_get_nNodes(const GRAPH *)
Definition: graph_stats.c:536
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define UNKNOWN
Definition: sepa_mcf.c:4095
SCIP_Real * reduce_solGetOffsetPointer(REDSOL *redsol)
Definition: reduce_sol.c:1285
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
SCIP_RETCODE reduce_solLevelTopTransferSolTo(const int *nodemap_orgToTop, REDSOL *redsol)
Definition: reduce_sol.c:1067
SCIP_RETCODE reduce_solLevelAdd(SCIP *scip, const GRAPH *g, REDSOL *redsol)
Definition: reduce_sol.c:897
SCIP_RETCODE reduce_solInitLocal(SCIP *scip, const GRAPH *g, REDSOL *redsol, REDSOLLOCAL **redsollocal_out)
Definition: reduce_sol.c:717
SCIP_Bool solstp_isValid(SCIP *scip, const GRAPH *graph, const int *result)
Definition: solstp.c:1650
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
SCIP_Bool graph_typeIsSpgLike(const GRAPH *)
Definition: graph_stats.c:57
static void redlevelClean(SCIP *scip, REDSOLLEVEL *redlevel)
Definition: reduce_sol.c:305
SCIP_RETCODE reduce_sollocalUpdateNodesol(SCIP *scip, const int *edgesol, GRAPH *g, REDSOLLOCAL *sollocal)
Definition: reduce_sol.c:565
includes various reduction methods for Steiner tree problems
SCIP_Real solstp_getObj(const GRAPH *g, const int *soledge, SCIP_Real offset)
Definition: solstp.c:1859
void graph_printInfoReduced(const GRAPH *)
Definition: graph_stats.c:375
static SCIP_RETCODE redlevelInitIncomplete(SCIP *scip, const REDSOL *redsol, REDSOLLEVEL *redlevel)
Definition: reduce_sol.c:342
SCIP callable library.