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:
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 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:
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.
#define SEPA_NAME "cgmip" |
Definition at line 106 of file sepa_cgmip.c.
#define SEPA_DESC "Chvatal-Gomory cuts via MIPs separator" |
Definition at line 107 of file sepa_cgmip.c.
#define SEPA_PRIORITY -1000 |
Definition at line 108 of file sepa_cgmip.c.
#define SEPA_FREQ -1 |
Definition at line 109 of file sepa_cgmip.c.
#define SEPA_MAXBOUNDDIST 0.0 |
Definition at line 110 of file sepa_cgmip.c.
#define SEPA_USESSUBSCIP TRUE |
does the separator use a secondary SCIP instance?
Definition at line 111 of file sepa_cgmip.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 112 of file sepa_cgmip.c.
#define DEFAULT_MAXROUNDS 5 |
maximal number of separation rounds per node (-1: unlimited)
Definition at line 114 of file sepa_cgmip.c.
#define DEFAULT_MAXROUNDSROOT 50 |
maximal number of separation rounds in the root node (-1: unlimited)
Definition at line 115 of file sepa_cgmip.c.
#define DEFAULT_MAXDEPTH -1 |
maximal depth at which the separator is applied
Definition at line 116 of file sepa_cgmip.c.
#define DEFAULT_DECISIONTREE FALSE |
Use decision tree to turn separation on/off?
Definition at line 117 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 118 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_MEMORYLIMIT 1e20 |
memory limit for sub-MIP
Definition at line 119 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 120 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 121 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 122 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_ONLYACTIVEROWS FALSE |
Use only active rows to generate cuts?
Definition at line 123 of file sepa_cgmip.c.
#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().
#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().
#define DEFAULT_ONLYINTVARS FALSE |
Generate cuts for problems with only integer variables?
Definition at line 126 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 127 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 128 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 129 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 130 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 131 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 132 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 133 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 134 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_OBJWEIGHT 1e-03 |
objective weight for artificial variables
Definition at line 135 of file sepa_cgmip.c.
#define DEFAULT_OBJWEIGHTSIZE TRUE |
Weight each row by its size?
Definition at line 136 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 137 of file sepa_cgmip.c.
#define DEFAULT_USECMIR TRUE |
Use CMIR-generator (otherwise add cut directly)?
Definition at line 138 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#define DEFAULT_USESTRONGCG FALSE |
Use strong CG-function to strengthen cut?
Definition at line 139 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#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().
#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().
#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().
#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().
#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().
#define DEFAULT_ADDVIOLCONSHDLR FALSE |
Add constraint handler to filter out violated cuts?
Definition at line 145 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 146 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#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().
#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().
#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().
#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 SCIPincludeHeurInit(), and SCIPincludeSepaCGMIP().
#define DEFAULT_RANDSEED 101 |
start random seed for random number generation
Definition at line 151 of file sepa_cgmip.c.
#define DEFAULT_GENPRIMALSOLS FALSE |
Try to generate primal solutions from Gomory cuts?
Definition at line 152 of file sepa_cgmip.c.
Referenced by SCIPincludeSepaCGMIP().
#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().
#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().
#define EPSILONVALUE 1e-03 |
epsilon value needed to model strict-inequalities
Definition at line 158 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 159 of file sepa_cgmip.c.
Referenced by createSubscip().
#define STALLNODELIMIT 1000LL |
number of stalling nodes if earlyterm is true
Definition at line 160 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 161 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 162 of file sepa_cgmip.c.
Referenced by createSubscip(), and subscipSetParams().
#define MAXNSOLS 1000 |
maximal number of solutions stored in sub-SCIP
Definition at line 163 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 164 of file sepa_cgmip.c.
Referenced by computeObjWeightSize().
#define BOUNDSWITCH 0.9999 |
Definition at line 167 of file sepa_cgmip.c.
#define USEVBDS TRUE |
Definition at line 168 of file sepa_cgmip.c.
#define POSTPROCESS TRUE |
Definition at line 169 of file sepa_cgmip.c.
#define MINFRAC 0.0009 |
to allow a deviation of the same size as EPSILONVALUE
Definition at line 170 of file sepa_cgmip.c.
#define MAXFRAC 0.9991 |
to allow a deviation of the same size as EPSILONVALUE
Definition at line 171 of file sepa_cgmip.c.
#define FIXINTEGRALRHS FALSE |
Definition at line 172 of file sepa_cgmip.c.
Referenced by createCGCutCMIR(), generateGMICuts(), and SCIP_DECL_SEPAEXECLP().
#define MAKECONTINTEGRAL FALSE |
Definition at line 173 of file sepa_cgmip.c.
#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().
#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().
#define SEPARATEROWS TRUE |
Separate rows with integral slack?
Definition at line 176 of file sepa_cgmip.c.
#define MAXAGGRLEN | ( | 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(), createCGCutStrongCG(), generateGMICuts(), and SCIP_DECL_SEPAEXECLP().
#define CONSHDLR_NAME "violatedCuts" |
Definition at line 281 of file sepa_cgmip.c.
#define CONSHDLR_DESC "only allow solutions corresponding to violated cuts" |
Definition at line 282 of file sepa_cgmip.c.
typedef enum CGMIP_ColType CGMIP_COLTYPE |
Definition at line 235 of file sepa_cgmip.c.
typedef struct CGMIP_MIPData CGMIP_MIPDATA |
Definition at line 273 of file sepa_cgmip.c.
enum CGMIP_ColType |
what happens for columns in the LP
Definition at line 227 of file sepa_cgmip.c.
|
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.
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 assert(), BMSclearMemoryArray, colContinuous, colConverted, colPresent, FALSE, i, MAXWEIGHTRANGE, NULL, nvars, obj, 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(), sepadata, sol, TRUE, var, and vars.
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 309 of file sepa_cgmip.c.
References assert(), computeCut(), FALSE, NULL, nvars, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPgetVarsData(), SCIPinfoMessage(), SCIPisEfficacious(), SCIPisZero(), SCIPvarGetLPSol(), SCIPvarGetObj(), sol, SQR, TRUE, var, and vars.
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 508 of file sepa_cgmip.c.
References assert(), NULL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfreeBlockMemory.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 525 of file sepa_cgmip.c.
References assert(), NULL, result, 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 552 of file sepa_cgmip.c.
References assert(), NULL, result, SCIP_FEASIBLE, and SCIP_OKAY.
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 566 of file sepa_cgmip.c.
References assert(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), sol, and solCutIsViolated().
|
static |
variable rounding lock method of constraint handler
Definition at line 592 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 601 of file sepa_cgmip.c.
References assert(), CONSHDLR_DESC, CONSHDLR_NAME, FALSE, NULL, 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 637 of file sepa_cgmip.c.
References assert(), NULL, nvars, REALABS, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIPerrorMessage, SCIPisZero(), and SQR.
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 777 of file sepa_cgmip.c.
References assert(), i, NULL, primsol, SCIP_OKAY, SCIP_Real, SCIPcolGetNLPNonz(), SCIPcolGetObj(), SCIPcolGetRows(), SCIPcolGetVals(), SCIPcolGetVar(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisNegative(), SCIPisZero(), SCIProwGetLPPos(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIPvarGetObj(), and sepadata.
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 888 of file sepa_cgmip.c.
References a, assert(), 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 & (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. origscip | SCIP data structure |
sepa | separator |
sepadata | separator data |
mipdata | data for sub-MIP |
Definition at line 1046 of file sepa_cgmip.c.
References assert(), BETAEPSILONVALUE, colAtLb, colAtUb, colContinuous, colConverted, colPresent, computeObjWeightSize(), EPSILONVALUE, FALSE, i, MINEFFICACY, NULL, obj, primsol, 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(), sepadata, transformColumn(), TRUE, and var.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
sets parameters for subscip
sepadata | separator data |
mipdata | data for sub-MIP |
Definition at line 2050 of file sepa_cgmip.c.
References assert(), 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(), sepadata, and TRUE.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
try to convert fractional gomory cuts to primal solutions of CG-MIP
scip | original SCIP data structure |
sepadata | separator data |
mipdata | data for sub-MIP |
Definition at line 2194 of file sepa_cgmip.c.
References assert(), AWAY, BMSclearMemoryArray, c, colPresent, FALSE, i, NULL, nvars, primsol, 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(), sepadata, sol, TRUE, var, and vars.
Referenced by solveSubscip().
|
static |
solve subscip
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 assert(), createCGMIPprimalsols(), FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), sepadata, 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 3260 of file sepa_cgmip.c.
References assert(), colContinuous, colConverted, colPresent, computeCut(), cutoff, FALSE, NULL, nvars, obj, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, 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(), sepadata, sol, storeCutInArrays(), TRUE, and vars.
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 3483 of file sepa_cgmip.c.
References ABS, assert(), BOUNDSWITCH, colContinuous, colConverted, cutoff, FALSE, FIXINTEGRALRHS, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, nvars, POSTPROCESS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), sepadata, sol, USEVBDS, var, and vars.
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 3773 of file sepa_cgmip.c.
References ABS, assert(), BOUNDSWITCH, cutoff, FALSE, MAKECONTINTEGRAL, MAXAGGRLEN, MAXFRAC, MINFRAC, NULL, nvars, POSTPROCESS, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_LONGINT_FORMAT, 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(), sepadata, sol, USEVBDS, and vars.
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 4004 of file sepa_cgmip.c.
References assert(), createCGCutCMIR(), createCGCutDirect(), createCGCutStrongCG(), cutoff, FALSE, NULL, nvars, SCIP_Bool, 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(), SCIPvarGetStatus(), sepadata, sol, and vars.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
frees "subscip" data
scip | SCIP data structure |
sepa | separator data |
mipdata | data for sub-MIP |
Definition at line 4158 of file sepa_cgmip.c.
References assert(), colPresent, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPfree(), SCIPfreeBlockMemoryArray, SCIPreleaseVar(), SCIPsepaGetData(), and sepadata.
Referenced by SCIP_DECL_SEPAEXECLP().
|
static |
initialization method of separator (called after problem was transformed)
Definition at line 4249 of file sepa_cgmip.c.
References assert(), DEFAULT_RANDSEED, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPsepaGetData(), sepadata, and TRUE.
|
static |
deinitialization method of separator (called before transformed problem is freed)
Definition at line 4264 of file sepa_cgmip.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeRandom(), SCIPsepaGetData(), and sepadata.
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 4278 of file sepa_cgmip.c.
References assert(), NULL, 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 4293 of file sepa_cgmip.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
LP solution separation method of separator
Definition at line 4315 of file sepa_cgmip.c.
References assert(), CONSHDLRFULLNORM, createCGCuts(), createSubscip(), cutoff, depth, FALSE, freeSubscip(), ncalls, NCOLSTOOSMALL, NROWSTOOSMALL, NULL, result, 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, sepadata, solveSubscip(), subscipSetParams(), and TRUE.