Scippy

SCIP

Solving Constraint Integer Programs

sepa_subtour.c File Reference

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
adjacencymatrixthe adjacency-matrices of all paths with 1,...,|Clutster| arcs
nlength
state1starting state
state2end 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
scipSCIP data structure.
sepathe subtour separator
adjacencymatrixthe adjacency-matrices of all paths with 1,...,|Clutster| arcs
adjacencygraphthe directed edge-graph
iscontractedinformation of intermediate contraction-nodes for contracted arcs
cyclelengththe length of the subtours to add
resultpointer to store the result of separation
ncutspointer 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
scipSCIP data structure.
sepathe subtour separator
adjacencymatrixthe adjacency-matrix of all paths with 1,...,|Clutster| arcs
adjacencygraphthe directed edge-graph
iscontractedinformation of intermediate contraction-nodes for contracted arcs
pathlengththe length of the subtours to add
resultpointer to store the result of separation
ncutspointer 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
scipSCIP data structure.
sepathe subtour separator
adjacencymatrixthe adjacency-matrix of all paths with 1,...,|Clutster| arcs
adjacencygraphthe directed edge-graph
iscontractedinformation of intermediate contraction-nodes for contracted arcs
tourlengththe length of the subtours to add
resultpointer to store the result of separation
ncutspointer 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
scipSCIP data structure
adjacencymatrixthe max-distance matrices for all number of arcs less than narcs.
adjacencygraphthe directed edge-graph
narcsthe 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()

◆ SCIPincludeSepaSubtour()

SCIP_RETCODE SCIPincludeSepaSubtour ( SCIP scip)

creates the Subtour separator and includes it in SCIP

Parameters
scipSCIP 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().