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 | AWAY 0.005 |
#define | MIN_VIOLATION 0.00 |
#define | EPS_COEFF 1e-11 |
#define | EPS_RELAX_ABS 1e-11 |
#define | EPS_RELAX_REL 1e-13 |
#define | MAX_DYN 1.0e+6 |
#define | MAX_SUPP_ABS 1000 |
#define | 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 70 of file sepa_gmi.c.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaGMI().
#define SEPA_DESC "Gomory Mixed-Integer cuts separator" |
Definition at line 71 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define SEPA_PRIORITY -1000 |
Definition at line 72 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define SEPA_FREQ 0 |
Definition at line 73 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 74 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 75 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 76 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAXROUNDS 5 |
maximal number of gomory separation rounds per node (-1: unlimited)
Definition at line 78 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAXROUNDSROOT 30 |
maximal number of gomory separation rounds in the root node (-1: unlimited)
Definition at line 79 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAXSEPACUTS -1 |
maximal number of gomory cuts separated per separation round
Definition at line 80 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_MAXSEPACUTSROOT -1 |
maximal number of gomory cuts separated per separation round in root node
Definition at line 81 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_DYNAMICCUTS TRUE |
should generated cuts be removed from the LP if they are no longer tight?
Definition at line 82 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define DEFAULT_SEPARATEROWS TRUE |
separate rows with integral slack?
Definition at line 83 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define AWAY 0.005 |
minimal fractionality of a basic variable in order to try GMI cut - default
Definition at line 85 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define MIN_VIOLATION 0.00 |
minimal violation to accept cut - default
Definition at line 86 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define EPS_COEFF 1e-11 |
tolerance for zeroing out small coefficients - default
Definition at line 87 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define EPS_RELAX_ABS 1e-11 |
absolute cut rhs relaxation - default
Definition at line 88 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define EPS_RELAX_REL 1e-13 |
relative cut rhs relaxation - default
Definition at line 89 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define MAX_DYN 1.0e+6 |
maximal valid range max(|weights|)/min(|weights|) of cut coefficients - default
Definition at line 90 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define MAX_SUPP_ABS 1000 |
maximum cut support - absolute value in the formula - default
Definition at line 91 of file sepa_gmi.c.
Referenced by SCIPincludeSepaGMI().
#define MAX_SUPP_REL 0.1 |
maximum cut support - relative value in the formula - default
Definition at line 92 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, 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 | number of nonzero elements in the cut in sparse format on output |
cutrhs | rhs of the cut |
Definition at line 126 of file sepa_gmi.c.
References EPSZ, FALSE, REALABS, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetUb(), SCIPisInfinity(), SCIPisZero(), 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, 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 | activity of the cut at the current LP optimum will go here on output |
Definition at line 203 of file sepa_gmi.c.
References FALSE, MAX, REALABS, SCIP_Real, SCIP_REAL_MAX, SCIPcolGetPrimsol(), SCIPdebugMsg, 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 | cut elements in sparse format will go here - must be of size ncols |
cutind | indices of nonzero cut coefficients will go here - must be of size ncols |
cutnz | number of nonzero elements in the cuts will go here |
cutrhs | cut rhs will go here |
cutact | cut activity at the current LP optimum will go here - only meaningful if returns TRUE |
workcoefs | working array of size ncols, allocated by caller for efficiency |
Definition at line 269 of file sepa_gmi.c.
References BMSclearMemoryArray, checkNumerics(), FALSE, modifyAndPackCut(), 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(), and SCIProwIsModifiable().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 529 of file sepa_gmi.c.
References 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 543 of file sepa_gmi.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
|
static |
LP solution separation method of separator
Definition at line 564 of file sepa_gmi.c.
References FALSE, getGMIFromRow(), 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(), SCIPgetDepth(), 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, and TRUE.
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 AWAY, DEFAULT_DYNAMICCUTS, DEFAULT_MAXROUNDS, DEFAULT_MAXROUNDSROOT, DEFAULT_MAXSEPACUTS, DEFAULT_MAXSEPACUTSROOT, DEFAULT_SEPARATEROWS, EPS_COEFF, EPS_RELAX_ABS, EPS_RELAX_REL, FALSE, MAX_DYN, MAX_SUPP_ABS, MAX_SUPP_REL, MIN_VIOLATION, 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, and SEPA_USESSUBSCIP.
Referenced by runSCIP(), and SCIP_DECL_SEPACOPY().