SCIP
Solving Constraint Integer Programs
sepa_cgmip.c File Reference
Detailed Description
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 possibilities to generate the final cut:
- The CMIR-routines of SCIP can be used (if
usecmiris true). One can determine which bound is used in the rounding operation (ifcmirownboundsis true) or let SCIP choose the best. This version is generally numerically the most stable. - If
usestrongcgis true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c). - One can directly generate the CG-cut as computed (if
usecmirandusestrongcgare false). The cut is not taken 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:
- There is a node limit (parameters minnodelimit and maxnodelimit).
- There is a time limit (parameter timelimit).
- If paramter earlyterm is true, the separation is run until the first cut that is violated is found. (Note that these cuts are not necessarily added to the LP, because here also the norm of the cuts are taken into account - which cannot easily be included into the separation subscip.) Then the solution process is continued for a certain number of nodes.
- Warning
- This separator should be used carefully - it may require a long separation time.
Definition in file sepa_cgmip.c.
#include "blockmemshell/memory.h"#include "scip/cons_linear.h"#include "scip/cuts.h"#include "scip/pub_cons.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_sepa.h"#include "scip/pub_var.h"#include "scip/scip_branch.h"#include "scip/scip_cons.h"#include "scip/scip_copy.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_prob.h"#include "scip/scip_randnumgen.h"#include "scip/scip_sepa.h"#include "scip/scip_sol.h"#include "scip/scip_solve.h"#include "scip/scip_solvingstats.h"#include "scip/scip_timing.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"#include "scip/scipdefplugins.h"#include "scip/sepa_cgmip.h"#include <string.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_Bool usefrac, 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 *origscip, SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata) |
| static SCIP_RETCODE | subscipSetParams (SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata) |
| static SCIP_RETCODE | createCGMIPprimalsols (SCIP *scip, SCIP_SEPADATA *sepadata, CGMIP_MIPDATA *mipdata) |
| static SCIP_RETCODE | solveSubscip (SCIP *origscip, 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) |
Macro Definition Documentation
◆ SEPA_NAME
| #define SEPA_NAME "cgmip" |
Definition at line 106 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaCGMIP().
◆ SEPA_DESC
| #define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator" |
Definition at line 107 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ SEPA_PRIORITY
| #define SEPA_PRIORITY -1000 |
Definition at line 108 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ SEPA_FREQ
| #define SEPA_FREQ -1 |
Definition at line 109 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ SEPA_MAXBOUNDDIST
| #define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 110 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ SEPA_USESSUBSCIP
| #define SEPA_USESSUBSCIP TRUE |
does the separator use a secondary SCIP instance?
Definition at line 111 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ SEPA_DELAY
| #define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 112 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MAXROUNDS
| #define DEFAULT_MAXROUNDS 5 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 114 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MAXROUNDSROOT
| #define DEFAULT_MAXROUNDSROOT 50 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 115 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MAXDEPTH
| #define DEFAULT_MAXDEPTH -1 |
maximal depth at which the separator is applied
Definition at line 116 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_DECISIONTREE
| #define DEFAULT_DECISIONTREE FALSE |
Use decision tree to turn separation on/off?
Definition at line 117 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_TIMELIMIT
| #define DEFAULT_TIMELIMIT 1e20 |
time limit for sub-MIP (set to infinity in order to be deterministic)
Definition at line 118 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MEMORYLIMIT
| #define DEFAULT_MEMORYLIMIT 1e20 |
memory limit for sub-MIP
Definition at line 119 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_CUTCOEFBND
| #define DEFAULT_CUTCOEFBND 1000.0 |
bounds on the values of the coefficients in the CG-cut
Definition at line 120 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MINNODELIMIT
| #define DEFAULT_MINNODELIMIT 500LL |
minimum number of nodes considered for sub-MIP (-1: unlimited)
Definition at line 121 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MAXNODELIMIT
| #define DEFAULT_MAXNODELIMIT 5000LL |
maximum number of nodes considered for sub-MIP (-1: unlimited)
Definition at line 122 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_ONLYACTIVEROWS
| #define DEFAULT_ONLYACTIVEROWS FALSE |
Use only active rows to generate cuts?
Definition at line 123 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_MAXROWAGE
| #define DEFAULT_MAXROWAGE -1 |
maximal age of rows to consider if onlyactiverows is false
Definition at line 124 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_ONLYRANKONE
| #define DEFAULT_ONLYRANKONE FALSE |
Separate rank 1 inequalities w.r.t. CG-MIP separator?
Definition at line 125 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_ONLYINTVARS
| #define DEFAULT_ONLYINTVARS FALSE |
Generate cuts for problems with only integer variables?
Definition at line 126 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_CONTCONVERT
| #define DEFAULT_CONTCONVERT FALSE |
Convert some integral variables to be continuous to reduce the size of the sub-MIP?
Definition at line 127 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_CONTCONVFRAC
| #define DEFAULT_CONTCONVFRAC 0.1 |
fraction of integral variables converted to be continuous (if contconvert)
Definition at line 128 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_CONTCONVMIN
| #define DEFAULT_CONTCONVMIN 100 |
minimum number of integral variables before some are converted to be continuous
Definition at line 129 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_INTCONVERT
| #define DEFAULT_INTCONVERT FALSE |
Convert some integral variables attaining fractional values to have integral value?
Definition at line 130 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_INTCONVFRAC
| #define DEFAULT_INTCONVFRAC 0.1 |
fraction of fractional integral variables converted to have integral value (if intconvert)
Definition at line 131 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_INTCONVMIN
| #define DEFAULT_INTCONVMIN 100 |
minimum number of integral variables before some are converted to have integral value
Definition at line 132 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_SKIPMULTBOUNDS
| #define DEFAULT_SKIPMULTBOUNDS TRUE |
Skip the upper bounds on the multipliers in the sub-MIP?
Definition at line 133 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_OBJLONE
| #define DEFAULT_OBJLONE FALSE |
Should the objective of the sub-MIP only minimize the l1-norm of the multipliers?
Definition at line 134 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_OBJWEIGHT
| #define DEFAULT_OBJWEIGHT 1e-03 |
objective weight for artificial variables
Definition at line 135 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_OBJWEIGHTSIZE
| #define DEFAULT_OBJWEIGHTSIZE TRUE |
Weight each row by its size?
Definition at line 136 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_DYNAMICCUTS
| #define DEFAULT_DYNAMICCUTS TRUE |
Should generated cuts be removed from the LP if they are no longer tight?
Definition at line 137 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_USECMIR
| #define DEFAULT_USECMIR TRUE |
Use CMIR-generator (otherwise add cut directly)?
Definition at line 138 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_USESTRONGCG
| #define DEFAULT_USESTRONGCG FALSE |
Use strong CG-function to strengthen cut?
Definition at line 139 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_CMIROWNBOUNDS
| #define DEFAULT_CMIROWNBOUNDS FALSE |
Tell CMIR-generator which bounds to used in rounding?
Definition at line 140 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_USECUTPOOL
| #define DEFAULT_USECUTPOOL TRUE |
Use cutpool to store CG-cuts even if the are not efficient?
Definition at line 141 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_PRIMALSEPARATION
| #define DEFAULT_PRIMALSEPARATION TRUE |
Only separate cuts that are tight for the best feasible solution?
Definition at line 142 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_EARLYTERM
| #define DEFAULT_EARLYTERM TRUE |
Terminate separation if a violated (but possibly sub-optimal) cut has been found?
Definition at line 143 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_ADDVIOLATIONCONS
| #define DEFAULT_ADDVIOLATIONCONS FALSE |
Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?
Definition at line 144 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_ADDVIOLCONSHDLR
| #define DEFAULT_ADDVIOLCONSHDLR FALSE |
Add constraint handler to filter out violated cuts?
Definition at line 145 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_CONSHDLRUSENORM
| #define DEFAULT_CONSHDLRUSENORM TRUE |
Should the violation constraint handler use the norm of a cut to check for feasibility?
Definition at line 146 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_USEOBJUB
| #define DEFAULT_USEOBJUB FALSE |
Use upper bound on objective function (via primal solution)?
Definition at line 147 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_USEOBJLB
| #define DEFAULT_USEOBJLB FALSE |
Use lower bound on objective function (via lower bound)?
Definition at line 148 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_SUBSCIPFAST
| #define DEFAULT_SUBSCIPFAST TRUE |
Should the settings for the sub-MIP be optimized for speed?
Definition at line 149 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_OUTPUT
| #define DEFAULT_OUTPUT FALSE |
Should information about the sub-MIP and cuts be displayed?
Definition at line 150 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ DEFAULT_RANDSEED
| #define DEFAULT_RANDSEED 101 |
start random seed for random number generation
Definition at line 151 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAINIT().
◆ DEFAULT_GENPRIMALSOLS
| #define DEFAULT_GENPRIMALSOLS FALSE |
Try to generate primal solutions from Gomory cuts?
Definition at line 152 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
◆ NROWSTOOSMALL
| #define NROWSTOOSMALL 5 |
only separate if the number of rows is larger than this number
Definition at line 155 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ NCOLSTOOSMALL
| #define NCOLSTOOSMALL 5 |
only separate if the number of columns is larger than this number
Definition at line 156 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ EPSILONVALUE
| #define EPSILONVALUE 1e-03 |
epsilon value needed to model strict-inequalities
Definition at line 158 of file sepa_cgmip.c.
Referenced by createSubscip().
◆ BETAEPSILONVALUE
| #define BETAEPSILONVALUE 1e-02 |
epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability
Definition at line 159 of file sepa_cgmip.c.
Referenced by createSubscip().
◆ STALLNODELIMIT
| #define STALLNODELIMIT 1000LL |
number of stalling nodes if earlyterm is true
Definition at line 160 of file sepa_cgmip.c.
Referenced by solveSubscip().
◆ CONSHDLRFULLNORM
| #define CONSHDLRFULLNORM FALSE |
compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true)
Definition at line 161 of file sepa_cgmip.c.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ MINEFFICACY
| #define MINEFFICACY 0.05 |
minimum efficacy of a cut - compare set.c
Definition at line 162 of file sepa_cgmip.c.
Referenced by createSubscip(), and subscipSetParams().
◆ MAXNSOLS
| #define MAXNSOLS 1000 |
maximal number of solutions stored in sub-SCIP
Definition at line 163 of file sepa_cgmip.c.
Referenced by subscipSetParams().
◆ OBJWEIGHTRANGE
| #define OBJWEIGHTRANGE 0.01 |
maximal range of scaling of objective w.r.t. size of rows
Definition at line 164 of file sepa_cgmip.c.
Referenced by computeObjWeightSize().
◆ BOUNDSWITCH
| #define BOUNDSWITCH 0.9999 |
Definition at line 167 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ USEVBDS
| #define USEVBDS TRUE |
Definition at line 168 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ POSTPROCESS
| #define POSTPROCESS TRUE |
Definition at line 169 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ MINFRAC
| #define MINFRAC 0.0009 |
to allow a deviation of the same size as EPSILONVALUE
Definition at line 170 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ MAXFRAC
| #define MAXFRAC 0.9991 |
to allow a deviation of the same size as EPSILONVALUE
Definition at line 171 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ FIXINTEGRALRHS
| #define FIXINTEGRALRHS FALSE |
Definition at line 172 of file sepa_cgmip.c.
Referenced by createCGCutCMIR().
◆ MAKECONTINTEGRAL
| #define MAKECONTINTEGRAL FALSE |
Definition at line 173 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ MAXWEIGHTRANGE
| #define MAXWEIGHTRANGE 1e+05 |
maximal valid range max(|weights|)/min(|weights|) of row weights
Definition at line 174 of file sepa_cgmip.c.
Referenced by computeCut().
◆ AWAY
| #define AWAY 0.005 |
minimal fractionality of a basic variable in order to try GMI cut
Definition at line 175 of file sepa_cgmip.c.
Referenced by createCGMIPprimalsols().
◆ SEPARATEROWS
| #define SEPARATEROWS TRUE |
Separate rows with integral slack?
Definition at line 176 of file sepa_cgmip.c.
◆ MAXAGGRLEN
| #define MAXAGGRLEN | ( | nvars | ) | nvars |
currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000)
Definition at line 178 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), and createCGCutStrongCG().
◆ CONSHDLR_NAME
| #define CONSHDLR_NAME "violatedCuts" |
Definition at line 281 of file sepa_cgmip.c.
Referenced by SCIPincludeConshdlrViolatedCut().
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "only allow solutions corresponding to violated cuts" |
Definition at line 282 of file sepa_cgmip.c.
Referenced by SCIPincludeConshdlrViolatedCut().
Typedef Documentation
◆ CGMIP_COLTYPE
| typedef enum CGMIP_ColType CGMIP_COLTYPE |
Definition at line 235 of file sepa_cgmip.c.
◆ CGMIP_MIPDATA
| typedef struct CGMIP_MIPData CGMIP_MIPDATA |
Definition at line 273 of file sepa_cgmip.c.
Enumeration Type Documentation
◆ CGMIP_ColType
| enum CGMIP_ColType |
what happens for columns in the LP
Definition at line 227 of file sepa_cgmip.c.
Function Documentation
◆ computeCut()
|
static |
Computes cut from the given multipliers
When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is checked and returned.
Moreover, 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 violation may be different as well, because the necessary changes in the lhs/rhs are not used here anymore.
- Parameters
-
scip original scip sepa separator mipdata data for sub-MIP sepadata separator data sol current solution for sub-MIP usefrac use fractional value of multipliers 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 2743 of file sepa_cgmip.c.
References BMSclearMemoryArray, colContinuous, colConverted, colPresent, FALSE, MAXWEIGHTRANGE, NULL, 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().
◆ solCutIsViolated()
|
static |
check whether cut corresponding to solution is violated
- Parameters
-
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 309 of file sepa_cgmip.c.
References computeCut(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfoMessage(), SCIPisEfficacious(), SCIPisZero(), SCIPvarGetLPSol(), SCIPvarGetObj(), and TRUE.
Referenced by SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOLP().
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 508 of file sepa_cgmip.c.
References NULL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeBlockMemory.
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 525 of file sepa_cgmip.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), SCIPgetNLPBranchCands(), and solCutIsViolated().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 552 of file sepa_cgmip.c.
References NULL, SCIP_FEASIBLE, and SCIP_OKAY.
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 566 of file sepa_cgmip.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), and solCutIsViolated().
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 592 of file sepa_cgmip.c.
References SCIP_OKAY.
◆ SCIPincludeConshdlrViolatedCut()
|
static |
creates the violated CG-cut constraint handler and includes it in SCIP
- Parameters
-
scip SCIP data structure mipdata data of separating sub-MIP
Definition at line 601 of file sepa_cgmip.c.
References CONSHDLR_DESC, CONSHDLR_NAME, FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemory, SCIPincludeConshdlrBasic(), and SCIPsetConshdlrFree().
Referenced by createSubscip().
◆ storeCutInArrays()
|
static |
stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm
copied from sepa_gomory.c
- Parameters
-
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 637 of file sepa_cgmip.c.
References NULL, REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, and SCIPisZero().
Referenced by createCGCutDirect().
◆ transformColumn()
|
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:
- If \(x_j \geq \ell_j\) has a (nonzero) lower bound, one can use \(s = -\ell_j\), \(\sigma = 1\), and obtain \(\gamma - a_j\,\ell_j \leq a^T x' \leq \delta - a_j\,\ell_j\), \(0 \leq x_j' \leq u_j - \ell_j\).
- If \(x_j \leq u_j\) has a (nonzero) upper bound, one can use \(s = u_j\), \(\sigma = -1\), and obtain \(\gamma - a_j\,u_j \leq \sum_{i \neq j} a_i\, x_i' - a_j\, x_j' \leq \delta - a_j\, u_j\), \(0 \leq x_j' \leq u_j - \ell_j\).
- Parameters
-
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 777 of file sepa_cgmip.c.
References NULL, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetObj(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisZero(), SCIProwGetLPPos(), SCIProwIsLocal(), SCIProwIsModifiable(), and SCIPvarGetObj().
Referenced by createSubscip().
◆ computeObjWeightSize()
|
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\).
- Parameters
-
rowsize size of current row minrowsize maximal size of rows maxrowsize minimal size of rows
Definition at line 888 of file sepa_cgmip.c.
References a, OBJWEIGHTRANGE, and SCIP_Real.
Referenced by createSubscip().
◆ 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 & (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:
- If the lower bounds on \(x_i\) or \(r_j\) are finite, we shift the variable to have a zero lower bound, i.e., we replace it by \(x_i - \ell_i\) (or \(r_j - u_j\)). This is helpful in several ways: As seen above, the resulting inequalities/formulations simplify. Moreover, it allows to drop a variable if \(x^*_i = 0\), see the next comment. If the lower bounds are not finite, but the upper bounds are finite, we can complement the variable. If the variables are free, the above formulation changes as follows: For free continuous variables, we require \(\tilde{C}^T y = 0\). For a free integer variable \(x_j\) (which rarely occurs in practice), we require \(f_j = 0\), i.e., we force that \((\tilde{A}^T y + \overline{z})_j = \alpha_j\).
- If \(x^*_j = 0 = \ell_j\) (after the above preprocessing), we drop variable \(\alpha_j\) from the formulation. Let \((\alpha^*, \beta^*, y^*, \overline{z}^*)\) be an optimal solution to the separating MIP. Then we can compute \(\alpha_j = \lfloor(\tilde{A}_j^T y^* + \overline{z}^*)\rfloor\).
- If \(x^*_i = u_i\), we complement the variable and drop it from the formulation, since the lower bound is 0 afterwards.
- If a variable has been shifted or complemented, we have to recompute \(\beta\) with the original lhs/rhs.
- If a continuous variable \(r_j\) is free, we have to force equality for the corresponding components in \(y^T \tilde{C} \, r \geq 0\).
- If an integer variable \(x_i\) is free, we are not allowed to round the cut down. In this case, the combintation of rows and bounds has to be integral. We force this by requiring that \(f_i = 0\).
- If
contconvertis 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. - If required, i.e., parameter
primalseparationis 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. - If required (via parameters
useobjuboruseobjlb), we add a row corresponding to the objective function with respect to the current lower and upper bounds.
- Parameters
-
origscip SCIP data structure sepa separator sepadata separator data mipdata data for sub-MIP
Definition at line 1046 of file sepa_cgmip.c.
References BETAEPSILONVALUE, colAtLb, colAtUb, colContinuous, colConverted, colPresent, computeObjWeightSize(), EPSILONVALUE, FALSE, MINEFFICACY, NULL, r, 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(), SCIPgetSubscipDepth(), 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(), SCIPsetSubscipDepth(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPwriteOrigProblem(), transformColumn(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ subscipSetParams()
|
static |
sets parameters for subscip
- Parameters
-
sepadata separator data mipdata data for sub-MIP
Definition at line 2050 of file sepa_cgmip.c.
References FALSE, MAXNSOLS, MINEFFICACY, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PARAMEMPHASIS_FEASIBILITY, SCIP_PARAMSETTING_FAST, SCIPgetProbName(), SCIPinfoMessage(), SCIPisParamFixed(), SCIPsetBoolParam(), SCIPsetEmphasis(), SCIPsetIntParam(), SCIPsetObjlimit(), SCIPsetPresolving(), SCIPsetRealParam(), SCIPsetSeparating(), SCIPsetSubscipsOff(), SCIPsnprintf(), SCIPwriteParams(), and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ createCGMIPprimalsols()
|
static |
try to convert fractional gomory cuts to primal solutions of CG-MIP
- Parameters
-
scip original SCIP data structure sepadata separator data mipdata data for sub-MIP
Definition at line 2194 of file sepa_cgmip.c.
References AWAY, BMSclearMemoryArray, colPresent, FALSE, NULL, r, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPcolGetLPPos(), SCIPcolGetPrimsol(), SCIPcolGetVar(), SCIPcreateSol(), SCIPdebugMsg, SCIPfeasFrac(), SCIPfloor(), SCIPfrac(), SCIPfreeBufferArray, SCIPgetLPBasisInd(), SCIPgetLPBInvRow(), SCIPgetLPColsData(), SCIPgetLPRowsData(), SCIPgetRowLPActivity(), SCIPgetVarsData(), SCIPgetVarSol(), SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIProwGetBasisStatus(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNLPNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsIntegral(), SCIProwIsModifiable(), SCIPsetSolVal(), SCIPtrySolFree(), SCIPvarGetType(), and TRUE.
Referenced by solveSubscip().
◆ solveSubscip()
|
static |
solve subscip
- Parameters
-
origscip SCIP data structure sepadata separator data mipdata data for sub-MIP success if setting was successful -> stop
Definition at line 2443 of file sepa_cgmip.c.
References createCGMIPprimalsols(), FALSE, MAX, NULL, 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(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetDualbound(), SCIPgetMemExternEstim(), SCIPgetMemUsed(), SCIPgetNLPIterations(), SCIPgetNNodes(), SCIPgetRealParam(), SCIPgetSolvingTime(), SCIPgetStatus(), SCIPisInfinity(), SCIPprintStatistics(), SCIPsetBoolParam(), SCIPsetIntParam(), SCIPsetLongintParam(), SCIPsetRealParam(), SCIPsolve(), SCIPtransformProb(), SCIPwarningMessage(), STALLNODELIMIT, and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
◆ createCGCutDirect()
|
static |
Create CG-cut directly from solution of sub-MIP
- Parameters
-
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 3260 of file sepa_cgmip.c.
References colContinuous, colConverted, colPresent, computeCut(), FALSE, NULL, 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().
◆ createCGCutCMIR()
|
static |
create CG-cut via CMIR-function
- Parameters
-
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 3483 of file sepa_cgmip.c.
References BOUNDSWITCH, colContinuous, colConverted, FALSE, FIXINTEGRALRHS, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, 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().
◆ createCGCutStrongCG()
|
static |
create CG-cut via strong-CG-function
- Parameters
-
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 3773 of file sepa_cgmip.c.
References BOUNDSWITCH, FALSE, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, 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().
◆ createCGCuts()
|
static |
Create CG-cuts from solutions of sub-MIP
- Parameters
-
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 4004 of file sepa_cgmip.c.
References createCGCutCMIR(), createCGCutDirect(), createCGCutStrongCG(), FALSE, NULL, 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().
◆ freeSubscip()
|
static |
frees "subscip" data
- Parameters
-
scip SCIP data structure sepa separator data mipdata data for sub-MIP
Definition at line 4158 of file sepa_cgmip.c.
References colPresent, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPreleaseVar(), and SCIPsepaGetData().
Referenced by SCIP_DECL_SEPAEXECLP().
◆ SCIP_DECL_SEPAINIT()
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 4249 of file sepa_cgmip.c.
References DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), and TRUE.
◆ SCIP_DECL_SEPAEXIT()
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 4264 of file sepa_cgmip.c.
References NULL, SCIP_OKAY, SCIPfreeRandom(), and SCIPsepaGetData().
◆ SCIP_DECL_SEPACOPY()
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 4278 of file sepa_cgmip.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaCGMIP(), SCIPsepaGetName(), and SEPA_NAME.
◆ SCIP_DECL_SEPAFREE()
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 4293 of file sepa_cgmip.c.
References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.
◆ SCIP_DECL_SEPAEXECLP()
|
static |
LP solution separation method of separator
Definition at line 4315 of file sepa_cgmip.c.
References CONSHDLRFULLNORM, createCGCuts(), createSubscip(), FALSE, freeSubscip(), NCOLSTOOSMALL, NROWSTOOSMALL, NULL, 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(), SCIPgetFirstLPTime(), SCIPgetLPSolstat(), SCIPgetNContVars(), SCIPgetNLPBranchCands(), SCIPgetNLPCols(), SCIPgetNLPRows(), SCIPisStopped(), SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaGetNCallsAtNode(), SCIPsetBoolParam(), SCIPverbMessage(), SEPA_NAME, SCIP_Sepa::sepadata, solveSubscip(), subscipSetParams(), and TRUE.