Scippy

SCIP

Solving Constraint Integer Programs

Macros | Functions
sepa_disjunctive.c File Reference

Detailed Description

disjunctive cut separator

Author
Tobias Fischer
Marc Pfetsch

We separate disjunctive cuts for two term disjunctions of the form $x_1 = 0 \vee x_2 = 0$. They can be generated directly from the simplex tableau. For further information, we refer to
"A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints"
Júdice, J.J., Sherali, H.D., Ribeiro, I.M., Faustino, A.M., Journal of Global Optimization 36(1), 89–114 (2006)

Definition in file sepa_disjunctive.c.

#include <assert.h>
#include <string.h>
#include <ctype.h>
#include "scip/sepa_disjunctive.h"
#include "scip/cons_sos1.h"

Go to the source code of this file.

Macros

#define SEPA_NAME   "disjunctive"
 
#define SEPA_DESC   "disjunctive cut separator"
 
#define SEPA_PRIORITY   10
 
#define SEPA_FREQ   0
 
#define SEPA_MAXBOUNDDIST   0.0
 
#define SEPA_USESSUBSCIP   FALSE
 
#define SEPA_DELAY   TRUE
 
#define DEFAULT_MAXRANK   20
 
#define DEFAULT_MAXRANKINTEGRAL   -1
 
#define DEFAULT_MAXWEIGHTRANGE   1e+03
 
#define DEFAULT_MAXDEPTH   -1
 
#define DEFAULT_MAXROUNDS   25
 
#define DEFAULT_MAXROUNDSROOT   100
 
#define DEFAULT_MAXINVCUTS   50
 
#define DEFAULT_MAXINVCUTSROOT   250
 
#define DEFAULT_MAXCONFSDELAY   100000
 

Functions

static int getVarRank (SCIP *scip, SCIP_Real *binvrow, SCIP_Real *rowsmaxval, SCIP_Real maxweightrange, SCIP_ROW **rows, int nrows)
 
static SCIP_RETCODE getSimplexCoefficients (SCIP *scip, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, SCIP_Real *coef, SCIP_Real *binvrow, SCIP_Real *simplexcoefs, int *nonbasicnumber)
 
static SCIP_RETCODE generateDisjCutSOS1 (SCIP *scip, SCIP_SEPA *sepa, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, int ndisjcuts, SCIP_Bool scale, SCIP_Real cutlhs1, SCIP_Real cutlhs2, SCIP_Real *simplexcoefs1, SCIP_Real *simplexcoefs2, SCIP_Real *cutcoefs, SCIP_ROW **row, SCIP_Bool *madeintegral)
 
static SCIP_DECL_SEPACOPY (sepaCopyDisjunctive)
 
static SCIP_DECL_SEPAFREE (sepaFreeDisjunctive)
 
static SCIP_DECL_SEPAEXITSOL (sepaInitsolDisjunctive)
 
static SCIP_DECL_SEPAEXECLP (sepaExeclpDisjunctive)
 
SCIP_RETCODE SCIPincludeSepaDisjunctive (SCIP *scip)
 

Macro Definition Documentation

#define SEPA_NAME   "disjunctive"

Definition at line 37 of file sepa_disjunctive.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaDisjunctive().

#define SEPA_DESC   "disjunctive cut separator"

Definition at line 38 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define SEPA_PRIORITY   10

priority for separation

Definition at line 39 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define SEPA_FREQ   0

frequency for separating cuts; zero means to separate only in the root node

Definition at line 40 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define SEPA_MAXBOUNDDIST   0.0

maximal relative distance from the current node's dual bound to primal bound compared to best node's dual bound for applying separation.

Definition at line 41 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define SEPA_USESSUBSCIP   FALSE

does the separator use a secondary SCIP instance?

Definition at line 44 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define SEPA_DELAY   TRUE

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

Definition at line 45 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXRANK   20

maximal rank of a cut that could not be scaled to integral coefficients (-1: unlimited)

Definition at line 47 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXRANKINTEGRAL   -1

maximal rank of a cut that could be scaled to integral coefficients (-1: unlimited)

Definition at line 48 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXWEIGHTRANGE   1e+03

maximal valid range max(|weights|)/min(|weights|) of row weights

Definition at line 49 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXDEPTH   -1

node depth of separating cuts (-1: no limit)

Definition at line 51 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXROUNDS   25

maximal number of separation rounds in a branching node (-1: no limit)

Definition at line 52 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXROUNDSROOT   100

maximal number of separation rounds in the root node (-1: no limit)

Definition at line 53 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXINVCUTS   50

maximal number of cuts investigated per iteration in a branching node

Definition at line 54 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXINVCUTSROOT   250

maximal number of cuts investigated per iteration in the root node

Definition at line 55 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

#define DEFAULT_MAXCONFSDELAY   100000

delay separation if number of conflict graph edges is larger than predefined value (-1: no limit)

Definition at line 56 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

Function Documentation

static int getVarRank ( SCIP *  scip,
SCIP_Real *  binvrow,
SCIP_Real *  rowsmaxval,
SCIP_Real  maxweightrange,
SCIP_ROW **  rows,
int  nrows 
)
static

gets rank of variable corresponding to row of $B^{-1}$

Parameters
scipSCIP pointer
binvrowrow of $B^{-1}$
rowsmaxvalmaximal row multiplicator from nonbasic matrix A_N
maxweightrangemaximal valid range max(|weights|)/min(|weights|) of row weights
rowsrows of LP relaxation of scip
nrowsnumber of rows

Definition at line 78 of file sepa_disjunctive.c.

References NULL, REALABS, SCIP_Real, SCIPisGT(), and SCIProwGetRank().

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_RETCODE getSimplexCoefficients ( SCIP *  scip,
SCIP_ROW **  rows,
int  nrows,
SCIP_COL **  cols,
int  ncols,
SCIP_Real *  coef,
SCIP_Real *  binvrow,
SCIP_Real *  simplexcoefs,
int *  nonbasicnumber 
)
static

gets the nonbasic coefficients of a simplex row

Parameters
scipSCIP pointer
rowsLP rows
nrowsnumber LP rows
colsLP columns
ncolsnumber of LP columns
coefrow of $B^{-1} \cdot A$
binvrowrow of $B^{-1}$
simplexcoefspointer to store the nonbasic simplex-coefficients
nonbasicnumberpointer to store the number of nonbasic simplex-coefficients

Definition at line 124 of file sepa_disjunctive.c.

References NULL, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_OKAY, SCIPcolGetBasisStatus(), SCIPgetRowLPActivity(), SCIPisFeasZero(), SCIProwGetBasisStatus(), SCIProwGetLhs(), and SCIProwGetRhs().

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_RETCODE generateDisjCutSOS1 ( SCIP *  scip,
SCIP_SEPA *  sepa,
SCIP_ROW **  rows,
int  nrows,
SCIP_COL **  cols,
int  ncols,
int  ndisjcuts,
SCIP_Bool  scale,
SCIP_Real  cutlhs1,
SCIP_Real  cutlhs2,
SCIP_Real *  simplexcoefs1,
SCIP_Real *  simplexcoefs2,
SCIP_Real *  cutcoefs,
SCIP_ROW **  row,
SCIP_Bool *  madeintegral 
)
static

computes a disjunctive cut inequality based on two simplex taubleau rows

Parameters
scipSCIP pointer
sepaseparator
rowsLP rows
nrowsnumber of LP rows
colsLP columns
ncolsnumber of LP columns
ndisjcutsnumber of disjunctive cuts found so far
scaleshould cut be scaled
cutlhs1left hand side of the first sum of simplex rows
cutlhs2left hand side of the second sum of simplex rows
simplexcoefs1simplex coefficients of first row
simplexcoefs2simplex coefficients of second row
cutcoefspointer to store cut coefficients (length: nscipvars)
rowpointer to store disjunctive cut inequality
madeintegralpointer to store whether cut has been scaled to integral values

Definition at line 181 of file sepa_disjunctive.c.

References FALSE, MAX, MIN, NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcolGetBasisStatus(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPepsilon(), SCIPflushRowExtensions(), SCIPgetDepth(), SCIPgetMaxDepth(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPinfinity(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisNegative(), SCIPmakeRowIntegral(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsInLP(), SCIPsepaGetName(), SCIPsnprintf(), SCIPsumepsilon(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP().

static SCIP_DECL_SEPACOPY ( sepaCopyDisjunctive  )
static

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

Definition at line 385 of file sepa_disjunctive.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaDisjunctive(), SCIPsepaGetName(), and SEPA_NAME.

static SCIP_DECL_SEPAFREE ( sepaFreeDisjunctive  )
static

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

Definition at line 400 of file sepa_disjunctive.c.

References NULL, SCIP_OKAY, SCIPfreeMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

static SCIP_DECL_SEPAEXITSOL ( sepaInitsolDisjunctive  )
static

solving process initialization method of separator

Definition at line 420 of file sepa_disjunctive.c.

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

static SCIP_DECL_SEPAEXECLP ( sepaExeclpDisjunctive  )
static

LP solution separation method for disjunctive cuts

Definition at line 435 of file sepa_disjunctive.c.

References FALSE, generateDisjCutSOS1(), getSimplexCoefficients(), getVarRank(), MAX, MIN, NULL, REALABS, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DELAYED, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddCut(), SCIPallocBufferArray, SCIPceil(), SCIPcolGetBasisStatus(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPconshdlrGetNConss(), SCIPdebug, SCIPdebugMessage, SCIPdigraphGetNArcs(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArrayNull, SCIPgetConflictgraphSOS1(), SCIPgetDepth(), SCIPgetLPBasisInd(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNCutsFound(), SCIPgetNSOS1Vars(), SCIPgetSolVal(), SCIPisCutEfficacious(), SCIPisFeasGT(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPnodeGetVarSOS1(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetVals(), SCIProwIsInLP(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsepaWasLPDelayed(), SCIPsortDownRealInt(), SCIPvarGetCol(), SCIPvarIsActive(), SEPA_NAME, and TRUE.

SCIP_RETCODE SCIPincludeSepaDisjunctive ( SCIP *  scip)

creates the disjunctive cut separator and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 807 of file sepa_disjunctive.c.

References DEFAULT_MAXCONFSDELAY, DEFAULT_MAXDEPTH, DEFAULT_MAXINVCUTS, DEFAULT_MAXINVCUTSROOT, DEFAULT_MAXRANK, DEFAULT_MAXRANKINTEGRAL, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXWEIGHTRANGE, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPincludeSepaBasic(), SCIPsetSepaCopy(), SCIPsetSepaFree(), SCIPsetSepaInitsol(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, and TRUE.

Referenced by SCIP_DECL_SEPACOPY(), and SCIPincludeDefaultPlugins().