44 #define DEFAULT_HEURRUNS 100 45 #define DEFAULT_DARUNS 7 46 #define DEFAULT_NMAXROOTS 8 47 #define PERTUBATION_RATIO 0.05 48 #define PERTUBATION_RATIO_PC 0.005 49 #define SOLPOOL_SIZE 20 50 #define STP_RED_MINBNDTERMS 750 51 #define STP_DABD_MAXDEGREE 5 52 #define STP_DABD_MAXDNEDGES 10 53 #define STP_DAEX_MAXDFSDEPTH 6 54 #define STP_DAEX_MINDFSDEPTH 4 55 #define STP_DAEX_MAXGRAD 8 56 #define STP_DAEX_MINGRAD 6 57 #define STP_DAEX_EDGELIMIT 50000 58 #define DAMAXDEVIATION_RANDOM_LOWER 0.15 59 #define DAMAXDEVIATION_RANDOM_UPPER 0.30 60 #define DAMAXDEVIATION_FAST 0.75 63 #define EXEDGE_FIXED 1 64 #define EXEDGE_KILLED 2 78 for(
IDX* curr = graph->
ancestors[edge]; curr !=
NULL && count <= STP_DAEX_MAXGRAD; curr = curr->parent, count++ )
80 const unsigned idx = ((unsigned) curr->index) / 2;
82 assert(curr->index >= 0 && idx < (
unsigned) (
MAX(graph->
edges, graph->
orgedges) / 2));
84 if( ancestormark[idx] )
87 ancestormark[idx] = 1;
105 for(
IDX* curr = graph->
ancestors[edge]; curr !=
NULL && count <= STP_DAEX_MAXGRAD; curr = curr->parent, count++ )
107 assert(curr->index >= 0 && curr->index / 2 < (
MAX(graph->
edges, graph->
orgedges) / 2));
108 assert((ancestormark[((
unsigned) curr->index) / 2]) == 0);
110 ancestormark[((unsigned) curr->index) / 2] = 1;
125 for(
IDX* curr = graph->
ancestors[edge]; curr !=
NULL && count <= STP_DAEX_MAXGRAD; curr = curr->parent, count++ )
127 assert(curr->index >= 0 && curr->index / 2 < (
MAX(graph->
edges, graph->
orgedges) / 2));
128 ancestormark[((unsigned) curr->index) / 2] = 0;
143 for(
IDX* curr = graph->
ancestors[edge]; curr !=
NULL && count <= STP_DAEX_MAXGRAD; curr = curr->parent, count++ )
145 const unsigned idx = ((unsigned) curr->index) / 2;
147 assert(curr->index >= 0 && curr->index / 2 < (
MAX(graph->
edges, graph->
orgedges) / 2));
148 assert(ancestormark[idx] == 1);
150 ancestormark[idx] = 0;
160 const int* treeedges,
171 if( localbound > *globalbound )
172 *globalbound = localbound;
179 for(
int etree = 0; etree < dfsdepth; etree++ )
181 const int node = edgeends[treeedges[etree]];
182 assert(nodepos[node]);
189 assert(dfsdepth == 0);
207 if(
Is_term(graph->
term[currhead]) || graph->
grad[currhead] > maxgrad || dfsdepth >= maxdfsdepth )
210 if( root != currhead )
213 if( extendedcost < *minbound )
214 *minbound = extendedcost;
224 int reduceAndExtendSubtree(
227 const int* graph_start,
228 const int* graph_next,
229 const int* graph_endp,
234 unsigned char* extensionmark
237 int n = nadded_edges;
242 for(
int e = graph_start[currnode]; e !=
EAT_LAST; e = graph_next[e] )
243 if( !nodepos[graph_endp[e]] )
247 const int vertex_exnew = graph_endp[e];
254 const int head = graph->
head[e2];
257 if( nodepos[head] < 0 )
259 const int stackposition = (-nodepos[head]) - 1;
260 const int edge_exold = edgestack[stackposition];
265 assert(edge_exold >= 0);
266 assert(e != e2 && e != edge_exold && edge_exold != e2);
268 if( (
SCIPisLT(scip, cost_alt, cost_exold) ||
SCIPisLT(scip, cost_alt, cost_exnew)) )
271 if( cost_exold <= cost_exnew && extensionmark[n - start] ==
EXEDGE_FREE )
273 assert(stackposition >= start);
281 if( cost_exold >= cost_exnew && extensionmark[stackposition - start] ==
EXEDGE_FREE )
286 assert(head == graph->
head[edge_exold]);
299 assert(nodepos[vertex_exnew] == 0);
300 nodepos[vertex_exnew] = -n;
304 for(
int i = start; i < n; i++ )
306 const int edge = edgestack[i];
309 assert(nodepos[graph->
head[edge]] <= 0);
310 assert(nodepos[graph->
head[edge]] < 0 || (extensionmark[i - start] ==
EXEDGE_KILLED));
312 nodepos[graph->
head[edge]] = 0;
318 for(
int i = start; i < n; i++ )
320 edgestack[newn++] = edgestack[i];
338 const int* treeedges,
345 unsigned int* nstallrounds
348 const int lastedge = treeedges[dfsdepth - 1];
350 assert(dfsdepth >= 1 && lastnode >= 0);
351 assert(
SCIPisGE(scip, treecostold, 0.0) && treecostoffset >= 0.0);
353 nodepos[lastnode] = 0;
357 if( (*nstallrounds)++ >= 9 )
363 for(
int i = 0; i < dfsdepth - 1; i++ )
364 treecost += redcost[treeedges[i]];
366 #if 0 // todo deleteeme 367 if( !
SCIPisEQ(scip, treecost, treecostold - redcost[lastedge]) )
369 printf(
"%.15f %.15f \n", treecost, treecostold - redcost[lastedge]);
375 assert(
SCIPisEQ(scip, treecost, treecostold - redcost[lastedge]));
378 return (treecostold - redcost[lastedge]);
399 int n = nadded_edges + 1;
400 nodepos[currhead] = dfsdepth + 1;
401 *treecost += redcost[curredge];
402 treeedges[dfsdepth] = curredge;
403 treecosts[dfsdepth] = graph->
cost[curredge];
408 if( !nodepos[graph->
head[e]] )
431 int n = nadded_edges + 1;
432 nodepos[currtail] = dfsdepth + 1;
433 *treecost += redcost[curredge];
434 treeedges[dfsdepth] = curredge;
435 treecosts[dfsdepth] = graph->
cost[curredge];
440 if( !nodepos[graph->
tail[e]] )
451 unsigned int* eqstack,
456 const unsigned int halfedge = ((
unsigned int) edge) / 2;
460 if( !eqmark[halfedge] )
462 eqmark[halfedge] =
TRUE;
463 eqstack[*eqstack_size] = halfedge;
465 *eqstack_size = *eqstack_size + 1;
478 const int* treeedges,
485 unsigned int* eqstack,
492 assert(!allow_eq ||(eqstack !=
NULL && eqstack_size !=
NULL && eqmark !=
NULL));
496 if(
SCIPisLE(scip, extedgecost, orgedgecost) )
498 if(
SCIPisEQ(scip, extedgecost, orgedgecost) )
504 else if(
SCIPisLT(scip, extedgecost, orgedgecost) )
507 if( nodepos[graph->
tail[extedge]] > graph->
knots )
509 start = nodepos[graph->
tail[extedge]] - 1 - graph->
knots;
510 assert(start >= 0 && start <= 3);
514 assert(basebottlenecks[start] > 0);
516 if(
SCIPisLT(scip, extedgecost, basebottlenecks[start]) )
523 start = nodepos[graph->
tail[extedge]];
524 assert(start >= 1 && start <= dfsdepth);
525 assert(start < dfsdepth || graph->tail[orgedge] == graph->
tail[extedge]);
529 for(
int i = start; i < dfsdepth; i++ )
531 assert(treecosts[i] >= 0.0);
535 if(
SCIPisLE(scip, extedgecost, treecosts[i]) )
537 if(
SCIPisEQ(scip, extedgecost, treecosts[i]) )
543 else if(
SCIPisLT(scip, extedgecost, treecosts[i]) )
558 const int* treeedges,
564 const int* ancestormark,
565 unsigned int* eqstack,
570 if( allowequality ? (extendedcost >= cutoff) :
SCIPisGT(scip, extendedcost, cutoff) )
579 if( ancestormark !=
NULL )
582 for(
IDX* curr = graph->
ancestors[curredge]; curr !=
NULL && count <= STP_DAEX_MAXGRAD; curr = curr->parent, count++ )
584 assert(curr->index >= 0 && curr->index / 2 < (
MAX(graph->
edges, graph->
orgedges) / 2));
585 if( ancestormark[((
unsigned) curr->index) / 2] )
590 currcost = graph->
cost[curredge];
591 currhead = graph->
head[curredge];
603 tail = graph->
tail[e];
604 ecost = graph->
cost[e];
610 if(
bottleneckRuleOut(scip, graph, treecosts, basebottlenecks, nodepos, treeedges, currcost,
611 ecost, curredge, e, dfsdepth, allow_eq, eqstack, eqstack_size, eqmark) )
619 e2 = graph->
oeat[e2], count++ )
628 head2 = graph->
head[e2];
629 assert(head2 != tail);
634 const SCIP_Bool allow_eq = (eqmark !=
NULL && eqmark[((unsigned) e) / 2] ==
FALSE && eqmark[((unsigned) e2) / 2] ==
FALSE);
636 assert(head2 != currhead);
639 nodepos, treeedges, currcost, extcost, curredge,
flipedge(e2), dfsdepth, allow_eq, eqstack, eqstack_size, eqmark) )
668 for(
int k = 0; k <
nnodes; k++ )
671 for(
int k = 0; k <
nnodes; k++ )
675 if( !graph->
mark[k] )
680 fixbnd = pathdist[k] + vnoi[k].
dist + lpobjval;
682 if( fixbnd > fixingbounds[k] )
683 fixingbounds[k] = fixbnd;
705 unsigned int* eqstack =
NULL;
709 const SCIP_Real cutoff = upperbound - lpobjval;
710 const int halfnedges = graph->
edges / 2;
716 for(
int k = 0; k <
nnodes; k++ )
725 for(
int node = 0; node <
nnodes; node++ )
727 const int degree = graph->
grad[node];
734 if(
SCIPisLT(scip, upperbound, replacebounds[node]) )
737 fixbnd = pathdist[node] + vnoi[node].
dist + vnoi[node +
nnodes].
dist + lpobjval;
744 int eqstack_size = 0;
750 outedges[edgecount++] = e;
752 assert(edgecount == degree);
755 for(
int i = 0; i < degree; i++ )
757 const int tmproot = graph->
head[outedges[i]];
758 const int rootedge =
flipedge(outedges[i]);
761 for(
int j = i + 1; j <= i + degree - 2; j++ )
763 for(
int k = j + 1; k <= i + degree - 1; k++ )
765 const int outedge1 = outedges[j % degree];
766 const int outedge2 = outedges[k % degree];
767 const int leaf1 = graph->
head[outedge1];
768 const int leaf2 = graph->
head[outedge2];
772 assert(leaf1 != leaf2 && tmproot != leaf1 && tmproot != leaf2);
773 assert(vbase[leaf1] >= 0 || vnoi[leaf1].dist >=
FARAWAY);
774 assert(vbase[leaf2] >= 0 || vnoi[leaf2].dist >=
FARAWAY);
776 if( leaf1 == root || leaf2 == root )
779 tmpcostY = pathdist[tmproot] + cost[rootedge] + cost[outedge1] + cost[outedge2];
781 if( vbase[leaf1] != vbase[leaf2] )
783 tmpcostY += vnoi[leaf1].
dist + vnoi[leaf2].
dist;
791 assert(vbase[leaf1 + nnodes] >= 0 || leaf1far ==
FARAWAY);
792 assert(vbase[leaf2 + nnodes] >= 0 || leaf2far ==
FARAWAY);
794 tmpcostY += MIN(leaf1far + vnoi[leaf2].dist, vnoi[leaf1].dist + leaf2far);
797 if( tmpcostY < fixbnd )
799 if( extendedsearch &&
SCIPisLE(scip, tmpcostY, cutoff) )
801 int tree3outedges[2];
806 tree3outedges[0] = outedge1;
807 tree3outedges[1] = outedge2;
809 SCIP_CALL(
reduce_check3Tree(scip, graph, root, cost, pathdist, vnoi, vbase, cutoff, tree3outedges, rootedge, nodearrint,
810 &tmpcostY, &ruleout, eqstack, &eqstack_size, eqmark) );
816 assert(tmpcostY >= tmpcostYorg);
820 if( tmpcostY < fixbnd )
829 assert(
SCIPisGE(scip, fixbnd, pathdist[node] + vnoi[node].dist + vnoi[node + nnodes].dist + lpobjval)
834 for(
int i = 0; i < eqstack_size; i++ )
835 eqmark[eqstack[i]] =
FALSE;
837 for(
int i = 0; i < halfnedges; i++ )
838 assert(eqmark[i] ==
FALSE);
842 if( fixbnd > replacebounds[node] )
843 replacebounds[node] = fixbnd;
848 assert(eqstack !=
NULL && eqmark !=
NULL);
874 assert(extnedges > 0);
877 for(
int e = 0; e < extnedges; e++ )
880 for(
int k = 0; k <
nnodes; k++ )
882 if( !graph->
mark[k] )
891 const int head = graph->
head[e];
893 if( graph->
mark[head] )
896 const SCIP_Real fixbnd = pathdist[k] + cost[e] + vnoi[head].
dist + lpobjval;
897 const SCIP_Real fixbndrev = pathdist[head] + cost[erev] + vnoi[k].
dist + lpobjval;
898 const SCIP_Real minbnd = MIN(fixbnd, fixbndrev);
900 assert(fixingbounds[e] == fixingbounds[erev]);
902 if( minbnd > fixingbounds[e] )
904 fixingbounds[e] = minbnd;
905 fixingbounds[erev] = minbnd;
914 const int head = graph->
head[e];
916 if( graph->
mark[head] )
918 const SCIP_Real fixbnd = pathdist[k] + cost[e] + vnoi[head].
dist + lpobjval;
920 if( fixbnd > fixingbounds[e] )
921 fixingbounds[e] = fixbnd;
943 for(
int k = 0; k <
nnodes; k++ )
950 if(
SCIPisLT(scip, upperbound, fixingbounds[k]) )
952 SCIPdebugMessage(
"delete knot %d %f < %f %d\n", k, upperbound, fixingbounds[k], graph->
grad[k]);
955 if( transgraph !=
NULL )
981 for(
int k = 0; k <
nnodes; k++ )
987 for(
int k = 0; k <
nnodes; k++ )
992 if(
SCIPisLT(scip, upperbound, replacebounds[k]) && nodetouched[k] == 0 )
998 nodetouched[graph->
head[e]]++;
1003 adjvert[edgecount++] = graph->
head[e];
1005 assert(edgecount == degree);
1008 for(
int i = 0; i < degree - 1; i++ )
1010 const int vert = adjvert[i];
1011 for(
int i2 = i + 1; i2 < degree; i2++ )
1013 const int vert2 = adjvert[i2];
1017 cutoffs[edgecount] = upperbound - lpobjval - (pathdist[vert] + vnoi[vert2].
dist);
1018 cutoffsrev[edgecount] = upperbound - lpobjval - (pathdist[vert2] + vnoi[vert].
dist);
1024 assert(edgecount > 0);
1034 assert(graph->
grad[k] == degree);
1038 nodetouched[graph->
head[e]]--;
1039 assert(nodetouched[graph->
head[e]] >= 0);
1066 for(
int k = 0; k <
nnodes; k++ )
1069 if( !graph->
mark[k] )
1077 const int enext = graph->
oeat[e];
1084 if( !solgiven || result[e] ==
CONNECT || result[erev] ==
CONNECT )
1085 delete = (
SCIPisLT(scip, upperbound, fixingbounds[e]) &&
SCIPisLT(scip, upperbound, fixingbounds[erev]));
1087 delete = (upperbound <= fixingbounds[e] && upperbound <= fixingbounds[erev]);
1094 if( transgraph !=
NULL )
1113 const GRAPH* transgraph,
1131 const int root = graph->
source;
1134 int nroots = *rootscount;
1141 assert(rerun || nroots == 0);
1150 for(
int i = 0; i < nroots; i++ )
1151 nodearrchar[roots[i]] =
TRUE;
1155 const int transroot = transgraph->
source;
1161 const int pseudoterm = transgraph->
head[e];
1166 assert(transgraph->
tail[transgraph->
term2edge[pseudoterm]] == pseudoterm);
1168 realterm = transgraph->
head[transgraph->
term2edge[pseudoterm]];
1171 if( rerun && nodearrchar[realterm] )
1174 if(
SCIPisGT(scip, cost[e], upperbound - lpobjval) ||
SCIPisGT(scip, bestcost[e], upperbound - bestlpobjval) )
1177 assert(nroots < graph->terms);
1179 roots[nroots++] = realterm;
1180 nodearrchar[realterm] =
TRUE;
1189 const int pseudoterm = graph->
head[e];
1196 assert(graph->
grad[pseudoterm] == 2);
1198 for(
int e2 = transgraph->
inpbeg[pseudoterm]; e2 !=
EAT_LAST; e2 = transgraph->
ieat[e2] )
1200 if( transgraph->
cost[e2] == 0.0 )
1201 realterm = transgraph->
tail[e2];
1206 if( rerun && nodearrchar[realterm] )
1209 assert(realterm >= 0);
1211 assert(realterm != root);
1213 assert(graph->
mark[realterm]);
1215 if(
SCIPisGT(scip, cost[e3], upperbound - lpobjval) ||
SCIPisGT(scip, bestcost[e3], upperbound - bestlpobjval) )
1218 assert(nroots < graph->terms);
1220 roots[nroots++] = realterm;
1221 nodearrchar[realterm] =
TRUE;
1228 if( nroots > *rootscount && graph->
terms > 2 )
1235 int qstart = *rootscount;
1237 for(
int i = 0; i <
nnodes; i++ )
1243 if(
Is_term(graph->
term[i]) && !nodearrchar[i] && graph->
mark[i] && maxprize < graph->prize[i] && graph->
prize[i] < prizesum )
1244 maxprize = graph->
prize[i];
1247 for(
int rounds = 0; rounds < 10 && qstart != nroots; rounds++ )
1249 const int oldnroots = nroots;
1253 for(
int i = qstart; i < nroots; i++ )
1256 const int term = roots[i];
1257 assert(nodearrchar[term]);
1262 graph_sdPaths(scip, graph, vnoi, graph->
cost, maxprize, pathedge, state, vbase, &nlabeled, term, term, 200);
1265 for(
int k = 0; k < nlabeled; k++ )
1267 const int l = vbase[k];
1269 assert(graph->
mark[l]);
1274 roots[nroots++] = l;
1275 nodearrchar[l] =
TRUE;
1287 for(
int k = 0; k <
nnodes; k++ )
1290 assert(vnoi[k].dist ==
FARAWAY);
1291 assert(vnoi[k].edge ==
UNKNOWN);
1303 *rootscount = nroots;
1323 const int root = graph->
source;
1329 if( *userec && *solpool !=
NULL )
1336 assert(graph !=
NULL);
1337 assert(roots !=
NULL);
1339 assert(nrootsnew >= 0 && nrootsold >= 0);
1341 for(
int i = nrootsold; i < nrootsnew; i++ )
1344 const int term = roots[i];
1353 if( root == graph->
tail[e] )
1359 graph->
prize[term] = prizesum;
1360 graph->
cost[e] = prizesum;
1377 int*
const queue = nodearrint;
1380 const int root = transgraph->
source;
1390 visited[root] =
TRUE;
1391 queue[qsize++] = root;
1396 const int k = queue[--qsize];
1401 const int head = transgraph->
head[
a];
1405 visited[head] =
TRUE;
1406 queue[qsize++] = head;
1409 assert(qsize <= nnodes);
1412 for(
int k = 0; k <
nnodes; k++ )
1434 const int root = graph->
source;
1435 const int newroot = transgraph->
source;
1437 const int nedges = graph->
edges;
1442 for( e = 0; e < nedges; e++ )
1443 if( result[e] ==
CONNECT && graph->
tail[e] != root )
1444 nodearrchar[graph->
head[e]] =
TRUE;
1445 srand((
unsigned)graph->
terms);
1451 for(
int k = 0; k <
nnodes; k++ )
1456 pratio = ((
SCIP_Real)(rand() % 10)) / (100.0) - 1.0 / 100.0;
1457 else if( randomize > 6 )
1458 pratio = ((
SCIP_Real)(rand() % 10)) / (200.0);
1459 else if( randomize > 4 )
1460 pratio = ((
SCIP_Real)(rand() % 10)) / (300.0);
1461 else if( randomize > 0 )
1462 pratio = ((
SCIP_Real)(rand() % 10)) / 1000.0;
1473 assert(transgraph->
tail[e] != root);
1476 transgraph->
cost[e] *= 1.0 - pratio;
1478 transgraph->
cost[e] *= 1.0 + pratio;
1481 else if(
Is_term(transgraph->
term[k]) && k != root && k != newroot )
1483 assert(transgraph->
grad[k] == 2);
1489 assert(transgraph->
tail[e] != root);
1493 transgraph->
cost[e] *= 1.0 - pratio;
1495 transgraph->
cost[e] *= 1.0 + pratio;
1505 for(
int k = 0; k <
nnodes; k++ )
1512 pratio = ((
SCIP_Real)(rand() % 10)) / (50.0) - 1.0 / 10.0;
1513 else if( randomize > 6 )
1514 pratio = ((
SCIP_Real)(rand() % 10)) / (20.0);
1515 else if( randomize > 4 )
1516 pratio = ((
SCIP_Real)(rand() % 10)) / (30.0);
1517 else if( randomize > 0 )
1518 pratio = ((
SCIP_Real)(rand() % 10)) / 100.0;
1524 if( nodearrchar[k] )
1527 transgraph->
cost[e] *= 1.0 - pratio;
1532 transgraph->
cost[e] *= 1.0 + pratio;
1535 else if(
Is_term(transgraph->
term[k]) && k != root && k != newroot )
1537 assert(transgraph->
grad[k] == 2);
1539 if( nodearrchar[k] )
1546 transgraph->
cost[e] *= 1.0 + pratio;
1555 transgraph->
cost[e] *= 1.0 - pratio;
1576 assert(terms !=
NULL);
1581 for(
int i = 0; i <
nterms; i++ )
1583 const int grad = graph->
grad[terms[i]];
1584 assert(terms[i] >= 0);
1586 termdegs[i] = -grad;
1589 maxdeg = termdegs[i];
1593 for(
int i = 0; i <
nterms; i++ )
1623 const int nedges = graph->
edges;
1637 SCIPdebugMessage(
"DA: first new sol value in computeDaSolPcMw: %f ... old value: %f \n", ub, *upperbound);
1646 for(
int i = 0; i < pool->
size; i++ )
1648 printf(
" %f ", pool->
sols[i]->
obj);
1653 if( success && pool->
size >= 2 )
1662 SCIP_CALL(
SCIPStpHeurRecRun(scip, pool,
NULL,
NULL, graph,
NULL, &solindex, 3, pool->
size,
FALSE, &solfound) );
1668 assert(pool->
size >= 2);
1669 assert(sol !=
NULL);
1687 if(
SCIPisLE(scip, ub, *upperbound) )
1689 SCIPdebugMessage(
"DA: improved incumbent %f vs %f, return \n", ub, *upperbound);
1746 const int root = graph->
source;
1747 const int nedges = graph->
edges;
1748 const int transnedges = transgraph->
edges;
1775 if(
SCIPisLE(scip, bound, *upperbound) )
1777 *upperbound =
bound;
1789 SCIP_CALL(
SCIPStpDualAscent(scip, transgraph, cost, pathdist, &lb,
FALSE,
FALSE, gnodearr,
NULL, transresult, state, root,
TRUE, -1.0, nodearrchar) );
1796 SCIP_CALL(
computeDaSolPcMw(scip, graph, pool, vnoi, cost, pathdist, upperbound, result, result2, vbase, pathedge, nodearrchar, apsol) );
1808 for( e = nedges; e < transnedges; e++ )
1828 if( transgraph->
head[e] == graph->
knots )
1838 assert(root == transgraph->
source);
1840 SCIP_CALL(
SCIPStpDualAscent(scip, transgraph, cost, pathdist, &lb,
FALSE,
FALSE, gnodearr, transresult,
NULL, state, root,
TRUE, -1.0, nodearrchar) );
1845 SCIP_CALL(
computeDaSolPcMw(scip, graph, pool, vnoi, cost, pathdist, upperbound, result, result2, vbase, pathedge, nodearrchar, apsol) );
1849 if(
SCIPisGE(scip, lb, *bestlpobjval) )
1856 *minpathcost = *upperbound - *lpobjval;
1874 const int root = transgraph->
source;
1875 const int transnnodes = transgraph->
knots;
1876 const int transnedges = transgraph->
edges;
1878 for(
int k = 0; k < transnnodes; k++ )
1879 transgraph->
mark[k] = (transgraph->
grad[k] > 0);
1884 for(
int k = 0; k < transnnodes; k++ )
1886 assert(
SCIPisEQ(scip, pathdist[k], 0.0));
1888 for(
int e = 0; e < transnedges; e++ )
1918 const int nedges = graph->
edges;
1925 for(
int k = 0; k <
nnodes; k++ )
1926 nodearrchar[k] =
FALSE;
1927 for(
int e = 0; e < nedges; e++ )
1931 nodearrchar[graph->
tail[e]] =
TRUE;
1932 nodearrchar[graph->
head[e]] =
TRUE;
1941 for(
int k = 0; k <
nnodes; k++ )
1946 if( !graph->
mark[k] )
1951 redcost = pathdist[k] + vnoi[k].
dist;
1955 (*offset) += graph->
prize[k];
1961 (
SCIPisGT(scip, redcost, minpathcost) || (solgiven &&
SCIPisEQ(scip, redcost, minpathcost) && !nodearrchar[k])) )
1963 nfixed += graph->
grad[k];
1971 const int head = graph->
head[e];
1972 const int enext = graph->
oeat[e];
1975 if( (rpc && !graph->
mark[head])
1982 redcost = pathdist[k] + cost[e] + vnoi[head].
dist;
1984 if(
SCIPisGT(scip, redcost, minpathcost)
2001 for(
int k = 0; k <
nnodes; k++ )
2002 if( graph->
grad[k] == 0 && k != root )
2029 assert(scip !=
NULL);
2030 assert(graph !=
NULL);
2031 assert(pathdist !=
NULL);
2032 assert(result !=
NULL);
2033 assert(cost !=
NULL);
2034 assert(vnoi !=
NULL);
2036 assert(
SCIPisGE(scip, minpathcost, 0.0));
2039 if( minpathcost < 0.0 )
2043 nnodes = graph->
knots;
2049 const int nedges = graph->
edges;
2051 for(
int k = 0; k <
nnodes; k++ )
2052 nodearrchar[k] =
FALSE;
2054 for(
int e = 0; e < nedges; e++ )
2060 nodearrchar[graph->
head[e]] =
TRUE;
2061 nodearrchar[graph->
tail[e]] =
TRUE;
2069 for(
int k = 0; k <
nnodes; k++ )
2071 if( !graph->
mark[k] )
2078 int e = graph->
outbeg[k];
2081 const int etmp = graph->
oeat[e];
2082 tmpcost = pathdist[k] + cost[e] + vnoi[graph->
head[e]].
dist;
2106 tmpcost = pathdist[k] + vnoi[k].
dist;
2108 if( (
SCIPisGT(scip, tmpcost, minpathcost) && !keepsol) ||
2109 (solgiven && tmpcost >= minpathcost && !nodearrchar[k]))
2113 const int e = transgraph->
outbeg[k];
2123 int e = transgraph->
outbeg[k];
2126 const int etmp = transgraph->
oeat[e];
2127 tmpcost = pathdist[k] + cost[e] + vnoi[transgraph->
head[e]].
dist;
2150 for(
int k = 0; k <
nnodes; k++ )
2151 if( graph->
grad[k] == 0 && k != graph->
source )
2187 *bestlpobjval = *lpobjval;
2192 if(
SCIPisGT(scip, *bestlpobjval, *lpobjval) &&
SCIPisLT(scip, *upperbound, oldupperbound) )
2198 *minpathcost = *upperbound - *bestlpobjval;
2199 assert(
SCIPisGE(scip, *minpathcost, 0.0));
2201 computeTransVoronoi(scip, transgraph, vnoi, bestcost, costrev, pathdist, vbase, pathedge);
2203 return reducePcMw(scip, graph, transgraph, vnoi, bestcost, pathdist, *minpathcost, result, marked, nodearrchar, *solgiven);
2223 unsigned int* eqstack,
2228 const int head = graph->
head[edge];
2229 const int tail = graph->
tail[edge];
2231 SCIP_Real edgebound = redcost[edge] + pathdist[tail] + vnoi[head].
dist;
2233 assert(scip !=
NULL);
2234 assert(graph !=
NULL);
2235 assert(redcost !=
NULL);
2236 assert(pathdist !=
NULL);
2237 assert(vnoi !=
NULL);
2238 assert(edge >= 0 && edge < graph->edges);
2243 if(
SCIPisGT(scip, edgebound, cutoff) || (equality &&
SCIPisEQ(scip, edgebound, cutoff)) || head == root )
2247 else if( (graph->
grad[tail] <= maxgrad && !
Is_term(graph->
term[tail]))
2263 basebottlenecks[0] = graph->
cost[edge];
2265 basebottlenecks[1] = -1.0;
2266 basebottlenecks[2] = -1.0;
2270 treecosts[i] = -1.0;
2280 const SCIP_Real treecostoffset = redcost[edge] + pathdist[tail];
2283 unsigned int rounds = 0;
2285 int nadded_edges = 0;
2288 nodepos[tail] = nnodes + 1;
2289 nodepos[head] = nnodes + 4;
2292 if( graph->
head[e] != tail )
2293 edgestack[nadded_edges++] = e;
2296 while( nadded_edges > 0 )
2298 const int curredge = edgestack[--nadded_edges];
2299 const int currhead = graph->
head[curredge];
2302 if( nodepos[currhead] )
2304 assert(dfsdepth >= 1 && treeedges[dfsdepth - 1] == curredge);
2306 treecost =
shortenSubtree(scip, graph, redcost, treeedges, treecost, treecostoffset, dfsdepth,
2307 currhead, nodepos, ancestormark, &rounds);
2313 const SCIP_Real extendedcost = treecost + redcost[curredge] + vnoi[currhead].
dist;
2315 if(
ruleOutSubtree(scip, graph, treecosts, basebottlenecks, nodepos, treeedges, cutoff, extendedcost, dfsdepth, curredge, equality,
2316 ancestormark, eqstack, eqstack_size, eqmark) )
2319 if(
truncateSubtree(graph, extendedcost, root, currhead, maxgrad, dfsdepth, maxdfsdepth, &minbound, &stopped) )
2322 if( stopped && minbound <= edgebound )
2328 nadded_edges =
extendSubtreeHead(scip, graph, redcost, curredge, currhead, dfsdepth, nadded_edges, &treecost, treecosts, nodepos,
2329 treeedges, edgestack, ancestormark);
2334 assert(stopped || minbound ==
FARAWAY);
2335 assert(
SCIPisGE(scip, minbound, redcost[edge] + pathdist[tail] + vnoi[head].dist));
2337 finalizeSubtree(graph, graph->
head, treeedges, dfsdepth, stopped, minbound, &edgebound, deletable, nodepos, ancestormark);
2341 if( !(*deletable) && !
Is_term(graph->
term[tail]) && graph->
grad[tail] <= maxgrad )
2343 const SCIP_Real treecostoffset = edgebound - pathdist[tail];
2347 int nadded_edges = 0;
2348 unsigned int rounds = 0;
2351 nodepos[head] = nnodes + 1;
2352 nodepos[tail] = nnodes + 4;
2355 if( graph->
tail[e] != head )
2356 edgestack[nadded_edges++] = e;
2359 while( nadded_edges > 0 )
2361 const int curredge = edgestack[--nadded_edges];
2362 const int currtail = graph->
tail[curredge];
2365 if( nodepos[currtail] )
2367 assert(dfsdepth >= 1 && treeedges[dfsdepth - 1] == curredge);
2369 treecost =
shortenSubtree(scip, graph, redcost, treeedges, treecost, treecostoffset, dfsdepth,
2370 currtail, nodepos, ancestormark, &rounds);
2376 const SCIP_Real extendedcost = treecost + redcost[curredge] + pathdist[currtail];
2378 if(
ruleOutSubtree(scip, graph, treecosts, basebottlenecks, nodepos, treeedges, cutoff, extendedcost, dfsdepth,
flipedge((
unsigned)curredge), equality,
2379 ancestormark, eqstack, eqstack_size, eqmark) )
2382 if(
truncateSubtree(graph, extendedcost, -1, currtail, maxgrad, dfsdepth, maxdfsdepth, &minbound, &stopped) )
2389 nadded_edges =
extendSubtreeTail(graph, redcost, curredge, currtail, dfsdepth, nadded_edges, &treecost, treecosts, nodepos, treeedges,
2390 edgestack, ancestormark);
2395 assert(stopped || minbound ==
FARAWAY);
2396 assert(
SCIPisGE(scip, minbound, redcost[edge] + pathdist[tail] + vnoi[head].dist));
2398 finalizeSubtree(graph, graph->
tail, treeedges, dfsdepth, stopped, minbound, &edgebound, deletable, nodepos, ancestormark);
2407 for(
int i = 0; i <
nnodes; i++ )
2408 assert(nodepos[i] == 0);
2410 assert(ancestormark[i] == 0);
2427 const int nedges = g->
edges;
2435 for(
int e = 0; e < nancestors; e++ )
2436 edgemark[e] =
FALSE;
2438 for(
int e = 0; e < nedges; e += 2 )
2473 const int* outedges,
2478 unsigned int* eqstack,
2484 const SCIP_Real orgtreebound = *treebound;
2486 assert(scip !=
NULL);
2487 assert(graph !=
NULL);
2488 assert(redcost !=
NULL);
2489 assert(ruleout !=
NULL);
2490 assert(pathdist !=
NULL);
2491 assert(vnoi !=
NULL);
2492 assert(vbase !=
NULL);
2493 assert(outedges !=
NULL);
2494 assert(inedge >= 0 && outedges[0] >= 0 && outedges[1] >= 0);
2495 assert(inedge < graph->edges && outedges[0] < graph->
edges && outedges[1] < graph->
edges);
2498 if(
SCIPisGT(scip, *treebound, cutoff) )
2507 const SCIP_Real basecost = redcost[inedge] + redcost[outedges[0]] + redcost[outedges[1]] + pathdist[graph->
tail[inedge]];
2511 const int innode = graph->
tail[inedge];
2512 const int basenode = graph->
head[inedge];
2516 assert(basenode == graph->
tail[outedges[0]] && basenode == graph->
tail[outedges[1]]);
2522 nodepos[basenode] = nnodes + 1;
2523 nodepos[innode] = nnodes + 2;
2528 treecosts[i] = -1.0;
2544 for(
int i = 0; i < 2 && !(*ruleout); i++ )
2548 const int startedge = outedges[i];
2549 const int costartedge = outedges[(i + 1) % 2];
2550 const int startnode = graph->
head[startedge];
2551 const int costartnode = graph->
head[costartedge];
2553 int nadded_edges = 0;
2555 unsigned int rounds = 0;
2559 assert(startnode != root && costartnode != root);
2562 basebottlenecks[0] = graph->
cost[startedge];
2565 basebottlenecks[1] =
MAX(graph->
cost[startedge], graph->
cost[inedge]);
2568 basebottlenecks[2] =
MAX(graph->
cost[startedge], graph->
cost[costartedge]);
2570 nodepos[costartnode] = nnodes + 3;
2571 nodepos[startnode] = nnodes + 4;
2574 if(
ruleOutSubtree(scip, graph, treecosts, basebottlenecks, nodepos, treeedges,
FARAWAY, 0.0, 0, startedge,
FALSE,
2582 if(
Is_term(graph->
term[startnode]) || graph->
grad[startnode] > maxgrad )
2585 assert(nodepos[startnode]);
2588 if( !nodepos[graph->
head[e]] )
2589 edgestack[nadded_edges++] = e;
2592 while ( nadded_edges > 0 )
2594 const int curredge = edgestack[--nadded_edges];
2595 const int currhead = graph->
head[curredge];
2598 if( nodepos[currhead] )
2600 assert(dfsdepth >= 1 && treeedges[dfsdepth - 1] == curredge);
2602 treecost =
shortenSubtree(scip, graph, redcost, treeedges, treecost, basecost, dfsdepth,
2603 currhead, nodepos, ancestormark, &rounds);
2609 SCIP_Real extendedcost = treecost + redcost[curredge];
2611 if( vbase[costartnode] == vbase[currhead] )
2617 assert(vbase[costartnode + nnodes] >= 0 || costartfar ==
FARAWAY);
2618 assert(vbase[currhead + nnodes] >= 0 || currentfar ==
FARAWAY);
2619 extendedcost += MIN(costartfar + vnoi[currhead].dist, vnoi[costartnode].dist + currentfar);
2622 extendedcost += vnoi[costartnode].
dist + vnoi[currhead].
dist;
2625 if(
ruleOutSubtree(scip, graph, treecosts, basebottlenecks, nodepos, treeedges, cutoff, extendedcost, dfsdepth, curredge,
FALSE,
2626 ancestormark, eqstack, eqstack_size, eqmark) )
2630 if(
truncateSubtree(graph, extendedcost, root, currhead, maxgrad, dfsdepth, maxdfsdepth, &minbound, &stopped) )
2632 if( stopped && minbound <= (*treebound) )
2638 nadded_edges =
extendSubtreeHead(scip, graph, redcost, curredge, currhead, dfsdepth, nadded_edges, &treecost, treecosts, nodepos,
2639 treeedges, edgestack, ancestormark);
2644 assert(stopped || minbound ==
FARAWAY);
2646 assert(
SCIPisGE(scip, minbound, orgtreebound));
2649 finalizeSubtree(graph, graph->
head, treeedges, dfsdepth, stopped, minbound, treebound, ruleout, nodepos, ancestormark);
2653 assert(*treebound >= orgtreebound);
2656 if( !(*ruleout) && !
Is_term(graph->
term[innode]) && graph->
grad[innode] <= maxgrad )
2659 const SCIP_Real treecostoffset = *treebound - pathdist[innode];
2663 int nadded_edges = 0;
2665 unsigned int rounds = 0;
2667 assert(treecost >= 0.0);
2668 assert(nodepos[innode] == nnodes + 2);
2669 assert(nodepos[basenode] == nnodes + 1);
2671 nodepos[graph->
head[outedges[0]]] = nnodes + 2;
2672 nodepos[graph->
head[outedges[1]]] = nnodes + 3;
2673 nodepos[innode] = nnodes + 4;
2676 basebottlenecks[0] = graph->
cost[inedge];
2679 basebottlenecks[1] =
MAX(graph->
cost[outedges[0]], graph->
cost[inedge]);
2682 basebottlenecks[2] =
MAX(graph->
cost[outedges[1]], graph->
cost[inedge]);
2685 if(
ruleOutSubtree(scip, graph, treecosts, basebottlenecks, nodepos, treeedges,
FARAWAY, 0.0, 0,
flipedge(inedge),
FALSE,
2693 if( !nodepos[graph->
tail[e]] )
2694 edgestack[nadded_edges++] = e;
2698 while( nadded_edges > 0 )
2700 const int curredge = edgestack[--nadded_edges];
2701 const int currtail = graph->
tail[curredge];
2704 if( nodepos[currtail] )
2706 assert(dfsdepth >= 1 && treeedges[dfsdepth - 1] == curredge);
2708 treecost =
shortenSubtree(scip, graph, redcost, treeedges, treecost, treecostoffset, dfsdepth,
2709 currtail, nodepos, ancestormark, &rounds);
2715 const SCIP_Real extendedcost = treecost + redcost[curredge] + pathdist[currtail];
2717 if(
ruleOutSubtree(scip, graph, treecosts, basebottlenecks, nodepos, treeedges, cutoff, extendedcost, dfsdepth,
flipedge((
unsigned)curredge),
FALSE,
2718 ancestormark, eqstack, eqstack_size, eqmark) )
2721 if(
truncateSubtree(graph, extendedcost, -1, currtail, maxgrad, dfsdepth, maxdfsdepth, &minbound, &stopped) )
2723 if( stopped && minbound <= (*treebound) )
2729 nadded_edges =
extendSubtreeTail(graph, redcost, curredge, currtail, dfsdepth, nadded_edges, &treecost, treecosts, nodepos,
2730 treeedges, edgestack, ancestormark);
2736 assert(stopped || minbound ==
FARAWAY);
2737 assert(
SCIPisGE(scip, minbound, orgtreebound));
2740 finalizeSubtree(graph, graph->
tail, treeedges, dfsdepth, stopped, minbound, treebound, ruleout, nodepos, ancestormark);
2744 nodepos[basenode] = 0;
2745 nodepos[innode] = 0;
2749 for(
int i = 0; i < 2; i++ )
2751 nodepos[graph->
head[outedges[i]]] = 0;
2756 assert(*treebound >= orgtreebound);
2758 for(
int i = 0; i <
nnodes; i++ )
2759 assert(nodepos[i] == 0);
2762 assert(ancestormark[i] == 0);
2787 unsigned int* eqstack;
2790 const int nedges = graph->
edges;
2792 const int halfnedges = graph->
edges / 2;
2805 for(
int e = 0; e < nedges; e += 2 )
2809 const int erev = e + 1;
2810 int eqstack_size = 0;
2819 if( marked ==
NULL || !marked[e] )
2821 SCIP_CALL_ABORT(
reduceCheckEdge(scip, graph, root, cost, pathdist, vnoi, minpathcost, e, allowequality, nodearr,
2822 &deletable, eqstack, &eqstack_size, eqmark));
2824 if( marked !=
NULL && deletable )
2828 if( (marked ==
NULL || !marked[erev]) && deletable )
2831 nodearr, &deletable, eqstack, &eqstack_size, eqmark));
2833 if( marked !=
NULL && deletable )
2834 marked[erev] =
TRUE;
2837 for(
int i = 0; i < eqstack_size; i++ )
2838 eqmark[eqstack[i]] =
FALSE;
2839 for(
int i = 0; i < halfnedges; i++ )
2840 assert(eqmark[i] ==
FALSE);
2853 for(
int k = 0; k <
nnodes; k++ )
2854 if( graph->
grad[k] == 0 && k != root )
2904 const int nedges = graph->
edges;
2911 assert(scip !=
NULL);
2912 assert(graph !=
NULL);
2913 assert(nelims !=
NULL);
2914 assert(nodearrint !=
NULL);
2919 if( graph->
terms <= 1 )
2934 if( !rpc && !directed )
2947 if( !rpc && extended )
2953 for(
int i = 0; i <
nnodes; i++ )
2956 graph->
mark[i] = (graph->
grad[i] > 0);
2958 if( graph->
mark[i] )
2963 if( !rpc && !directed )
2981 if( !rpc && heursources !=
NULL )
2984 starts = heursources;
2992 for(
int e = 0; e < nedges; e++ )
2994 cost[e] = graph->
cost[e];
2999 if( directed || rpc )
3003 SCIP_CALL(
SCIPStpHeurTMRun(scip,
NULL, graph, starts, &best_start, result, runs, graph->
source, cost, costrev,
NULL,
NULL, 0.0, &success,
FALSE) );
3009 if(
SCIPisLT(scip, ubnew, upperbound) )
3018 damaxdeviation = -1.0;
3021 if( !rpc && !directed )
3023 assert(terms !=
NULL);
3028 if( prevrounds > 0 )
3040 for(
int outerrounds = 0; outerrounds < 2; outerrounds++ )
3043 for(
int run = 0; run < nruns; run++ )
3045 int root = graph->
source;
3056 if( !rpc && !directed )
3058 assert(terms !=
NULL);
3070 SCIPStpDualAscent(scip, graph, cost, pathdist, &lpobjval,
FALSE,
FALSE, gnodearr,
NULL, edgearrint, state, root,
FALSE, damaxdeviation, nodearrchar));
3080 const int realroot = graph->
source;
3083 graph->
source = realroot;
3089 SCIPStpDualAscent(scip, graph, cost, pathdist, &lpobjval,
FALSE,
FALSE, gnodearr, result, edgearrint, state, root,
FALSE, damaxdeviation, nodearrchar));
3096 SCIPStpDualAscent(scip, graph, cost, pathdist, &lpobjval,
FALSE,
FALSE, gnodearr,
NULL, edgearrint, state, root,
FALSE, damaxdeviation, nodearrchar));
3110 if( userec && !rpc )
3123 if( userec && soladded && pool->
size >= 2 && ubnew < upperbound )
3131 SCIP_CALL(
SCIPStpHeurRecRun(scip, pool,
NULL,
NULL, graph,
NULL, &solindex, 1, pool->
size,
FALSE, &solfound));
3137 assert(sol !=
NULL);
3141 if( sol->
obj < ubnew )
3150 if( ubnew < sol->obj )
3156 if(
SCIPisLE(scip, ubnew, upperbound) )
3164 minpathcost = upperbound - lpobjval;
3165 assert(
SCIPisGE(scip, minpathcost, 0.0));
3169 for( k = 0; k <
nnodes; k++ )
3170 graph->
mark[k] = (graph->
grad[k] > 0);
3175 for(
unsigned e = 0; e < (unsigned) nedges; e++ )
3186 if( directed || rpc )
3193 for(
int i = 0; i <
nnodes; i++ )
3196 assert(vbase[i] != root || vnoi[i].dist >=
FARAWAY);
3197 assert(vbase[i + nnodes] != root || vnoi[i + nnodes].dist >=
FARAWAY);
3200 assert(vbase[i] == i);
3206 nfixed +=
reduceSPG(scip, graph, offset, marked, nodearrchar, vnoi, cost, pathdist, result, minpathcost, root, apsol);
3208 if( !directed && !rpc )
3218 nfixed +=
reduce_extendedEdge(scip, graph, vnoi, cost, pathdist, (apsol ? result :
NULL), minpathcost, root, nodearrint, marked);
3223 updateNodeReplaceBounds(scip, nodereplacebounds, graph, cost, pathdist, vnoi, vbase, nodearrint, lpobjval, upperbound, root,
3224 (run == 0), extended));
3233 for( k = 0; k <
nnodes; k++ )
3234 graph->
mark[k] = graph->
grad[k] > 0;
3243 if( !directed && !rpc && !
SCIPisZero(scip, minpathcost) )
3246 if( nfixed == 0 || !userec )
3334 assert(scip !=
NULL);
3335 assert(cost !=
NULL);
3336 assert(graph !=
NULL);
3337 assert(nelims !=
NULL);
3338 assert(solnode !=
NULL);
3339 assert(costrev !=
NULL);
3340 assert(pathedge !=
NULL);
3341 assert(upperbound !=
NULL);
3342 assert(edgearrint !=
NULL);
3343 assert(edgearrint2 !=
NULL);
3344 assert(nodearrchar !=
NULL);
3345 assert(edgearrchar !=
NULL);
3353 nedges = graph->
edges;
3354 nnodes = graph->
knots;
3357 if( grad[graph->
source] == 0 )
3360 marked = edgearrchar;
3371 for( i = 0; i < 4; i++ )
3374 ancestors[i] =
NULL;
3375 revancestors[i] =
NULL;
3380 for( i = 0; i <
nnodes; i++ )
3383 graph->
mark[i] = (grad[i] > 0);
3384 if( graph->
mark[i] )
3399 for( i = 0; i <
nnodes; i++ )
3401 assert(grad[i] > 0);
3412 for( i = 0; i <
nnodes; i++ )
3415 for( e = 0; e < nedges; e++ )
3420 for( i = 0; i <
nnodes; i++ )
3442 for( l = nnodes - 1; l >= 0; --l )
3448 if( edgearrint[e] ==
CONNECT )
3456 if( edgearrint[e] ==
CONNECT )
3472 if( solgiven || i == nnodes )
3476 SCIP_CALL(
SCIPStpDualAscent(scip, graph, cost, pathdist, &lpobjval,
FALSE,
FALSE, gnodearr, edgearrint, edgearrint2, state, root,
FALSE, -1.0, nodearrchar) );
3481 SCIP_CALL(
SCIPStpDualAscent(scip, graph, cost, pathdist, &lpobjval,
FALSE,
FALSE, gnodearr,
NULL, edgearrint2, state, root,
FALSE, -1.0, nodearrchar) );
3488 GRAPH* prunegraph = graph;
3489 int* mark = graph->
mark;
3492 for( k = 0; k <
nnodes; k++ )
3510 head = prunegraph->
head[
a];
3524 for( k = 0; k <
nnodes; k++ )
3526 printf(
"in bnd FAIL %d not marked, but terminal, \n", k);
3535 if( success &&
SCIPisLT(scip, objprune, obj ) )
3538 for( i = 0; i <
nnodes; i++ )
3541 for( e = 0; e < nedges; e++ )
3543 edgearrint[e] = edgearrint2[e];
3544 if( edgearrint[e] ==
CONNECT )
3554 for( e = 0; e < nedges; e++ )
3556 if( edgearrint[e] ==
CONNECT )
3557 obj += graph->
cost[e];
3565 for( k = 0; k <
nnodes; k++ )
3566 graph->
mark[k] = (grad[k] > 0);
3578 for( k = 0; k <
nnodes; k++ )
3580 assert(vbase[k + nnodes] != root );
3589 for( e = 0; e < nedges; e++ )
3592 for( redrounds = 0; redrounds < 3; redrounds++ )
3594 if( redrounds == 0 )
3599 else if( redrounds == 1 )
3601 assert(minelims > 0);
3602 assert(2 * minelims < nedges);
3608 minpathcost = costrev[nedges - 2 * minelims];
3610 if(
SCIPisLE(scip, minpathcost, 0.0) )
3613 k = nedges - 2 * minelims;
3616 for( e = nedges - 1; e > k && e >= 2; e = e - 2 )
3618 if(
SCIPisLE(scip, costrev[e - 2], minpathcost) )
3622 if(
SCIPisGT(scip, costrev[e], minpathcost) )
3623 minpathcost = costrev[e];
3625 if(
SCIPisLE(scip, minpathcost, 0.0) )
3628 for( e = 0; e < nedges; e++ )
3636 minpathcost = costrev[nedges - 2 * minelims];
3638 if(
SCIPisLE(scip, minpathcost, 0.0) )
3641 for( e = 0; e < nedges; e++ )
3645 for( k = 0; k <
nnodes; k++ )
3650 if( nfixed > minelims )
3653 if( !
Is_term(graph->
term[k]) && (!eliminate || pathdist[k] + vnoi[k].
dist >= minpathcost) && solnode[k] !=
CONNECT )
3657 tmpcost = pathdist[k] + vnoi[k].
dist;
3661 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
3662 costrev[e] = tmpcost;
3666 if(
SCIPisGT(scip, tmpcost, costrev[e2]) )
3667 costrev[e2] = tmpcost;
3682 etmp = graph->
oeat[e];
3683 head = graph->
head[e];
3686 if( (rpc && !graph->
mark[head])
3693 tmpcost = pathdist[k] + cost[e] + vnoi[head].
dist;
3695 if( (!eliminate) || tmpcost >= minpathcost )
3706 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
3707 costrev[e] = tmpcost;
3723 for( k = 0; k <
nnodes; k++ )
3725 if( nfixed > minelims )
3735 if( !eliminate || tmpcost >= minpathcost )
3739 e2 = graph->
oeat[e];
3741 e3 = graph->
oeat[e2];
3751 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
3752 costrev[e] = tmpcost;
3756 if(
SCIPisGT(scip, tmpcost, costrev[e2]) )
3757 costrev[e2] = tmpcost;
3773 assert(graph->
mark[root]);
3779 for( k = 0; k < 4; k++ )
3793 if( edgearrchar ==
NULL )
3844 const int root = graph->
source;
3845 const int nedges = graph->
edges;
3846 const int extnedges = nedges + 2 * (graph->
terms - 1);
3851 assert(scip !=
NULL);
3852 assert(graph !=
NULL);
3853 assert(nelims !=
NULL);
3854 assert(nodearrchar !=
NULL);
3857 if( graph->
terms <= 1 )
3862 varyroot = varyroot && userec;
3865 if( edgearrint ==
NULL )
3868 result = edgearrint;
3885 for(
int i = 0; i <
nnodes; i++ )
3886 if( graph->
mark[i] )
3910 gnodearr,
NULL, transresult, state, root,
TRUE, damaxdeviation, nodearrchar) );
3913 bestlpobjval = lpobjval;
3919 SCIP_CALL(
computeDaSolPcMw(scip, graph,
NULL, vnoi, cost, pathdist, &upperbound, result, result2, vbase, pathedge, nodearrchar, &apsol) );
3921 assert(apsol && upperbound <
FARAWAY);
3925 minpathcost = upperbound - lpobjval;
3940 for(
int e = 0; e < extnedges; e++ )
3949 nfixed +=
reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar,
TRUE);
3959 if( solbasedda && graph->
terms > 2 &&
SCIPisGT(scip, minpathcost, 0.0) )
3961 const SCIP_Real oldupperbound = upperbound;
3967 SCIP_CALL(
SCIPStpHeurTMRun(scip,
NULL, graph,
NULL,
NULL, result2,
DEFAULT_HEURRUNS / 5, root, graph->
cost, graph->
cost,
NULL,
NULL, 0.0, &success,
FALSE) );
3974 SCIPdebugMessage(
"added initial TM sol to pool? %d , ub %f \n", success, ub);
3978 SCIP_CALL(
computePertubedSol(scip, graph, transgraph, pool, vnoi, gnodearr, cost, costrev, bestcost, pathdist, state, vbase, pathedge, result, result2,
3979 transresult, nodearrchar, &upperbound, &lpobjval, &bestlpobjval, &minpathcost, &apsol, offset, extnedges, 0) );
3991 nfixed +=
reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar, apsol);
3993 nfixed +=
reducePcMwTryBest(scip, graph, transgraph, vnoi, cost, costrev, bestcost, pathdist, &upperbound,
3994 &lpobjval, &bestlpobjval, &minpathcost, oldupperbound, result, vbase, state, pathedge, marked, nodearrchar, &apsol, extnedges);
4000 SCIPdebugMessage(
"eliminations after sol based run2 with best dual sol %d bestlb %f newlb %f\n", nfixed, bestlpobjval, lpobjval);
4018 SCIP_CALL(
computePertubedSol(scip, graph, transgraph, pool, vnoi, gnodearr, cost, costrev, bestcost, pathdist, state, vbase, pathedge, result, result2,
4019 transresult, nodearrchar, &upperbound, &lpobjval, &bestlpobjval, &minpathcost, &apsol, offset, extnedges, run) );
4022 SCIPdebugMessage(
"DA: pertubated run %d minpathcost: %f \n", run, upperbound - lpobjval);
4028 nfixed +=
reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar, apsol);
4030 nfixed +=
reducePcMwTryBest(scip, graph, transgraph, vnoi, cost, costrev, bestcost, pathdist, &upperbound,
4031 &lpobjval, &bestlpobjval, &minpathcost, oldupperbound, result, vbase, state, pathedge, marked, nodearrchar, &apsol, extnedges);
4044 if( varyroot || markroots )
4048 findDaRoots(scip, graph, transgraph, cost, bestcost, lpobjval, bestlpobjval, upperbound, prizesum,
FALSE,
FALSE,
4049 vnoi, state, pathedge, vbase, nodearrchar, roots, &nroots);
4052 if( nroots > 0 && markroots )
4053 markPcMwRoots(scip, roots, 0, nroots, prizesum, graph, &userec, &pool);
4055 if( nroots > 0 && varyroot )
4072 for(
int run = 0; run < nusedroots; run++ )
4074 const int tmproot = roots[run];
4079 assert(roots !=
NULL);
4082 if( graph->
terms <= 2 )
4089 transnnodes = transgraph->
knots;
4090 transnedges = transgraph->
edges;
4092 for(
int k = 0; k < transnnodes; k++ )
4093 transgraph->
mark[k] = (transgraph->
grad[k] > 0);
4101 if( apsol && run > 1 )
4106 gnodearr, transresult, result2, state, tmproot,
FALSE, -1.0, nodearrchar));
4111 gnodearr,
NULL, transresult, state, tmproot,
FALSE, -1.0, nodearrchar));
4118 const int k = graph->
head[e];
4128 for(
int k = 0; k <
nnodes; k++ )
4134 const int head = graph->
head[e];
4142 SCIP_CALL(
computeDaSolPcMw(scip, graph, pool, vnoi, cost, pathdist, &upperbound, result, result2, vbase, pathedge, nodearrchar, &apsol) );
4147 for(
int k = 0; k < transnnodes; k++ )
4148 transgraph->
mark[k] = (transgraph->
grad[k] > 0);
4151 minpathcost = upperbound - lpobjval;
4155 const int oldnroots = nroots;
4156 findDaRoots(scip, graph, transgraph, cost, cost, lpobjval, lpobjval, upperbound, prizesum,
TRUE,
TRUE,
4157 vnoi, state, pathedge, vbase, nodearrchar, roots, &nroots);
4160 if( nroots > oldnroots )
4161 markPcMwRoots(scip, roots, oldnroots, nroots, prizesum, graph, &userec, &pool);
4170 for(
int e = 0; e < transnedges; e++ )
4184 assert(graph->
mark[tmproot]);
4189 for(
int e = 0; e < extnedges; e++ )
4190 edgefixingbounds[e] = MIN(edgefixingbounds[e], edgefixingbounds[
flipedge(e)]);
4195 for(
int e = 0; e < transnedges; e++ )
4199 nfixed +=
reducePcMw(scip, graph, transgraph, vnoi, cost, pathdist, minpathcost, result, marked, nodearrchar, apsol);
4227 if( edgearrint ==
NULL )
4293 assert(scip !=
NULL);
4294 assert(graph !=
NULL);
4295 assert(nelims !=
NULL);
4296 assert(nodearrchar !=
NULL);
4300 nnodes = graph->
knots;
4301 nedges = graph->
edges;
4306 if( graph->
terms <= 3 )
4310 if( soledge ==
NULL )
4331 for( i = 0; i < 4; i++ )
4334 ancestors[i] =
NULL;
4335 revancestors[i] =
NULL;
4342 for( i = 0; i <
nnodes; i++ )
4344 if( graph->
grad[i] > 0 )
4362 transnnodes = transgraph->
knots;
4363 transnedges = transgraph->
edges;
4367 for( k = 0; k <
nnodes; k++ )
4368 nodearrchar[k] = (solnode[k] ==
CONNECT);
4370 for( e = 0; e < nedges; e++ )
4372 cost[e] = graph->
cost[e];
4382 for( e = 0; e < nedges; e++ )
4384 cost[e] = graph->
cost[e];
4400 SCIP_CALL(
SCIPStpHeurTMRun(scip, tmheurdata, graph,
NULL, &best_start, transresult, runs, root, cost, costrev, &hopfactor,
NULL, 0.0, &success,
FALSE) );
4410 if(
SCIPisLE(scip, ub, upperbound) )
4413 for( e = 0; e < nedges; e++ )
4414 result[e] = transresult[e];
4419 SCIP_CALL(
SCIPStpDualAscent(scip, transgraph, cost, pathdist, &lpobjval,
FALSE,
FALSE, gnodearr,
NULL, transresult, state, root,
FALSE, -1.0, nodearrchar) );
4432 if(
SCIPisLE(scip, ub, upperbound) )
4433 for( e = 0; e < nedges; e++ )
4434 result[e] = transresult[e];
4441 for( e = 0; e < transnedges; e++ )
4447 for( k = 0; k < transnnodes; k++ )
4448 transgraph->
mark[k] = (transgraph->
grad[k] > 0);
4453 for( i = 0; i < transnnodes; i++ )
4455 assert(
SCIPisEQ(scip, pathdist[i], 0.0));
4467 for( k = 0; k <
nnodes; k++ )
4470 for( e = 0; e < nedges; e++ )
4480 for( redrounds = 0; redrounds < 3; redrounds++ )
4482 if( redrounds == 0 )
4487 else if( redrounds == 1 )
4489 assert(minelims > 0);
4490 assert(2 * minelims < nedges);
4496 minpathcost = costrev[nedges - 2 * minelims];
4498 if(
SCIPisLE(scip, minpathcost, 0.0) )
4501 k = nedges - 2 * minelims;
4504 for( e = nedges - 1; e > k && e >= 2; e = e - 2 )
4506 if(
SCIPisLE(scip, costrev[e - 2], minpathcost) )
4510 if(
SCIPisGT(scip, costrev[e], minpathcost) )
4511 minpathcost = costrev[e];
4513 if(
SCIPisLE(scip, minpathcost, 0.0) )
4517 for( e = 0; e < nedges; e++ )
4525 minpathcost = costrev[nedges - 2 * minelims];
4527 if(
SCIPisLE(scip, minpathcost, 0.0) )
4530 for( e = 0; e < nedges; e++ )
4535 for( k = 0; k <
nnodes; k++ )
4537 if( !graph->
mark[k] )
4540 if( nfixed > minelims )
4547 tmpcost = pathdist[k] + vnoi[k].
dist;
4549 if(
SCIPisGT(scip, tmpcost, minpathcost) ||
4550 (
SCIPisGE(scip, tmpcost, minpathcost) && solnode[k] !=
CONNECT) || (!eliminate && solnode[k] !=
CONNECT) )
4556 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
4557 costrev[e] = tmpcost;
4561 if(
SCIPisGT(scip, tmpcost, costrev[e2]) )
4562 costrev[e2] = tmpcost;
4570 e = transgraph->
outbeg[k];
4579 e = transgraph->
outbeg[k];
4582 etmp = transgraph->
oeat[e];
4583 tmpcost = pathdist[k] + cost[e] + vnoi[transgraph->
head[e]].
dist;
4585 if(
SCIPisGT(scip, tmpcost, minpathcost) ||
4598 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
4599 costrev[e] = tmpcost;
4615 assert(root == transgraph->
source);
4628 for( k = 0; k < 4; k++ )
4644 if( soledge ==
NULL )
4705 assert(scip !=
NULL);
4706 assert(graph !=
NULL);
4707 assert(vnoi !=
NULL);
4708 assert(cost !=
NULL);
4709 assert(radius !=
NULL);
4710 assert(costrev !=
NULL);
4711 assert(heap !=
NULL);
4712 assert(state !=
NULL);
4713 assert(vbase !=
NULL);
4714 assert(nelims !=
NULL);
4715 assert(graph->
source >= 0);
4716 assert(upperbound !=
NULL);
4722 nedges = graph->
edges;
4723 nnodes = graph->
knots;
4728 ub =
SCIPisGT(scip, *upperbound, 0.0);
4750 for( k = 0; k <
nnodes; k++ )
4754 assert(stnode !=
NULL);
4758 graph->
mark[k] = (graph->
grad[k] > 0);
4759 if( graph->
mark[k] )
4768 if( nterms <= 2 || (pcmw && nterms <= 3) )
4796 for( e = 0; e < nedges; e++ )
4800 assert(result !=
NULL);
4803 cost[e] = graph->
cost[e];
4806 assert(
SCIPisGE(scip, cost[e], 0.0));
4809 maxcost = graph->
cost[e];
4826 graph_get2next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
4829 graph_get3next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
4833 graph_get4next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
4838 assert(adjgraph !=
NULL);
4849 for( k = 1; k <
nterms; k++ )
4854 tmpcost = adjgraph->
cost[e];
4858 else if(
SCIPisGT(scip, tmpcost, r) )
4862 mstobj2 = mstobj -
r;
4869 for( k = 0; k <
nnodes; k++ )
4875 radius[k] = prize[k];
4880 for( k = 0; k <
nnodes; k++ )
4882 if( !graph->
mark[k] )
4886 radius[k] = prize[k];
4892 for( k = 0; k <
nnodes; k++ )
4897 assert(
SCIPisGE(scip, prize[k], 0.0));
4898 if(
SCIPisGT(scip, prize[k], max) )
4901 if(
SCIPisGE(scip, radius[k], 0.0 ) )
4904 radius[k] = -radius[k];
4912 for( k = 0; k <
nnodes; k++ )
4926 for( k = 2; k <
nterms; k++ )
4929 radiim2 += radius[k];
4934 for( k = 0; k < nterms - 2; k++ )
4937 radiim2 += radius[k];
4940 radii = radiim2 + radius[nterms - 2] + radius[nterms - 1];
4943 radiim3 = radiim2 - radius[nterms - 3];
4954 assert(stnode !=
NULL);
4955 assert(result !=
NULL);
4961 SCIP_CALL(
SCIPStpHeurTMRun(scip, tmheurdata, graph, starts, &best_start, result, runs, root, cost, costrev, &obj,
NULL, maxcost, &success,
FALSE) );
4985 for( e = 0; e < nedges; e++ )
4989 head = graph->
head[e];
4992 if( graph->
mark[head] )
4994 assert(stnode[head] ==
FALSE);
5000 obj += graph->
cost[e];
5001 stnode[head] =
TRUE;
5014 if(
SCIPisGT(scip, radiim2, mstobj) )
5020 for( k = 0; k <
nnodes; k++ )
5022 if( (!graph->
mark[k] && (pcmw)) || graph->
grad[k] == 0 )
5042 etemp = graph->
oeat[e];
5043 tail = graph->
tail[e];
5044 head = graph->
head[e];
5045 if( !graph->
mark[head] )
5050 tmpcost = bound - graph->
prize[k];
5051 if( vbase[tail] != vbase[head] )
5053 tmpcost -= vnoi[head].
dist + vnoi[tail].
dist;
5057 if(
SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
5062 if( (
SCIPisLT(scip, tmpcost, obj)) )
5077 || (((stnode !=
NULL) ? !stnode[k] : 0) &&
SCIPisGE(scip, tmpcost, obj))) )
5084 assert(!pc || graph->
tail[e] != root);
5085 assert(!pc || graph->
mark[graph->
head[e]]);
5097 etemp = graph->
oeat[e];
5098 tail = graph->
tail[e];
5099 head = graph->
head[e];
5102 if( vbase[tail] != vbase[head] )
5104 tmpcost += vnoi[head].
dist + vnoi[tail].
dist;
5108 if(
SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
5112 assert(
SCIPisGE(scip, tmpcost, vnoi[head].dist + vnoi[tail].dist + graph->
cost[e] + bound));
5139 for( k = 0; k <
nnodes; k++ )
5141 if( (!graph->
mark[k] && pc) || graph->
grad[k] == 0 )
5151 assert(graph->
grad[k] == 0 || (graph->
grad[k] == 4 && !success));
5163 for( k = 0; k <
nnodes; k++ )
5168 assert(perm !=
NULL);
5169 for( l = 0; l <
nterms; l++ )
5173 tmpcost = vnoi[k].
dist + radii - radius[l];
5175 if( l == nterms - 1 )
5176 tmpcost -= radius[nterms - 2];
5178 tmpcost -= radius[nterms - 1];
5185 (*offset) += graph->
prize[k];
5190 if( l >= nterms - 2 )
5191 tmpcost -= radius[nterms - 3];
5193 tmpcost -= radius[nterms - 2];
5194 if(
SCIPisGT(scip, tmpcost, obj) ||
SCIPisGT(scip, mstobj2 + vnoi[k].dist + vnoi[k + nnodes].dist, obj) )
5203 (*offset) += graph->
prize[k];
5272 assert(scip !=
NULL);
5273 assert(graph !=
NULL);
5274 assert(vnoi !=
NULL);
5275 assert(path !=
NULL);
5276 assert(cost !=
NULL);
5277 assert(radius !=
NULL);
5278 assert(costrev !=
NULL);
5279 assert(heap !=
NULL);
5280 assert(state !=
NULL);
5281 assert(vbase !=
NULL);
5282 assert(nelims !=
NULL);
5283 assert(graph->
source >= 0);
5286 prize = graph->
prize;
5287 nedges = graph->
edges;
5288 nnodes = graph->
knots;
5289 nterms = graph->
terms - 1;
5292 assert(prize !=
NULL);
5300 for( e = 0; e < nedges; e++ )
5302 cost[e] = graph->
cost[e];
5305 assert(
SCIPisGE(scip, cost[e], 0.0));
5312 for( k = 0; k <
nnodes; k++ )
5317 assert(vbase[k] == k);
5318 assert(
SCIPisGE(scip, prize[k], 0.0));
5324 if(
SCIPisGE(scip, radius[k], prize[k] ) )
5327 radius[k] = prize[k] - radius[k];
5331 for( k = 0; k <
nnodes; k++ )
5341 graph_get2next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
5343 for( k = 0; k <
nnodes; k++ )
5348 assert(vbase[k] == k);
5355 for( k = 2; k <
nterms; k++ )
5358 radiim2 += radius[k];
5366 for( e = 0; e < nedges; e++ )
5370 head = graph->
head[e];
5372 if( graph->
mark[head] )
5385 for( k = 0; k <
nnodes; k++ )
5394 if( (
SCIPisLT(scip, tmpcost, obj)) )
5441 const int root = graph->
source;
5443 const int nedges = graph->
edges;
5450 assert(scip !=
NULL);
5451 assert(vnoi !=
NULL);
5452 assert(cost !=
NULL);
5453 assert(heap !=
NULL);
5454 assert(graph !=
NULL);
5455 assert(state !=
NULL);
5456 assert(vbase !=
NULL);
5457 assert(nelims !=
NULL);
5458 assert(radius !=
NULL);
5459 assert(costrev !=
NULL);
5460 assert(solnode !=
NULL);
5461 assert(soledge !=
NULL);
5462 assert(graph->
source >= 0);
5474 for(
int k = 0; k <
nnodes; k++ )
5475 graph->
mark[k] = (graph->
grad[k] > 0);
5479 for(
int e = 0; e < nedges; e++ )
5481 cost[e] = graph->
cost[e];
5484 assert(
SCIPisGE(scip, cost[e], 0.0));
5487 maxcost = graph->
cost[e];
5502 graph_get2next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
5505 graph_get3next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
5507 assert(adjgraph !=
NULL);
5518 for(
int k = 1; k <
nterms; k++ )
5520 const int e = mst[k].
edge;
5523 tmpcost = adjgraph->
cost[e];
5543 graph_get2next(scip, graph, cost, costrev, vnoi, vbase, heap, state);
5551 for(
int k = 0; k <
nnodes; k++ )
5557 radius[k] = prize[k];
5562 for(
int k = 0; k <
nnodes; k++ )
5564 if( !graph->
mark[k] )
5568 radius[k] = prize[k];
5580 for(
int e = 0; e < nedges; e++ )
5587 for(
int e = 0; e < nedges; e++ )
5591 for(
int k = 0; k < nterms - 2; k++ )
5594 radiim2 += radius[k];
5597 radiim3 = radiim2 - radius[nterms - 3];
5601 if(
SCIPisGT(scip, radiim2, mstobj) )
5607 for(
int redrounds = 0; redrounds < 3; redrounds++ )
5609 int nrealelims = MIN(2 * minelims, nedges - 1);
5611 if( redrounds == 0 )
5616 else if( redrounds == 1 )
5618 assert(minelims > 0);
5619 assert(2 * minelims < nedges);
5625 obj = costrev[nrealelims];
5629 obj = costrev[nedges - nrealelims];
5639 obj = costrev[nrealelims] + 2 *
SCIPepsilon(scip);
5643 obj = costrev[nedges - nrealelims] - 2 *
SCIPepsilon(scip);
5653 for(
int k = 0; k <
nnodes; k++ )
5655 if( (*nelims) >= minelims )
5666 if( (!eliminate ||
SCIPisLT(scip, tmpcost, obj)) && solnode[k] !=
CONNECT )
5680 if(
SCIPisLT(scip, tmpcost, costrev[e]) )
5682 costrev[e] = tmpcost;
5688 else if( solnode[k] ==
CONNECT )
5690 int e = graph->
outbeg[k];
5694 const int etemp = graph->
oeat[e];
5695 const int tail = graph->
tail[e];
5696 const int head = graph->
head[e];
5704 tmpcost = graph->
prize[head] + graph->
prize[tail];
5706 if( vbase[tail] != vbase[head] )
5708 tmpcost -= vnoi[head].
dist + vnoi[tail].
dist;
5712 if(
SCIPisGT(scip, -vnoi[tail].dist -vnoi[head + nnodes].dist, -vnoi[tail + nnodes].dist -vnoi[head].dist) )
5718 if( (!eliminate ||
SCIPisLT(scip, tmpcost, obj))
5729 else if(
SCIPisLT(scip, tmpcost, costrev[e]) )
5731 costrev[e] = tmpcost;
5745 for(
int k = 0; k <
nnodes; k++ )
5747 if( (*nelims) >= minelims )
5752 if( (!graph->
mark[k] && (pcmw)) || graph->
grad[k] == 0 )
5765 const int e = graph->
outbeg[k];
5768 assert(!pc || graph->
tail[e] != graph->
source);
5769 assert(!pc || graph->
mark[graph->
head[e]]);
5780 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
5782 costrev[e] = tmpcost;
5790 int e = graph->
outbeg[k];
5793 const int etemp = graph->
oeat[e];
5794 const int tail = graph->
tail[e];
5795 const int head = graph->
head[e];
5811 if( vbase[tail] != vbase[head] )
5813 tmpcost += vnoi[head].
dist + vnoi[tail].
dist;
5817 if(
SCIPisGT(scip, vnoi[tail].dist + vnoi[head + nnodes].dist, vnoi[tail + nnodes].dist + vnoi[head].dist) )
5822 assert(
SCIPisGE(scip, tmpcost, vnoi[head].dist + vnoi[tail].dist + graph->
cost[e] + bound));
5825 if( (!eliminate ||
SCIPisGT(scip, tmpcost, obj))
5836 else if(
SCIPisGT(scip, tmpcost, costrev[e]) )
5838 costrev[e] = tmpcost;
5848 for(
int k = 0; k <
nnodes; k++ )
5850 if( (*nelims) >= minelims )
5853 if( (!graph->
mark[k] && pc) || graph->
grad[k] <= 0 )
5866 if(
SCIPisGT(scip, tmpcost, costrev[e]) )
5868 costrev[e] = tmpcost;
5885 assert(graph->
grad[k] == 0 || (graph->
grad[k] == 4 && !success));