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 42 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 43 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY 1000 |
Definition at line 44 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_FREQ
#define SEPA_FREQ 5 |
Definition at line 45 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ SEPA_MAXBOUNDDIST
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 46 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 47 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 48 of file sepa_subtour.c.
Referenced by SCIPincludeSepaSubtour().
◆ MAXCUTS
#define MAXCUTS 2000 |
Definition at line 49 of file sepa_subtour.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ MAXROUNDS
#define MAXROUNDS 15 |
Definition at line 50 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 75 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 90 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 288 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 468 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 618 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 676 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 690 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 876 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().