If there exists a transition forward along the cycle, then the state that the transition originates from can be reached only after another ncluster - 1 transitions. Therefore cycles with a number of transitions smaller than that can be separated.
Definition in file sepa_subtour.c.
#include <assert.h>
#include <string.h>
#include "sepa_subtour.h"
#include "probdata_cyc.h"
#include "scip/cons_linear.h"
#include "scip/pub_misc.h"
Go to the source code of this file.
Macros | |
#define | SEPA_NAME "subtour" |
#define | SEPA_DESC "separator that elininates subtours of length smaller than |NCluster|" |
#define | SEPA_PRIORITY 1000 |
#define | SEPA_FREQ 5 |
#define | SEPA_MAXBOUNDDIST 0.0 |
#define | SEPA_USESSUBSCIP FALSE |
#define | SEPA_DELAY FALSE |
#define | MAXCUTS 2000 |
#define | MAXROUNDS 15 |
Functions | |
static SCIP_Real | getDist (SCIP_Real ***adjacencymatrix, int n, int state1, int state2) |
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) |
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) |
static | SCIP_DECL_SEPACOPY (sepaCopySubtour) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpSubtour) |
SCIP_RETCODE | SCIPincludeSepaSubtour (SCIP *scip) |
#define SEPA_NAME "subtour" |
Definition at line 42 of file sepa_subtour.c.
#define SEPA_DESC "separator that elininates subtours of length smaller than |NCluster|" |
Definition at line 43 of file sepa_subtour.c.
#define SEPA_PRIORITY 1000 |
Definition at line 44 of file sepa_subtour.c.
#define SEPA_FREQ 5 |
Definition at line 45 of file sepa_subtour.c.
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 46 of file sepa_subtour.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 47 of file sepa_subtour.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 48 of file sepa_subtour.c.
#define MAXCUTS 2000 |
Definition at line 49 of file sepa_subtour.c.
#define MAXROUNDS 15 |
Definition at line 50 of file sepa_subtour.c.
get distance of longest path between two states with exactly n arcs from the matrix
adjacencymatrix | the adjacency-matrices of all paths with 1,...,|Clutster| arcs |
n | length |
state1 | starting state |
state2 | end state |
Definition at line 75 of file sepa_subtour.c.
References assert(), NULL, and SCIP_Real.
Referenced by addPathCuts(), addSubtourCuts(), addTourCuts(), computeNextAdjacency(), and SCIP_DECL_SEPAEXECLP().
|
static |
After finding a violation, construct and add all violated subtour cuts to scip
scip | SCIP data structure. |
sepa | the subtour separator |
adjacencymatrix | the adjacency-matrices of all paths with 1,...,|Clutster| arcs |
adjacencygraph | the directed edge-graph |
iscontracted | information of intermediate contraction-nodes for contracted arcs |
cyclelength | the length of the subtours to add |
result | pointer to store the result of separation |
ncuts | pointer to store number of cuts |
Definition at line 90 of file sepa_subtour.c.
References assert(), c, FALSE, getDist(), getEdgevar(), MAX, MIN, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPcycGetEdgevars(), SCIPcycGetNCluster(), SCIPdebug, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPflushRowExtensions(), SCIPfreeBlockMemoryArray, SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), SCIPvarGetLPSol(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
Detect if path inequalities are violated and if so, add them to scip
scip | SCIP data structure. |
sepa | the subtour separator |
adjacencymatrix | the adjacency-matrix of all paths with 1,...,|Clutster| arcs |
adjacencygraph | the directed edge-graph |
iscontracted | information of intermediate contraction-nodes for contracted arcs |
pathlength | the length of the subtours to add |
result | pointer to store the result of separation |
ncuts | pointer to store number of cuts |
Definition at line 288 of file sepa_subtour.c.
References assert(), FALSE, getDist(), getEdgevar(), i, MAX, MIN, NULL, result, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPallocMemoryArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPcycGetEdgevars(), SCIPcycGetNCluster(), SCIPdebug, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPflushRowExtensions(), SCIPfreeMemoryArray, SCIPgetRowMaxCoef(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisPositive(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), SCIPvarGetLPSol(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
detect if path inequalities are violated and if so, add them to scip
scip | SCIP data structure. |
sepa | the subtour separator |
adjacencymatrix | the adjacency-matrix of all paths with 1,...,|Clutster| arcs |
adjacencygraph | the directed edge-graph |
iscontracted | information of intermediate contraction-nodes for contracted arcs |
tourlength | the length of the subtours to add |
result | pointer to store the result of separation |
ncuts | pointer to store number of cuts |
Definition at line 468 of file sepa_subtour.c.
References FALSE, getDist(), getEdgevar(), i, MAX, MIN, NULL, result, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPallocMemoryArray, SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPcycGetEdgevars(), SCIPdebug, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPflushRowExtensions(), SCIPfreeMemoryArray, SCIPgetRowMaxCoef(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPprintRow(), SCIPreleaseRow(), SCIPsnprintf(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
compute the next matrix with the weight off all the longest paths with exactly narcs and store it in adjacencymatrix[narcs - 1]. For this, simply compute
\begin{align*} d^{k}(currentnode,successor) = max_{l=1,\ldots,n} \{d^{k-1}(currentnode,l) + d^1(l,successor) \} \end{align*}
.
scip | SCIP data structure |
adjacencymatrix | the max-distance matrices for all number of arcs less than narcs. |
adjacencygraph | the directed edge-graph |
narcs | the current number of arcs in the paths |
Definition at line 617 of file sepa_subtour.c.
References assert(), FALSE, getDist(), narcs, nnodes, SCIP_Bool, SCIP_Real, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisGT(), SCIPisPositive(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 676 of file sepa_subtour.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaSubtour(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
LP solution separation method of separator
Definition at line 690 of file sepa_subtour.c.
References addPathCuts(), addSubtourCuts(), addTourCuts(), assert(), computeNextAdjacency(), getDist(), getEdgevar(), i, MAX, MAXCUTS, MAXROUNDS, MIN, NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPallocClearBlockMemoryArray, SCIPcreateDigraph(), SCIPcycGetEdgeGraph(), SCIPcycGetEdgevars(), SCIPcycGetNBins(), SCIPcycGetNCluster(), SCIPdigraphAddArc(), SCIPdigraphFree(), SCIPdigraphFreeComponents(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBlockMemoryArray, SCIPisLT(), SCIPisZero(), SCIPsepaGetNCallsAtNode(), and SCIPvarGetLPSol().
SCIP_RETCODE SCIPincludeSepaSubtour | ( | SCIP * | scip | ) |
creates the Subtour separator and includes it in SCIP
scip | SCIP data structure |
Definition at line 876 of file sepa_subtour.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaBasic(), SCIPsetSepaCopy(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, and SEPA_USESSUBSCIP.
Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeCycPlugins().