Chvatal-Gomory cuts computed via a sub-MIP.
Separate Chvátal-Gomory cuts using a sub-MIP. The approach is based on the following papers.
M. Fischetti and A. Lodi
Optimizing over the first Chvátal closure,
in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization IPCO 2005,
LNCS 3509, pp. 12-22. Springer, Berlin Heidelberg New York (2005)
M. Fischetti and A. Lodi
Optimizing over the first Chvátal closure,
Mathematical Programming 110, 3-20 (2007)
P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi
Projected Chvátal-Gomory cuts for mixed integer linear programs,
Mathematical Programming 113, No. 2 (2008)
There are several versions to generate the final cut:
usecmir
is true). One can determine which bound is used in the rounding operation (if cmirownbounds is true) or let SCIP choose the best. This version is generally numerically the most stable.usestrongcg
is true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c).usecmir
and usestrongcg
are false). The cut is not take from the solution of the MIP, but is recomputed, and some care (but not as much as in the first version) has been taken to create a valid cut.The computation time of the separation MIP is limited as follows:
Definition in file sepa_cgmip.c.
#include <assert.h>
#include <string.h>
#include "scip/sepa_cgmip.h"
#include "scip/scipdefplugins.h"
#include "scip/cons_linear.h"
#include "scip/pub_misc.h"
#include "scip/pub_lp.h"
Go to the source code of this file.
Typedefs | |
typedef enum CGMIP_ColType | CGMIP_COLTYPE |
typedef struct CGMIP_MIPData | CGMIP_MIPDATA |
Enumerations | |
enum | CGMIP_ColType { colPresent = 0, colContinuous = 1, colConverted = 2, colAtUb = 3, colAtLb = 4 } |
Functions | |
static SCIP_RETCODE | computeCut (SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata, SCIP_SEPADATA *sepadata, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, SCIP_Bool *localrowsused, SCIP_Bool *localboundsused, int *cutrank, SCIP_Bool *success) |
static SCIP_RETCODE | solCutIsViolated (SCIP *scip, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Bool *violated) |
static | SCIP_DECL_CONSFREE (consFreeViolatedCuts) |
static | SCIP_DECL_CONSENFOLP (consEnfolpViolatedCuts) |
static | SCIP_DECL_CONSENFOPS (consEnfopsViolatedCuts) |
static | SCIP_DECL_CONSCHECK (consCheckViolatedCuts) |
static | SCIP_DECL_CONSLOCK (consLockViolatedCuts) |
static SCIP_RETCODE | SCIPincludeConshdlrViolatedCut (SCIP *scip, CGMIP_MIPDATA *mipdata) |
static SCIP_RETCODE | storeCutInArrays (SCIP *scip, int nvars, SCIP_Real *cutcoefs, SCIP_Real *varsolvals, char normtype, int *cutinds, SCIP_Real *cutvals, int *cutlen, SCIP_Real *cutact, SCIP_Real *cutnorm) |
static SCIP_RETCODE | transformColumn (SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_COL *col, SCIP_Real offset, SCIP_Real sigma, SCIP_Real *lhs, SCIP_Real *rhs, SCIP_Real *lb, SCIP_Real *ub, SCIP_Real *primsol) |
static SCIP_Real | computeObjWeightSize (int rowsize, int minrowsize, int maxrowsize) |
static SCIP_RETCODE | createSubscip (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata) |
static SCIP_RETCODE | subscipSetParams (SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success) |
static SCIP_RETCODE | solveSubscip (SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *success) |
static SCIP_RETCODE | createCGCutDirect (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen) |
static SCIP_RETCODE | createCGCutCMIR (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen) |
static SCIP_RETCODE | createCGCutStrongCG (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_SOL *sol, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real *cutvals, SCIP_Real *varsolvals, SCIP_Real *weights, int *nprevrows, SCIP_ROW **prevrows, SCIP_Bool *cutoff, unsigned int *ngen) |
static SCIP_RETCODE | createCGCuts (SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata, SCIP_Bool *cutoff, unsigned int *ngen) |
static SCIP_RETCODE | freeSubscip (SCIP *scip, SCIP_SEPA *sepa, CGMIP_MIPDATA *mipdata) |
static | SCIP_DECL_SEPAINIT (sepaInitCGMIP) |
static | SCIP_DECL_SEPAEXIT (sepaExitCGMIP) |
static | SCIP_DECL_SEPACOPY (sepaCopyCGMIP) |
static | SCIP_DECL_SEPAFREE (sepaFreeCGMIP) |
static | SCIP_DECL_SEPAEXECLP (sepaExeclpCGMIP) |
SCIP_RETCODE | SCIPincludeSepaCGMIP (SCIP *scip) |
#define SEPA_NAME "cgmip" |
Definition at line 73 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaCGMIP().
#define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator" |
Definition at line 74 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define SEPA_PRIORITY -1000 |
Definition at line 75 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define SEPA_FREQ -1 |
Definition at line 76 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 77 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define SEPA_USESSUBSCIP TRUE |
does the separator use a secondary SCIP instance?
Definition at line 78 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 79 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MAXROUNDS 5 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 81 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MAXROUNDSROOT 50 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 82 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MAXDEPTH -1 |
maximal depth at which the separator is applied
Definition at line 83 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_DECISIONTREE FALSE |
Use decision tree to turn separation on/off?
Definition at line 84 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_TIMELIMIT 1e20 |
time limit for sub-MIP (set to infinity in order to be deterministic)
Definition at line 85 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MEMORYLIMIT 1e20 |
memory limit for sub-MIP
Definition at line 86 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_CUTCOEFBND 1000.0 |
bounds on the values of the coefficients in the CG-cut
Definition at line 87 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MINNODELIMIT 500LL |
minimum number of nodes considered for sub-MIP (-1: unlimited)
Definition at line 88 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MAXNODELIMIT 5000LL |
maximum number of nodes considered for sub-MIP (-1: unlimited)
Definition at line 89 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_ONLYACTIVEROWS FALSE |
Use only active rows to generate cuts?
Definition at line 90 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MAXROWAGE -1 |
maximal age of rows to consider if onlyactiverows is false
Definition at line 91 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_ONLYRANKONE FALSE |
Separate rank 1 inequalities w.r.t. CG-MIP separator?
Definition at line 92 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_ONLYINTVARS FALSE |
Generate cuts for problems with only integer variables?
Definition at line 93 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_CONTCONVERT FALSE |
Convert some integral variables to be continuous to reduce the size of the sub-MIP?
Definition at line 94 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_CONTCONVFRAC 0.1 |
fraction of integral variables converted to be continuous (if contconvert)
Definition at line 95 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_CONTCONVMIN 100 |
minimum number of integral variables before some are converted to be continuous
Definition at line 96 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_INTCONVERT FALSE |
Convert some integral variables attaining fractional values to have integral value?
Definition at line 97 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_INTCONVFRAC 0.1 |
fraction of fractional integral variables converted to have integral value (if intconvert)
Definition at line 98 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_INTCONVMIN 100 |
minimum number of integral variables before some are converted to have integral value
Definition at line 99 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_SKIPMULTBOUNDS TRUE |
Skip the upper bounds on the multipliers in the sub-MIP?
Definition at line 100 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_OBJLONE FALSE |
Should the objective of the sub-MIP only minimize the l1-norm of the multipliers?
Definition at line 101 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_OBJWEIGHT 1e-03 |
objective weight for artificial variables
Definition at line 102 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_OBJWEIGHTSIZE TRUE |
Weight each row by its size?
Definition at line 103 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_DYNAMICCUTS TRUE |
Should generated cuts be removed from the LP if they are no longer tight?
Definition at line 104 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_USECMIR TRUE |
Use CMIR-generator (otherwise add cut directly)?
Definition at line 105 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_USESTRONGCG FALSE |
Use strong CG-function to strengthen cut?
Definition at line 106 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_CMIROWNBOUNDS FALSE |
Tell CMIR-generator which bounds to used in rounding?
Definition at line 107 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_USECUTPOOL TRUE |
Use cutpool to store CG-cuts even if the are not efficient?
Definition at line 108 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_PRIMALSEPARATION TRUE |
Only separate cuts that are tight for the best feasible solution?
Definition at line 109 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_EARLYTERM TRUE |
Terminate separation if a violated (but possibly sub-optimal) cut has been found?
Definition at line 110 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_ADDVIOLATIONCONS FALSE |
Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?
Definition at line 111 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_ADDVIOLCONSHDLR FALSE |
Add constraint handler to filter out violated cuts?
Definition at line 112 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_CONSHDLRUSENORM TRUE |
Should the violation constraint handler use the norm of a cut to check for feasibility?
Definition at line 113 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_USEOBJUB FALSE |
Use upper bound on objective function (via primal solution)?
Definition at line 114 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_USEOBJLB FALSE |
Use lower bound on objective function (via lower bound)?
Definition at line 115 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_SUBSCIPFAST TRUE |
Should the settings for the sub-MIP be optimized for speed?
Definition at line 116 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_OUTPUT FALSE |
Should information about the sub-MIP and cuts be displayed?
Definition at line 117 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_RANDSEED 101 |
start random seed for random number generation
Definition at line 118 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAINIT().
#define NROWSTOOSMALL 5 |
only separate if the number of rows is larger than this number
Definition at line 120 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAEXECLP().
#define NCOLSTOOSMALL 5 |
only separate if the number of columns is larger than this number
Definition at line 121 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAEXECLP().
#define EPSILONVALUE 1e-03 |
epsilon value needed to model strict-inequalities
Definition at line 123 of file sepa_cgmip.c.
Referenced by createSubscip().
#define BETAEPSILONVALUE 1e-02 |
epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability
Definition at line 124 of file sepa_cgmip.c.
Referenced by createSubscip().
#define STALLNODELIMIT 1000LL |
number of stalling nodes if earlyterm is true
Definition at line 125 of file sepa_cgmip.c.
Referenced by solveSubscip().
#define CONSHDLRFULLNORM FALSE |
compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true)
Definition at line 126 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAEXECLP().
#define MINEFFICACY 0.05 |
minimum efficacy of a cut - compare set.c
Definition at line 127 of file sepa_cgmip.c.
Referenced by createSubscip(), and subscipSetParams().
#define MAXNSOLS 1000 |
maximal number of solutions stored in sub-SCIP
Definition at line 128 of file sepa_cgmip.c.
Referenced by subscipSetParams().
#define OBJWEIGHTRANGE 0.01 |
maximal range of scaling of objective w.r.t. size of rows
Definition at line 129 of file sepa_cgmip.c.
Referenced by computeObjWeightSize().
#define BOUNDSWITCH 0.9999 |
Definition at line 132 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define USEVBDS TRUE |
Definition at line 133 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define POSTPROCESS TRUE |
Definition at line 134 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define MINFRAC 0.0009 /* to allow a deviation of the same size as EPSILONVALUE */ |
Definition at line 135 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define MAXFRAC 0.9991 /* to allow a deviation of the same size as EPSILONVALUE */ |
Definition at line 136 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define FIXINTEGRALRHS FALSE |
Definition at line 137 of file sepa_cgmip.c.
Referenced by createCGCutCMIR().
#define MAKECONTINTEGRAL FALSE |
Definition at line 138 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define MAXWEIGHTRANGE 1e+05 |
maximal valid range max(|weights|)/min(|weights|) of row weights
Definition at line 139 of file sepa_cgmip.c.
Referenced by computeCut().
#define MAXAGGRLEN | ( | nvars | ) | nvars |
currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000)
Definition at line 141 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
#define CONSHDLR_NAME "violatedCuts" |
Definition at line 240 of file sepa_cgmip.c.
Referenced by SCIPincludeConshdlrViolatedCut().
#define CONSHDLR_DESC "only allow solutions corresponding to violated cuts" |
Definition at line 241 of file sepa_cgmip.c.
Referenced by SCIPincludeConshdlrViolatedCut().
typedef enum CGMIP_ColType CGMIP_COLTYPE |
Definition at line 197 of file sepa_cgmip.c.
typedef struct CGMIP_MIPData CGMIP_MIPDATA |
Definition at line 232 of file sepa_cgmip.c.
enum CGMIP_ColType |
what happens for columns in the LP
Definition at line 189 of file sepa_cgmip.c.
|
static |
Computes cut from the given multipliers
Note that the cut computed here in general will not be the same as the one computed with the sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are combined in any case. This makes a difference, if the coefficients in the matrix are large and hence yield a value that is larger than the tolerance.
Because of the transformations we have the following:
If variable \(x_j\) was complemented, we have \(x'_j = u_j - x_j\). If in the transformed system the lower bound is used, its corresponding multiplier is \(y^T A'_j - \lfloor y^T A'_j \rfloor\), which corresponds to
\[ y^T A'_j - \lfloor y^T A'_j \rfloor = - y^T A_j - \lfloor - y^T A_j \rfloor = - y^T A_j + \lceil y^T A_j \rceil \]
in the original system.
If such a variable was at its upper bound before the transformation, it is at its lower bound afterwards. Hence, its contribution to the cut is 0.
Note that if the original LP-solution does not satisfy some of the rows with equality the violation of the cut might be smaller than what is computed with the reduced sub-MIP.
Furthermore, note that if continuous variables have been shifted, the computed violated may be different as well, because the necessary changes in the lhs/rhs are not used here anymore.
scip | original scip |
sepa | separator |
mipdata | data for sub-MIP |
sepadata | separator data |
sol | current solution for sub-MIP |
cutcoefs | coefficients of the cut |
cutrhs | rhs of the cut |
localrowsused | pointer to store whether local rows were used in summation |
localboundsused | pointer to store whether local bounds were used in summation |
cutrank | pointer to store the cut rank |
success | whether we produced a valid cut |
Definition at line 2363 of file sepa_cgmip.c.
References BMSclearMemoryArray, colContinuous, colConverted, colPresent, FALSE, MAXWEIGHTRANGE, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetLb(), SCIPcolGetLPPos(), SCIPcolGetObj(), SCIPcolGetUb(), SCIPcolGetVar(), SCIPfeasCeil(), SCIPfeasFloor(), SCIPfrac(), SCIPgetLowerbound(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPgetVarsData(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPisIntegral(), SCIPisNegative(), SCIPisObjIntegral(), SCIPisSumPositive(), SCIPisSumZero(), SCIPisZero(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetOriginSepa(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPvarGetCol(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and TRUE.
Referenced by createCGCutDirect(), and solCutIsViolated().
|
static |
check whether cut corresponding to solution is violated
scip | SCIP data structure |
mipdata | data of separating sub-MIP |
sol | solution to be checked |
violated | pointer to store if the cut is violated |
Definition at line 267 of file sepa_cgmip.c.
References computeCut(), FALSE, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfoMessage(), SCIPisEfficacious(), SCIPisZero(), SCIPvarGetLPSol(), and SCIPvarGetObj().
Referenced by SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOLP().
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 460 of file sepa_cgmip.c.
References SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeBlockMemory.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 477 of file sepa_cgmip.c.
References SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPgetNLPBranchCands(), and solCutIsViolated().
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 504 of file sepa_cgmip.c.
References SCIP_FEASIBLE, and SCIP_OKAY.
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 518 of file sepa_cgmip.c.
References SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), and solCutIsViolated().
|
static |
variable rounding lock method of constraint handler
Definition at line 544 of file sepa_cgmip.c.
References SCIP_OKAY.
|
static |
creates the violated CG-cut constraint handler and includes it in SCIP
scip | SCIP data structure |
mipdata | data of separating sub-MIP |
Definition at line 553 of file sepa_cgmip.c.
References CONSHDLR_DESC, CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPincludeConshdlrBasic(), and SCIPsetConshdlrFree().
Referenced by createSubscip().
|
static |
stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm
copied from sepa_gomory.c
scip | SCIP data structure |
nvars | number of problem variables |
cutcoefs | dense coefficient vector |
varsolvals | dense variable LP solution vector |
normtype | type of norm to use for efficacy norm calculation |
cutinds | array to store variables of sparse cut vector |
cutvals | array to store coefficients of sparse cut vector |
cutlen | pointer to store number of nonzero entries in cut |
cutact | pointer to store activity of cut |
cutnorm | pointer to store norm of cut vector |
Definition at line 589 of file sepa_cgmip.c.
References REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().
Referenced by createCGCutDirect().
|
static |
Compute lhs/rhs for transformed column
Consider a variable \(x_j\) and some row of the original system:
\[ \gamma \leq a^T x \leq \delta, \quad \ell_j \leq x_j \leq u_j. \]
We perform the transformation
\[ x_i' = \left\{ \begin{array}{ll} s + \frac{1}{\sigma}\, x_j & \mbox{if }i = j\\ x_i & \mbox{otherwise}, \end{array} \right. \]
where \(s\) is the offset value and \(\sigma\) is a scaling factor. The new system is
\[ \gamma + \sigma\, a_j\,s \leq \sum_{i \neq j} a_i\, x_i' + \sigma a_j\, x_j' \leq \delta + \sigma\, a_j\, s \]
with bounds
\[ \frac{1}{\sigma} \ell_j + s \leq x_j' \leq \frac{1}{\sigma} u_j + s, \qquad \mbox{ if }\sigma > 0 \]
and
\[ \frac{1}{\sigma} u_j + s \leq x_j' \leq \frac{1}{\sigma} \ell_j + s, \qquad \mbox{ if }\sigma < 0. \]
This can be used as follows:
scip | SCIP data structure |
sepadata | separator data |
mipdata | data for sub-MIP |
col | column that should be complemented |
offset | offset by which column should be shifted |
sigma | scaling factor |
lhs | array of lhs of rows |
rhs | array rhs of rows |
lb | pointer to lb of column |
ub | pointer to ub of column |
primsol | pointer to solution value |
Definition at line 729 of file sepa_cgmip.c.
References SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetObj(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisZero(), SCIProwGetLPPos(), SCIProwIsLocal(), SCIProwIsModifiable(), and SCIPvarGetObj().
Referenced by createSubscip().
|
static |
compute objective coefficient for rows that are weighted by size
The objective is computed by multiplying a default value by
\[ 1 - (r_{\mbox{max}} - r) \frac{1 - a}{r_{\mbox{max}} - r_{\mbox{min}}}, \]
where \(r\) is the size of the current row, \(a \in [0,1]\) is a parameter, and \(r_{\mbox{max}}\) and \(r_{\mbox{min}}\) are the maximal and minimal size of a row, respectively.
Thus, if \(r = r_{\mbox{max}}\), we get 1 and if \(r = r_{\mbox{min}}\), we get \(a\).
rowsize | size of current row |
minrowsize | maximal size of rows |
maxrowsize | minimal size of rows |
Definition at line 840 of file sepa_cgmip.c.
References OBJWEIGHTRANGE, and SCIP_Real.
Referenced by createSubscip().
|
static |
Creates a subscip representing the separating MIP.
Let the constraints of the original MIP be of the following form:
\[ \begin{array}{l@{\;}ll} a \leq A x + & C r & \leq b\\ \ell \leq x & & \leq u\\ c \leq & r & \leq d\\ x \in Z^n. \end{array} \]
Here, some of the bounds may have value \(\infty\) or \(-\infty\). Written in \(\leq\)-form this becomes:
\[ \begin{array}{r@{\;}l} \tilde{A} x + \tilde{C} r & \leq \tilde{b}\\ -x & \leq -\ell\\ x & \leq u\\ -r & \leq -c\\ r & \leq d\\ x \in Z^n, \end{array} \]
where we use
\[ \tilde{A} = \left[ \begin{array}{r} -A \\ A \end{array} \right], \quad \tilde{C} = \left[ \begin{array}{r} - C\\ C \end{array} \right] \qquad\mbox{ and }\qquad \tilde{b} = \left[ \begin{array}{r} -a\\ b \end{array} \right]. \]
For the moment we assume that \(c = 0\), i.e., the lower bounds on the continuous variables are 0. To obtain a Chvátal-Gomory cut we have to find nonnegative multipliers \(y\), \(\underline{z}\), and \(\overline{z}\) such that
\[ y^T \tilde{A} - \underline{z}^T + \overline{z}^T \in Z \qquad\mbox{ and }\qquad y^T \tilde{C} \geq 0. \]
Note that we use zero multipliers for the bounds on the continuous variables \(r\). Moreover, if some bounds are infinity, the corresponding multipliers are assumed to be 0. From these conditions, we obtain
\[ (y^T \tilde{A} - \underline{z}^T + \overline{z}^T)\, x + y^T \tilde{C} \, r \leq y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u. \]
Because \(r \geq 0\), we can ignore the term \(y^T \tilde{C} \, r \geq 0\) and obtain the following cut:
\[ (y^T \tilde{A} - \underline{z}^T + \overline{z}^T )\, x \leq \lfloor y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u \rfloor. \]
Assume that \(\ell = 0\) for the meantime. Then the cut can be written as:
\[ \lfloor y^T \tilde{A} + \overline{z}^T \rfloor \, x \leq \lfloor y^T \tilde{b} + \overline{z}^T u \rfloor. \]
Following Fischetti and Lodi [2005], let \((x^*,r^*)\) be a fractional solution of the above original system. The separating MIP created below is
\[ \begin{array}{rlr@{\;}l} \max & \multicolumn{2}{@{}l}{(x^*)^T \alpha - \beta - w^T y} &\\ & f = & \tilde{A}^T y + \overline{z} - \alpha & \\ & \tilde{f} = & \tilde{b}^T y + u^T \overline{z} - \beta &\\ & & \tilde{C}^T y & \geq 0\\ & & 0 \leq f & \leq 1 - \epsilon \\ & & 0 \leq \tilde{f} & \leq 1 - \epsilon\\ & & 0 \leq y, \overline{z} & \leq 1 - \epsilon.\\ & & \alpha \in Z^m, \beta & \in Z. \end{array} \]
Here, \(w\) is a weight vector; it's idea is to make the sum over all components of \(y\) as small as possible, in order to generate sparse cuts.
We perform the following additional computations:
contconvert
is true some integral variables are randomly treated as if they were continuous. This has the effect that in the resulting cut the corresponding coefficient has value 0. This makes the cuts more sparse. Moreover, the separation problems should become easier.primalseparation
is true, we force a primal separation step. For this we require that the cut is tight at the currently best solution. To get reliable solutions we relax equality by EPSILONVALUE.useobjub
or useobjlb
), we add a row corresponding to the objective function with respect to the current lower and upper bounds. scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
mipdata | data for sub-MIP |
Definition at line 998 of file sepa_cgmip.c.
References BETAEPSILONVALUE, colAtLb, colAtUb, colContinuous, colConverted, colPresent, computeObjWeightSize(), EPSILONVALUE, FALSE, MINEFFICACY, REALABS, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_INTEGER, SCIPaddCons(), SCIPaddVar(), SCIPallocBlockMemoryArray, SCIPallocBufferArray, SCIPcolGetLb(), SCIPcolGetNLPNonz(), SCIPcolGetObj(), SCIPcolGetPrimsol(), SCIPcolGetRows(), SCIPcolGetUb(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPcolIsIntegral(), SCIPcreate(), SCIPcreateConsLinear(), SCIPcreateProb(), SCIPcreateVar(), SCIPdebugMsg, SCIPfeasCeil(), SCIPfeasFloor(), SCIPfreeBufferArray, SCIPgetBestSol(), SCIPgetLowerbound(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNObjVars(), SCIPgetProbName(), SCIPgetRowLPActivity(), SCIPgetSolVal(), SCIPgetUpperbound(), SCIPgetVarSol(), SCIPincludeConshdlrViolatedCut(), SCIPincludeDefaultPlugins(), SCIPinfinity(), SCIPinfoMessage(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasLT(), SCIPisGT(), SCIPisInfinity(), SCIPisLT(), SCIPisObjIntegral(), SCIPisZero(), SCIPrandomGetReal(), SCIPreleaseCons(), SCIProwGetAge(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetLPPos(), SCIProwGetName(), SCIProwGetNLPNonz(), SCIProwGetOriginSepa(), SCIProwGetRhs(), SCIProwIsIntegral(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsetObjsense(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPwriteOrigProblem(), transformColumn(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
sets parameters for subscip
sepadata | separator data |
mipdata | data for sub-MIP |
success | if setting was successful -> stop solution otherwise |
Definition at line 1993 of file sepa_cgmip.c.
References FALSE, MAXNSOLS, MINEFFICACY, SCIP_CALL, SCIP_OKAY, SCIP_PARAMEMPHASIS_FEASIBILITY, SCIP_PARAMSETTING_FAST, SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
solve subscip
scip | SCIP data structure |
sepadata | separator data |
mipdata | data for sub-MIP |
success | if setting was successful -> stop solution otherwise |
Definition at line 2126 of file sepa_cgmip.c.
References FALSE, MAX, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_LONGINT_MAX, SCIP_OKAY, SCIP_Real, SCIP_STATUS_BESTSOLLIMIT, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_MEMLIMIT, SCIP_STATUS_NODELIMIT, SCIP_STATUS_OPTIMAL, SCIP_STATUS_STALLNODELIMIT, SCIP_STATUS_TIMELIMIT, SCIP_STATUS_USERINTERRUPT, SCIPcheckCopyLimits(), SCIPcopyLimits(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetNLPIterations(), SCIPgetRealParam(), SCIPgetStatus(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), SCIPwarningMessage(), STALLNODELIMIT, and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
Create CG-cut directly from solution of sub-MIP
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
mipdata | data for sub-MIP |
sol | solution of sub-MIP |
cutcoefs | cut coefficients |
cutinds | problem indices of variables appearing in cut |
cutvals | values of variables in cut |
varsolvals | solution value of variables |
weights | weights to compute cmir cut |
nprevrows | number of previously generated rows |
prevrows | previously generated rows |
cutoff | whether a cutoff has been detected |
ngen | number of generated cuts |
Definition at line 2855 of file sepa_cgmip.c.
References colContinuous, colConverted, colPresent, computeCut(), FALSE, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcolGetVar(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutEfficacy(), SCIPgetLPColsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisGE(), SCIPisPositive(), SCIPprintRow(), SCIPprintSol(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRhs(), SCIPsnprintf(), SCIPvarGetObj(), SCIPvarGetProbindex(), storeCutInArrays(), and TRUE.
Referenced by createCGCuts().
|
static |
create CG-cut via CMIR-function
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
mipdata | data for sub-MIP |
sol | solution of sub-MIP |
aggrrow | aggregation row to use for creating MIR cut |
cutcoefs | cut coefficients |
cutinds | problem indices of variables appearing in cut |
cutvals | values of variables in cut |
varsolvals | solution value of variables |
weights | weights to compute cmir cut |
boundsfortrans | bounds for cmir function of NULL |
boundtypesfortrans | type of bounds for cmir function or NULL |
nprevrows | number of previously generated rows |
prevrows | previously generated rows |
cutoff | whether a cutoff has been detected |
ngen | number of generated cuts |
Definition at line 3071 of file sepa_cgmip.c.
References BOUNDSWITCH, colContinuous, colConverted, FALSE, FIXINTEGRALRHS, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, POSTPROCESS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPaggrRowSumRows(), SCIPcacheRowExtensions(), SCIPcalcMIR(), SCIPcolGetLPPos(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPepsilon(), SCIPflushRowExtensions(), SCIPfrac(), SCIPgetCutEfficacy(), SCIPgetLPRowsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPisSumPositive(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsnprintf(), SCIPsumepsilon(), SCIPvarGetCol(), SCIPvarGetStatus(), SCIPvarIsIntegral(), and USEVBDS.
Referenced by createCGCuts().
|
static |
create CG-cut via strong-CG-function
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
mipdata | data for sub-MIP |
sol | solution of sub-MIP |
aggrrow | aggregation row to use for creating MIR cut |
cutcoefs | cut coefficients |
cutinds | problem indices of variables appearing in cut |
cutvals | values of variables in cut |
varsolvals | solution value of variables |
weights | weights to compute cmir cut |
nprevrows | number of previously generated rows |
prevrows | previously generated rows |
cutoff | whether a cutoff has been detected |
ngen | number of generated cuts |
Definition at line 3361 of file sepa_cgmip.c.
References BOUNDSWITCH, FALSE, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPaggrRowSumRows(), SCIPcacheRowExtensions(), SCIPcalcStrongCG(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPepsilon(), SCIPflushRowExtensions(), SCIPfrac(), SCIPgetCutEfficacy(), SCIPgetLPRowsData(), SCIPgetNLPs(), SCIPgetRowLPActivity(), SCIPgetRowMaxCoef(), SCIPgetRowMinCoef(), SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPisEfficacious(), SCIPisEQ(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisGE(), SCIPmakeRowIntegral(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIProwGetNorm(), SCIProwGetParallelism(), SCIProwGetRank(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPsnprintf(), SCIPsumepsilon(), and USEVBDS.
Referenced by createCGCuts().
|
static |
Create CG-cuts from solutions of sub-MIP
scip | SCIP data structure |
sepa | separator |
sepadata | separator data |
mipdata | data for sub-MIP |
cutoff | whether a cutoff has been detected |
ngen | number of generated cuts |
Definition at line 3592 of file sepa_cgmip.c.
References createCGCutCMIR(), createCGCutDirect(), createCGCutStrongCG(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVED, SCIP_STAGE_SOLVING, SCIP_VARSTATUS_COLUMN, SCIPaggrRowCreate(), SCIPaggrRowFree(), SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetNLPRows(), SCIPgetNSols(), SCIPgetSols(), SCIPgetStage(), SCIPgetVarsData(), SCIPreleaseRow(), SCIPvarGetLPSol(), and SCIPvarGetStatus().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
frees "subscip" data
scip | SCIP data structure |
sepa | separator data |
mipdata | data for sub-MIP |
Definition at line 3746 of file sepa_cgmip.c.
References colPresent, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPreleaseVar(), and SCIPsepaGetData().
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 3835 of file sepa_cgmip.c.
References DEFAULT_RANDSEED, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), and SCIPsepaGetData().
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 3850 of file sepa_cgmip.c.
References SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 3864 of file sepa_cgmip.c.
References SCIP_CALL, SCIP_OKAY, SCIPincludeSepaCGMIP(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 3879 of file sepa_cgmip.c.
References SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
|
static |
LP solution separation method of separator
Definition at line 3901 of file sepa_cgmip.c.
References CONSHDLRFULLNORM, createCGCuts(), createSubscip(), FALSE, freeSubscip(), NCOLSTOOSMALL, NROWSTOOSMALL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_LPSOLSTAT_OPTIMAL, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_VERBLEVEL_NORMAL, SCIPallocBlockMemory, SCIPdebugMsg, SCIPfreeBlockMemory, SCIPgetCharParam(), SCIPgetDepth(), SCIPgetFirstLPTime(), SCIPgetLPSolstat(), SCIPgetNContVars(), SCIPgetNLPBranchCands(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsetBoolParam(), SCIPverbMessage(), SEPA_NAME, SCIP_Sepa::sepadata, solveSubscip(), subscipSetParams(), and TRUE.