Detailed Description
disjunctive cut separator
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.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaDisjunctive().
◆ SEPA_DESC
#define SEPA_DESC "disjunctive cut separator" |
Definition at line 70 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ SEPA_PRIORITY
#define SEPA_PRIORITY 10 |
priority for separation
Definition at line 71 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ 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.
Referenced by SCIPincludeSepaDisjunctive().
◆ 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 73 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ SEPA_USESSUBSCIP
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 76 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ SEPA_DELAY
#define SEPA_DELAY TRUE |
should separation method be delayed, if other separators found cuts?
Definition at line 77 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXRANK
#define DEFAULT_MAXRANK 20 |
maximal rank of a cut that could not be scaled to integral coefficients (-1: unlimited)
Definition at line 79 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXRANKINTEGRAL
#define DEFAULT_MAXRANKINTEGRAL -1 |
maximal rank of a cut that could be scaled to integral coefficients (-1: unlimited)
Definition at line 80 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXWEIGHTRANGE
#define DEFAULT_MAXWEIGHTRANGE 1e+03 |
maximal valid range max(|weights|)/min(|weights|) of row weights
Definition at line 81 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_STRENGTHEN
#define DEFAULT_STRENGTHEN TRUE |
strengthen cut if integer variables are present
Definition at line 82 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXDEPTH
#define DEFAULT_MAXDEPTH -1 |
node depth of separating cuts (-1: no limit)
Definition at line 84 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXROUNDS
#define DEFAULT_MAXROUNDS 25 |
maximal number of separation rounds in a branching node (-1: no limit)
Definition at line 85 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXROUNDSROOT 100 |
maximal number of separation rounds in the root node (-1: no limit)
Definition at line 86 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXINVCUTS
#define DEFAULT_MAXINVCUTS 50 |
maximal number of cuts investigated per iteration in a branching node
Definition at line 87 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ DEFAULT_MAXINVCUTSROOT
#define DEFAULT_MAXINVCUTSROOT 250 |
maximal number of cuts investigated per iteration in the root node
Definition at line 88 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ 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 89 of file sepa_disjunctive.c.
Referenced by SCIPincludeSepaDisjunctive().
◆ MAKECONTINTEGRAL
#define MAKECONTINTEGRAL FALSE |
convert continuous variable to integral variables in SCIPmakeRowIntegral()
Definition at line 91 of file sepa_disjunctive.c.
Referenced by SCIP_DECL_SEPAEXECLP().
Function Documentation
◆ getVarRank()
|
static |
gets rank of variable corresponding to row of \(B^{-1}\)
- Parameters
-
scip SCIP pointer binvrow row of \(B^{-1}\) rowsmaxval maximal row multiplicator from nonbasic matrix A_N maxweightrange maximal valid range max(|weights|)/min(|weights|) of row weights rows rows of LP relaxation of scip nrows number of rows
Definition at line 114 of file sepa_disjunctive.c.
References getSimplexCoefficients(), NULL, r, REALABS, SCIP_Real, SCIPisGT(), and SCIProwGetRank().
Referenced by SCIP_DECL_SEPAEXECLP().
◆ getSimplexCoefficients()
|
static |
gets the nonbasic coefficients of a simplex row
- Parameters
-
scip SCIP pointer rows LP rows nrows number LP rows cols LP columns ncols number of LP columns coef row of \(B^{-1} \cdot A\) binvrow row of \(B^{-1}\) simplexcoefs pointer to store the nonbasic simplex-coefficients nonbasicnumber pointer to store the number of nonbasic simplex-coefficients
Definition at line 160 of file sepa_disjunctive.c.
References generateDisjCutSOS1(), NULL, r, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_OKAY, SCIPcolGetBasisStatus(), SCIPgetRowLPActivity(), SCIPisFeasZero(), SCIProwGetBasisStatus(), SCIProwGetLhs(), and SCIProwGetRhs().
Referenced by getVarRank(), and SCIP_DECL_SEPAEXECLP().
◆ generateDisjCutSOS1()
|
static |
computes a disjunctive cut inequality based on two simplex tableau rows
- Parameters
-
scip SCIP pointer sepa separator depth current depth rows LP rows nrows number of LP rows cols LP columns ncols number of LP columns ndisjcuts number of disjunctive cuts found so far scale should cut be scaled strengthen should cut be strengthened if integer variables are present cutlhs1 left hand side of the first simplex row cutlhs2 left hand side of the second simplex row bound1 bound of first simplex row bound2 bound of second simplex row simplexcoefs1 simplex coefficients of first row simplexcoefs2 simplex coefficients of second row cutcoefs pointer to store cut coefficients (length: nscipvars) row pointer to store disjunctive cut inequality madeintegral pointer to store whether cut has been scaled to integral values
Definition at line 217 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_DECL_SEPACOPY(), 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 getSimplexCoefficients(), and SCIP_DECL_SEPAEXECLP().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 446 of file sepa_disjunctive.c.
References NULL, SCIP_CALL, SCIP_DECL_SEPAFREE(), SCIP_OKAY, SCIPincludeSepaDisjunctive(), SCIPsepaGetName(), and SEPA_NAME.
Referenced by generateDisjCutSOS1().
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 461 of file sepa_disjunctive.c.
References NULL, SCIP_DECL_SEPAEXITSOL(), SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
Referenced by SCIP_DECL_SEPACOPY().
◆ SCIP_DECL_SEPAEXITSOL()
|
static |
solving process initialization method of separator
Definition at line 481 of file sepa_disjunctive.c.
References NULL, SCIP_DECL_SEPAEXECLP(), SCIP_OKAY, SCIPfindConshdlr(), and SCIPsepaGetData().
Referenced by SCIP_DECL_SEPAFREE().
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method for disjunctive cuts
Definition at line 496 of file sepa_disjunctive.c.
References FALSE, generateDisjCutSOS1(), getSimplexCoefficients(), getVarRank(), MAKECONTINTEGRAL, 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(), SCIPincludeSepaDisjunctive(), 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.
Referenced by SCIP_DECL_SEPAEXITSOL().