SCIP
Solving Constraint Integer Programs
cuts.c File Reference
Detailed Description
methods for aggregation of rows
Definition in file cuts.c.
#include "blockmemshell/memory.h"#include "scip/cuts.h"#include "scip/dbldblarith.h"#include "scip/lp.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_select.h"#include "scip/pub_misc_sort.h"#include "scip/pub_var.h"#include "scip/scip_cut.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_prob.h"#include "scip/scip_sol.h"#include "scip/scip_solvingstats.h"#include "scip/scip_var.h"#include "scip/struct_lp.h"#include "scip/struct_scip.h"#include "scip/struct_set.h"Go to the source code of this file.
Data Structures | |
| struct | LiftingData |
| struct | SNF_Relaxation |
Macros | |
| #define | NONZERO(x) (COPYSIGN(1e-100, (x)) + (x)) |
| #define | MAXCMIRSCALE 1e+6 |
| #define | NO_EXACT_KNAPSACK |
| #define | MAXABSVBCOEF 1e+5 |
| #define | MAXBOUND 1e+10 |
Typedefs | |
| typedef struct LiftingData | LIFTINGDATA |
| typedef struct SNF_Relaxation | SNF_RELAXATION |
Functions | |
| static SCIP_RETCODE | varVecAddScaledRowCoefs (int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale) |
| static SCIP_RETCODE | varVecAddScaledRowCoefsQuad (int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row, SCIP_Real scale) |
| static SCIP_Real | calcEfficacy (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz) |
| static SCIP_Real | calcEfficacyNormQuad (SCIP *scip, SCIP_Real *vals, int *inds, int nnz) |
| static SCIP_Real | calcEfficacyDenseStorageQuad (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz) |
| static SCIP_Bool | removeZerosQuad (SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz) |
| static SCIP_Bool | removeZeros (SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz) |
| static | SCIP_DECL_SORTINDCOMP (compareAbsCoefsQuad) |
| static | SCIP_DECL_SORTINDCOMP (compareAbsCoefs) |
| static SCIP_Bool | chgCoeffWithBound (SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal, QUAD(SCIP_Real *cutrhs)) |
| static SCIP_Bool | chgQuadCoeffWithBound (SCIP *scip, SCIP_VAR *var, QUAD(SCIP_Real oldcoeff), SCIP_Real newcoeff, SCIP_Bool cutislocal, QUAD(SCIP_Real *cutrhs)) |
| static SCIP_RETCODE | cutTightenCoefsQuad (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant) |
| static SCIP_RETCODE | cutTightenCoefs (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant) |
| SCIP_Bool | SCIPcutsTightenCoefficients (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs) |
| SCIP_RETCODE | SCIPaggrRowCreate (SCIP *scip, SCIP_AGGRROW **aggrrow) |
| void | SCIPaggrRowFree (SCIP *scip, SCIP_AGGRROW **aggrrow) |
| void | SCIPaggrRowPrint (SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file) |
| SCIP_RETCODE | SCIPaggrRowCopy (SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source) |
| SCIP_RETCODE | SCIPaggrRowAddRow (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype) |
| void | SCIPaggrRowCancelVarWithBound (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid) |
| SCIP_RETCODE | SCIPaggrRowAddObjectiveFunction (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale) |
| SCIP_RETCODE | SCIPaggrRowAddCustomCons (SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local) |
| void | SCIPaggrRowClear (SCIP_AGGRROW *aggrrow) |
| SCIP_Real | SCIPaggrRowCalcEfficacyNorm (SCIP *scip, SCIP_AGGRROW *aggrrow) |
| static SCIP_RETCODE | addOneRow (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *rowtoolong) |
| SCIP_RETCODE | SCIPaggrRowSumRows (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid) |
| static SCIP_RETCODE | postprocessCut (SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, SCIP_Real *cutrhs, SCIP_Bool *success) |
| static SCIP_RETCODE | postprocessCutQuad (SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, QUAD(SCIP_Real *cutrhs), SCIP_Bool *success) |
| void | SCIPaggrRowRemoveZeros (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid) |
| int | SCIPaggrRowGetNRows (SCIP_AGGRROW *aggrrow) |
| int * | SCIPaggrRowGetRowInds (SCIP_AGGRROW *aggrrow) |
| SCIP_Real * | SCIPaggrRowGetRowWeights (SCIP_AGGRROW *aggrrow) |
| SCIP_Bool | SCIPaggrRowHasRowBeenAdded (SCIP_AGGRROW *aggrrow, SCIP_ROW *row) |
| int * | SCIPaggrRowGetInds (SCIP_AGGRROW *aggrrow) |
| int | SCIPaggrRowGetNNz (SCIP_AGGRROW *aggrrow) |
| int | SCIPaggrRowGetRank (SCIP_AGGRROW *aggrrow) |
| SCIP_Bool | SCIPaggrRowIsLocal (SCIP_AGGRROW *aggrrow) |
| SCIP_Real | SCIPaggrRowGetRhs (SCIP_AGGRROW *aggrrow) |
| static int | filterWithParallelism (SCIP_ROW *cut, SCIP_ROW **cuts, SCIP_Real *scores, int ncuts, SCIP_Real goodscore, SCIP_Real goodmaxparall, SCIP_Real maxparall) |
| static void | selectBestCut (SCIP_ROW **cuts, SCIP_Real *scores, int ncuts) |
| SCIP_RETCODE | SCIPselectCuts (SCIP *scip, SCIP_ROW **cuts, SCIP_RANDNUMGEN *randnumgen, SCIP_Real goodscorefac, SCIP_Real badscorefac, SCIP_Real goodmaxparall, SCIP_Real maxparall, SCIP_Real dircutoffdistweight, SCIP_Real efficacyweight, SCIP_Real objparalweight, SCIP_Real intsupportweight, int ncuts, int nforcedcuts, int maxselectedcuts, int *nselectedcuts) |
| static SCIP_RETCODE | findBestLb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype) |
| static SCIP_RETCODE | findBestUb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype) |
| static SCIP_RETCODE | determineBestBounds (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real *bestlb, SCIP_Real *bestub, int *bestlbtype, int *bestubtype, SCIP_BOUNDTYPE *selectedbound, SCIP_Bool *freevariable) |
| static SCIP_RETCODE | cutsTransformMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | cutsRoundMIR (SCIP *scip, SCIP_Real *RESTRICT cutcoefs, QUAD(SCIP_Real *RESTRICT cutrhs), int *RESTRICT cutinds, int *RESTRICT nnz, int *RESTRICT varsign, int *RESTRICT boundtype, QUAD(SCIP_Real f0)) |
| static SCIP_RETCODE | cutsSubstituteMIR (SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, QUAD(SCIP_Real f0)) |
| SCIP_RETCODE | SCIPcalcMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success) |
| static SCIP_Real | computeMIREfficacy (SCIP *scip, SCIP_Real *RESTRICT coefs, SCIP_Real *RESTRICT solvals, SCIP_Real rhs, SCIP_Real contactivity, SCIP_Real contsqrnorm, SCIP_Real delta, int nvars, SCIP_Real minfrac, SCIP_Real maxfrac) |
| SCIP_RETCODE | SCIPcutGenerationHeuristicCMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success) |
| static SCIP_RETCODE | getClosestVlb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *rowcoefs, int8_t *binvarused, SCIP_Real bestsub, SCIP_Real rowcoef, SCIP_Real *closestvlb, int *closestvlbidx) |
| static SCIP_RETCODE | getClosestVub (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *rowcoefs, int8_t *binvarused, SCIP_Real bestslb, SCIP_Real rowcoef, SCIP_Real *closestvub, int *closestvubidx) |
| static SCIP_RETCODE | determineBoundForSNF (SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *rowcoefs, int *rowinds, int varposinrow, int8_t *binvarused, SCIP_Bool allowlocal, SCIP_Real boundswitch, SCIP_Real *bestlb, SCIP_Real *bestub, SCIP_Real *bestslb, SCIP_Real *bestsub, int *bestlbtype, int *bestubtype, int *bestslbtype, int *bestsubtype, SCIP_BOUNDTYPE *selectedbounds, SCIP_Bool *freevariable) |
| static SCIP_RETCODE | constructSNFRelaxation (SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_Real *rowcoefs, QUAD(SCIP_Real rowrhs), int *rowinds, int nnz, SNF_RELAXATION *snf, SCIP_Bool *success, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | allocSNFRelaxation (SCIP *scip, SNF_RELAXATION *snf, int nvars) |
| static void | destroySNFRelaxation (SCIP *scip, SNF_RELAXATION *snf) |
| static SCIP_RETCODE | SCIPsolveKnapsackApproximatelyLT (SCIP *scip, int nitems, SCIP_Real *weights, SCIP_Real *profits, SCIP_Real capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval) |
| static void | buildFlowCover (SCIP *scip, int *coefs, SCIP_Real *vubcoefs, SCIP_Real rhs, int *solitems, int *nonsolitems, int nsolitems, int nnonsolitems, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, QUAD(SCIP_Real *flowcoverweight), SCIP_Real *lambda) |
| static SCIP_RETCODE | getFlowCover (SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found) |
| static SCIP_Real | evaluateLiftingFunction (SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x) |
| static void | getAlphaAndBeta (SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta) |
| static SCIP_RETCODE | computeLiftingData (SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid) |
| static void | destroyLiftingData (SCIP *scip, LIFTINGDATA *liftingdata) |
| static SCIP_RETCODE | generateLiftedFlowCoverCut (SCIP *scip, SNF_RELAXATION *snf, SCIP_AGGRROW *aggrrow, int *flowcoverstatus, SCIP_Real lambda, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, SCIP_Bool *success) |
| SCIP_RETCODE | SCIPcalcFlowCover (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success) |
| static SCIP_RETCODE | cutsTransformStrongCG (SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | cutsRoundStrongCG (SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, QUAD(SCIP_Real f0), SCIP_Real k) |
| static SCIP_RETCODE | cutsSubstituteStrongCG (SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, QUAD(SCIP_Real f0), SCIP_Real k) |
| SCIP_RETCODE | SCIPcalcStrongCG (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success) |
Macro Definition Documentation
◆ NONZERO
| #define NONZERO | ( | x | ) | (COPYSIGN(1e-100, (x)) + (x)) |
macro to make sure a value is not equal to zero, i.e. NONZERO(x) != 0.0 will be TRUE for every x including 0.0
To avoid branches it will add 1e-100 with the same sign as x to x which will be rounded away for any sane non-zero value but will make sure the value is never exactly 0.0.
Definition at line 108 of file cuts.c.
Referenced by cutsRoundMIR(), cutsTransformMIR(), cutsTransformStrongCG(), SCIPaggrRowAddCustomCons(), SCIPaggrRowAddObjectiveFunction(), SCIPcalcStrongCG(), varVecAddScaledRowCoefs(), and varVecAddScaledRowCoefsQuad().
◆ MAXCMIRSCALE
| #define MAXCMIRSCALE 1e+6 |
maximal scaling (scale/(1-f0)) allowed in c-MIR calculations
Definition at line 2695 of file cuts.c.
Referenced by computeMIREfficacy(), and SCIPcalcMIR().
◆ NO_EXACT_KNAPSACK
◆ MAXABSVBCOEF
| #define MAXABSVBCOEF 1e+5 |
maximal absolute coefficient in variable bounds used for snf relaxation
Definition at line 4987 of file cuts.c.
Referenced by getClosestVlb(), and getClosestVub().
◆ MAXBOUND
| #define MAXBOUND 1e+10 |
maximal value of normal bounds used for snf relaxation
Definition at line 4988 of file cuts.c.
Referenced by determineBoundForSNF().
Typedef Documentation
◆ LIFTINGDATA
| typedef struct LiftingData LIFTINGDATA |
structure that contains all data required to perform the sequence independent lifting
◆ SNF_RELAXATION
| typedef struct SNF_Relaxation SNF_RELAXATION |
structure that contains all the data that defines the single-node-flow relaxation of an aggregation row
Function Documentation
◆ varVecAddScaledRowCoefs()
|
static |
add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
- Parameters
-
inds pointer to array with variable problem indices of non-zeros in variable vector vals array with values of variable vector nnz number of non-zeros coefficients of variable vector row row coefficients to add to variable vector scale scale for adding given row to variable vector
Definition at line 114 of file cuts.c.
References SCIP_Row::cols, SCIP_Row::len, NONZERO, NULL, SCIP_OKAY, SCIP_Real, SCIP_Row::vals, and SCIP_Col::var_probindex.
Referenced by generateLiftedFlowCoverCut().
◆ varVecAddScaledRowCoefsQuad()
|
static |
add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
- Parameters
-
inds pointer to array with variable problem indices of non-zeros in variable vector vals array with values of variable vector nnz number of non-zeros coefficients of variable vector row row coefficients to add to variable vector scale scale for adding given row to variable vector
Definition at line 157 of file cuts.c.
References SCIP_Row::cols, SCIP_Row::len, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_HI, SCIP_OKAY, SCIP_Real, SCIPquadprecSumQD, SCIP_Row::vals, and SCIP_Col::var_probindex.
Referenced by addOneRow(), cutsSubstituteMIR(), cutsSubstituteStrongCG(), and SCIPaggrRowAddRow().
◆ calcEfficacy()
|
static |
calculates the cuts efficacy for the given solution
- Parameters
-
scip SCIP data structure sol solution to calculate the efficacy for (NULL for LP solution) cutcoefs array of the non-zero coefficients in the cut cutrhs the right hand side of the cut cutinds array of the problem indices of variables with a non-zero coefficient in the cut cutnnz the number of non-zeros in the cut
Definition at line 198 of file cuts.c.
References MAX, NULL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), and SCIPgetVectorEfficacyNorm().
Referenced by SCIPcalcFlowCover(), SCIPcalcMIR(), and SCIPcalcStrongCG().
◆ calcEfficacyNormQuad()
calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
- Parameters
-
scip SCIP data structure vals array of the non-zero coefficients in the vector; this is a quad precision array! inds array of the problem indices of variables with a non-zero coefficient in the vector nnz the number of non-zeros in the vector
Definition at line 228 of file cuts.c.
References FALSE, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPisZero(), SCIP_Set::sepa_efficacynorm, and Scip::set.
Referenced by calcEfficacyDenseStorageQuad(), and SCIPaggrRowCalcEfficacyNorm().
◆ calcEfficacyDenseStorageQuad()
|
static |
calculates the cuts efficacy for the given solution; the cut coefs are stored densely and in quad precision
- Parameters
-
scip SCIP data structure sol solution to calculate the efficacy for (NULL for LP solution) cutcoefs array of the non-zero coefficients in the cut; this is a quad precision array! cutrhs the right hand side of the cut cutinds array of the problem indices of variables with a non-zero coefficient in the cut cutnnz the number of non-zeros in the cut
Definition at line 290 of file cuts.c.
References calcEfficacyNormQuad(), MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), and Scip::set.
Referenced by SCIPcutGenerationHeuristicCMIR().
◆ removeZerosQuad()
|
static |
safely remove all items with |a_i| or |u_i - l_i)| below the given value; returns TRUE if the cut became redundant if it is a local cut, use local bounds, otherwise, using global bounds
- Parameters
-
scip SCIP data structure minval minimal absolute value of coefficients that should not be removed cutislocal is the cut local? cutcoefs array of the non-zero coefficients in the cut cutinds array of the problem indices of variables with a non-zero coefficient in the cut cutnnz the number of non-zeros in the cut
Definition at line 327 of file cuts.c.
References EPSZ, FALSE, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_Bool, SCIP_Real, SCIPepsilon(), SCIPgetVars(), SCIPisEQ(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by postprocessCutQuad(), SCIPaggrRowRemoveZeros(), SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
◆ removeZeros()
|
static |
safely remove all items with |a_i| or |u_i - l_i)| below the given value; returns TRUE if the cut became redundant if it is a local cut, use local bounds, otherwise, using global bounds
- Parameters
-
scip SCIP data structure minval minimal absolute value of coefficients that should not be removed cutislocal is the cut local? cutcoefs array of the non-zero coefficients in the cut cutinds array of the problem indices of variables with a non-zero coefficient in the cut cutnnz the number of non-zeros in the cut
Definition at line 415 of file cuts.c.
References EPSZ, FALSE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_Bool, SCIP_Real, SCIPepsilon(), SCIPgetVars(), SCIPisEQ(), SCIPisInfinity(), SCIPquadprecSumQD, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by postprocessCut(), and SCIPcalcFlowCover().
◆ SCIP_DECL_SORTINDCOMP() [1/2]
|
static |
Definition at line 500 of file cuts.c.
References QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, and SCIP_Real.
◆ SCIP_DECL_SORTINDCOMP() [2/2]
|
static |
◆ chgCoeffWithBound()
|
static |
change given coefficient to new given value, adjust right hand side using the variables bound; returns TRUE if the right hand side would need to be changed to infinity and FALSE otherwise
- Parameters
-
scip SCIP data structure var variable the coefficient belongs to oldcoeff old coefficient value newcoeff new coefficient value cutislocal is the cut local?
Definition at line 544 of file cuts.c.
References FALSE, QUAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumDD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by cutTightenCoefs().
◆ chgQuadCoeffWithBound()
|
static |
change given (quad) coefficient to new given value, adjust right hand side using the variables bound; returns TRUE if the right hand side would need to be changed to infinity and FALSE otherwise
- Parameters
-
scip SCIP data structure var variable the coefficient belongs to newcoeff new coefficient value cutislocal is the cut local?
Definition at line 586 of file cuts.c.
References FALSE, QUAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by cutTightenCoefsQuad().
◆ cutTightenCoefsQuad()
|
static |
scales the cut and then tightens the coefficients of the given cut based on the maximal activity; see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse quad precision array;
- Parameters
-
scip SCIP data structure cutislocal is the cut local? cutcoefs array of the non-zero coefficients in the cut cutinds array of the problem indices of variables with a non-zero coefficient in the cut cutnnz the number of non-zeros in the cut redundant whether the cut was detected to be redundant
Definition at line 629 of file cuts.c.
References chgQuadCoeffWithBound(), EPSISINT, FALSE, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPdebugPrintf, SCIPepsilon(), SCIPfeastol(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPround(), SCIPsortDownInd(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), SCIP_Set::sepa_maxcoefratio, Scip::set, and TRUE.
Referenced by postprocessCutQuad().
◆ cutTightenCoefs()
|
static |
scales the cut and then tightens the coefficients of the given cut based on the maximal activity; see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;
- Parameters
-
scip SCIP data structure cutislocal is the cut local? cutcoefs array of the non-zero coefficients in the cut cutinds array of the problem indices of variables with a non-zero coefficient in the cut cutnnz the number of non-zeros in the cut redundant pointer to return whtether the cut was detected to be redundant
Definition at line 1017 of file cuts.c.
References chgCoeffWithBound(), EPSISINT, FALSE, MAX, NULL, QUAD, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPdebugPrintf, SCIPepsilon(), SCIPfeastol(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPround(), SCIPsortDownInd(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), SCIP_Set::sepa_maxcoefratio, Scip::set, and TRUE.
Referenced by postprocessCut().
◆ addOneRow()
|
static |
Adds one row to the aggregation row. Differs from SCIPaggrRowAddRow() by providing some additional parameters required for SCIPaggrRowSumRows()
- Parameters
-
scip SCIP data structure aggrrow the aggregation row row the row to add weight weight of row to add sidetypebasis choose sidetypes of row (lhs/rhs) based on basis information? allowlocal should local rows allowed to be used? negslack should negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes) maxaggrlen maximal length of aggregation row rowtoolong is the aggregated row too long
Definition at line 2021 of file cuts.c.
References SCIP_Row::constant, FALSE, SCIP_AggrRow::inds, SCIP_Row::integral, SCIP_Row::lhs, SCIP_AggrRow::local, SCIP_Row::local, SCIP_Row::lppos, MAX, SCIP_AggrRow::nnz, SCIP_AggrRow::nrows, NULL, SCIP_AggrRow::rank, SCIP_Row::rank, SCIP_Row::rhs, SCIP_AggrRow::rowsinds, SCIP_AggrRow::rowssize, SCIP_AggrRow::rowweights, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPceil(), SCIPfloor(), SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPquadprecSumQD, SCIPreallocBlockMemoryArray, SCIProwGetBasisStatus(), SCIProwGetLhs(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIP_AggrRow::slacksign, TRUE, SCIP_AggrRow::vals, and varVecAddScaledRowCoefsQuad().
Referenced by SCIPaggrRowSumRows().
◆ postprocessCut()
|
static |
checks for cut redundancy and performs activity based coefficient tightening; removes coefficients that are zero with QUAD_EPSILON tolerance and uses variable bounds to remove small coefficients (relative to the maximum absolute coefficient)
- Parameters
-
scip SCIP data structure cutislocal is the cut a local cut cutinds variable problem indices of non-zeros in cut cutcoefs non-zeros coefficients of cut nnz number non-zeros coefficients of cut cutrhs right hand side of cut success pointer to return whether post-processing was succesful or cut is redundant
Definition at line 2192 of file cuts.c.
References cutTightenCoefs(), FALSE, MAX, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, REALABS, removeZeros(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), SCIPsumepsilon(), SCIP_Set::sepa_maxcoefratio, and Scip::set.
Referenced by SCIPcalcFlowCover().
◆ postprocessCutQuad()
|
static |
checks for cut redundancy and performs activity based coefficient tightening; removes coefficients that are zero with QUAD_EPSILON tolerance and uses variable bounds to remove small coefficients (relative to the maximum absolute coefficient). The cutcoefs must be a quad precision array, i.e. allocated with size QUAD_ARRAY_SIZE(nvars) and accessed with QUAD_ARRAY_LOAD and QUAD_ARRAY_STORE macros.
- Parameters
-
scip SCIP data structure cutislocal is the cut a local cut cutinds variable problem indices of non-zeros in cut cutcoefs non-zeros coefficients of cut nnz number non-zeros coefficients of cut success pointer to return whether the cleanup was successful or if it is useless
Definition at line 2261 of file cuts.c.
References cutTightenCoefsQuad(), FALSE, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_HI, QUAD_TO_DBL, REALABS, removeZerosQuad(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), SCIPsumepsilon(), SCIP_Set::sepa_maxcoefratio, and Scip::set.
Referenced by SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
◆ filterWithParallelism()
|
static |
filters the given array of cuts to enforce a maximum parallelism constraints for the given cut; moves filtered cuts to the end of the array and returns number of selected cuts
- Parameters
-
cut cut to filter orthogonality with cuts array with cuts to perform selection algorithm scores array with scores of cuts to perform selection algorithm ncuts number of cuts in given array goodscore threshold for the score to be considered a good cut goodmaxparall maximal parallelism for good cuts maxparall maximal parallelism for all cuts that are not good
Definition at line 2442 of file cuts.c.
References NULL, SCIP_Real, SCIProwGetParallelism(), SCIPswapPointers(), and SCIPswapReals().
Referenced by SCIPselectCuts().
◆ selectBestCut()
move the cut with the highest score to the first position in the array; there must be at least one cut
- Parameters
-
cuts array with cuts to perform selection algorithm scores array with scores of cuts to perform selection algorithm ncuts number of cuts in given array
Definition at line 2479 of file cuts.c.
References NULL, SCIP_Real, SCIPswapPointers(), and SCIPswapReals().
Referenced by SCIPselectCuts().
◆ findBestLb()
|
static |
finds the best lower bound of the variable to use for MIR transformation
- Parameters
-
scip SCIP data structure var problem variable sol the solution that should be separated, or NULL for LP solution usevbds should variable bounds be used in bound transformation? allowlocal should local information allowed to be used, resulting in a local cut? bestlb pointer to store best bound value simplebound pointer to store simple bound value bestlbtype pointer to store best bound type
Definition at line 2699 of file cuts.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPgetVarClosestVlb(), SCIPisGE(), SCIPisGT(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), and SCIPvarGetVlbVars().
Referenced by cutsTransformStrongCG(), determineBestBounds(), determineBoundForSNF(), and SCIPcutGenerationHeuristicCMIR().
◆ findBestUb()
|
static |
finds the best upper bound of the variable to use for MIR transformation
- Parameters
-
scip SCIP data structure var problem variable sol the solution that should be separated, or NULL for LP solution usevbds should variable bounds be used in bound transformation? allowlocal should local information allowed to be used, resulting in a local cut? bestub pointer to store best bound value simplebound pointer to store simple bound bestubtype pointer to store best bound type
Definition at line 2760 of file cuts.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPgetVarClosestVub(), SCIPisLE(), SCIPisLT(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIPvarGetVubVars().
Referenced by cutsTransformStrongCG(), determineBestBounds(), determineBoundForSNF(), and SCIPcutGenerationHeuristicCMIR().
◆ determineBestBounds()
|
static |
determine the best bounds with respect to the given solution for complementing the given variable
- Parameters
-
scip SCIP data structure var variable to determine best bound for sol the solution that should be separated, or NULL for LP solution boundswitch fraction of domain up to which lower bound is used in transformation usevbds should variable bounds be used in bound transformation? allowlocal should local information allowed to be used, resulting in a local cut? fixintegralrhs should complementation tried to be adjusted such that rhs gets fractional? ignoresol should the LP solution be ignored? (eg, apply MIR to dualray) boundsfortrans bounds that should be used for transformed variables: vlb_idx/vub_idx, -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound; NULL for using closest bound for all variables boundtypesfortrans type of bounds that should be used for transformed variables; NULL for using closest bound for all variables bestlb pointer to store best lower bound of variable bestub pointer to store best upper bound of variable bestlbtype pointer to store type of best lower bound of variable bestubtype pointer to store type of best upper bound of variable selectedbound pointer to store whether the lower bound or the upper bound should be preferred freevariable pointer to store if this is a free variable
Definition at line 2821 of file cuts.c.
References findBestLb(), findBestUb(), NULL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), and TRUE.
Referenced by cutsTransformMIR(), cutsTransformStrongCG(), and infinityCountUpdate().
◆ cutsTransformMIR()
|
static |
Transform equation \( a \cdot x = b; lb \leq x \leq ub \) into standard form \( a^\prime \cdot x^\prime = b,\; 0 \leq x^\prime \leq ub' \).
Transform variables (lb or ub):
\[ \begin{array}{llll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \mbox{if lb is used in transformation}\\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if ub is used in transformation} \end{array} \]
and move the constant terms \( a_j\, lb_j \) or \( a_j\, ub_j \) to the rhs.
Transform variables (vlb or vub):
\[ \begin{array}{llll} x^\prime_j := x_j - (bl_j\, zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \mbox{if vlb is used in transf.} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if vub is used in transf.} \end{array} \]
move the constant terms \( a_j\, dl_j \) or \( a_j\, du_j \) to the rhs, and update the coefficient of the VLB variable:
\[ \begin{array}{ll} a_{zl_j} := a_{zl_j} + a_j\, bl_j,& \mbox{or} \\ a_{zu_j} := a_{zu_j} + a_j\, bu_j & \end{array} \]
- Parameters
-
scip SCIP data structure sol the solution that should be separated, or NULL for LP solution boundswitch fraction of domain up to which lower bound is used in transformation usevbds should variable bounds be used in bound transformation? allowlocal should local information allowed to be used, resulting in a local cut? fixintegralrhs should complementation tried to be adjusted such that rhs gets fractional? ignoresol should the LP solution be ignored? (eg, apply MIR to dualray) boundsfortrans bounds that should be used for transformed variables: vlb_idx/vub_idx, -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound; NULL for using closest bound for all variables boundtypesfortrans type of bounds that should be used for transformed variables; NULL for using closest bound for all variables minfrac minimal fractionality of rhs to produce MIR cut for maxfrac maximal fractionality of rhs to produce MIR cut for cutcoefs array of coefficients of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut varsign stores the sign of the transformed variable in summation boundtype stores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub freevariable stores whether a free variable was found in MIR row -> invalid summation localbdsused pointer to store whether local bounds were used in transformation
Definition at line 3046 of file cuts.c.
References determineBestBounds(), EPSFRAC, EPSZ, FALSE, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPerrorMessage, SCIPfrac(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumDD, SCIPquadprecSumQQ, SCIPsortDownInt(), SCIPsumepsilon(), SCIPvarGetLPSol(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), and SCIPvarIsActive().
Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().
◆ cutsRoundMIR()
|
static |
Calculate fractionalities \( f_0 := b - down(b), f_j := a^\prime_j - down(a^\prime_j) \), and derive MIR cut \( \tilde{a} \cdot x' \leq down(b) \)
\[ \begin{array}{rll} integers :& \tilde{a}_j = down(a^\prime_j), & if \qquad f_j \leq f_0 \\ & \tilde{a}_j = down(a^\prime_j) + (f_j - f_0)/(1 - f_0),& if \qquad f_j > f_0 \\ continuous:& \tilde{a}_j = 0, & if \qquad a^\prime_j \geq 0 \\ & \tilde{a}_j = a^\prime_j/(1 - f_0), & if \qquad a^\prime_j < 0 \end{array} \]
Transform inequality back to \( \hat{a} \cdot x \leq rhs \):
(lb or ub):
\[ \begin{array}{lllll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation} \\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation} \end{array} \]
and move the constant terms
\[ \begin{array}{cl} -\tilde{a}_j \cdot lb_j = -\hat{a}_j \cdot lb_j,& \mbox{or} \\ \tilde{a}_j \cdot ub_j = -\hat{a}_j \cdot ub_j & \end{array} \]
to the rhs.
(vlb or vub):
\[ \begin{array}{lllll} x^\prime_j := x_j - (bl_j \cdot zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)} \end{array} \]
move the constant terms
\[ \begin{array}{cl} -\tilde{a}_j\, dl_j = -\hat{a}_j\, dl_j,& \mbox{or} \\ \tilde{a}_j\, du_j = -\hat{a}_j\, du_j & \end{array} \]
to the rhs, and update the VB variable coefficients:
\[ \begin{array}{ll} \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\ \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j\, bu_j = \hat{a}_{zu_j} - \hat{a}_j\, bu_j & \end{array} \]
- Parameters
-
scip SCIP data structure cutcoefs array of coefficients of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut varsign stores the sign of the transformed variable in summation boundtype stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)
Definition at line 3495 of file cuts.c.
References BMScopyMemoryArray, EPSZ, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisLE(), SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), and SCIPvarIsActive().
Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().
◆ cutsSubstituteMIR()
|
static |
substitute aggregated slack variables:
The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack variable only appears in its own row: \( a^\prime_r = scale * weight[r] * slacksign[r]. \)
Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
\[ \begin{array}{rll} integers : & \hat{a}_r = \tilde{a}_r = down(a^\prime_r), & \mbox{if}\qquad f_r <= f0 \\ & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f0)/(1 - f0),& \mbox{if}\qquad f_r > f0 \\ continuous:& \hat{a}_r = \tilde{a}_r = 0, & \mbox{if}\qquad a^\prime_r >= 0 \\ & \hat{a}_r = \tilde{a}_r = a^\prime_r/(1 - f0), & \mbox{if}\qquad a^\prime_r < 0 \end{array} \]
Substitute \( \hat{a}_r \cdot s_r \) by adding \( \hat{a}_r \) times the slack's definition to the cut.
- Parameters
-
scip SCIP data structure weights row weights in row summation slacksign stores the sign of the row's slack variable in summation rowinds sparsity pattern of used rows nrowinds number of used rows scale additional scaling factor multiplied to all rows cutcoefs array of coefficients of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut
Definition at line 3809 of file cuts.c.
References SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, EPSFLOOR, EPSZ, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, NULL, QUAD, QUAD_ASSIGN, QUAD_EPSILON, QUAD_HI, QUAD_TO_DBL, r, SCIP_Row::rhs, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPepsilon(), SCIPfloor(), SCIPgetLPRows(), SCIPgetNLPRows(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIPquadprecDivDQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_Row::vals, and varVecAddScaledRowCoefsQuad().
Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().
◆ computeMIREfficacy()
|
static |
compute the efficacy of the MIR cut for the given values without computing the cut. This is used for the CMIR cut generation heuristic.
- Parameters
-
scip SCIP datastructure coefs array with coefficients in row solvals solution values of variables in the row rhs right hand side of MIR cut contactivity aggregated activity of continuous variables in the row contsqrnorm squared norm of continuous variables delta delta value to compute the violation for nvars number of variables in the row, i.e. the size of coefs and solvals arrays minfrac minimal fractionality of rhs to produce MIR cut for maxfrac maximal fractionality of rhs to produce MIR cut for
Definition at line 4196 of file cuts.c.
References MAX, MAXCMIRSCALE, SCIP_Real, SCIPepsilon(), SCIPfloor(), and SCIPisFeasZero().
Referenced by SCIPcutGenerationHeuristicCMIR().
◆ getClosestVlb()
|
static |
get solution value and index of variable lower bound (with binary variable) which is closest to the current LP solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the given variable
- Parameters
-
scip SCIP data structure var given active problem variable sol solution to use for variable bound; NULL for LP solution rowcoefs (dense) array of coefficients of row binvarused array that stores if a binary variable was already used (+1) was not used (0) or was not used but is contained in the row (-1) bestsub closest simple upper bound of given variable rowcoef coefficient of given variable in current row closestvlb pointer to store the LP sol value of the closest variable lower bound closestvlbidx pointer to store the index of the closest vlb; -1 if no vlb was found
Definition at line 5036 of file cuts.c.
References EPSZ, MAXABSVBCOEF, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_OKAY, SCIP_Real, SCIPgetNBinVars(), SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPvarGetNVlbs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), and SCIPvarIsBinary().
Referenced by determineBoundForSNF().
◆ getClosestVub()
|
static |
get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the given variable
- Parameters
-
scip SCIP data structure var given active problem variable sol solution to use for variable bound; NULL for LP solution rowcoefs (dense) array of coefficients of row binvarused array that stores if a binary variable was already used (+1) was not used (0) or was not used but is contained in the row (-1) bestslb closest simple lower bound of given variable rowcoef coefficient of given variable in current row closestvub pointer to store the LP sol value of the closest variable upper bound closestvubidx pointer to store the index of the closest vub; -1 if no vub was found
Definition at line 5166 of file cuts.c.
References EPSZ, MAXABSVBCOEF, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_OKAY, SCIP_Real, SCIPgetNBinVars(), SCIPgetSolVal(), SCIPinfinity(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), and SCIPvarIsBinary().
Referenced by determineBoundForSNF().
◆ determineBoundForSNF()
|
static |
determines the bounds to use for constructing the single-node-flow relaxation of a variable in the given row.
- Parameters
-
scip SCIP data structure sol solution to use for variable bound; NULL for LP solution vars array of problem variables rowcoefs (dense) array of variable coefficients in the row rowinds array with positions of non-zero values in the rowcoefs array varposinrow position of variable in the rowinds array for which the bounds should be determined binvarused array that stores if a binary variable was already used (+1) was not used (0) or was not used but is contained in the row (-1) allowlocal should local information allowed to be used, resulting in a local cut? boundswitch fraction of domain up to which lower bound is used in transformation bestlb pointer to store best lower bound for transformation bestub pointer to store best upper bound for transformation bestslb pointer to store best simple lower bound for transformation bestsub pointer to store best simple upper bound for transformation bestlbtype pointer to store type of best lower bound bestubtype pointer to store type of best upper bound bestslbtype pointer to store type of best simple lower bound bestsubtype pointer to store type of best simple upper bound selectedbounds pointer to store the preferred bound for the transformation freevariable pointer to store if variable is a free variable
Definition at line 5294 of file cuts.c.
References EPSZ, FALSE, findBestLb(), findBestUb(), getClosestVlb(), getClosestVub(), MAXBOUND, QUAD, QUAD_ARRAY_LOAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPdebugMsg, SCIPgetSolVal(), SCIPinfinity(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPvarGetName(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbVars(), SCIPvarGetVubVars(), and TRUE.
Referenced by constructSNFRelaxation().
◆ constructSNFRelaxation()
|
static |
construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set corresponding to the given aggrrow a * x <= rhs
- Parameters
-
scip SCIP data structure sol the solution that should be separated, or NULL for LP solution boundswitch fraction of domain up to which lower bound is used in transformation allowlocal should local information allowed to be used, resulting in a local cut? rowcoefs array of coefficients of row rowinds array of variables problem indices for non-zero coefficients in row nnz number of non-zeros in row snf stores the sign of the transformed variable in summation success stores whether the transformation was valid localbdsused pointer to store whether local bounds were used in transformation
Definition at line 5475 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, determineBoundForSNF(), EPSZ, FALSE, MAX, SNF_Relaxation::ntransvars, NULL, SNF_Relaxation::origbinvars, SNF_Relaxation::origcontvars, QUAD, QUAD_ARRAY_LOAD, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPdebugMsg, SCIPdebugMsgPrint, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetNBinVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumDD, SCIPquadprecSumQQ, SCIPsortDownInt(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transcontvarsolvals, SNF_Relaxation::transrhs, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, and TRUE.
Referenced by SCIPcalcFlowCover().
◆ allocSNFRelaxation()
|
static |
allocate buffer arrays for storing the single-node-flow relaxation
- Parameters
-
scip SCIP data structure snf pointer to snf relaxation to be destroyed nvars number of active problem variables
Definition at line 6036 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, SNF_Relaxation::origbinvars, SNF_Relaxation::origcontvars, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transcontvarsolvals, SNF_Relaxation::transvarcoefs, and SNF_Relaxation::transvarvubcoefs.
Referenced by SCIPcalcFlowCover().
◆ destroySNFRelaxation()
|
static |
free buffer arrays for storing the single-node-flow relaxation
- Parameters
-
scip SCIP data structure snf pointer to snf relaxation to be destroyed
Definition at line 6057 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, SNF_Relaxation::origbinvars, SNF_Relaxation::origcontvars, SCIPfreeBufferArray, SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transcontvarsolvals, SNF_Relaxation::transvarcoefs, and SNF_Relaxation::transvarvubcoefs.
Referenced by SCIPcalcFlowCover().
◆ SCIPsolveKnapsackApproximatelyLT()
|
static |
solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide arrays to store all selected items and all not selected items
- Parameters
-
scip SCIP data structure nitems number of available items weights item weights profits item profits capacity capacity of knapsack items item numbers solitems array to store items in solution, or NULL nonsolitems array to store items not in solution, or NULL nsolitems pointer to store number of items in solution, or NULL nnonsolitems pointer to store number of items not in solution, or NULL solval pointer to store optimal solution value, or NULL
Definition at line 6077 of file cuts.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfeastol(), SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisInfinity(), and SCIPselectWeightedDownRealRealInt().
Referenced by buildFlowCover(), and getFlowCover().
◆ buildFlowCover()
|
static |
build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished flow cover contains variables which have been fixed in advance
- Parameters
-
scip SCIP data structure coefs coefficient of all real variables in N1&N2 vubcoefs coefficient in vub of all real variables in N1&N2 rhs right hand side of 0-1 single node flow constraint solitems items in knapsack nonsolitems items not in knapsack nsolitems number of items in knapsack nnonsolitems number of items not in knapsack nflowcovervars pointer to store number of variables in flow cover nnonflowcovervars pointer to store number of variables not in flow cover flowcoverstatus pointer to store whether variable is in flow cover (+1) or not (-1) lambda pointer to store lambda
Definition at line 6172 of file cuts.c.
References BMSclearMemoryArray, FALSE, getFlowCover(), getIntegralVal(), isIntegralScalar(), LiftingData::lambda, MAXDELTA, MAXDNOM, MAXSCALE, MINDELTA, SNF_Relaxation::ntransvars, NULL, QUAD, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_HI, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisIntegral(), SCIPquadprecSumQD, SCIPrelDiff(), SCIPsolveKnapsackApproximatelyLT(), SCIPsolveKnapsackExactly(), SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transrhs, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, and TRUE.
Referenced by getFlowCover().
◆ getFlowCover()
|
static |
get a flow cover \((C1, C2)\) for a given 0-1 single node flow set \({(x,y) in {0,1}^n x R^n : sum_{j in N1} y_j - sum_{j in N2} y_j <= b, 0 <= y_j <= u_j x_j}\), i.e., get sets \( C1 \subset N1 \) and \( C2 \subset N2 \) with \( \sum_{j in C1} u_j - sum_{j in C2} u_j = b + lambda \) and \( lambda > 0 \)
- Parameters
-
scip SCIP data structure snf the 0-1 single node flow relaxation nflowcovervars pointer to store number of variables in flow cover nnonflowcovervars pointer to store number of variables not in flow cover flowcoverstatus pointer to store whether variable is in flow cover (+1) or not (-1) lambda pointer to store lambda found pointer to store whether a cover was found
Definition at line 6688 of file cuts.c.
References BMSclearMemoryArray, buildFlowCover(), FALSE, SNF_Relaxation::ntransvars, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisIntegral(), SCIPquadprecSumQD, SCIPsolveKnapsackApproximatelyLT(), SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transrhs, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, and TRUE.
Referenced by buildFlowCover(), and SCIPcalcFlowCover().
◆ evaluateLiftingFunction()
|
static |
evaluate the super-additive lifting function for the lifted simple generalized flowcover inequalities for a given value \( x \in \{ u_j \mid j \in C- \} \).
- Parameters
-
scip SCIP data structure liftingdata lifting data to use x value where to evaluate lifting function
Definition at line 6952 of file cuts.c.
References LiftingData::lambda, LiftingData::M, LiftingData::m, MAX, LiftingData::ml, LiftingData::mp, QUAD, QUAD_ASSIGN, QUAD_HI, QUAD_TO_DBL, LiftingData::r, SCIP_Real, SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPquadprecProdDD, SCIPquadprecSumDD, SCIPquadprecSumQD, and LiftingData::t.
Referenced by generateLiftedFlowCoverCut().
◆ getAlphaAndBeta()
|
static |
computes
\[ (\alpha_j, \beta_j) = \begin{cases} (0, 0) &\quad\text{if} M_i \leq u_j \leq M_{i+1} - \lambda \\ (1, M_i - i \lambda) &\quad\text{if} M_i − \lambda < u_j < M_i \\ \end{cases} \]
- Parameters
-
scip SCIP data structure liftingdata pointer to lifting function struct vubcoef vub coefficient to get alpha and beta for alpha get alpha coefficient for lifting beta get beta coefficient for lifting
Definition at line 7034 of file cuts.c.
References LiftingData::lambda, LiftingData::M, QUAD, QUAD_TO_DBL, LiftingData::r, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisSumLE(), SCIPquadprecProdDD, and SCIPquadprecSumQD.
Referenced by generateLiftedFlowCoverCut().
◆ computeLiftingData()
|
static |
compute relevant data for performing the sequence independent lifting
- Parameters
-
scip SCIP data structure snf pointer to SNF relaxation transvarflowcoverstatus pointer to store whether non-binary var is in L2 (2) or not (-1 or 1) lambda lambda liftingdata pointer to lifting function struct valid is the lifting data valid
Definition at line 7071 of file cuts.c.
References LiftingData::d1, LiftingData::d2, FALSE, LiftingData::lambda, LiftingData::M, LiftingData::m, LiftingData::ml, LiftingData::mp, SNF_Relaxation::ntransvars, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, LiftingData::r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_UNUSED, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPinfinity(), SCIPisGT(), SCIPisInfinity(), SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPsortDownReal(), SCIPsortedvecFindDownReal(), LiftingData::t, SNF_Relaxation::transrhs, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, and TRUE.
Referenced by generateLiftedFlowCoverCut().
◆ destroyLiftingData()
|
static |
destroy data used for the sequence independent lifting
- Parameters
-
scip SCIP data structure liftingdata pointer to lifting function struct
Definition at line 7192 of file cuts.c.
References LiftingData::M, LiftingData::m, and SCIPfreeBufferArray.
Referenced by generateLiftedFlowCoverCut().
◆ generateLiftedFlowCoverCut()
|
static |
store the simple lifted flowcover cut defined by the given data in the given arrays the array for storing the cut coefficients must be all zeros
- Parameters
-
scip SCIP data structure snf pointer to SNF relaxation aggrrow aggrrow used to construct SNF relaxation flowcoverstatus pointer to store whether variable is in flow cover (+1) or not (-1) lambda lambda cutcoefs array of coefficients of cut cutrhs pointer to right hand side of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut success was the cut successfully generated
Definition at line 7205 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, computeLiftingData(), SCIP_Row::constant, LiftingData::d1, destroyLiftingData(), evaluateLiftingFunction(), getAlphaAndBeta(), SCIP_Row::integral, LiftingData::lambda, SCIP_Row::lhs, SCIP_AggrRow::nrows, SNF_Relaxation::ntransvars, SNF_Relaxation::origbinvars, SNF_Relaxation::origcontvars, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Row::rhs, SCIP_AggrRow::rowsinds, SCIP_AggrRow::rowweights, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPceil(), SCIPepsilon(), SCIPfloor(), SCIPgetLPRows(), SCIPgetRowMaxActivity(), SCIPgetRowMinActivity(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_AggrRow::slacksign, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, and varVecAddScaledRowCoefs().
Referenced by SCIPcalcFlowCover().
◆ cutsTransformStrongCG()
|
static |
Transform equation \( a \cdot x = b; lb \leq x \leq ub \) into standard form \( a^\prime \cdot x^\prime = b,\; 0 \leq x^\prime \leq ub' \).
Transform variables (lb or ub):
\[ \begin{array}{llll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \mbox{if lb is used in transformation}\\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if ub is used in transformation} \end{array} \]
and move the constant terms \( a_j\, lb_j \) or \( a_j\, ub_j \) to the rhs.
Transform variables (vlb or vub):
\[ \begin{array}{llll} x^\prime_j := x_j - (bl_j\, zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \mbox{if vlb is used in transf.} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if vub is used in transf.} \end{array} \]
move the constant terms \( a_j\, dl_j \) or \( a_j\, du_j \) to the rhs, and update the coefficient of the VLB variable:
\[ \begin{array}{ll} a_{zl_j} := a_{zl_j} + a_j\, bl_j,& \mbox{or} \\ a_{zu_j} := a_{zu_j} + a_j\, bu_j & \end{array} \]
- Parameters
-
scip SCIP data structure sol the solution that should be separated, or NULL for LP solution boundswitch fraction of domain up to which lower bound is used in transformation usevbds should variable bounds be used in bound transformation? allowlocal should local information allowed to be used, resulting in a local cut? cutcoefs array of coefficients of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut varsign stores the sign of the transformed variable in summation boundtype stores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub freevariable stores whether a free variable was found in MIR row -> invalid summation localbdsused pointer to store whether local bounds were used in transformation
Definition at line 7625 of file cuts.c.
References determineBestBounds(), EPSZ, FALSE, findBestLb(), findBestUb(), NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_HI, QUAD_TO_DBL, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPsortDownInt(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), and TRUE.
Referenced by SCIPcalcStrongCG().
◆ cutsRoundStrongCG()
|
static |
Calculate fractionalities \( f_0 := b - down(b) \), \( f_j := a^\prime_j - down(a^\prime_j) \) and integer \( k >= 1 \) with \( 1/(k + 1) <= f_0 < 1/k \) and \( (=> k = up(1/f_0) + 1) \) integer \( 1 <= p_j <= k \) with \( f_0 + ((p_j - 1) * (1 - f_0)/k) < f_j <= f_0 + (p_j * (1 - f_0)/k)\) \( (=> p_j = up( k*(f_j - f_0)/(1 - f_0) )) \) and derive strong CG cut \( \tilde{a}*x^\prime <= down(b) \)
\[ \begin{array}{rll} integers : & \tilde{a}_j = down(a^\prime_j) &, if \qquad f_j <= f_0 \\ & \tilde{a}_j = down(a^\prime_j) + p_j/(k + 1) &, if \qquad f_j > f_0 \\ continuous:& \tilde{a}_j = 0 &, if \qquad a^\prime_j >= 0 \\ & \mbox{no strong CG cut found} &, if \qquad a^\prime_j < 0 \end{array} \]
Transform inequality back to \( \hat{a}*x <= rhs \):
(lb or ub):
\[ \begin{array}{lllll} x^\prime_j := x_j - lb_j,& x_j == x^\prime_j + lb_j,& a^\prime_j == a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation} \\ x^\prime_j := ub_j - x_j,& x_j == ub_j - x^\prime_j,& a^\prime_j == -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation} \end{array} \]
\[ and move the constant terms \begin{array}{rl} -\tilde{a}_j * lb_j == -\hat{a}_j * lb_j, & \mbox{or} \\ \tilde{a}_j * ub_j == -\hat{a}_j * ub_j & \end{array} \]
to the rhs.
(vlb or vub):
\[ \begin{array}{lllll} x^\prime_j := x_j - (bl_j * zl_j + dl_j),& x_j == x^\prime_j + (bl_j * zl_j + dl_j),& a^\prime_j == a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\ x^\prime_j := (bu_j * zu_j + du_j) - x_j,& x_j == (bu_j * zu_j + du_j) - x^\prime_j,& a^\prime_j == -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)} \end{array} \]
move the constant terms
\[ \begin{array}{rl} -\tilde{a}_j * dl_j == -\hat{a}_j * dl_j,& \mbox{or} \\ \tilde{a}_j * du_j == -\hat{a}_j * du_j & \end{array} \]
to the rhs, and update the VB variable coefficients:
\[ \begin{array}{ll} \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j * bl_j == \hat{a}_{zl_j} - \hat{a}_j * bl_j,& \mbox{or} \\ \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j * bu_j == \hat{a}_{zu_j} - \hat{a}_j * bu_j & \end{array} \]
- Parameters
-
scip SCIP data structure cutcoefs array of coefficients of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut varsign stores the sign of the transformed variable in summation boundtype stores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) k factor to strengthen strongcg cut
Definition at line 7913 of file cuts.c.
References BMScopyMemoryArray, EPSZ, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPepsilon(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisLE(), SCIPquadprecDivDD, SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and SCIPvarIsIntegral().
Referenced by SCIPcalcStrongCG().
◆ cutsSubstituteStrongCG()
|
static |
substitute aggregated slack variables:
The coefficient of the slack variable s_r is equal to the row's weight times the slack's sign, because the slack variable only appears in its own row: \( a^\prime_r = scale * weight[r] * slacksign[r] \).
Depending on the slacks type (integral or continuous), its coefficient in the cut calculates as follows:
\[ \begin{array}{rll} integers: & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) &, if \qquad f_r <= f0 \\ & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + p_r/(k + 1) &, if \qquad f_r > f0 \\ continuous:& \hat{a}_r = \tilde{a}_r = 0 &, if \qquad a^\prime_r >= 0 \\ & \mbox{no strong CG cut found} &, if \qquad a^\prime_r < 0 \end{array} \]
Substitute \( \hat{a}_r * s_r \) by adding \( \hat{a}_r \) times the slack's definition to the cut.
- Parameters
-
scip SCIP datastructure weights row weights in row summation slacksign stores the sign of the row's slack variable in summation rowinds sparsity pattern of used rows nrowinds number of used rows scale additional scaling factor multiplied to all rows cutcoefs array of coefficients of cut cutinds array of variables problem indices for non-zero coefficients in cut nnz number of non-zeros in cut k factor to strengthen strongcg cut
Definition at line 8136 of file cuts.c.
References SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, EPSFLOOR, EPSZ, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, NULL, QUAD, QUAD_ASSIGN, QUAD_EPSILON, QUAD_HI, QUAD_TO_DBL, LiftingData::r, SCIP_Row::rhs, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPepsilon(), SCIPfloor(), SCIPgetLPRows(), SCIPgetNLPRows(), SCIPisInfinity(), SCIPisLE(), SCIPisPositive(), SCIPisZero(), SCIPquadprecDivDD, SCIPquadprecDivDQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_Row::vals, and varVecAddScaledRowCoefsQuad().
Referenced by SCIPcalcStrongCG().