38 #define ADDCUTSTOPOOL FALSE 39 #define TERMSEPA_SPARSE_MAXRATIO 4 40 #define TERMSEPA_MAXCUTSIZE_DEFAULT 5 41 #define TERMSEPA_MAXNCUTS_DEFAULT 100 42 #define TERMSEPA_NROOTCANDS 3 49 #define FLOW_FACTOR 1000000 50 #define CREEP_VALUE 10 109 #ifdef STP_MAXFLOW_WRITE 122 fptr = fopen(
"flow",
"w+");
123 assert(fptr !=
NULL);
125 fprintf(fptr,
"p max %d %d \n", nnodes, nedges);
126 fprintf(fptr,
"n %d s \n", g->
source + 1);
127 fprintf(fptr,
"n %d t \n", sinkterm + 1);
129 for(
int k = 0; k <
nnodes; k++ )
133 fprintf(fptr,
"a %d %d %d \n", k + 1, g->
head[e] + 1, capa[e]);
137 fprintf(fptr,
"x\n");
147 void debugPrintCutNodes(
155 printf(
"root component nodes: \n");
157 for(
int i = 0; i <
nnodes; i++ )
159 if( nodes_wakeState[i] )
163 printf(
"remaining nodes: \n");
165 for(
int i = 0; i <
nnodes; i++ )
167 if( !nodes_wakeState[i] )
173 void debugPrintCutEdges(
181 printf(
"cut edges: \n");
183 for(
int i = 0; i <
nnodes; i++ )
185 if( !nodes_wakeState[i] )
190 const int head = g->
head[e];
192 if( nodes_wakeState[head] == 0 )
202 void debugPrintCsrCutEdges(
215 printf(
"CSR cut edges: \n");
217 for(
int i = 0; i < nnodes_extended; i++ )
219 const int start = csr_start[i];
220 const int end = csr_start[i + 1];
222 if( !nodes_wakeState[i] )
225 for(
int j = start; j != end; j++ )
227 const int head = csr_headarr[j];
229 if( nodes_wakeState[head] == 0 )
231 printf(
"%d->%d, c=%d \n", i, head, edges_capa[j]);
246 const int*
const residual = g->
mincut_r;
254 for(
int i = 0; i < nnodes_extended; i++ )
256 const int start = csr_start[i];
257 const int end = csr_start[i + 1];
259 for(
int j = start; j != end; j++ )
261 const int head = csr_headarr[j];
263 printf(
"edge %d: %d->%d, r=%d (fliped=%d) \n", j, i, head, residual[j], csr_edgeflipped[j]);
278 const int*
const residual = g->
mincut_r;
286 for(
int i = 0; i < nnodes_extended; i++ )
288 const int start = csr_start[i];
289 const int end = csr_start[i + 1];
291 for(
int j = start; j != end; j++ )
293 assert(csr_edgeflipped[j] >= 0);
295 if( csr_headarr[csr_edgeflipped[j]] != i )
300 assert(residual[j] > 0 || residual[csr_edgeflipped[j]] > 0);
328 assert(ncutterms > 0);
329 assert(nodes_wakeState[sinkterm] == 0);
334 for(
int i = 0; i <
nnodes; i++ )
336 nodes_isBlocked[i] =
FALSE;
337 nodes_isVisited[i] =
FALSE;
340 for(
int i = 0; i < ncutterms; i++ )
343 assert(!nodes_isBlocked[cutterms[i]]);
345 nodes_isBlocked[cutterms[i]] =
TRUE;
348 assert(!nodes_isBlocked[mincut->
root]);
350 for(
int i = 0; i <
nnodes; i++ )
352 if( nodes_wakeState[i] == 0 )
361 nodes_isVisited[sinkterm] =
TRUE;
368 assert(nodes_isVisited[k]);
372 const int head = g->
head[e];
373 if( !nodes_isVisited[head] && !nodes_isBlocked[head] )
376 nodes_isVisited[head] =
TRUE;
384 if( nvisted > nsinknodes )
390 if( nodes_isVisited[mincut->
root] )
437 nodes_isVisited[rootcand] =
TRUE;
442 const int node = queue[i];
443 assert(nodes_isVisited[node]);
450 for(
int e = g->
outbeg[node]; e >= 0; e = g->
oeat[e] )
452 const int head = g->
head[e];
453 if( !nodes_isVisited[head] )
455 nodes_isVisited[head] =
TRUE;
463 const int node = queue[i];
464 assert(nodes_isVisited[node]);
465 nodes_isVisited[node] =
FALSE;
471 for(
int i = 0; i <
nnodes; i++ )
473 assert(nodes_isVisited[i] ==
FALSE);
477 if( compsize > *rootcompsize )
479 *rootcompsize = compsize;
505 int sourcecompsize = 0;
511 for(
int i = 0; i < ntries; i++ )
514 const int cand = terms[pos];
519 assert(sourcecompsize > 0);
553 for(
int i = 0; i < nnodes_extended && isGood; i++ )
555 const int start = csr_start[i];
556 const int end = csr_start[i + 1];
558 if( !nodes_wakeState[i] )
561 for(
int j = start; j != end; j++ )
563 const int head = csr_headarr[j];
565 if( nodes_wakeState[head] == 0 && edges_capa[j] > 0 )
567 assert(n <= maxsepasize);
568 assert(edges_capa[j] == 1 || edges_capa[j] == capa_inf);
570 if( edges_capa[j] == capa_inf || n == maxsepasize )
602 int* RESTRICT termcands = mincut->
terms;
607 assert(ncutterms > 0);
612 for(
int i = 0; i < ncutterms; i++ )
615 assert(!nodes_isVisited[cutterms[i]]);
617 nodes_isVisited[cutterms[i]] =
TRUE;
620 assert(!nodes_isVisited[mincut->
root]);
625 nodes_isVisited[sinkterm] =
TRUE;
630 const int node = queue[i];
631 assert(nodes_isVisited[node]);
633 if( removeTerms &&
Is_term(g->
term[node]) && node != sinkterm )
642 if( node == termcands[t] )
655 for(
int e = g->
outbeg[node]; e >= 0; e = g->
oeat[e] )
657 const int head = g->
head[e];
658 if( !nodes_isVisited[head] )
660 nodes_isVisited[head] =
TRUE;
671 const int node = queue[i];
672 assert(nodes_isVisited[node]);
673 nodes_isVisited[node] =
FALSE;
675 if( updateVisitedTerms &&
Is_term(g->
term[node]) && node != sinkterm )
687 for(
int i = 0; i < ncutterms; i++ )
689 assert(nodes_isVisited[cutterms[i]]);
690 nodes_isVisited[cutterms[i]] =
FALSE;
696 for(
int i = 0; i <
nnodes; i++ )
698 assert(nodes_isVisited[i] ==
FALSE);
767 assert(0 <= nsepas_all && nsepas_all < termsepas->maxnsepas);
768 assert(0 <= ncutterms && ncutterms <= termsepas->maxsepasize);
778 SCIPdebugMessage(
"discarding already covered component because of SEPA size: %d>=%d, COMP size: %d>=%d \n", ncutterms
785 sepas[nsepas_all].
sinkterm = sinkterm;
791 int nsinknodes_dbg = 0;
793 for(
int i = 0; i <
nnodes; i++ )
795 if( nodes_wakeState[i] == 0 )
799 assert(nsinknodes_dbg >= nsinknodes);
806 termsepas->
nsepas[ncutterms]++;
811 if( ncutterms <= TERMSEPA_MAXCUTSIZE )
813 printf(
"terminal cut of size %d for sink %d \n", ncutterms, sinkterm);
814 printf(
"nsinknodes=%d \n", nsinknodes);
816 for(
int i = 0; i < ncutterms; i++ )
818 printf(
"%d \n", cutterms[i]);
875 for(
int e = 0; e < nedges; e++ )
876 csr_edgeDefaultToCsr[e] = -1;
898 assert(nodes_wakeState && nodes_termToCopy);
900 for(
int k = 0; k < nnodes_org; k++ )
903 assert(nodes_termToCopy[k] == -1);
914 const int head = g->
head[e];
917 if( nodes_wakeState[head] == 0 )
924 if( nodes_wakeState[k] == 0 )
927 terms[ntermcands++] = k;
932 nodes_termToCopy[k] = nnodes_org + nsepaterms;
935 assert(excess[nodes_termToCopy[k]] == 0);
937 if( nodes_wakeState[k] != 0 )
940 excess[nodes_termToCopy[k]] = 1;
943 SCIPdebugMessage(
"adding separator terminal %d (copyindex=%d) \n", k, nodes_termToCopy[k]);
953 printf(
"PERMUTE \n\n \n");
972 int* RESTRICT residual = g->
mincut_r;
980 const int capa_one = 1;
984 assert(residual && edgecurr && edges_capa);
987 for(
int k = 0; k < nnodes_org; k++ )
989 const SCIP_Bool kIsSepaTerm = nodes_termToCopy[k] >= 0;
996 const int kCopy = nodes_termToCopy[k];
1002 csr_headarr[csr_nedges++] = kCopy;
1006 if( kIsSepaTerm || nodes_wakeState[k] == 0 )
1008 assert(k != mincut->
root);
1015 const int head = g->
head[e];
1018 if( nodes_termToCopy[head] >= 0 )
1020 const int headCopy = nodes_termToCopy[head];
1026 csr_headarr[csr_nedges++] = headCopy;
1032 const int head = g->
head[e];
1033 const SCIP_Bool headIsSepaTerm = nodes_termToCopy[head] >= 0;
1035 if( kIsSepaTerm && headIsSepaTerm )
1038 if( headIsSepaTerm || nodes_wakeState[head] == 0 )
1041 residual[
csr_nedges] = kIsSepaTerm ? 0 : capa_infinity;
1042 csr_headarr[csr_nedges++] = head;
1047 if( edgecurr[k] == csr_nedges )
1049 assert(g->
grad[k] == 0);
1050 nodes_wakeState[k] = 1;
1056 for(
int k = 0; k < nnodes_org; k++ )
1058 const SCIP_Bool kIsSepaTerm = nodes_termToCopy[k] >= 0;
1062 const int kCopy = nodes_termToCopy[k];
1064 assert(nodes_wakeState[kCopy] == 0);
1073 csr_headarr[csr_nedges++] = k;
1076 #ifdef SCIP_DISABLED 1079 const int head = g->
head[e];
1081 if( nodes_termToCopy[head] >= 0 )
1083 const int headCopy = nodes_termToCopy[head];
1086 assert(nnodes_org <= headCopy && headCopy < mincut->termsepa_nnodes);
1089 csr_headarr[csr_nedges++] = headCopy;
1096 const int head = g->
head[e];
1097 const SCIP_Bool headIsSepaTerm = nodes_termToCopy[head] >= 0;
1099 if( headIsSepaTerm || nodes_wakeState[head] == 0 )
1102 csr_headarr[csr_nedges++] = head;
1135 for(
int copyterm = nnodes_org; copyterm < nnodes_extended; copyterm++ )
1137 const int copyedges_start = csr_start[copyterm];
1138 const int copyedges_end = csr_start[copyterm + 1];
1140 assert(copyedges_start < copyedges_end);
1142 for(
int copyedge = copyedges_start; copyedge != copyedges_end; copyedge++ )
1145 const int copyneighbor = csr_headarr[copyedge];
1146 const int neighboredges_start = csr_start[copyneighbor];
1147 const int neighboredges_end = csr_start[copyneighbor + 1];
1149 assert(neighboredges_start < neighboredges_end);
1152 for( antiedge = neighboredges_start; antiedge != neighboredges_end; antiedge++ )
1154 if( csr_headarr[antiedge] == copyterm )
1160 assert(antiedge < neighboredges_end);
1161 assert(csr_edgeflipped[antiedge] == -1 || csr_edgeflipped[antiedge] == copyedge);
1162 assert(csr_edgeflipped[copyedge] == -1 || csr_edgeflipped[copyedge] == antiedge);
1164 csr_edgeflipped[antiedge] = copyedge;
1165 csr_edgeflipped[copyedge] = antiedge;
1169 for(
int e = 0; e < nedges_org; e++ )
1171 if( csr_edgeDefaultToCsr[e] >= 0 )
1173 const int csr_pos = csr_edgeDefaultToCsr[e];
1174 assert(csr_edgeflipped[csr_pos] == -1);
1175 csr_edgeflipped[csr_pos] = csr_edgeDefaultToCsr[
flipedge(e)];
1193 assert(nterms >= 2);
1195 return nnodes + nterms - 1;
1208 int nedges_enlarged = nedges;
1212 assert(nedges >= 2);
1214 for(
int i = 0; i <
nnodes; i++ )
1220 nedges_enlarged += 2 * g->
grad[i] + 2;
1223 return nedges_enlarged;
1239 nodes_wakeState[
root] = 1;
1240 rootcut[rootcutsize++] =
root;
1245 const int k = rootcut[i];
1247 assert(rootcutsize <= g->knots);
1248 assert(k < g->knots);
1256 const int head = g->
head[e];
1259 if( nodes_wakeState[head] == 0 )
1261 nodes_wakeState[head] = 1;
1264 rootcut[rootcutsize++] = head;
1311 assert(mincut && scip);
1316 assert(mincut->
xval);
1329 for(
int i = 0; i < nedges; i++ )
1335 for(
int k = 0; k <
nnodes; k++ )
1337 nodes_wakeState[k] = 0;
1341 for(
int i = 0; i < nedges; i++ )
1359 int* RESTRICT nodes_termToCopy;
1361 int* RESTRICT terms_sepasize;
1363 int nnodes_enlarged;
1364 int nedges_enlarged;
1368 assert(mincut && scip);
1393 for(
int i = 0; i <
nnodes; i++ )
1395 nodes_termToCopy[i] = -1;
1396 terms_sepasize[i] =
nnodes;
1397 terms_mincompsize[i] =
nnodes;
1406 for(
int k = 0; k < nnodes_enlarged; k++ )
1408 nodes_wakeState[k] = 0;
1412 for(
int i = 0; i < nedges_enlarged; i++ )
1500 int* RESTRICT excess = g->
mincut_e;
1501 int* RESTRICT residual = g->
mincut_r;
1504 assert(residual && edgecurr);
1505 assert(xval && vars && edges_isRemoved);
1508 #ifdef SCIP_DISABLED 1509 for(
int e = 0; e < nedges; e += 2 )
1511 const int erev = e + 1;
1517 eIsRemoved = edges_isRemoved[e] && edges_isRemoved[erev];
1519 assert(eIsRemoved || !edges_isRemoved[e] || !edges_isRemoved[erev]);
1524 edges_capa[erev] = 0;
1529 csr_headarr[erev] = 1;
1539 csr_headarr[e] =
SCIPisFeasGE(scip, xval[e], 1.0) ? 0 : 1;
1540 csr_headarr[erev] =
SCIPisFeasGE(scip, xval[erev], 1.0) ? 0 : 1;
1545 for(
int e = 0; e < nedges; e++ )
1547 SCIP_Bool eIsRemoved = edges_isRemoved[e];
1549 if( intree && !eIsRemoved )
1565 csr_headarr[e] =
SCIPisFeasGE(scip, xval[e], 1.0) ? 0 : 1;
1573 nodes_wakeState[
root] = 1;
1575 rootcut[rootcutsize++] =
root;
1580 const int k = rootcut[i];
1582 assert(rootcutsize <= nnodes);
1588 const int head = g->
head[e];
1591 if( nodes_wakeState[head] == 0 )
1593 if( csr_headarr[e] == 0 )
1595 nodes_wakeState[head] = 1;
1596 rootcut[rootcutsize++] = head;
1601 assert(nodes_wakeState[head] == 0);
1602 excess[head] += edges_capa[e];
1608 for(
int e = 0; e < nedges; e++ )
1609 csr_edgeDefaultToCsr[e] = -1;
1615 for(
int k = 0; k <
nnodes; k++ )
1620 if( nodes_wakeState[k] == 0 )
1625 const int head = g->
head[e];
1626 if( nodes_wakeState[head] == 0 )
1628 if( edges_capa[e] == 0 && edges_capa[
flipedge(e)] == 0 )
1633 csr_headarr[csr_nedges++] = head;
1638 if( edgecurr[k] == csr_nedges )
1640 nodes_wakeState[k] = 1;
1644 terms[ntermcands++] = k;
1660 for(
int e = 0; e < nedges; e++ )
1662 if( csr_edgeDefaultToCsr[e] >= 0 )
1664 const int csr_pos = csr_edgeDefaultToCsr[e];
1665 csr_edgeflipped[csr_pos] = csr_edgeDefaultToCsr[
flipedge(e)];
1703 int* RESTRICT termcands = mincut->
terms;
1707 int mindist = g->
knots + 1;
1710 assert(termcands !=
NULL);
1711 assert(ntermcands > 0);
1718 assert(0 <= pos && pos <= ntermcands - 1);
1720 SWAP_INTS(termcands[ntermcands - 1], termcands[pos]);
1723 assert(w[termcands[ntermcands - 1]] == 0);
1724 return termcands[ntermcands - 1];
1731 assert(w[termcands[i]] >= 0);
1733 if( w[termcands[i]] == 0 )
1751 if( w[termcands[i]] > wmax )
1754 wmax = w[termcands[i]];
1757 else if( w[termcands[i]] == wmax && g->
mincut_dist[termcands[i]] < mindist )
1768 assert(k < ntermcands);
1771 termcands[k] = termcands[ntermcands - 1];
1794 assert(g->
source == root);
1819 assert(scip && mincut);
1840 #ifdef SCIP_DISABLED 1861 for(
int i = 0; i <
nnodes; i++ )
1862 nodes_isVisited[i] =
FALSE;
1864 printf(
"check for removables from %d \n", sinkterm);
1869 nodes_isVisited[sinkterm] =
TRUE;
1874 const int node = queue[i];
1880 for(
int e = g->
outbeg[node]; e >= 0; e = g->
oeat[e] )
1882 const int head = g->
head[e];
1884 if( nodes_wakeState[head] == 0 && !nodes_isVisited[head] )
1888 nodes_isVisited[head] =
TRUE;
1893 printf(
"found terminal %d \n", head);
1902 if( head == mincut->
terms[t] )
1904 printf(
"removing terminal %d \n", head);
1933 const int* nodes_inRootComp,
1937 const int updatecapa,
1946 const int*
const gtail = g->
tail;
1947 const int*
const ghead = g->
head;
1950 assert(g->
knots > 0);
1952 assert(!updatecapa);
1959 assert(nodes_inRootComp[g->
source]);
1961 for(
int i = 0; i < nedges; i++ )
1963 if( !nodes_inRootComp[ghead[i]] && nodes_inRootComp[gtail[i]] )
1965 #ifdef STP_USE_ADVANCED_FLOW 1981 if( edges_isRemoved[i] )
1983 assert(
EQ(xvals[i], 0.0));
2012 assert(!infeasible);
2040 int nedges = g->
edges;
2042 assert(0 &&
"currently not supported!");
2044 assert(xval !=
NULL);
2046 for( k = 0; k < nedges; k += 2 )
2052 capa[krev] = (int) (xval[krev] *
FLOW_FACTOR + 0.5);
2084 assert(maxnsepas >= 1);
2085 assert(maxsepasize >= 2);
2088 tsepas = *termsepas;
2102 for(
int i = 0; i <= maxsepasize; i++ )
2119 assert(scip && termsepas);
2121 tsepas = *termsepas;
2153 assert(sepasize >= 1 && sepasize <= termsepas->maxsepasize);
2154 assert(termsepas->
nsepas[sepasize] >= 0);
2157 return termsepas->
nsepas[sepasize];
2169 assert(termsepas && sinkterm && nsinknodes);
2170 assert(sepasize >= 1 && sepasize <= termsepas->maxsepasize);
2186 assert(termsepas && sinkterm && nsinknodes);
2187 assert(sepasize >= 1 && sepasize <= termsepas->maxsepasize);
2188 assert(termsepas->
currsepa_n[sepasize] >= -1);
2201 const int startpos = termsepas->
currsepa_n[sepasize] + 1;
2204 assert(0 <= startpos && startpos <= termsepas->nsepas_all);
2206 for( s = startpos; s < termsepas->
nsepas_all; s++ )
2208 const int size = starts[s + 1] - starts[s];
2209 assert(sepasize >= 1 && sepasize <= termsepas->maxsepasize);
2211 if( size == sepasize )
2217 if( s < termsepas->nsepas_all )
2223 return &(terms[starts[s]]);
2238 return termsepas->
root;
2264 assert(nnodes > 0 && nedges >= 2);
2265 assert(nedges % 2 == 0);
2285 assert(scip && g && termsepas);
2306 assert(nodes_wakeState);
2331 if( nodes_wakeState[sinkterm] != 1 )
2334 assert(nodes_wakeState[mincut->
root] != 0);
2338 debugPrintCsrCutEdges(g, mincut);
2372 #ifdef SCIP_DISABLED 2373 const SCIP_Bool nested_cut = conshdlrdata->nestedcut;
2374 const SCIP_Bool back_cut = conshdlrdata->backcut;
2375 const SCIP_Bool creep_flow = conshdlrdata->creepflow;
2376 const SCIP_Bool disjunct_cut = conshdlrdata->disjunctcut;
2389 #ifdef STP_MAXFLOW_TIME 2390 clock_t startt, endt;
2391 double cpu_time_used;
2395 assert(conshdlr && ncuts);
2396 assert(creep_flow ==
TRUE);
2397 assert(nested_cut ==
FALSE);
2398 assert(disjunct_cut ==
FALSE);
2405 #ifdef STP_MAXFLOW_TIME 2407 cpu_time_used = ((double) (endt - startt)) / CLOCKS_PER_SEC;
2413 xval = mincut->
xval;
2419 assert(xval && nodes_wakeState && edges_isRemoved);
2435 if( nested_cut && !disjunct_cut )
2441 const SCIP_Bool localcut = (termorg !=
NULL && termorg[sinkterm] != g->
term[sinkterm]);
2443 #ifdef STP_MAXFLOW_WRITE 2448 if( nodes_wakeState[sinkterm] != 1 )
2451 assert(nodes_wakeState[g->
source] != 0);
2454 mincut->
edges_capa, nested_cut || disjunct_cut, localcut, &addedcut) );
2467 for(
int k = 0; k <
nnodes; k++ )
2473 mincut->
edges_capa, nested_cut || disjunct_cut, localcut, &addedcut) );
2483 if( *ncuts >= maxncuts )
2491 while( nested_cut );
2494 #ifdef STP_MAXFLOW_TIME 2496 cpu_time_used = ((double) (endt - startt)) / CLOCKS_PER_SEC;
2499 #ifdef SCIP_DISABLED 2506 for( k = 0; k <
nnodes; k++ )
2507 nodes_wakeState[k] = 0;
2509 if( !nested_cut || disjunct_cut )
2521 assert(g->
terms[i] == 0);
2524 if( nested_cut && !disjunct_cut )
2535 for( k = 0; k <
nnodes; k++ )
2537 g->
mark[k] = (nodes_wakeState[k] != 0) ? 0 : 1;
2538 nodes_wakeState[k] = 0;
2546 if( *ncuts >= maxncuts )
2551 #ifdef SCIP_DISABLED 2552 if (nested_cut || disjunct_cut)
2553 for(k = p->beg[p->rcnt - 1]; k < p->nzcnt; k++)
2555 + (((p->ind[k] % nedges) % 2)
2559 while( nested_cut );
#define STP_Vectype(type)
int graph_get_nEdges(const GRAPH *)
static volatile int nterms
#define StpVecGetSize(vec)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
static void termsepaCsrAddEdges(const GRAPH *g, MINCUT *mincut)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
#define SCIPfreeMemoryArray(scip, ptr)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_VAR ** SCIPprobdataGetVars(SCIP *scip)
static void updateTerminalSource(SCIP *scip, int rootcand, const GRAPH *g, int *root, int *rootcompsize)
#define SCIPallocMemoryArray(scip, ptr, num)
void graph_knot_printInfo(const GRAPH *, int)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool mincut_findTerminalSeparatorsIsPromising(const GRAPH *g)
int mincut_termsepasGetSource(const TERMSEPAS *termsepas)
static SCIP_RETCODE lpcutAdd(SCIP *scip, SCIP_CONSHDLR *conshdlr, const GRAPH *g, const int *nodes_inRootComp, const STP_Bool *edges_isRemoved, const SCIP_Real *xvals, int *capa, const int updatecapa, SCIP_Bool local, SCIP_Bool *success)
SCIP_Real SCIPinfinity(SCIP *scip)
Problem data for stp problem.
#define SWAP_INTS(int1, int2)
enum SCIP_Retcode SCIP_RETCODE
static void termsepaCsrAddReverseEdges(const GRAPH *g, MINCUT *mincut)
static void mincutExec(const GRAPH *g, int sinkterm, SCIP_Bool wasRerun, MINCUT *mincut)
#define StpVecPopBack(vec)
#define StpVecReserve(scip, vec, _size_)
int SCIPrandomGetInt(SCIP_RANDNUMGEN *randnumgen, int minrandval, int maxrandval)
SCIP_RETCODE graph_mincut_reInit(SCIP *, int, int, GRAPH *)
static void termsepaCollectCutNodes(const GRAPH *g, const TERMSEPAS *termsepas, const MINCUT *mincut, int sinkterm, int *cutterms, int *ncutterms, SCIP_Bool *cutIsGood)
#define SCIPfreeBufferArray(scip, ptr)
static SCIP_RETCODE termsepaStoreCutTry(SCIP *scip, const GRAPH *g, int sinkterm, MINCUT *mincut, TERMSEPAS *termsepas)
int mincut_termsepasGetNall(const TERMSEPAS *termsepas)
header only, simple implementation of an STL like vector
#define TERMSEPA_SPARSE_MAXRATIO
static SCIP_RETCODE mincutInitForTermSepa(SCIP *scip, GRAPH *g, MINCUT *mincut)
#define SCIPallocCleanBufferArray(scip, ptr, num)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
static int mincutGetNextSinkTerm(const GRAPH *g, SCIP_Bool firstrun, MINCUT *mincut)
#define TERMSEPA_NROOTCANDS
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
STP_Bool * edges_isRemoved
static SCIP_RETCODE mincutPrepareForLp(SCIP *scip, const GRAPH *g, MINCUT *mincut)
int *RESTRICT mincut_dist
miscellaneous methods used for solving Steiner problems
int graph_get_nTerms(const GRAPH *)
void graph_get_nVET(const GRAPH *, int *, int *, int *)
void graph_mincut_setDefaultVals(GRAPH *)
static SCIP_RETCODE mincutInitForLp(SCIP *scip, const GRAPH *g, MINCUT *mincut)
SCIP_RETCODE mincut_findTerminalSeparators(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, GRAPH *g, TERMSEPAS *termsepas)
static SCIP_Bool termsepaCutIsCorrect(SCIP *scip, const GRAPH *g, int ncutterms, const int *cutterms, int sinkterm, const MINCUT *mincut)
#define SCIPfreeBufferArrayNull(scip, ptr)
static SCIP_RETCODE termsepaCsrInit(const GRAPH *g, MINCUT *mincut)
SCIP_RETCODE reduce_unconnected(SCIP *, GRAPH *)
struct terminal_separator TSEPA
static int termsepaCsrGetMaxNnodes(const GRAPH *g)
static SCIP_RETCODE mincutPrepareForTermSepa(SCIP *scip, GRAPH *g, MINCUT *mincut)
int * termsepa_termToCopy
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
static SCIP_RETCODE mincutInit(SCIP *scip, SCIP_RANDNUMGEN *randnumgen, SCIP_Bool isLpcut, GRAPH *g, MINCUT **mincut)
static void lpcutSetEdgeCapacity(const GRAPH *g, const SCIP_Real *xval, SCIP_Bool creep_flow, SCIP_Bool flip, int *RESTRICT capa)
#define SCIPallocBufferArray(scip, ptr, num)
int SCIPgetDepth(SCIP *scip)
int mincut_termsepasGetN(const TERMSEPAS *termsepas, int sepasize)
void mincut_termsepasFree(SCIP *scip, TERMSEPAS **termsepas)
void SCIPrandomPermuteIntArray(SCIP_RANDNUMGEN *randnumgen, int *array, int begin, int end)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
static SCIP_Bool csrFlipedgesAreValid(const GRAPH *g, const MINCUT *mincut)
void graph_mincut_exec(const GRAPH *, const int, const int, const int, const int, const int, const int *, const int *, int *RESTRICT, const int *, const int *, const int *, const SCIP_Bool)
#define BMScopyMemoryArray(ptr, source, num)
void graph_edge_printInfo(const GRAPH *, int)
struct minimum_cut_helper MINCUT
static int termsepaFindTerminalSource(SCIP *scip, const GRAPH *g, const MINCUT *mincut)
static void mincutFree(SCIP *scip, MINCUT **mincut)
static void termsepaCsrAddTermCopies(const GRAPH *g, MINCUT *mincut)
SCIP_RETCODE mincut_termsepasInit(SCIP *scip, const GRAPH *g, int maxnsepas, int maxsepasize, TERMSEPAS **termsepas)
int *RESTRICT mincut_numb
#define SCIPfreeMemory(scip, ptr)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
const int * mincut_termsepasGetFirst(int sepasize, TERMSEPAS *termsepas, int *sinkterm, int *nsinknodes)
SCIP_RANDNUMGEN * randnumgen
static SCIP_RETCODE termsepaBuildCsr(const GRAPH *g, MINCUT *mincut)
static int termsepaCsrGetMaxNedges(int root, const GRAPH *g)
const int * mincut_termsepasGetNext(int sepasize, TERMSEPAS *termsepas, int *sinkterm, int *nsinknodes)
#define SCIPfreeCleanBufferArray(scip, ptr)
SCIP_Bool SCIPisStopped(SCIP *scip)
#define StpVecFree(scip, vec)
SCIP_Real * SCIPprobdataGetXval(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
int graph_get_nNodes(const GRAPH *)
#define SCIPallocMemory(scip, ptr)
SCIP_Bool graph_knot_isInRange(const GRAPH *, int)
void graph_getTerms(const GRAPH *, int *)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
#define StpVecPushBack(scip, vec, value)
int * csr_edgeDefaultToCsr
#define SCIP_CALL_ABORT(x)
SCIP_RETCODE SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Minimum cut routines for Steiner problems.
includes various reduction methods for Steiner tree problems
static void termsepaBuildRootcomp(const GRAPH *g, MINCUT *mincut)
static SCIP_RETCODE termsepaGetCompNnodes(SCIP *scip, const GRAPH *g, int ncutterms, const int *cutterms, int sinkterm, MINCUT *mincut, int *ncompnodes)
void graph_printInfoReduced(const GRAPH *)
static int termsepaGetCapaInf(const GRAPH *g, const MINCUT *mincut)
SCIP_RETCODE mincut_separateLp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_RANDNUMGEN *randnumgen, const int *termorg, GRAPH *g, int maxncuts, int *ncuts)
static SCIP_RETCODE termsepaStoreCutFinalize(SCIP *scip, const GRAPH *g, int sinkterm, MINCUT *mincut, int ncutterms, const int *cutterms, TERMSEPAS *termsepas, SCIP_Bool *success)
static SCIP_RETCODE termsepaTraverseSinkComp(SCIP *scip, const GRAPH *g, SCIP_Bool removeTerms, SCIP_Bool updateVisitedTerms, int ncutterms, const int *cutterms, int sinkterm, MINCUT *mincut, int *ncompnodes)
static SCIP_RETCODE termsepaRemoveCutTerminals(SCIP *scip, const GRAPH *g, int ncutterms, const int *cutterms, int sinkterm, MINCUT *mincut)