sepa_subtour.c
Go to the documentation of this file.
25 * @brief If there exists a transition forward along the cycle, then the state that the transition originates from can
26 * be reached only after another ncluster - 1 transitions. Therefore cycles with a number of transitions smaller than
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
76 SCIP_Real*** adjacencymatrix, /**< the adjacency-matrices of all paths with 1,...,|Clutster| arcs */
93 SCIP_Real*** adjacencymatrix, /**< the adjacency-matrices of all paths with 1,...,|Clutster| arcs */
131 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &subtours[k], cyclelength + 1) ); /*lint !e866, !e776*/
142 if( SCIPisGT(scip, getDist(adjacencymatrix, cyclelength - 1, anchor, anchor), cyclelength - 1.0) )
190 /* if this anchor is already in another subtour, we check if the subtour is the same, since we don't want to
231 SCIP_CALL( SCIPaddVarToRow(scip, cut, getEdgevar(edgevars, currentnode, intermediate, 1), 1.0) );
252 if( SCIPvarGetLPSol(getEdgevar(edgevars, MAX(currentnode, successor), MIN(currentnode, successor), 0))
291 SCIP_Real*** adjacencymatrix, /**< the adjacency-matrix of all paths with 1,...,|Clutster| arcs */
394 SCIP_CALL( SCIPaddVarToRow(scip, cut, getEdgevar(edgevars, currentnode, intermediate, 1), 1.0) );
409 getEdgevar(edgevars, MAX(currentnode, intermediate), MIN(currentnode, intermediate), 0), 1.0) );
471 SCIP_Real*** adjacencymatrix, /**< the adjacency-matrix of all paths with 1,...,|Clutster| arcs */
566 SCIP_CALL( SCIPaddVarToRow(scip, cut, getEdgevar(edgevars, currentnode, intermediate, 1), 1.0) );
612 /** compute the next matrix with the weight off all the longest paths with exactly narcs and store it in
614 * \f{align*}{ d^{k}(currentnode,successor) = max_{l=1,\ldots,n} \{d^{k-1}(currentnode,l) + d^1(l,successor) \} \f}.
618 (
620 SCIP_Real*** adjacencymatrix, /**< the max-distance matrices for all number of arcs less than narcs. */
657 adjacencymatrix[narcs - 1][currentnode][successor] = getDist(adjacencymatrix, 0, currentnode, intermediate)
668 if( SCIPisGT(scip, getDist(adjacencymatrix, narcs - 1, currentnode, currentnode), narcs - 1.0) )
742 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &adjacencymatrix[k][j], nstates) ); /*lint !e866*/
765 /* contract the adjacency matrix if it is better to take z_{ij} + y_{jk} rather than z_{ik} directly,
790 if( edgevars[state1][state2] == NULL || edgevars[state2][state3] == NULL || edgevars[state1][state3] == NULL )
822 /* Iterate until we have found a sufficient number of cuts or until we have checked all possible violations */
831 SCIP_CALL( addSubtourCuts(scip, sepa, adjacencymatrix, adjacencygraph, iscontracted, cyclelength,
836 SCIP_CALL( addPathCuts(scip, sepa, adjacencymatrix, adjacencygraph, iscontracted, cyclelength, result, &ncuts) );
884 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
Definition: type_result.h:42
static SCIP_Bool computeNextAdjacency(SCIP *scip, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int narcs)
Definition: sepa_subtour.c:618
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
Separate Subtours-Elimination inequalities in Cycle-Clustering Applications.
Definition: struct_scip.h:68
void SCIPdigraphFreeComponents(SCIP_DIGRAPH *digraph)
Definition: misc.c:8429
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_VAR * getEdgevar(SCIP_VAR ****edgevars, int state1, int state2, int direction)
Definition: probdata_cyc.c:1480
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1698
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7731
Definition: struct_var.h:207
Definition: type_result.h:49
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:445
Definition: struct_sepa.h:46
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_RETCODE SCIPcreateDigraph(SCIP *scip, SCIP_DIGRAPH **digraph, int nnodes)
Definition: scip_datastructures.c:617
static SCIP_RETCODE addTourCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int **iscontracted, int tourlength, SCIP_RESULT *result, int *ncuts)
Definition: sepa_subtour.c:468
static SCIP_Real getDist(SCIP_Real ***adjacencymatrix, int n, int state1, int state2)
Definition: sepa_subtour.c:75
Definition: type_result.h:44
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:458
Definition: type_retcode.h:42
SCIP_RETCODE SCIPdigraphAddArc(SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
Definition: misc.c:7574
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)
Definition: scip_sepa.c:109
public data structures and miscellaneous methods
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
Definition: misc.c:7716
static SCIP_RETCODE addPathCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int **iscontracted, int pathlength, SCIP_RESULT *result, int *ncuts)
Definition: sepa_subtour.c:288
Definition: struct_lp.h:201
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)
Definition: scip_lp.c:1453
problem data for cycle clustering problem
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:484
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2209
Definition: objbenders.h:43
static SCIP_RETCODE addSubtourCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real ***adjacencymatrix, SCIP_DIGRAPH *adjacencygraph, int **iscontracted, int cyclelength, SCIP_RESULT *result, int *ncuts)
Definition: sepa_subtour.c:90
Definition: struct_misc.h:219