Detailed Description
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) |
Macro Definition Documentation
◆ SEPA_NAME
#define SEPA_NAME "subtour" |
Definition at line 33 of file sepa_subtour.c.
Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaSubtour().
◆ SEPA_DESC
#define SEPA_DESC "separator that elininates subtours of length smaller than |NCluster|" |
Definition at line 34 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY 1000 |
Definition at line 35 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_FREQ
#define SEPA_FREQ 5 |
Definition at line 36 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 37 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 38 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_DELAY
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 39 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ MAXCUTS
#define MAXCUTS 2000 |
Definition at line 40 of file sepa_subtour.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ MAXROUNDS
#define MAXROUNDS 15 |
Definition at line 41 of file sepa_subtour.c.
Referenced by SCIP_DECL_SEPAEXECLP().
Function Documentation
◆ getDist()
get distance of longest path between two states with exactly n arcs from the matrix
- Parameters
-
adjacencymatrix the adjacency-matrices of all paths with 1,...,|Clutster| arcs n length state1 starting state state2 end state
Definition at line 66 of file sepa_subtour.c.
References NULL.
Referenced by addPathCuts(), addSubtourCuts(), addTourCuts(), computeNextAdjacency(), and SCIP_DECL_SEPAEXECLP().
◆ addSubtourCuts()
|
static |
After finding a violation, construct and add all violated subtour cuts to scip
- Parameters
-
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 81 of file sepa_subtour.c.
References FALSE, getDist(), getEdgevar(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, 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().
◆ addPathCuts()
|
static |
Detect if path inequalities are violated and if so, add them to scip
- Parameters
-
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 279 of file sepa_subtour.c.
References FALSE, getDist(), getEdgevar(), MAX, NULL, 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().
◆ addTourCuts()
|
static |
detect if path inequalities are violated and if so, add them to scip
- Parameters
-
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 459 of file sepa_subtour.c.
References computeNextAdjacency(), FALSE, getDist(), getEdgevar(), MAX, NULL, SCIP_Bool, 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().
◆ computeNextAdjacency()
|
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*}
.
- Parameters
-
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 609 of file sepa_subtour.c.
References FALSE, getDist(), nnodes, SCIP_Bool, SCIPdigraphGetNNodes(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPisGT(), SCIPisPositive(), and TRUE.
Referenced by addTourCuts(), and SCIP_DECL_SEPAEXECLP().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 667 of file sepa_subtour.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaSubtour(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 681 of file sepa_subtour.c.
References addPathCuts(), addSubtourCuts(), addTourCuts(), computeNextAdjacency(), getDist(), getEdgevar(), MAX, MAXCUTS, MAXROUNDS, NULL, 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().
◆ SCIPincludeSepaSubtour()
SCIP_RETCODE SCIPincludeSepaSubtour | ( | SCIP * | scip | ) |
creates the Subtour separator and includes it in SCIP
- Parameters
-
scip SCIP data structure
Definition at line 867 of file sepa_subtour.c.
References 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().