SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
methods for aggregation of rows
Definition in file cuts.c.
#include "scip/scip.h"#include "scip/cuts.h"#include "scip/misc.h"#include "scip/struct_lp.h"#include "scip/lp.h"#include "scip/struct_cuts.h"#include "scip/cons_knapsack.h"#include "scip/struct_scip.h"#include "scip/dbldblarith.h"Go to the source code of this file.
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 *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 SCIP_RETCODE | findBestLb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, int *bestlbtype) |
| static SCIP_RETCODE | findBestUb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, 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) |
| #define NONZERO | ( | x | ) | (COPYSIGN(1e-100, (x)) + (x)) |
Definition at line 95 of file cuts.c.
Referenced by cutsRoundMIR(), cutsTransformMIR(), cutsTransformStrongCG(), SCIPaggrRowAddCustomCons(), SCIPaggrRowAddObjectiveFunction(), SCIPcalcStrongCG(), varVecAddScaledRowCoefs(), and varVecAddScaledRowCoefsQuad().
| #define MAXCMIRSCALE 1e+6 |
maximal scaling (scale/(1-f0)) allowed in c-MIR calculations
Definition at line 2385 of file cuts.c.
Referenced by computeMIREfficacy(), and SCIPcalcMIR().
| #define MAXABSVBCOEF 1e+5 |
maximal absolute coefficient in variable bounds used for snf relaxation
Definition at line 4602 of file cuts.c.
Referenced by getClosestVlb(), and getClosestVub().
| #define MAXBOUND 1e+10 |
maximal value of normal bounds used for snf relaxation
Definition at line 4603 of file cuts.c.
Referenced by determineBoundForSNF().
| typedef struct LiftingData LIFTINGDATA |
structure that contains all data required to perform the sequence independent lifting
| typedef struct SNF_Relaxation SNF_RELAXATION |
structure that contains all the data that defines the single-node-flow relaxation of an aggregation row
|
static |
add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
| 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 101 of file cuts.c.
References SCIP_Row::cols, SCIP_Row::len, NONZERO, SCIP_OKAY, SCIP_Real, SCIP_Row::vals, and SCIP_Col::var_probindex.
Referenced by generateLiftedFlowCoverCut().
|
static |
add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
| 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 144 of file cuts.c.
References SCIP_Row::cols, SCIP_Row::len, NONZERO, 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().
|
static |
| 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 185 of file cuts.c.
References MAX, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), and SCIPgetVectorEfficacyNorm().
Referenced by SCIPcalcFlowCover(), SCIPcalcMIR(), and SCIPcalcStrongCG().
| 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 214 of file cuts.c.
References FALSE, MAX, QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPisZero(), SCIP_Set::sepa_efficacynorm, and Scip::set.
Referenced by calcEfficacyDenseStorageQuad(), and SCIPaggrRowCalcEfficacyNorm().
|
static |
| 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 277 of file cuts.c.
References calcEfficacyNormQuad(), MAX, QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, SCIP_Real, SCIPgetSolVal(), SCIPgetVars(), and Scip::set.
Referenced by SCIPcutGenerationHeuristicCMIR().
|
static |
safely remove all coefficients below the given value; returns TRUE if the cut became redundant
| 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 312 of file cuts.c.
References EPSZ, FALSE, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPepsilon(), SCIPgetVars(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by postprocessCutQuad(), SCIPaggrRowRemoveZeros(), SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
|
static |
safely remove all coefficients below the given value; returns TRUE if the cut became redundant
| 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 383 of file cuts.c.
References EPSZ, FALSE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPepsilon(), SCIPgetVars(), SCIPisInfinity(), SCIPquadprecSumQD, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by postprocessCut(), and SCIPcalcFlowCover().
|
static |
Definition at line 453 of file cuts.c.
References QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, and SCIP_Real.
|
static |
|
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
| 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 497 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().
|
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
| scip | SCIP data structure |
| var | variable the coefficient belongs to |
| newcoeff | new coefficient value |
| cutislocal | is the cut local? |
Definition at line 539 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().
|
static |
scales the cut and then tighten 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;
| 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 583 of file cuts.c.
References chgQuadCoeffWithBound(), EPSISINT, FALSE, MAX, 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().
|
static |
scales the cut and then tighten 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;
| 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 971 of file cuts.c.
References chgCoeffWithBound(), EPSISINT, FALSE, MAX, 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().
|
static |
Adds one row to the aggregation row. Differs from SCIPaggrRowAddRow() by providing some additional parameters required for SCIPaggrRowSumRows()
| 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 1975 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, 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().
|
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)
| 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 2149 of file cuts.c.
References cutTightenCoefs(), FALSE, MAX, 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().
|
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.
| 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 2214 of file cuts.c.
References cutTightenCoefsQuad(), FALSE, MAX, 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().
|
static |
finds the best lower bound of the variable to use for MIR transformation
| 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 |
| bestlbtype | pointer to store best bound type |
Definition at line 2389 of file cuts.c.
References 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().
|
static |
finds the best upper bound of the variable to use for MIR transformation
| 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 |
| bestubtype | pointer to store best bound type |
Definition at line 2447 of file cuts.c.
References 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().
|
static |
determine the best bounds with respect to the given solution for complementing the given variable
| 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 2505 of file cuts.c.
References findBestLb(), findBestUb(), REALABS, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPgetSolVal(), 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(), and 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} \]
| 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 2720 of file cuts.c.
References determineBestBounds(), EPSFRAC, EPSZ, FALSE, NONZERO, 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().
|
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} \]
| 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 3169 of file cuts.c.
References BMScopyMemoryArray, EPSZ, NONZERO, 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().
|
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.
| 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 3483 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, QUAD, QUAD_ASSIGN, QUAD_EPSILON, QUAD_HI, QUAD_TO_DBL, 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().
|
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.
| 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 3869 of file cuts.c.
References MAX, MAXCMIRSCALE, SCIP_Real, SCIPepsilon(), SCIPfloor(), and SCIPisFeasZero().
Referenced by SCIPcutGenerationHeuristicCMIR().
|
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
| 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 4651 of file cuts.c.
References EPSZ, MAXABSVBCOEF, 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().
|
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
| 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 4782 of file cuts.c.
References EPSZ, MAXABSVBCOEF, 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().
|
static |
determines the bounds to use for constructing the single-node-flow relaxation of a variable in the given row.
| 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 4911 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().
|
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
| 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 5091 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, determineBoundForSNF(), EPSZ, FALSE, MAX, SNF_Relaxation::ntransvars, 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().
|
static |
allocate buffer arrays for storing the single-node-flow relaxation
| scip | SCIP data structure |
| snf | pointer to snf relaxation to be destroyed |
| nvars | number of active problem variables |
Definition at line 5642 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().
|
static |
free buffer arrays for storing the single-node-flow relaxation
| scip | SCIP data structure |
| snf | pointer to snf relaxation to be destroyed |
Definition at line 5663 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().
|
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
| 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 5683 of file cuts.c.
References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfeastol(), SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisInfinity(), and SCIPselectWeightedDownRealRealInt().
Referenced by buildFlowCover(), and getFlowCover().
|
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
| 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 5779 of file cuts.c.
References BMSclearMemoryArray, FALSE, getFlowCover(), isIntegralScalar(), LiftingData::lambda, MAXDNOM, MAXSCALE, SNF_Relaxation::ntransvars, 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().
|
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 \)
| 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 6295 of file cuts.c.
References BMSclearMemoryArray, buildFlowCover(), FALSE, SNF_Relaxation::ntransvars, 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().
|
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- \} \).
| scip | SCIP data structure |
| liftingdata | lifting data to use |
| x | value where to evaluate lifting function |
Definition at line 6559 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().
|
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} \]
| 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 6641 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().
|
static |
compute relevant data for performing the sequence independent lifting
| 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 6678 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().
|
static |
destroy data used for the sequence independent lifting
| scip | SCIP data structure |
| liftingdata | pointer to lifting function struct |
Definition at line 6799 of file cuts.c.
References LiftingData::M, LiftingData::m, and SCIPfreeBufferArray.
Referenced by 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
| 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 6812 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().
|
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} \]
| 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 7232 of file cuts.c.
References determineBestBounds(), EPSZ, FALSE, findBestLb(), findBestUb(), NONZERO, 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().
|
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} \]
| 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 7516 of file cuts.c.
References BMScopyMemoryArray, EPSZ, 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().
|
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.
| 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 7739 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, 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().