Scippy

SCIP

Solving Constraint Integer Programs

sepa_oddcycle.c File Reference

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
varsproblem variables
nbinvarsnumber of binary problem variables
sepadataseparator data structure
anode index of first variable
bnode 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
afirst node of the checked cycle chain of length 3
bsecond node of the checked cycle chain of length 3
cthird node of the checked cycle chain of length 3
icurrent lifting candidate
cyclelist of cycle nodes in order of the cycle
ncyclevarsnumber of variables in the odd cycle
varsproblem variables
nbinvarsnumber of binary problem variables
liftedlist of lifted nodes
nliftednumber of lifted nodes
sepadataseparator data structure
myiflag 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
scipSCIP data structure
icurrent lifting candidate
cyclelist of cycle nodes in order of the cycle
ncyclevarsnumber of variables in the odd cycle
varsproblem variables
nbinvarsnumber of binary problem variables
liftedlist of lifted nodes
nliftednumber of lifted nodes
sepadataseparator data structure
myiflag 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
scipSCIP data structure
nliftednumber of lifted variables
liftedindices of the lifted variables
liftcoeflifting coefficients
sepadataseparator data structure
varsproblem variables
nbinvarsnumber of binary problem variables
startnodea node of the cycle
predpredecessor of each node (original and negated) in odd cycle
ncyclevarsnumber of variables in the odd cycle
valsvalues of the variables in the given solution
resultpointer 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
scipSCIP data structure
sepaseparator
solgiven primal solution
varsproblem variables
nbinvarsnumber of binary problem variables
startnodea node of the cycle
predpredecessor of each node (original and negated) in odd cycle
ncyclevarsnumber of variables in the odd cycle
incutTRUE iff node is covered already by a cut
valsvalues of the variables in the given solution
sepadataseparator data structure
resultpointer 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
scipSCIP data structure
predpredecessor list of current cycle segment
incycleflag array iff node is in cycle segment
incutflag array iff node is already covered by a cut
xindex of current variable
startnodeindex of first variable of cycle segment
nbinvarsnumber of binary problem variables
ncyclevarsnumber of nodes in current cycle segment
repaircyclesuser flag if we should try to repair damaged cycles
allowmultiplecutsuser flag if we allow multiple cuts per node
successFALSE 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
scipSCIP data structure
graphLEVELGRAPH data structure
sizegiven size
targetArraygiven target array (or NULL if sourceAdjArray and targetAdjArray given)
weightArraygiven weight array
sourceAdjArraygiven sourceAdj array (or NULL if targetArray given)
targetAdjArraygiven targetAdj array (or NULL if targetArray given)
successFALSE, 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
scipSCIP data structure
graphLEVELGRAPH data structure
usource node
vtarget node
levelnumber of current level
weightweight of the arc
nAdjarray of numbers of arcs inside levels
successFALSE, 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
scipSCIP data structure
sepadataseparator data structure
varsproblem variables
valsvalues of the binary variables in the current LP relaxation
ucurrent node
graphLEVELGRAPH data structure
levelnumber of current level
inlevelgraphflag array if node is already inserted in level graph
newlevelarray of nodes of the next level
nnewlevelnumber of nodes of the next level
nAdjarray of numbers of arcs inside levels
successFALSE, 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
scipSCIP data structure
graphLEVELGRAPH data structure
nbinvarsnumber of binary problem variables
ncurlevelnumber of nodes of the current level
usource node
valsvalues of the binary variables in the current LP relaxation
varsproblem variables
sepadataseparator data structure
nnewlevelnumber of nodes of the next level
inlevelgraphnodes in new graph corr. to old graph (-1 if unassigned)
levelnumber of current level
newlevelarray of nodes of the next level
successFALSE, 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
scipSCIP data structure
scalescaling factor for edge weights
graphLEVELGRAPH data structure
startnodestart node for path search
distancedistances of searched nodes from root
queuenode queue for path search
inQueuewhether node is in the queue
parentTreeparent 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
scipSCIP data structure
graphLEVELGRAPH data structure
startnodestart node
inlevelgraphnodes in new graph corr. to old graph (-1 if unassigned)
blockedwhether node is blocked
parentTreeparent tree
rootroot 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
scipSCIP data structure
scalescaling factor for edge weights
graphLEVELGRAPH data structure
startnodestart node for path search
distancedistances of searched nodes from root
queuenode queue for path search
inQueuewhether node is in the queue
parentTreeBackwardparent tree (-1 if no parent)
rootroot of the current level graph
blockedwhether 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
scipSCIP data structure
sepadataseparator data structure
varsproblem variables
valsvalues of the binary variables in the current LP relaxation
graphLEVELGRAPH data structure
levelnumber of current level
inlevelgraphflag array if node is already inserted in level graph
curlevelarray of nodes of the current level
ncurlevelnumber of nodes of the current level
newlevelarray of nodes of the next level
nnewlevelnumber of nodes of the next level
successFALSE, 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
scipSCIP data structure
sepaseparator
sepadataseparator data structure
solgiven primal solution
resultpointer 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
scipSCIP data structure
maxarcsmaximal size of graph->head and graph->weight
arraysizecurrent size of graph->head and graph->weight
graphDijkstra Graph data structure
successFALSE, 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
scipSCIP data structure
sepadataseparator data structure
varsproblem variables
varsidxindex of current variable inside the problem variables
dijkindexindex of current variable inside the Dijkstra Graph
valsvalue of the variables in the given solution
nbinvarsnumber of binary problem variables
ncliquesnumber of cliques of the current node
graphDijkstra Graph data structure
narcscurrent number of arcs inside the Dijkstra Graph
maxarcsmaximal number of arcs inside the Dijkstra Graph
originalTRUE, iff variable is a problem variable
emptygraphTRUE, iff there is no arc in the implication graph of the binary variables of SCIP
arraysizecurrent size of graph->head and graph->weight
successFALSE, 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
scipSCIP data structure
sepaseparator
sepadataseparator data structure
solgiven primal solution
resultpointer to store the result of the separation call

Definition at line 2938 of file sepa_oddcycle.c.

References addGLSCliques(), DIJKSTRA_Graph::arcs, BMSclearMemoryArray, checkArraySizesGLS(), cleanCycle(), DIJKSTRA_FARAWAY, DIJKSTRA_UNUSED, dijkstraGraphIsValid(), dijkstraPairCutoff(), dijkstraPairCutoffIgnore(), FALSE, generateOddCycleCut(), DIJKSTRA_Graph::head, MAXIMAL_FRACTIONALITY, MAXIMAL_LPVALUE, DIJKSTRA_Graph::maxweight, MIN, MINIMAL_FRACTIONALITY, MINIMAL_LPVALUE, DIJKSTRA_Graph::minweight, DIJKSTRA_Graph::nodes, NULL, DIJKSTRA_Graph::outbeg, DIJKSTRA_Graph::outcnt, SCIP_Bool, SCIP_CALL, SCIP_DECL_SEPACOPY(), SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VERBLEVEL_HIGH, SCIPABORT, SCIPallocBufferArray, SCIPceil(), SCIPdebugMessage, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetNLPs(), SCIPgetProbName(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPisFeasIntegral(), SCIPisStopped(), SCIPsnprintf(), SCIPsortDownRealPtr(), SCIPsortRealPtr(), SCIPsplitFilename(), SCIPvarGetNCliques(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarIsBinary(), SCIPverbMessage(), SCIPwriteCliqueGraph(), TRUE, UNSORTED, and DIJKSTRA_Graph::weight.

Referenced by addGLSCliques(), and SCIP_DECL_SEPAEXECLP().

static SCIP_DECL_SEPACOPY ( sepaCopyOddcycle  )
static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 3456 of file sepa_oddcycle.c.

References NULL, SCIP_CALL, SCIP_DECL_SEPAFREE(), SCIP_OKAY, SCIPincludeSepaOddcycle(), SCIPsepaGetName(), and SEPA_NAME.

Referenced by separateGLS().

static SCIP_DECL_SEPAFREE ( sepaFreeOddcycle  )
static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 3471 of file sepa_oddcycle.c.

References NULL, SCIP_DECL_SEPAINIT(), SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), and SCIPsepaSetData().

Referenced by SCIP_DECL_SEPACOPY().

static SCIP_DECL_SEPAINIT ( sepaInitOddcycle  )
static

initialization method of separator (called after problem was transformed)

Definition at line 3487 of file sepa_oddcycle.c.

References NULL, SCIP_DECL_SEPAINITSOL(), SCIP_OKAY, and SCIPsepaGetData().

Referenced by SCIP_DECL_SEPAFREE().

static SCIP_DECL_SEPAINITSOL ( sepaInitsolOddcycle  )
static

solving process initialization method of separator (called when branch and bound process is about to begin)

Definition at line 3507 of file sepa_oddcycle.c.

References NULL, SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, and SCIPsepaGetData().

Referenced by SCIP_DECL_SEPAINIT().