Scippy

    SCIP

    Solving Constraint Integer Programs

    Macros | Functions
    sepa_disjunctive.c File Reference
    Implementation files (.c files) » SCIP Default Plugins » Default Separators

    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)

    Cut coefficients belonging to integer variables can be strengthened by the 'monoidal cut strengthening' procedure, see
    "Strengthening cuts for mixed integer programs"
    Egon Balas, Robert G. Jeroslow, European Journal of Operational Research, Volume 4, Issue 4, 1980, Pages 224-234

    Definition in file sepa_disjunctive.c.

    #include "blockmemshell/memory.h"
    #include "scip/cons_sos1.h"
    #include "scip/pub_cons.h"
    #include "scip/pub_lp.h"
    #include "scip/pub_message.h"
    #include "scip/pub_misc.h"
    #include "scip/pub_misc_sort.h"
    #include "scip/pub_sepa.h"
    #include "scip/pub_var.h"
    #include "scip/scip_cons.h"
    #include "scip/scip_cut.h"
    #include "scip/scip_general.h"
    #include "scip/scip_lp.h"
    #include "scip/scip_mem.h"
    #include "scip/scip_message.h"
    #include "scip/scip_numerics.h"
    #include "scip/scip_param.h"
    #include "scip/scip_sepa.h"
    #include "scip/scip_sol.h"
    #include "scip/scip_solvingstats.h"
    #include "scip/scip_tree.h"
    #include "scip/sepa_disjunctive.h"
    #include <string.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_STRENGTHEN   TRUE
     
    #define DEFAULT_MAXDEPTH   -1
     
    #define DEFAULT_MAXROUNDS   25
     
    #define DEFAULT_MAXROUNDSROOT   100
     
    #define DEFAULT_MAXINVCUTS   50
     
    #define DEFAULT_MAXINVCUTSROOT   250
     
    #define DEFAULT_MAXCONFSDELAY   100000
     
    #define MAKECONTINTEGRAL   FALSE
     

    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, int depth, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, int ndisjcuts, SCIP_Bool scale, SCIP_Bool strengthen, SCIP_Real cutlhs1, SCIP_Real cutlhs2, SCIP_Real bound1, SCIP_Real bound2, 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

    ◆ SEPA_NAME

    #define SEPA_NAME   "disjunctive"

    Definition at line 69 of file sepa_disjunctive.c.

    ◆ SEPA_DESC

    #define SEPA_DESC   "disjunctive cut separator"

    Definition at line 70 of file sepa_disjunctive.c.

    ◆ SEPA_PRIORITY

    #define SEPA_PRIORITY   10

    priority for separation

    Definition at line 71 of file sepa_disjunctive.c.

    ◆ SEPA_FREQ

    #define SEPA_FREQ   0

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

    Definition at line 72 of file sepa_disjunctive.c.

    ◆ SEPA_MAXBOUNDDIST

    #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 74 of file sepa_disjunctive.c.

    ◆ SEPA_USESSUBSCIP

    #define SEPA_USESSUBSCIP   FALSE

    does the separator use a secondary SCIP instance?

    Definition at line 75 of file sepa_disjunctive.c.

    ◆ SEPA_DELAY

    #define SEPA_DELAY   TRUE

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

    Definition at line 76 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXRANK

    #define DEFAULT_MAXRANK   20

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

    Definition at line 78 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXRANKINTEGRAL

    #define DEFAULT_MAXRANKINTEGRAL   -1

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

    Definition at line 79 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXWEIGHTRANGE

    #define DEFAULT_MAXWEIGHTRANGE   1e+03

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

    Definition at line 80 of file sepa_disjunctive.c.

    ◆ DEFAULT_STRENGTHEN

    #define DEFAULT_STRENGTHEN   TRUE

    strengthen cut if integer variables are present

    Definition at line 81 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXDEPTH

    #define DEFAULT_MAXDEPTH   -1

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

    Definition at line 83 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXROUNDS

    #define DEFAULT_MAXROUNDS   25

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

    Definition at line 84 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXROUNDSROOT

    #define DEFAULT_MAXROUNDSROOT   100

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

    Definition at line 85 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXINVCUTS

    #define DEFAULT_MAXINVCUTS   50

    maximal number of cuts investigated per iteration in a branching node

    Definition at line 86 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXINVCUTSROOT

    #define DEFAULT_MAXINVCUTSROOT   250

    maximal number of cuts investigated per iteration in the root node

    Definition at line 87 of file sepa_disjunctive.c.

    ◆ DEFAULT_MAXCONFSDELAY

    #define DEFAULT_MAXCONFSDELAY   100000

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

    Definition at line 88 of file sepa_disjunctive.c.

    ◆ MAKECONTINTEGRAL

    #define MAKECONTINTEGRAL   FALSE

    convert continuous variable to integral variables in SCIPmakeRowIntegral()

    Definition at line 90 of file sepa_disjunctive.c.

    Function Documentation

    ◆ getVarRank()

    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 113 of file sepa_disjunctive.c.

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

    Referenced by SCIP_DECL_SEPAEXECLP().

    ◆ getSimplexCoefficients()

    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 159 of file sepa_disjunctive.c.

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

    Referenced by SCIP_DECL_SEPAEXECLP().

    ◆ generateDisjCutSOS1()

    static SCIP_RETCODE generateDisjCutSOS1 ( SCIP *  scip,
    SCIP_SEPA *  sepa,
    int  depth,
    SCIP_ROW **  rows,
    int  nrows,
    SCIP_COL **  cols,
    int  ncols,
    int  ndisjcuts,
    SCIP_Bool  scale,
    SCIP_Bool  strengthen,
    SCIP_Real  cutlhs1,
    SCIP_Real  cutlhs2,
    SCIP_Real  bound1,
    SCIP_Real  bound2,
    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 tableau rows

    Parameters
    scipSCIP pointer
    sepaseparator
    depthcurrent depth
    rowsLP rows
    nrowsnumber of LP rows
    colsLP columns
    ncolsnumber of LP columns
    ndisjcutsnumber of disjunctive cuts found so far
    scaleshould cut be scaled
    strengthenshould cut be strengthened if integer variables are present
    cutlhs1left hand side of the first simplex row
    cutlhs2left hand side of the second simplex row
    bound1bound of first simplex row
    bound2bound of second simplex row
    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 216 of file sepa_disjunctive.c.

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

    Referenced by SCIP_DECL_SEPAEXECLP().

    ◆ SCIP_DECL_SEPACOPY()

    static SCIP_DECL_SEPACOPY ( sepaCopyDisjunctive  )
    		static

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

    Definition at line 445 of file sepa_disjunctive.c.

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

    ◆ SCIP_DECL_SEPAFREE()

    static SCIP_DECL_SEPAFREE ( sepaFreeDisjunctive  )
    		static

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

    Definition at line 460 of file sepa_disjunctive.c.

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

    ◆ SCIP_DECL_SEPAEXITSOL()

    static SCIP_DECL_SEPAEXITSOL ( sepaInitsolDisjunctive  )
    		static

    solving process initialization method of separator

    Definition at line 480 of file sepa_disjunctive.c.

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

    ◆ SCIP_DECL_SEPAEXECLP()

    static SCIP_DECL_SEPAEXECLP ( sepaExeclpDisjunctive  )
    		static

    LP solution separation method for disjunctive cuts

    Definition at line 495 of file sepa_disjunctive.c.

    References FALSE, generateDisjCutSOS1(), getSimplexCoefficients(), getVarRank(), MAKECONTINTEGRAL, scip::max(), 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, SCIPaddRow(), SCIPallocBufferArray, SCIPceil(), SCIPcolGetBasisStatus(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetUb(), SCIPconshdlrGetNConss(), SCIPdebug, SCIPdebugMsg, SCIPdigraphGetNArcs(), SCIPdigraphGetNSuccessors(), SCIPdigraphGetSuccessors(), SCIPfreeBufferArrayNull, SCIPgetConflictgraphSOS1(), SCIPgetLPBasisInd(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNCutsFound(), SCIPgetNSOS1Vars(), SCIPgetRowLPActivity(), SCIPgetSolVal(), SCIPisCutEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPnodeGetVarSOS1(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsInLP(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsepaWasLPDelayed(), SCIPsortDownRealInt(), SCIPvarGetCol(), SCIPvarIsActive(), and SEPA_NAME.