42#define SEPA_NAME "subtour"
43#define SEPA_DESC "separator that elininates subtours of length smaller than |NCluster|"
44#define SEPA_PRIORITY 1000
46#define SEPA_MAXBOUNDDIST 0.0
47#define SEPA_USESSUBSCIP FALSE
48#define SEPA_DELAY FALSE
65 for(
i = 0;
i < cyclelength; ++
i )
76 SCIP_Real*** adjacencymatrix,
85 return adjacencymatrix[n][state1][state2];
93 SCIP_Real*** adjacencymatrix,
121 SCIP_Bool isduplicate;
129 for( k = 0; k < nstates; ++k )
136 for( anchor = 0; anchor < nstates; ++anchor )
142 if(
SCIPisGT(
scip,
getDist(adjacencymatrix, cyclelength - 1, anchor, anchor), cyclelength - 1.0) )
144 subtours[anchor][0] = anchor;
145 if( insubtour[anchor] == -1 )
146 insubtour[anchor] = anchor;
149 for( k = 0; k < cyclelength -1; ++k )
151 currentnode = subtours[anchor][k];
153 assert(0 <= currentnode && currentnode < nstates);
159 for( l = 0; l < nsuccessors; l++ )
161 successor = successors[l];
163 assert(0 <= successor && successor < nstates);
167 +
getDist(adjacencymatrix, cyclelength - (k + 2), successor, anchor),
168 getDist(adjacencymatrix, cyclelength - (k + 1), currentnode, anchor)) )
170 subtours[anchor][k + 1] = successor;
171 insubtour[successor] = anchor;
173 if( iscontracted[currentnode][successor] != -1 )
182 subtours[anchor][cyclelength] = anchor;
185 if( iscontracted[subtours[anchor][cyclelength - 1]][anchor] != -1 )
193 if( insubtour[anchor] != anchor )
198 while( subtours[insubtour[anchor]][
c] != anchor )
201 for( k = 0; k < cyclelength && isduplicate; ++k )
203 if( subtours[insubtour[anchor]][(k +
c) % cyclelength] != subtours[anchor][k] )
212 liftabley = cyclelength - 1;
217 cyclelength, ncontractions );
223 for( k = 0; k < cyclelength; ++k )
225 currentnode = subtours[anchor][k];
226 successor = subtours[anchor][k+1];
227 intermediate = iscontracted[currentnode][successor];
229 if( intermediate != -1 )
233 getEdgevar(edgevars,
MAX(intermediate, successor),
MIN(intermediate, successor), 0), 1.0) );
235 greater = intermediate > currentnode ? intermediate : currentnode;
236 smaller = intermediate < currentnode ? intermediate : currentnode;
253 > 0 && liftabley > 0 )
256 getEdgevar(edgevars,
MAX(currentnode, successor),
MIN(currentnode, successor), 0), 1.0) );
276 for( k = 0; k < nstates; ++k )
291 SCIP_Real*** adjacencymatrix,
323 for( start = 0; start < nstates; ++start )
332 path[pathlength] = end;
336 +
getDist(adjacencymatrix, 0, start, end), (SCIP_Real) pathlength) )
339 for( k = 0; k < pathlength - 1; ++k )
341 currentnode = path[k];
343 assert(0 <= currentnode && currentnode < nstates);
348 for(
i = 0;
i < nsuccessors; ++
i )
350 successor = successors[
i];
352 assert(0 <= successor && successor < nstates);
355 +
getDist(adjacencymatrix, pathlength - (k + 2), successor, end),
356 getDist(adjacencymatrix, pathlength - (k + 1), currentnode, end)) )
358 path[k + 1] = successor;
360 if( iscontracted[currentnode][successor] != -1 )
369 if( iscontracted[path[pathlength - 1]][end] != -1 )
372 if( iscontracted[start][end] != -1 )
380 start, end, pathlength, ncontractions );
386 for( k = 0; k < pathlength; ++k )
388 currentnode = path[k];
389 successor = path[k+1];
390 intermediate = iscontracted[currentnode][successor];
392 if( intermediate != -1 )
396 getEdgevar(edgevars,
MAX(intermediate, successor),
MIN(intermediate, successor), 0), 1.0) );
406 getEdgevar(edgevars,
MAX(currentnode, intermediate),
MIN(currentnode, intermediate), 0))) )
409 getEdgevar(edgevars,
MAX(currentnode, intermediate),
MIN(currentnode, intermediate), 0), 1.0) );
418 getEdgevar(edgevars,
MAX(currentnode, successor),
MIN(currentnode, successor), 0))) )
421 getEdgevar(edgevars,
MAX(currentnode, successor),
MIN(currentnode, successor), 0), 1.0) );
428 intermediate = iscontracted[start][end];
430 if( iscontracted[start][end] != -1 )
434 MAX(intermediate, end),
MIN(intermediate, end), 0), 1.0) );
471 SCIP_Real*** adjacencymatrix,
484 int* succerssorsstart;
485 int nsuccessorsstart;
503 for( start = 0; start < nstates; ++start )
509 for( j = 0; j < nsuccessorsstart; ++j )
513 end = succerssorsstart[j];
514 tour[tourlength] = end;
518 -
getDist(adjacencymatrix, 0, end, start), (SCIP_Real) tourlength - 1) )
521 for( k = 0; k < tourlength - 1; ++k )
523 currentnode = tour[k];
527 for(
i = 0;
i < nsuccessors; ++
i )
529 successor = successors[
i];
532 +
getDist(adjacencymatrix, tourlength - (k + 2), successor, end)
533 ,
getDist(adjacencymatrix, tourlength - (k + 1), currentnode, end)) )
535 tour[k + 1] = successor;
537 if( iscontracted[currentnode][successor] != -1 )
545 if( iscontracted[tour[tourlength - 1]][end] != -1 )
547 if( iscontracted[end][start] != -1 )
552 start, end, tourlength, ncontractions );
554 (SCIP_Real) tourlength + ncontractions - 1,
FALSE,
FALSE,
TRUE) );
558 for( k = 0; k < tourlength; ++k )
560 currentnode = tour[k];
561 successor = tour[k+1];
562 intermediate = iscontracted[currentnode][successor];
564 if( intermediate != -1 )
568 getEdgevar(edgevars,
MAX(intermediate, successor),
MIN(intermediate, successor), 0), 1.0) );
577 intermediate = iscontracted[end][start];
578 if( iscontracted[end][start] != -1 )
582 getEdgevar(edgevars,
MAX(intermediate, start),
MIN(intermediate, start), 0), 1.0) );
620 SCIP_Real*** adjacencymatrix,
632 SCIP_Bool foundviolation;
634 foundviolation =
FALSE;
637 for( currentnode = 0; currentnode <
nnodes; ++currentnode )
642 for( l = 0; l < nintermediates; ++l )
644 intermediate = intermediates[l];
648 for( successor = 0; successor <
nnodes; ++successor )
654 +
getDist(adjacencymatrix,
narcs - 2, intermediate, successor),
655 getDist(adjacencymatrix,
narcs - 1, currentnode, successor)) )
657 adjacencymatrix[
narcs - 1][currentnode][successor] =
getDist(adjacencymatrix, 0, currentnode, intermediate)
658 +
getDist(adjacencymatrix,
narcs - 2, intermediate, successor);
666 for( currentnode = 0; currentnode <
nnodes; ++currentnode )
669 foundviolation =
TRUE;
671 return foundviolation;
693 SCIP_Real*** adjacencymatrix;
729 assert(ncluster > 0 && ncluster < nstates);
736 for( k = 0; k < ncluster; ++k )
740 for( j = 0; j < nstates; ++j )
752 for(
i = 0;
i < nstates; ++
i )
756 for( j = 0; j < nstates; ++j )
758 iscontracted[
i][j] = -1;
768 for(
i = 0;
i < nstates; ++
i )
777 for( j = 0; j < nsuccessors1; ++j )
779 state2 = successors1[j];
786 for( k = 0 ; k < nsuccessors2; ++k )
788 state3 = successors2[k];
790 if( edgevars[state1][state2] ==
NULL || edgevars[state2][state3] ==
NULL || edgevars[state1][state3] ==
NULL )
800 iscontracted[state1][state3] = state2;
807 for(
i = 0;
i < nstates; ++
i )
809 for( j = 0; j < nstates; ++j )
823 while( cyclelength < ncluster )
838 if( cyclelength == ncluster - 1 )
855 for(
i = 0;
i < nstates; ++
i )
861 for(
i = 0;
i < ncluster; ++
i )
863 for( j = 0; j < nstates; ++j )
886 sepaExeclpSubtour,
NULL,
Constraint handler for linear constraints in their most general form, .
void SCIPdigraphFreeComponents(SCIP_DIGRAPH *digraph)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
int SCIPdigraphGetNNodes(SCIP_DIGRAPH *digraph)
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
void SCIPdigraphFree(SCIP_DIGRAPH **digraph)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
#define SCIPallocMemoryArray(scip, ptr, num)
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
#define SCIPfreeMemoryArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetLPSol(SCIP_VAR *var)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
SCIP_VAR * getEdgevar(SCIP_VAR ****edgevars, int state1, int state2, int direction)
SCIP_VAR **** SCIPcycGetEdgevars(SCIP *scip)
int SCIPcycGetNBins(SCIP *scip)
int SCIPcycGetNCluster(SCIP *scip)
SCIP_DIGRAPH * SCIPcycGetEdgeGraph(SCIP *scip)
problem data for cycle clustering problem
public data structures and miscellaneous methods
static SCIP_RETCODE addSubtourCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int **iscontracted, int cyclelength, SCIP_RESULT *result, int *ncuts)
static SCIP_RETCODE addPathCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int **iscontracted, int pathlength, SCIP_RESULT *result, int *ncuts)
#define SEPA_MAXBOUNDDIST
static SCIP_Real getDist(SCIP_Real ***adjacencymatrix, int n, int state1, int state2)
static SCIP_RETCODE addTourCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int **iscontracted, int tourlength, SCIP_RESULT *result, int *ncuts)
static SCIP_Bool computeNextAdjacency(SCIP *scip, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int narcs)
SCIP_RETCODE SCIPincludeSepaSubtour(SCIP *scip)
Separate Subtours-Elimination inequalities in Cycle-Clustering Applications.
enum SCIP_Result SCIP_RESULT
enum SCIP_Retcode SCIP_RETCODE
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPACOPY(x)