Detailed Description

oddcycle separator

Author: Robert Waniek; Marc Pfetsch

We separate odd cycle inequalities in the implication graph. Implemented are the classic method by Groetschel, Lovasz, and Schrijver (GLS) and the levelgraph method by Hoffman and Padberg (HP)

Odd cycle inequalities are lifted by a heuristic method based on an idea from Alvarez-Valdes, Parreno, and Tamarit.

Some part of this code is based on the odd cycle separator of the program colorbitopt by Marc Pfetsch.

Definition in file sepa_oddcycle.c.

#include <assert.h>
#include <string.h>
#include "scip/sepa_oddcycle.h"
#include "scip/pub_misc.h"
#include "dijkstra/dijkstra.h"

Go to the source code of this file.

Macros
#define	SEPA_NAME "oddcycle"

#define	SEPA_DESC "odd cycle separator"

#define	SEPA_PRIORITY -15000

#define	SEPA_FREQ -1

#define	SEPA_MAXBOUNDDIST 1.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_SCALEFACTOR 1000

#define	DEFAULT_USEGLS TRUE

#define	DEFAULT_LIFTODDCYCLES FALSE

#define	DEFAULT_REPAIRCYCLES TRUE

#define	DEFAULT_ADDSELFARCS TRUE

#define	DEFAULT_INCLUDETRIANGLES TRUE

#define	DEFAULT_MULTIPLECUTS FALSE

#define	DEFAULT_ALLOWMULTIPLECUTS TRUE

#define	DEFAULT_LPLIFTCOEF FALSE

#define	DEFAULT_RECALCLIFTCOEF TRUE

#define	DEFAULT_MAXSEPACUTS 5000

#define	DEFAULT_MAXSEPACUTSROOT 5000

#define	DEFAULT_PERCENTTESTVARS 0

#define	DEFAULT_OFFSETTESTVARS 100

#define	DEFAULT_MAXCUTSROOT 1

#define	DEFAULT_SORTSWITCH 3

#define	DEFAULT_MAXREFERENCE 0

#define	DEFAULT_MAXROUNDS 10

#define	DEFAULT_MAXROUNDSROOT 10

#define	DEFAULT_MAXNLEVELS 20

#define	DEFAULT_MAXPERNODESLEVEL 100

#define	DEFAULT_OFFSETNODESLEVEL 10

#define	DEFAULT_SORTROOTNEIGHBORS TRUE

#define	DEFAULT_MAXCUTSLEVEL 50

#define	DEFAULT_MAXUNSUCESSFULL 3

#define	DEFAULT_CUTTHRESHOLD -1

Typedefs
typedef struct levelGraph	LEVELGRAPH

typedef enum sorttype	SORTTYPE

Enumerations
enum	sorttype { UNSORTED = 0, MAXIMAL_LPVALUE = 1, MINIMAL_LPVALUE = 2, MAXIMAL_FRACTIONALITY = 3, MINIMAL_FRACTIONALITY = 4 }

Functions
static SCIP_Bool	isNeighbor (SCIP_VAR *vars, unsigned int nbinvars, SCIP_SEPADATA sepadata, unsigned int a, unsigned int b)

static void	checkBlocking (unsigned int a, unsigned int b, unsigned int c, unsigned int i, unsigned int cycle, unsigned int ncyclevars, SCIP_VAR vars, unsigned int nbinvars, unsigned int lifted, unsigned int nlifted, SCIP_SEPADATA sepadata, SCIP_Bool *myi)

static unsigned int	getCoef (SCIP scip, unsigned int i, unsigned int cycle, unsigned int ncyclevars, SCIP_VAR *vars, unsigned int nbinvars, unsigned int lifted, unsigned int nlifted, SCIP_SEPADATA sepadata, SCIP_Bool *myi)

static SCIP_RETCODE	liftOddCycleCut (SCIP scip, unsigned int nlifted, unsigned int lifted, unsigned int liftcoef, SCIP_SEPADATA sepadata, SCIP_VAR vars, unsigned int nbinvars, unsigned int startnode, unsigned int pred, unsigned int ncyclevars, SCIP_Real vals, SCIP_RESULT result)

static SCIP_RETCODE	generateOddCycleCut (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_VAR vars, unsigned int nbinvars, unsigned int startnode, unsigned int pred, unsigned int ncyclevars, unsigned int incut, SCIP_Real vals, SCIP_SEPADATA sepadata, SCIP_RESULT result)

static SCIP_RETCODE	cleanCycle (SCIP scip, unsigned int pred, SCIP_Bool incycle, unsigned int incut, unsigned int x, unsigned int startnode, unsigned int nbinvars, unsigned int ncyclevars, SCIP_Bool repaircycles, SCIP_Bool allowmultiplecuts, SCIP_Bool success)

static SCIP_RETCODE	checkArraySizesHeur (SCIP scip, LEVELGRAPH graph, unsigned int size, int targetArray, unsigned int weightArray, unsigned int sourceAdjArray, unsigned int targetAdjArray, SCIP_Bool success)

static SCIP_RETCODE	addArc (SCIP scip, LEVELGRAPH graph, unsigned int u, unsigned int v, unsigned int level, unsigned int weight, unsigned int nAdj, SCIP_Bool success)

static SCIP_RETCODE	addNextLevelCliques (SCIP scip, SCIP_SEPADATA sepadata, SCIP_VAR *vars, SCIP_Real vals, unsigned int u, LEVELGRAPH graph, unsigned int level, SCIP_Bool inlevelgraph, unsigned int newlevel, unsigned int nnewlevel, unsigned int nAdj, SCIP_Bool success)

static SCIP_RETCODE	insertSortedRootNeighbors (SCIP scip, LEVELGRAPH graph, unsigned int nbinvars, unsigned int ncurlevel, unsigned int u, SCIP_Real vals, SCIP_VAR vars, SCIP_SEPADATA sepadata, unsigned int nnewlevel, SCIP_Bool inlevelgraph, unsigned int level, unsigned int newlevel, SCIP_Bool success)

static SCIP_RETCODE	findShortestPathToRoot (SCIP scip, int scale, LEVELGRAPH graph, unsigned int startnode, unsigned int distance, unsigned int queue, SCIP_Bool inQueue, int parentTree)

static SCIP_RETCODE	blockRootPath (SCIP scip, LEVELGRAPH graph, unsigned int startnode, SCIP_Bool inlevelgraph, SCIP_Bool blocked, int *parentTree, unsigned int root)

static SCIP_RETCODE	findUnblockedShortestPathToRoot (SCIP scip, int scale, LEVELGRAPH graph, unsigned int startnode, unsigned int distance, unsigned int queue, SCIP_Bool inQueue, int parentTreeBackward, unsigned int root, SCIP_Bool *blocked)

static SCIP_RETCODE	createNextLevel (SCIP scip, SCIP_SEPADATA sepadata, SCIP_VAR *vars, SCIP_Real vals, LEVELGRAPH graph, unsigned int level, SCIP_Bool inlevelgraph, unsigned int curlevel, unsigned int ncurlevel, unsigned int newlevel, unsigned int nnewlevel, SCIP_Bool success)

static SCIP_RETCODE	separateHeur (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, SCIP_SOL sol, SCIP_RESULT *result)

static SCIP_RETCODE	checkArraySizesGLS (SCIP scip, unsigned int maxarcs, unsigned int arraysize, DIJKSTRA_GRAPH graph, SCIP_Bool success)

static SCIP_RETCODE	addGLSCliques (SCIP scip, SCIP_SEPADATA sepadata, SCIP_VAR *vars, unsigned int varsidx, unsigned int dijkindex, SCIP_Real vals, unsigned int nbinvars, unsigned int ncliques, DIJKSTRA_GRAPH graph, unsigned int narcs, unsigned int maxarcs, SCIP_Bool original, SCIP_Bool emptygraph, unsigned int arraysize, SCIP_Bool *success)

static SCIP_RETCODE	separateGLS (SCIP scip, SCIP_SEPA sepa, SCIP_SEPADATA sepadata, SCIP_SOL sol, SCIP_RESULT *result)

static	SCIP_DECL_SEPACOPY (sepaCopyOddcycle)

static	SCIP_DECL_SEPAFREE (sepaFreeOddcycle)

static	SCIP_DECL_SEPAINIT (sepaInitOddcycle)

static	SCIP_DECL_SEPAINITSOL (sepaInitsolOddcycle)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpOddcycle)

SCIP_RETCODE	SCIPincludeSepaOddcycle (SCIP *scip)

Macro Definition Documentation

#define SEPA_NAME "oddcycle"

Definition at line 41 of file sepa_oddcycle.c.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeSepaOddcycle().

#define SEPA_DESC "odd cycle separator"

Definition at line 42 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define SEPA_PRIORITY -15000

Definition at line 43 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define SEPA_FREQ -1

Definition at line 44 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 45 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 46 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define SEPA_DELAY FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 47 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_SCALEFACTOR 1000

factor for scaling of the arc-weights in the Dijkstra algorithm

Definition at line 51 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_USEGLS TRUE

use GLS method, otherwise HP method

Definition at line 52 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_LIFTODDCYCLES FALSE

lift odd cycle cuts

Definition at line 53 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_REPAIRCYCLES TRUE

try to repair violated cycles in which a variable and its negated appear

Definition at line 54 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_ADDSELFARCS TRUE

add links between a variable and its negated

Definition at line 55 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_INCLUDETRIANGLES TRUE

separate triangles (3-cliques) found as 3-cycles or repaired larger cycles

Definition at line 56 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MULTIPLECUTS FALSE

still try variable as start, even if it is already covered by a cut

Definition at line 57 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_ALLOWMULTIPLECUTS TRUE

allow another inequality to use variable, even if it is already covered

Definition at line 58 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_LPLIFTCOEF FALSE

TRUE: choose lifting candidate with highest value of coefficient*lpvalue FALSE: choose lifting candidate with highest coefficient

Definition at line 59 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_RECALCLIFTCOEF TRUE

whether lifting coefficients should be recomputed

Definition at line 62 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXSEPACUTS 5000

maximal number of oddcycle cuts separated per separation round

Definition at line 63 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXSEPACUTSROOT 5000

maximal number of oddcycle cuts separated per separation round in root node

Definition at line 64 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_PERCENTTESTVARS 0

percent of variables to try the chosen method on [0-100]

Definition at line 65 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_OFFSETTESTVARS 100

offset of variables to try the chosen method on

Definition at line 66 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXCUTSROOT 1

maximal number of oddcycle cuts generated per root of the levelgraph

Definition at line 67 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_SORTSWITCH 3

unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4)

Definition at line 68 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXREFERENCE 0

minimal weight on an edge (in level graph or Dijkstra graph)

Definition at line 69 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXROUNDS 10

maximal number of rounds pre node

Definition at line 70 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXROUNDSROOT 10

maximal number of rounds in the root node

Definition at line 71 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXNLEVELS 20

maximal number of levels in level graph

Definition at line 72 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXPERNODESLEVEL 100

maximal percentage of nodes allowed in one level of the levelgraph [0-100]

Definition at line 73 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_OFFSETNODESLEVEL 10

additional offset of nodes allowed in one level of the levelgraph

Definition at line 74 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_SORTROOTNEIGHBORS TRUE

sort neighbors of the root in the level graph

Definition at line 75 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXCUTSLEVEL 50

maximal number of cuts produced per level

Definition at line 76 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_MAXUNSUCESSFULL 3

maximal number of unsuccessful calls at each node

Definition at line 77 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

#define DEFAULT_CUTTHRESHOLD -1

maximal number of other cuts s.t. separation is applied (-1 for direct call)

Definition at line 78 of file sepa_oddcycle.c.

Referenced by SCIPincludeSepaOddcycle().

Typedef Documentation

typedef struct levelGraph LEVELGRAPH

Definition at line 125 of file sepa_oddcycle.c.

typedef enum sorttype SORTTYPE

Definition at line 143 of file sepa_oddcycle.c.

Enumeration Type Documentation

enum sorttype

sorting type for starting node or root node iteration order

If the array should be sorted (1-4), the variable array is sorted every round by the chosen sorttype and the search method tries the nodes in order of the array. If the array is used unsorted (0), the search methods tries the nodes in order of the array and stores the last processed start node or root node and continues from this position in the next separation round.

Enumerator
UNSORTED	variable array is unsorted
MAXIMAL_LPVALUE	variable array is sorted by maximal lp-value
MINIMAL_LPVALUE	variable array is sorted by minimal fractionality
MAXIMAL_FRACTIONALITY	variable array is sorted by maximal lp-value
MINIMAL_FRACTIONALITY	variable array is sorted by minimal fractionality

Definition at line 135 of file sepa_oddcycle.c.

Function Documentation

static SCIP_Bool isNeighbor	(	SCIP_VAR **	vars,
		unsigned int	nbinvars,
		SCIP_SEPADATA *	sepadata,
		unsigned int	a,
		unsigned int	b
	)

static

using the level graph (if possible) or Dijkstra graph data structure (depending on the used method) we determine whether two nodes are adjacent

Parameters

vars	problem variables
nbinvars	number of binary problem variables
sepadata	separator data structure
a	node index of first variable
b	node index of second variable

Definition at line 269 of file sepa_oddcycle.c.

References checkBlocking(), FALSE, NULL, SCIP_Bool, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.

Referenced by checkBlocking(), and getCoef().

static void checkBlocking	(	unsigned int	a,
		unsigned int	b,
		unsigned int	c,
		unsigned int	i,
		unsigned int *	cycle,
		unsigned int	ncyclevars,
		SCIP_VAR **	vars,
		unsigned int	nbinvars,
		unsigned int *	lifted,
		unsigned int *	nlifted,
		SCIP_SEPADATA *	sepadata,
		SCIP_Bool *	myi
	)

static

inside the lifting heuristic we determine the lifting coefficient by counting the length of chains adjacent to the lifting candidate.

since we have to exclude all chains adjacent to an already lifted node which is not adjacent to the current lifting candidate we check all chains of the cycle of length three and block them if they are adjacent.

Parameters

a	first node of the checked cycle chain of length 3
b	second node of the checked cycle chain of length 3
c	third node of the checked cycle chain of length 3
i	current lifting candidate
cycle	list of cycle nodes in order of the cycle
ncyclevars	number of variables in the odd cycle
vars	problem variables
nbinvars	number of binary problem variables
lifted	list of lifted nodes
nlifted	number of lifted nodes
sepadata	separator data structure
myi	flag array, if cycle node is inner point of a counted chain

Definition at line 479 of file sepa_oddcycle.c.

References FALSE, getCoef(), isNeighbor(), and NULL.

Referenced by getCoef(), and isNeighbor().

static unsigned int getCoef	(	SCIP *	scip,
		unsigned int	i,
		unsigned int *	cycle,
		unsigned int	ncyclevars,
		SCIP_VAR **	vars,
		unsigned int	nbinvars,
		unsigned int *	lifted,
		unsigned int *	nlifted,
		SCIP_SEPADATA *	sepadata,
		SCIP_Bool *	myi
	)

static

determine the heuristic lifting coefficient by counting the length of the adjacent chains of the candidate (we have to exclude all chains that are adjacent to an already lifted node which is not adjacent to the current candidate)

Parameters

scip	SCIP data structure
i	current lifting candidate
cycle	list of cycle nodes in order of the cycle
ncyclevars	number of variables in the odd cycle
vars	problem variables
nbinvars	number of binary problem variables
lifted	list of lifted nodes
nlifted	number of lifted nodes
sepadata	separator data structure
myi	flag array, if cycle node is inner point of a counted chain

Definition at line 532 of file sepa_oddcycle.c.

References checkBlocking(), isNeighbor(), liftOddCycleCut(), NULL, and SCIPfloor().

Referenced by checkBlocking(), and liftOddCycleCut().

static SCIP_RETCODE liftOddCycleCut	(	SCIP *	scip,
		unsigned int *	nlifted,
		unsigned int *	lifted,
		unsigned int *	liftcoef,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR **	vars,
		unsigned int	nbinvars,
		unsigned int	startnode,
		unsigned int *	pred,
		unsigned int	ncyclevars,
		SCIP_Real *	vals,
		SCIP_RESULT *	result
	)

static

Lifting Heuristic based on an idea by Alvarez-Valdes, Parreno, Tamarit

This method is based on the observation, that a non-cycle node can be lifted into the inequality with coefficient $1$ if the node is adjacent to the nodes of a 3-chain on the cycle.

The coefficient can be calculated as $\left\lfloor{\frac{|C|-1}{2}}\right\rfloor$ where $C$ is the chain on the cycle.

If the node is connected to several chains, the coefficients of the chains can be summed up, resulting in a feasible lifting coefficient.

Additionally further variables can be lifted by considering chains connected to the additional lifting node which are not connected to already lifted nodes.

This method is a feasible heuristic which gives a valid lifted inequality. (Furthermore the first lifting coefficient is always smaller or equal to the largest possible lifting coefficient.)

Parameters

scip	SCIP data structure
nlifted	number of lifted variables
lifted	indices of the lifted variables
liftcoef	lifting coefficients
sepadata	separator data structure
vars	problem variables
nbinvars	number of binary problem variables
startnode	a node of the cycle
pred	predecessor of each node (original and negated) in odd cycle
ncyclevars	number of variables in the odd cycle
vals	values of the variables in the given solution
result	pointer to store the result of the separation call

Definition at line 668 of file sepa_oddcycle.c.

References FALSE, generateOddCycleCut(), getCoef(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisStopped(), and TRUE.

Referenced by generateOddCycleCut(), and getCoef().

static SCIP_RETCODE generateOddCycleCut	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_VAR **	vars,
		unsigned int	nbinvars,
		unsigned int	startnode,
		unsigned int *	pred,
		unsigned int	ncyclevars,
		unsigned int *	incut,
		SCIP_Real *	vals,
		SCIP_SEPADATA *	sepadata,
		SCIP_RESULT *	result
	)

static

add the inequality corresponding to the given odd cycle to the LP (if violated) after lifting it (if requested by user flag)

Parameters

scip	SCIP data structure
sepa	separator
sol	given primal solution
vars	problem variables
nbinvars	number of binary problem variables
startnode	a node of the cycle
pred	predecessor of each node (original and negated) in odd cycle
ncyclevars	number of variables in the odd cycle
incut	TRUE iff node is covered already by a cut
vals	values of the variables in the given solution
sepadata	separator data structure
result	pointer to store the result of the separation call

Definition at line 839 of file sepa_oddcycle.c.

References cleanCycle(), FALSE, liftOddCycleCut(), NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPaddCut(), SCIPaddPoolCut(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPchgRowRhs(), SCIPchgVarLb(), SCIPchgVarUb(), SCIPcreateEmptyRowSepa(), SCIPdebugMessage, SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisCutEfficacious(), SCIPisStopped(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetRhs(), SCIPsnprintf(), and TRUE.

Referenced by liftOddCycleCut(), separateGLS(), and separateHeur().

static SCIP_RETCODE cleanCycle	(	SCIP *	scip,
		unsigned int *	pred,
		SCIP_Bool *	incycle,
		unsigned int *	incut,
		unsigned int	x,
		unsigned int	startnode,
		unsigned int	nbinvars,
		unsigned int *	ncyclevars,
		SCIP_Bool	repaircycles,
		SCIP_Bool	allowmultiplecuts,
		SCIP_Bool *	success
	)

static

check whether the given object is really a cycle without sub-cycles (sub-cycles may be calculated by the GLS algorithm in case there is no violated odd cycle inequality) and removes pairs of original and negated variables from the cycle

Parameters

scip	SCIP data structure
pred	predecessor list of current cycle segment
incycle	flag array iff node is in cycle segment
incut	flag array iff node is already covered by a cut
x	index of current variable
startnode	index of first variable of cycle segment
nbinvars	number of binary problem variables
ncyclevars	number of nodes in current cycle segment
repaircycles	user flag if we should try to repair damaged cycles
allowmultiplecuts	user flag if we allow multiple cuts per node
success	FALSE iff an irreparable cycle appears

Definition at line 1038 of file sepa_oddcycle.c.

References checkArraySizesHeur(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by generateOddCycleCut(), separateGLS(), and separateHeur().

static SCIP_RETCODE checkArraySizesHeur	(	SCIP *	scip,
		LEVELGRAPH *	graph,
		unsigned int *	size,
		int **	targetArray,
		unsigned int **	weightArray,
		unsigned int **	sourceAdjArray,
		unsigned int **	targetAdjArray,
		SCIP_Bool *	success
	)

static

memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)

Since the array sizes differ the method can be called for each of the three data structure types:

Forward: sizeForward, targetForward, weightForward
Backward: sizeBackward, targetBackward, weightBackward
Adj (inner level edges): sizeAdj, sourceAdj, targetAdj, weightAdj

Parameters

scip	SCIP data structure
graph	LEVELGRAPH data structure
size	given size
targetArray	given target array (or NULL if sourceAdjArray and targetAdjArray given)
weightArray	given weight array
sourceAdjArray	given sourceAdj array (or NULL if targetArray given)
targetAdjArray	given targetAdj array (or NULL if targetArray given)
success	FALSE, iff memory reallocation fails

Definition at line 1206 of file sepa_oddcycle.c.

References addArc(), FALSE, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPisInfinity(), SCIPisStopped(), and SCIPreallocBufferArray.

Referenced by addArc(), cleanCycle(), createNextLevel(), and insertSortedRootNeighbors().

static SCIP_RETCODE addArc	(	SCIP *	scip,
		LEVELGRAPH *	graph,
		unsigned int	u,
		unsigned int	v,
		unsigned int	level,
		unsigned int	weight,
		unsigned int *	nAdj,
		SCIP_Bool *	success
	)

static

Add arc to level graph

Parameters

scip	SCIP data structure
graph	LEVELGRAPH data structure
u	source node
v	target node
level	number of current level
weight	weight of the arc
nAdj	array of numbers of arcs inside levels
success	FALSE, iff memory reallocation fails

Definition at line 1291 of file sepa_oddcycle.c.

References addNextLevelCliques(), checkArraySizesHeur(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by addNextLevelCliques(), checkArraySizesHeur(), and createNextLevel().

static SCIP_RETCODE addNextLevelCliques	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		unsigned int	u,
		LEVELGRAPH *	graph,
		unsigned int	level,
		SCIP_Bool *	inlevelgraph,
		unsigned int *	newlevel,
		unsigned int *	nnewlevel,
		unsigned int *	nAdj,
		SCIP_Bool *	success
	)

static

add implications from cliques of the given node u

See also: createNextLevel()

Parameters

scip	SCIP data structure
sepadata	separator data structure
vars	problem variables
vals	values of the binary variables in the current LP relaxation
u	current node
graph	LEVELGRAPH data structure
level	number of current level
inlevelgraph	flag array if node is already inserted in level graph
newlevel	array of nodes of the next level
nnewlevel	number of nodes of the next level
nAdj	array of numbers of arcs inside levels
success	FALSE, iff memory reallocation fails

Definition at line 1368 of file sepa_oddcycle.c.

References addArc(), FALSE, insertSortedRootNeighbors(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPisFeasIntegral(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.

Referenced by addArc(), and createNextLevel().

static SCIP_RETCODE insertSortedRootNeighbors	(	SCIP *	scip,
		LEVELGRAPH *	graph,
		unsigned int	nbinvars,
		unsigned int	ncurlevel,
		unsigned int	u,
		SCIP_Real *	vals,
		SCIP_VAR **	vars,
		SCIP_SEPADATA *	sepadata,
		unsigned int *	nnewlevel,
		SCIP_Bool *	inlevelgraph,
		unsigned int	level,
		unsigned int *	newlevel,
		SCIP_Bool *	success
	)

static

sort level of root neighbors

If we limit the size of nodes of a level, we want to add the best neighbors to the next level. Since sorting every level is too expensive, we sort the neighbors of the root (if requested).

Create the first level as follows:

create flag array for binary variables and their negated and set their values FALSE
iterate over the implication and clique neighbors of the root and set their flag array values to TRUE
create variable array and insert all variables with flag value TRUE
sort variable array by maximal fractionality
add variables from sorted array to levelgraph until first level is full (or all variables are inserted)

Even inserting all variables might help for the following creation of further levels since the neighbors of nodes with high fractionality often have high fractionalities themselves and would be inserted first when further levels would have been sorted (which actually is not the case).

Parameters

scip	SCIP data structure
graph	LEVELGRAPH data structure
nbinvars	number of binary problem variables
ncurlevel	number of nodes of the current level
u	source node
vals	values of the binary variables in the current LP relaxation
vars	problem variables
sepadata	separator data structure
nnewlevel	number of nodes of the next level
inlevelgraph	nodes in new graph corr. to old graph (-1 if unassigned)
level	number of current level
newlevel	array of nodes of the next level
success	FALSE, iff memory reallocation fails

Definition at line 1533 of file sepa_oddcycle.c.

References BMSclearMemoryArray, checkArraySizesHeur(), FALSE, findShortestPathToRoot(), MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPfreeBufferArray, SCIPisFeasIntegral(), SCIPsortDownRealInt(), SCIPvarGetCliques(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), and TRUE.

Referenced by addNextLevelCliques(), and createNextLevel().

static SCIP_RETCODE findShortestPathToRoot	(	SCIP *	scip,
		int	scale,
		LEVELGRAPH *	graph,
		unsigned int	startnode,
		unsigned int *	distance,
		unsigned int *	queue,
		SCIP_Bool *	inQueue,
		int *	parentTree
	)

static

Find shortest path from start node to root

We perform a BFS to find the shortest path to the root. D stores the distance to the start node, P stores the partent nodes in the shortest path tree (-1 if node has not been reached).

Parameters

scip	SCIP data structure
scale	scaling factor for edge weights
graph	LEVELGRAPH data structure
startnode	start node for path search
distance	distances of searched nodes from root
queue	node queue for path search
inQueue	whether node is in the queue
parentTree	parent tree (-1 if no parent)

Definition at line 1736 of file sepa_oddcycle.c.

References blockRootPath(), FALSE, NULL, SCIP_OKAY, and TRUE.

Referenced by insertSortedRootNeighbors(), and separateHeur().

static SCIP_RETCODE blockRootPath	(	SCIP *	scip,
		LEVELGRAPH *	graph,
		unsigned int	startnode,
		SCIP_Bool *	inlevelgraph,
		SCIP_Bool *	blocked,
		int *	parentTree,
		unsigned int	root
	)

static

Block shortest path

We traverse the shortest path found by findShortestPathToRoot() and block all neighbors (in the original graph) of nodes in the path, i.e., we set blocked to TRUE. We do not block neighbors of the root node, since they have to be used. For the start node we only block nodes on the previous layers,

See also: findShortestPathToRoot()

Parameters

scip	SCIP data structure
graph	LEVELGRAPH data structure
startnode	start node
inlevelgraph	nodes in new graph corr. to old graph (-1 if unassigned)
blocked	whether node is blocked
parentTree	parent tree
root	root of the current level graph

Definition at line 1827 of file sepa_oddcycle.c.

References findUnblockedShortestPathToRoot(), NULL, SCIP_OKAY, and TRUE.

Referenced by findShortestPathToRoot(), and separateHeur().

static SCIP_RETCODE findUnblockedShortestPathToRoot	(	SCIP *	scip,
		int	scale,
		LEVELGRAPH *	graph,
		unsigned int	startnode,
		unsigned int *	distance,
		unsigned int *	queue,
		SCIP_Bool *	inQueue,
		int *	parentTreeBackward,
		unsigned int	root,
		SCIP_Bool *	blocked
	)

static

Find shortest path from root to target node

We perform a BFS to find the shortest path from the root. The only difference to findShortestPathToRoot() is that we avoid nodes that are blocked.

Parameters

scip	SCIP data structure
scale	scaling factor for edge weights
graph	LEVELGRAPH data structure
startnode	start node for path search
distance	distances of searched nodes from root
queue	node queue for path search
inQueue	whether node is in the queue
parentTreeBackward	parent tree (-1 if no parent)
root	root of the current level graph
blocked	whether nodes can be used

Definition at line 1916 of file sepa_oddcycle.c.

References createNextLevel(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, and TRUE.

Referenced by blockRootPath(), and separateHeur().

static SCIP_RETCODE createNextLevel	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR **	vars,
		SCIP_Real *	vals,
		LEVELGRAPH *	graph,
		unsigned int	level,
		SCIP_Bool *	inlevelgraph,
		unsigned int *	curlevel,
		unsigned int	ncurlevel,
		unsigned int *	newlevel,
		unsigned int *	nnewlevel,
		SCIP_Bool *	success
	)

static

create next level of level graph for odd cycle separation

See also: separateHeur()

Parameters

scip	SCIP data structure
sepadata	separator data structure
vars	problem variables
vals	values of the binary variables in the current LP relaxation
graph	LEVELGRAPH data structure
level	number of current level
inlevelgraph	flag array if node is already inserted in level graph
curlevel	array of nodes of the current level
ncurlevel	number of nodes of the current level
newlevel	array of nodes of the next level
nnewlevel	number of nodes of the next level
success	FALSE, iff memory reallocation fails

Definition at line 2036 of file sepa_oddcycle.c.

References addArc(), addNextLevelCliques(), checkArraySizesHeur(), insertSortedRootNeighbors(), NULL, SCIP_CALL, SCIP_OKAY, separateHeur(), and TRUE.

Referenced by findUnblockedShortestPathToRoot(), and separateHeur().

static SCIP_RETCODE separateHeur	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

The heuristic method for finding odd cycles by Hoffman, Padberg uses a level graph which is constructed as follows: First we choose a node (i.e. a variable of the problem or its negated) as root and assign it to level 0 (and no other node is assigned to level 0). All neighbors of the root are assigned to level 1 and the arcs between are added.

In general: All neighbors of nodes in level i that are assigned to level i+1, if they do not already appear in levels <= i. All arcs between nodes in level i and their neighbors are added.

In the construction we only take nodes that are contained in the fractional graph, i.e., their current LP values are not integral.

Since SCIP stores implications between original and negated variables, the level graph has at most twice the number of fractional binary variables of the problem.

Since the implication graph of SCIP is (normally) incomplete, it is possible to use arcs between an original variable and its negated to obtain more cycles which are valid but not found due to missing links.

Parameters

scip	SCIP data structure
sepa	separator
sepadata	separator data structure
sol	given primal solution
result	pointer to store the result of the separation call

Definition at line 2213 of file sepa_oddcycle.c.

References blockRootPath(), BMSclearMemoryArray, checkArraySizesGLS(), cleanCycle(), createNextLevel(), DIJKSTRA_UNUSED, FALSE, findShortestPathToRoot(), findUnblockedShortestPathToRoot(), generateOddCycleCut(), MAXIMAL_FRACTIONALITY, MAXIMAL_LPVALUE, MIN, MINIMAL_FRACTIONALITY, MINIMAL_LPVALUE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPABORT, SCIPallocBufferArray, SCIPceil(), SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisStopped(), SCIPsortDownRealPtr(), SCIPsortRealPtr(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarIsBinary(), TRUE, and UNSORTED.

Referenced by createNextLevel(), and SCIP_DECL_SEPAEXECLP().

static SCIP_RETCODE checkArraySizesGLS	(	SCIP *	scip,
		unsigned int	maxarcs,
		unsigned int *	arraysize,
		DIJKSTRA_GRAPH *	graph,
		SCIP_Bool *	success
	)

static

memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)

Parameters

scip	SCIP data structure
maxarcs	maximal size of graph->head and graph->weight
arraysize	current size of graph->head and graph->weight
graph	Dijkstra Graph data structure
success	FALSE, iff memory reallocation fails

Definition at line 2701 of file sepa_oddcycle.c.

References addGLSCliques(), DIJKSTRA_UNUSED, FALSE, DIJKSTRA_Graph::head, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetRealParam(), SCIPisInfinity(), SCIPisStopped(), SCIPreallocBufferArray, and DIJKSTRA_Graph::weight.

Referenced by addGLSCliques(), separateGLS(), and separateHeur().

static SCIP_RETCODE addGLSCliques	(	SCIP *	scip,
		SCIP_SEPADATA *	sepadata,
		SCIP_VAR **	vars,
		unsigned int	varsidx,
		unsigned int	dijkindex,
		SCIP_Real *	vals,
		unsigned int	nbinvars,
		unsigned int	ncliques,
		DIJKSTRA_GRAPH *	graph,
		unsigned int *	narcs,
		unsigned int	maxarcs,
		SCIP_Bool	original,
		SCIP_Bool *	emptygraph,
		unsigned int *	arraysize,
		SCIP_Bool *	success
	)

static

add implications from cliques of the given node

Parameters

scip	SCIP data structure
sepadata	separator data structure
vars	problem variables
varsidx	index of current variable inside the problem variables
dijkindex	index of current variable inside the Dijkstra Graph
vals	value of the variables in the given solution
nbinvars	number of binary problem variables
ncliques	number of cliques of the current node
graph	Dijkstra Graph data structure
narcs	current number of arcs inside the Dijkstra Graph
maxarcs	maximal number of arcs inside the Dijkstra Graph
original	TRUE, iff variable is a problem variable
emptygraph	TRUE, iff there is no arc in the implication graph of the binary variables of SCIP
arraysize	current size of graph->head and graph->weight
success	FALSE, iff memory reallocation fails

Definition at line 2779 of file sepa_oddcycle.c.

References checkArraySizesGLS(), FALSE, DIJKSTRA_Graph::head, MAX, DIJKSTRA_Graph::maxweight, DIJKSTRA_Graph::minweight, NULL, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPcliqueGetNVars(), SCIPcliqueGetValues(), SCIPcliqueGetVars(), SCIPfeasCeil(), SCIPisFeasIntegral(), SCIPvarGetCliques(), SCIPvarGetProbindex(), separateGLS(), and DIJKSTRA_Graph::weight.

Referenced by checkArraySizesGLS(), and separateGLS().

static SCIP_RETCODE separateGLS	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SEPADATA *	sepadata,
		SCIP_SOL *	sol,
		SCIP_RESULT *	result
	)

static

The classical method for finding odd cycles by Groetschel, Lovasz, Schrijver uses a bipartite graph which contains in each partition a node for every node in the original graph. All arcs uv of the original graph are copied to arcs from u of the first partition to v' of the second partition and from u' of the second partition to v of the first partition. A Dijkstra algorithm is used to find a path from a node x to its copy x', if existing. The nodes in the original graph corresponding to the nodes on the path form an odd cycle.

Since SCIP stores implications between original and negated variables, our original graph has at most twice the number of binary variables of the problem. By creating the bipartite graph we gain 4 segments of the graph:

I - nodes of the original variables in the first bipartition
II - nodes of the negated variables in the first bipartition
III - nodes of the original variables in the second bipartition
IV - nodes of the negated variables in the second bipartition

The length of every segment if the number of binary variables in the original problem.

Since the implication graph of SCIP is (normally) incomplete, it is possible to use arcs between an original variable and its negated to obtain more cycles which are valid but not found due to missing links.

Parameters