34 #define SP_MAXNDISTS 10000 35 #define SP_MAXLENGTH 11 36 #define SP_MAXDEGREE 8 37 #define SP_MAXDEGREE_FAST 5 38 #define SP_MAXDEGREE_PC 10 39 #define SP_MAXNSTARTS 10000 40 #define VNODES_UNSET -1 41 #define SP_MAXNPULLS 4 55 int* RESTRICT sp_starts;
56 int* RESTRICT nodes_index;
59 SCIP_Bool* RESTRICT firstneighbors_isKilled;
79 const int* nodes_index,
95 if( source1 != nonsource && nodes_index[source1] < 0 )
103 if( source2 != nonsource && nodes_index[source2] < 0 )
121 return g->
head[pr->pathedges[npathedges - 1]];
141 const int*
const result = extperma->
result;
169 for(
int i = 0; i <
nnodes; ++i )
176 assert(g->
grad[i] == 0);
183 if( g->
grad[sibling] == 0 )
185 else if( g->
grad[sibling] == 1 )
201 const SCIP_Real*
const sp_dists = pr->sp_dists;
204 const int nfirst = pr->nfirstneighbors;
209 assert(
FALSE == *needFullRuleOut);
210 SCIPdebugMessage(
"starting head rule-out with pathcost=%f \n", pr->pathcost);
212 for(
int i = 0; i < ncurrneighbors; i++ )
215 const int neighbor = pr->currneighbors[i];
216 const int sp_start = pr->sp_starts[pr->nodes_index[neighbor]];
221 assert(pr->nodes_index[neighbor] >= 0);
223 for( j = 0; j < nfirst; j++ )
225 if( pr->firstneighbors_isKilled[j] )
228 SCIPdebugMessage(
"dist for neighbor=%d, idx=%d: %f \n", neighbor, j, sp_dists[sp_start + j]);
229 if(
GT(sp_dists[sp_start + j], pathcost) )
233 const int fneighbor = pr->firstneighbors[j];
236 if(
LT(sd, pathcost) )
239 if(
EQ(sd, pathcost) )
241 const int startedge = pr->pathedges[0];
243 if(
LE(sd, pathcost) )
262 *needFullRuleOut =
TRUE;
265 failneighbor = neighbor;
269 pr->failneighbor = failneighbor;
282 const SCIP_Real*
const sp_dists = pr->sp_dists;
283 const int*
const sp_starts = pr->sp_starts;
285 const int pathhead_idx = pr->nodes_index[pathhead];
289 assert(!*isRuledOut);
293 for(
int i = 0; i < pr->nfirstneighbors; i++ )
295 if( !pr->firstneighbors_isKilled[i] )
297 const SCIP_Real extpathcost = pr->pathcost + pr->firstneighborcosts[i];
298 const SCIP_Real altpathcost = sp_dists[sp_starts[pathhead_idx] + i];
303 if(
GT(altpathcost, extpathcost) )
307 const int fneighbor = pr->firstneighbors[i];
310 if(
LT(sd, extpathcost) )
313 if(
EQ(sd, extpathcost) )
315 const int startedge = pr->pathedges[0];
317 if(
LE(sd, extpathcost) )
341 const SCIP_Real*
const sp_dists = pr->sp_dists;
342 const int*
const sp_starts = pr->sp_starts;
344 const int pathhead_idx = pr->nodes_index[pathhead];
349 SCIPdebugMessage(
"try full tail rule-out with pathcost=%f \n", pr->pathcost);
351 for(
int i = 0; i < pr->nfirstneighbors; i++ )
353 const SCIP_Real altpathcost = sp_dists[sp_starts[pathhead_idx] + i];
357 if(
GT(altpathcost, pr->pathcost) )
361 const int fneighbor = pr->firstneighbors[i];
364 if(
LT(sd, pr->pathcost) )
366 pr->firstneighbors_isKilled[i] =
TRUE;
370 if(
EQ(sd, pr->pathcost) )
372 const int startedge = pr->pathedges[0];
374 if(
LE(sd, pr->pathcost) )
376 pr->firstneighbors_isKilled[i] =
TRUE;
387 pr->firstneighbors_isKilled[i] =
TRUE;
394 assert(!*isRuledOut);
415 pr->nodeindices_isPath[pr->nodes_index[node]] =
TRUE;
430 pr->nodeindices_isPath[pr->nodes_index[node]] =
FALSE;
444 const int*
const dcsr_heads = dcsr->
head;
446 const int extnode = pr->failneighbor;
449 assert(pr->nodes_index[extnode] >= 0);
450 assert(!pr->nodeindices_isPath[pr->nodes_index[extnode]]);
451 assert(extnode >= 0);
455 for( j = dcsr_range[pathhead].start; j != dcsr_range[pathhead].
end; j++ )
457 if( dcsr_heads[j] == extnode )
460 assert(j != dcsr_range[pathhead].end);
464 pr->pathcost += dcsr->
cost[j];
465 pr->nodeindices_isPath[pr->nodes_index[extnode]] =
TRUE;
470 pr->pathcost -= g->
prize[pathhead];
489 const int*
const dcsr_heads = dcsr->
head;
490 SCIP_Real* RESTRICT sp_dists = pr->sp_dists;
491 int* RESTRICT sp_starts = pr->sp_starts;
492 int starts_final = pr->nfirstneighbors;
496 sp_starts[starts_final + 1] = sp_starts[starts_final] + pr->nfirstneighbors;
497 for(
int i = sp_starts[starts_final], j = 0; i != sp_starts[starts_final + 1]; i++, j++ )
498 sp_dists[i] = pr->firstneighborcosts[j];
503 sp_starts[starts_final + 1] = sp_starts[starts_final] + pr->nfirstneighbors;
504 for(
int i = sp_starts[starts_final]; i != sp_starts[starts_final + 1]; i++ )
508 for(
int j = dcsr_range[startdege_head].start; j != dcsr_range[startdege_head].
end; j++ )
510 const int head = dcsr_heads[j];
511 const int head_index = pr->nodes_index[head];
514 if( head_index < 0 || head == startedge_tail )
517 assert(0 <= head_index && head_index < pr->nfirstneighbors);
518 assert(
EQ(sp_dists[sp_starts[starts_final] + head_index],
FARAWAY));
519 SCIPdebugMessage(
"setting distance from first path node(%d) for initial neighbor (idx=%d) to %f \n",
520 startdege_head, head_index, dcsr->
cost[j]);
521 sp_dists[sp_starts[starts_final] + head_index] = dcsr->
cost[j];
536 SCIP_Real* RESTRICT sp_dists = pr->sp_dists;
537 const int*
const dcsr_heads = dcsr->
head;
538 int* RESTRICT nodes_index = pr->nodes_index;
539 int* RESTRICT sp_starts = pr->sp_starts;
541 const int nfirstneighbors = pr->nfirstneighbors;
547 for(
int i = dcsr_range[basenode].start; i != dcsr_range[basenode].
end; i++ )
549 const int head = dcsr_heads[i];
550 int head_index = nodes_index[head];
552 if( head_index >= 0 && pr->nodeindices_isPath[head_index] )
564 nodes_index[head] = head_index;
566 pr->nodeindices_isPath[head_index] =
FALSE;
569 sp_starts[head_index + 1] = sp_starts[head_index] + nfirstneighbors;
571 for(
int j = sp_starts[head_index]; j != sp_starts[head_index + 1]; j++ )
591 SCIP_Real* RESTRICT sp_dists = pr->sp_dists;
592 const int*
const dcsr_heads = dcsr->
head;
593 const int*
const nodes_index = pr->nodes_index;
594 const int*
const sp_starts = pr->sp_starts;
595 const int nfirstneighbors = pr->nfirstneighbors;
597 const int pathtail = pr->pathtail;
603 currneighbors = pr->currneighbors;
605 for(
int loop = 0; loop < nloops; loop++ )
609 for(
int iter = 0; iter <= nneighbors; iter++ )
611 const int node = currneighbors[iter];
612 const int node_start = sp_starts[nodes_index[node]];
614 assert(nodes_index[node] >= 0);
616 for(
int i = dcsr_range[node].start; i != dcsr_range[node].
end; i++ )
618 const int head = dcsr_heads[i];
623 const int head_start = sp_starts[nodes_index[head]];
625 if( head == pathtail && node == pathhead )
628 if( nodes_index[head] > nfirstneighbors )
630 assert(head != pathtail);
631 head_profit =
getSdProfit(sdprofit, nodes_index, head, node);
634 for(
int k = 0; k < nfirstneighbors; k++ )
636 SCIP_Real newdist = dcsr_costs[i] + sp_dists[head_start + k];
637 SCIP_Real profitBias = MIN(head_profit, dcsr_costs[i]);
639 profitBias = MIN(profitBias, sp_dists[head_start + k]);
642 newdist -= profitBias;
644 if(
LT(newdist, sp_dists[node_start + k]) )
646 SCIPdebugMessage(
"(l=%d) updating distance for node %d to orgindex %d to %f \n",
647 loop, node, k, newdist);
648 sp_dists[node_start + k] = newdist;
673 const int basetail = g->
tail[startedge];
674 const int basehead = g->
head[startedge];
677 const int*
const dcsr_heads = dcsr->
head;
679 SCIP_Real* RESTRICT sp_dists = pr->sp_dists;
680 int* RESTRICT sp_starts = pr->sp_starts;
691 pr->pathcost = g->
cost[startedge];
692 pr->pathtail = basetail;
695 for(
int i = dcsr_range[basetail].start; i != dcsr_range[basetail].
end; i++ )
697 const int head = dcsr_heads[i];
701 if( head == basehead )
718 for(
int i = 0; i < pr->nfirstneighbors; i++ )
720 const int neighbor = pr->currneighbors[i];
721 const SCIP_Real basecost = pr->firstneighborcosts[i];
722 sp_starts[i + 1] = sp_starts[i] + pr->nfirstneighbors;
727 for(
int j = sp_starts[i], k = 0; j != sp_starts[i + 1]; j++, k++ )
729 assert(
LE(g->
prize[basetail], MIN(basecost, pr->firstneighborcosts[k])));
730 sp_dists[j] = basecost + pr->firstneighborcosts[k] - g->
prize[basetail];
733 assert(
EQ(sp_dists[sp_starts[i] + i], 2.0 * basecost - g->
prize[basetail]));
737 for(
int j = sp_starts[i], k = 0; j != sp_starts[i + 1]; j++, k++ )
738 sp_dists[j] = basecost + pr->firstneighborcosts[k];
740 assert(
EQ(sp_dists[sp_starts[i] + i], 2.0 * basecost));
744 for(
int j = sp_starts[i]; j != sp_starts[i + 1]; j++ )
745 printf(
"%d->%d dist=%f \n", i, j - sp_starts[i], sp_dists[j]);
749 sp_dists[sp_starts[i] + i] = 0.0;
752 for(
int j = dcsr_range[neighbor].start; j != dcsr_range[neighbor].
end; j++ )
754 const int head = dcsr_heads[j];
755 const int head_index = pr->nodes_index[head];
758 if( head_index < 0 || head == basetail )
761 assert(0 <= head_index && head_index < pr->nfirstneighbors);
764 if(
LT(dcsr_costs[j], sp_dists[sp_starts[i] + head_index]) )
765 printf(
"updating %d->%d distold=%f distnew=%f \n", i, head_index, sp_dists[sp_starts[i] + head_index], dcsr_costs[j]);
767 if(
LT(dcsr_costs[j], sp_dists[sp_starts[i] + head_index]) )
768 sp_dists[sp_starts[i] + head_index] = dcsr_costs[j];
772 for(
int i = 0; i < pr->nfirstneighbors; i++ )
773 pr->firstneighbors_isKilled[i] =
FALSE;
780 for(
int i = 0; i < pr->nfirstneighbors; i++ )
782 pr->firstneighborcosts[i] -= g->
prize[basetail];
783 assert(
GE(pr->firstneighborcosts[i], 0.0));
805 assert(*isExendible);
806 assert(!(*isRedundant));
808 if( npathedges >
SP_MAXLENGTH || g->
grad[pathhead] > pr->maxdegree || pr->nodes_isTerm[pathhead] )
810 *isExendible =
FALSE;
836 if( needCombRuleOut && !isCombRuledOut )
838 *isExendible =
FALSE;
844 if( !isSingleRuledOut )
846 *isExendible =
FALSE;
882 pr->useSd = (extperma !=
NULL);
897 for(
int i = 0; i <
nnodes; i++ )
903 pr->currneighbors =
NULL;
904 pr->firstneighborcosts =
NULL;
905 pr->pathedges =
NULL;
906 pr->firstneighbors =
NULL;
907 pr->visitednodes =
NULL;
908 pr->nfirstneighbors = -1;
911 StpVecReserve(scip, pr->firstneighborcosts, pr->maxdegree + 1);
928 for(
int i = 0; i < nvisited; i++ )
930 const int node = pr->visitednodes[i];
942 for(
int i = 0; i < pr->nnodes; i++ )
946 pr->sp_starts[i] = -1;
958 PR* pr = *pathreplace;
1001 const int tail = g->
tail[startedge];
1002 const int head = g->
head[startedge];
1003 const int maxdeg = pr->maxdegree;
1006 if( g->
grad[tail] > maxdeg || g->
grad[head] > maxdeg || pr->nodes_isTerm[tail] || pr->nodes_isTerm[head] )
1009 if( g->
grad[tail] <= 1 )
1014 while( pathIsExtendable )
1016 assert(!pathIsRedundant);
1017 pathExend(scip, g, pr, &pathIsExtendable, &pathIsRedundant);
1019 if( pathIsRedundant )
1050 for(
int e = 0; e < nedges; e++ )
1090 assert(scip && g && extperma);
1102 prFree(scip, &pathreplace);
1137 prFree(scip, &pathreplace);
#define STP_Vectype(type)
static void addPathHeadEdge(SCIP *scip, const GRAPH *g, PR *pr)
int graph_get_nEdges(const GRAPH *)
#define StpVecGetSize(vec)
void reduce_nodesDeg1(SCIP *, GRAPH *)
SCIP_RETCODE reduce_pathreplaceExt(SCIP *scip, GRAPH *g, EXTPERMA *extperma, int *nelims)
#define SCIPfreeMemoryArray(scip, ptr)
SCIP_Bool graph_valid(SCIP *, const GRAPH *)
SCIP_Real extreduce_distDataGetSdDoubleEq(SCIP *, const GRAPH *, SCIP_Real, int, int, DISTDATA *)
int *RESTRICT nodes_biassource2
void graph_getIsTermArray(const GRAPH *, SCIP_Bool *)
#define SCIPallocMemoryArray(scip, ptr, num)
static void ruleOutFromTailCombs(SCIP *scip, const GRAPH *g, PR *pr, SCIP_Bool *isRuledOut)
static SCIP_RETCODE prInit(SCIP *scip, const GRAPH *g, EXTPERMA *extperma, PR **pathreplace)
void graph_free_dcsr(SCIP *, GRAPH *)
struct path_replacement PR
DISTDATA * distdata_default
enum SCIP_Retcode SCIP_RETCODE
#define StpVecPopBack(vec)
static SCIP_RETCODE processPath(SCIP *scip, int startedge, PR *pr, GRAPH *g, int *nelims)
#define StpVecReserve(scip, vec, _size_)
static void pathExend(SCIP *scip, const GRAPH *g, PR *pr, SCIP_Bool *isExendible, SCIP_Bool *isRedundant)
static void addNonPathNode(SCIP *scip, int node, PR *pr)
SCIP_RETCODE graph_init_dcsr(SCIP *, GRAPH *)
static void pathExendPrepare(SCIP *scip, const GRAPH *g, int startedge, PR *pr)
static SCIP_Real getSdProfit(const SDPROFIT *sdprofit, const int *nodes_index, int node, int nonsource)
This file implements extended reduction techniques for several Steiner problems.
SCIP_Bool graph_pc_edgeIsExtended(const GRAPH *, int)
static void deletenodesDeg1(SCIP *scip, EXTPERMA *extperma, GRAPH *g)
static void prFree(SCIP *scip, PR **pathreplace)
void extreduce_edgeRemove(SCIP *, int, GRAPH *, DISTDATA *, EXTPERMA *)
void reduce_sdprofitFree(SCIP *, SDPROFIT **)
void graph_edge_delFull(SCIP *, GRAPH *, int, SCIP_Bool)
static void ruleOutFromHead(SCIP *scip, const GRAPH *g, PR *pr, SCIP_Bool *needFullRuleOut)
static void pathneighborsUpdateDistances(SCIP *scip, const GRAPH *g, PR *pr)
SCIP_Real *RESTRICT nodes_bias2
SCIP_Bool reduce_sdgraphEdgeIsInMst(const SDGRAPH *, int)
SCIP_Bool graph_pc_isPc(const GRAPH *)
SCIP_Real extreduce_distDataGetSdDoubleForbiddenSingle(SCIP *, const GRAPH *, int, int, int, DISTDATA *)
static void pathneighborsCollect(SCIP *scip, const GRAPH *g, PR *pr)
#define SCIPfreeMemory(scip, ptr)
static void addPathNode(SCIP *scip, int node, PR *pr)
static int pathGetHead(const GRAPH *g, const PR *pr)
SCIP_RETCODE reduce_pathreplace(SCIP *scip, GRAPH *g, int *nelims)
static void deleteEdge(SCIP *scip, int edge, GRAPH *g, PR *pr)
static void prClean(PR *pr)
SCIP_Bool graph_pc_knotIsDummyTerm(const GRAPH *, int)
SCIP_Real *RESTRICT nodes_bias
#define StpVecFree(scip, vec)
static SCIP_Bool prIsPromising(const GRAPH *g)
#define SP_MAXDEGREE_FAST
SCIP_RETCODE reduce_sdprofitInit(SCIP *, const GRAPH *, SDPROFIT **)
int *RESTRICT nodes_biassource
int graph_get_nNodes(const GRAPH *)
#define SCIPallocMemory(scip, ptr)
static SCIP_RETCODE pathreplaceExec(SCIP *scip, PR *pr, GRAPH *g, int *nelims)
#define StpVecPushBack(scip, vec, value)
static void ruleOutFromTailSingle(SCIP *scip, const GRAPH *g, PR *pr, SCIP_Bool *isRuledOut)
includes various reduction methods for Steiner tree problems
static void addInitialPathNodes(SCIP *scip, const GRAPH *g, int startedge_tail, int startdege_head, PR *pr)