Gomory Mixed-Integer Cuts.
This file implements a Gomory Mixed-Integer (GMI) cuts generator that reads cuts from the simplex tableau, applying the textbook formula:
\[ \sum_{j \in J_I : f_j \leq f_0} f_j x_j + \sum_{j \in J_I : f_j > f_0} f_0 \frac{1-f_j}{1 - f_0} x_j + \sum_{j \in J_C : a_j \geq 0} a_j x_j - \sum_{j \in J_C : a_j < 0} f_0 \frac{a_j}{1-f_0} x_j \geq f_0. \]
Here, \(J_I\) and \(J_C \subseteq \{1, \ldots, n\}\) are the indices of integer and continuous non basic variables, respectively. The tableaux row is given by \(a_j\) and its right hand side is \(a_0\). The values \(f_j\) for \(j = 0, \ldots, n\) denote the fractional values of the tableaux row and rhs, i.e., \(f_j = a_j - \lfloor a_j \rfloor\).
Here is a brief description of the simplex tableau that we can expect from the SCIP LP interfaces:
Generated cuts are modified and their numerical properties are checked before being added to the LP relaxation. Default parameters for cut modification and checking procedures are taken from the paper
G. Cornuejols, F. Margot, and G. Nannicini:
On the safety of Gomory cut generators.
Mathematical Programming Computation 5, No. 4 (2013), pp. 345-395.
In addition to the routines described in the paper above, here we additionally check the support of the cutting plane.
Definition in file sepa_gmi.c.
Go to the source code of this file.
Macros | |
#define | SEPA_NAME "gmi" |
#define | SEPA_DESC "Gomory Mixed-Integer cuts separator" |
#define | SEPA_PRIORITY -1000 |
#define | SEPA_FREQ 0 |
#define | SEPA_MAXBOUNDDIST 0.0 |
#define | SEPA_USESSUBSCIP FALSE |
#define | SEPA_DELAY FALSE |
#define | DEFAULT_MAXROUNDS 5 |
#define | DEFAULT_MAXROUNDSROOT 30 |
#define | DEFAULT_MAXSEPACUTS -1 |
#define | DEFAULT_MAXSEPACUTSROOT -1 |
#define | DEFAULT_DYNAMICCUTS TRUE |
#define | DEFAULT_SEPARATEROWS TRUE |
#define | DEFAULT_AWAY 0.005 |
#define | DEFAULT_MIN_VIOLATION 0.00 |
#define | DEFAULT_EPS_COEFF 1e-11 |
#define | DEFAULT_EPS_RELAX_ABS 1e-11 |
#define | DEFAULT_EPS_RELAX_REL 1e-13 |
#define | DEFAULT_MAX_DYN 1.0e+6 |
#define | DEFAULT_MAX_SUPP_ABS 1000 |
#define | DEFAULT_MAX_SUPP_REL 0.1 |
Functions | |
static SCIP_Bool | modifyAndPackCut (SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *densecoefs, SCIP_Real *sparsecoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs) |
static SCIP_Bool | checkNumerics (SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, SCIP_COL **cols, SCIP_Real *cutcoefs, int *cutind, int cutnz, SCIP_Real cutrhs, SCIP_Real *cutact) |
static SCIP_Bool | getGMIFromRow (SCIP *scip, SCIP_SEPADATA *sepadata, int ncols, int nrows, SCIP_COL **cols, SCIP_ROW **rows, SCIP_Real *binvrow, SCIP_Real *binvarow, SCIP_Real rowrhs, SCIP_Real *cutcoefs, int *cutind, int *cutnz, SCIP_Real *cutrhs, SCIP_Real *cutact, SCIP_Real *workcoefs) |
static | SCIP_DECL_SEPACOPY (sepaCopyGMI) |
static | SCIP_DECL_SEPAFREE (sepaFreeGMI) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpGMI) |
SCIP_RETCODE | SCIPincludeSepaGMI (SCIP *scip) |
#define SEPA_NAME "gmi" |
Definition at line 79 of file sepa_gmi.c.
#define SEPA_DESC "Gomory Mixed-Integer cuts separator" |
Definition at line 80 of file sepa_gmi.c.
#define SEPA_PRIORITY -1000 |
Definition at line 81 of file sepa_gmi.c.
#define SEPA_FREQ 0 |
Definition at line 82 of file sepa_gmi.c.
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 83 of file sepa_gmi.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 84 of file sepa_gmi.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 85 of file sepa_gmi.c.
#define DEFAULT_MAXROUNDS 5 |
maximal number of GMI separation rounds per node (-1: unlimited)
Definition at line 87 of file sepa_gmi.c.
#define DEFAULT_MAXROUNDSROOT 30 |
maximal number of GMI separation rounds in the root node (-1: unlimited)
Definition at line 88 of file sepa_gmi.c.
#define DEFAULT_MAXSEPACUTS -1 |
maximal number of GMI cuts separated per separation round
Definition at line 89 of file sepa_gmi.c.
#define DEFAULT_MAXSEPACUTSROOT -1 |
maximal number of GMI cuts separated per separation round in root node
Definition at line 90 of file sepa_gmi.c.
#define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 91 of file sepa_gmi.c.
#define DEFAULT_SEPARATEROWS TRUE |
separate rows with integral slack?
Definition at line 92 of file sepa_gmi.c.
#define DEFAULT_AWAY 0.005 |
minimal fractionality of a basic variable in order to try GMI cut - default
Definition at line 94 of file sepa_gmi.c.
#define DEFAULT_MIN_VIOLATION 0.00 |
minimal violation to accept cut - default
Definition at line 95 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_EPS_COEFF 1e-11 |
tolerance for zeroing out small coefficients - default
Definition at line 96 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_EPS_RELAX_ABS 1e-11 |
absolute cut rhs relaxation - default
Definition at line 97 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_EPS_RELAX_REL 1e-13 |
relative cut rhs relaxation - default
Definition at line 98 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAX_DYN 1.0e+6 |
maximal valid range max(|weights|)/min(|weights|) of cut coefficients - default
Definition at line 99 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAX_SUPP_ABS 1000 |
maximum cut support - absolute value in the formula - default
Definition at line 100 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAX_SUPP_REL 0.1 |
maximum cut support - relative value in the formula - default
Definition at line 101 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
|
static |
Modify the cut to make it numerically safer, and packs it from dense format to sparse format.
See paper "On the safety of Gomory cut generators" by Cornuejols, Margot, and Nannicini for more information. Returns TRUE if cut is accepted, FALSE if it is discarded.
scip | pointer to the SCIP environment |
sepadata | pointer to separator data |
ncols | number of columns in the LP |
cols | columns of the LP |
densecoefs | cut in dense format on input |
sparsecoefs | cut coefficients in sparse format on output |
cutind | cut indices in sparse format on output |
cutnz | pointer to store the number of nonzero elements in the cut in sparse format on output |
cutrhs | pointer to store the rhs of the cut, initialized to original value, modified |
Definition at line 135 of file sepa_gmi.c.
References assert(), c, EPSZ, FALSE, i, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPisInfinity(), SCIPisZero(), sepadata, and TRUE.
Referenced by getGMIFromRow().
|
static |
Check the numerical properties of the cut.
See paper "On the safety of Gomory cut generators" by Cornuejols, Margot, and Nannicini for more information. Returns TRUE if cut is accepted, FALSE if it is discarded.
scip | pointer to the SCIP environment |
sepadata | pointer to separator data |
ncols | number of columns in the LP |
cols | columns of the LP |
cutcoefs | cut in sparse format |
cutind | cut indices in sparse format |
cutnz | number of nonzero elements in the cut in sparse format |
cutrhs | rhs of the cut |
cutact | pointer to store activity of the cut at the current LP optimum will go here on output |
Definition at line 212 of file sepa_gmi.c.
References assert(), FALSE, i, MAX, MIN, NULL, REALABS, SCIP_Bool, SCIP_Real, SCIP_REAL_MAX, SCIPcolGetPrimsol(), SCIPdebugMsg, sepadata, and TRUE.
Referenced by getGMIFromRow().
|
static |
Method to obtain a GMI in the space of the original variables from a row of the simplex tableau.
Returns TRUE if cut is successfully created, FALSE if no cut was generated or if it should be discarded. If the function returns FALSE, the contents of cutcoefs, cutind, cutnz, cutrhs, cutact may be garbage.
scip | pointer to the SCIP environment |
sepadata | pointer to separator data |
ncols | number of columns in the LP |
nrows | number of rows in the LP |
cols | columns of the LP |
rows | rows of the LP |
binvrow | row of the basis inverse |
binvarow | row of the simplex tableau |
rowrhs | rhs of the tableau row, i.e., corresponding element in the LP solution |
cutcoefs | array for cut elements in sparse format - must be of size ncols |
cutind | array for indices of nonzero cut coefficients - must be of size ncols |
cutnz | pointer to store number of nonzero elements in the cut |
cutrhs | pointer to store cut rhs |
cutact | pointer to store cut activity at the current LP optimum - only meaningful if returns TRUE |
workcoefs | working array of size ncols, allocated by caller for efficiency |
Definition at line 276 of file sepa_gmi.c.
References assert(), BMSclearMemoryArray, c, checkNumerics(), FALSE, i, modifyAndPackCut(), NULL, SCIP_BASESTAT_BASIC, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_BASESTAT_ZERO, SCIP_Bool, SCIP_Real, SCIPcolGetBasisStatus(), SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPcolIsIntegral(), SCIPdebugMsg, SCIPfeasFrac(), SCIPfrac(), SCIPgetRowLPActivity(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsModifiable(), and sepadata.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 536 of file sepa_gmi.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaGMI(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 550 of file sepa_gmi.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
LP solution separation method of separator
Definition at line 571 of file sepa_gmi.c.
References assert(), c, depth, FALSE, getGMIFromRow(), i, ncalls, NULL, nvars, primsol, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_INVALID, SCIP_LPSOLSTAT_OPTIMAL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VARTYPE_CONTINUOUS, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebug, SCIPdebugMsg, SCIPfeasFrac(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetCutEfficacy(), SCIPgetLPBasisInd(), SCIPgetLPBInvARow(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetLPSolstat(), SCIPgetNCutsFound(), SCIPgetNLPBranchCands(), SCIPgetNLPs(), SCIPgetRowActivity(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetVarsData(), SCIPgetVarSol(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisFeasNegative(), SCIPisInfinity(), SCIPisLPSolBasic(), SCIPisStopped(), SCIPprintRow(), SCIPreleaseRow(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetNorm(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetType(), SEPA_NAME, sepadata, TRUE, var, and vars.
SCIP_RETCODE SCIPincludeSepaGMI | ( | SCIP * | scip | ) |
creates the GMI MIR cut separator and includes it in SCIP
scip | SCIP data structure |
Definition at line 824 of file sepa_gmi.c.
References assert(), DEFAULT_AWAY, DEFAULT_DYNAMICCUTS, DEFAULT_EPS_COEFF, DEFAULT_EPS_RELAX_ABS, DEFAULT_EPS_RELAX_REL, DEFAULT_MAX_DYN, DEFAULT_MAX_SUPP_ABS, DEFAULT_MAX_SUPP_REL, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_MIN_VIOLATION, DEFAULT_SEPARATEROWS, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIP_REAL_MAX, SCIPaddBoolParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocBlockMemory, SCIPincludeSepaBasic(), SCIPsetSepaCopy(), SCIPsetSepaFree(), SEPA_DELAY, SEPA_DESC, SEPA_FREQ, SEPA_MAXBOUNDDIST, SEPA_NAME, SEPA_PRIORITY, SEPA_USESSUBSCIP, and sepadata.
Referenced by runSCIP(), and SCIP_DECL_SEPACOPY().