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.

Author: Leon Eifler

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()

static SCIP_Real getDist	(	SCIP_Real ***	adjacencymatrix,
		int	n,
		int	state1,
		int	state2
	)

static

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 SCIP_RETCODE addSubtourCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_Real ***	adjacencymatrix,
		SCIP_DIGRAPH *	adjacencygraph,
		int **	iscontracted,
		int	cyclelength,
		SCIP_RESULT *	result,
		int *	ncuts
	)

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, MIN, 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 SCIP_RETCODE addPathCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_Real ***	adjacencymatrix,
		SCIP_DIGRAPH *	adjacencygraph,
		int **	iscontracted,
		int	pathlength,
		SCIP_RESULT *	result,
		int *	ncuts
	)

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, MIN, 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 SCIP_RETCODE addTourCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_Real ***	adjacencymatrix,
		SCIP_DIGRAPH *	adjacencygraph,
		int **	iscontracted,
		int	tourlength,
		SCIP_RESULT *	result,
		int *	ncuts
	)

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, MIN, 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 SCIP_Bool computeNextAdjacency	(	SCIP *	scip,
		SCIP_Real ***	adjacencymatrix,
		SCIP_DIGRAPH *	adjacencygraph,
		int	narcs
	)

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 SCIP_DECL_SEPACOPY ( sepaCopySubtour )

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 SCIP_DECL_SEPAEXECLP ( sepaExeclpSubtour )

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, MIN, 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().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ MAXCUTS

◆ MAXROUNDS

Function Documentation

◆ getDist()

◆ addSubtourCuts()

◆ addPathCuts()

◆ addTourCuts()

◆ computeNextAdjacency()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIPincludeSepaSubtour()