- Generated by
1.16.1
methods for aggregation of rows
Definition in file cuts.c.
#include "blockmemshell/memory.h"#include "scip/cuts.h"#include "scip/certificate.h"#include "scip/dbldblarith.h"#include "scip/intervalarith.h"#include "scip/lp.h"#include "scip/misc.h"#include "scip/pub_lp.h"#include "scip/pub_lpexact.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_certificate.h"#include "scip/scip_cut.h"#include "scip/scip_exact.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_lpexact.h"#include "scip/struct_scip.h"#include "scip/struct_set.h"#include "scip/struct_certificate.h"#include "scip/type_certificate.h"#include "scip/rational.h"Go to the source code of this file.
Data Structures | |
| struct | MIR_Data |
| struct | LiftingData |
| struct | SNF_Relaxation |
Macros | |
| #define | NONZERO(x) |
| #define | MAXCMIRSCALE 1e+6 |
| #define | NSECTIONS 6 |
| #define | NO_EXACT_KNAPSACK |
| #define | MAXABSVBCOEF 1e+5 |
| #define | MAXBOUND 1e+10 |
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_RETCODE | varVecAddScaledRowCoefsQuadScale (int *RESTRICT inds, SCIP_Real *RESTRICT vals, int *RESTRICT nnz, SCIP_ROW *row,) |
| static SCIP_RETCODE | varVecAddScaledRowCoefsSafely (SCIP *scip, int *inds, SCIP_Real *vals, int *nnz, SCIP_ROW *row, SCIP_Real scale, SCIP_Real *rhschange, SCIP_Bool *success) |
| 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 | calcEfficacyDenseStorage (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz) |
| static SCIP_Real | calcEfficacyDenseStorageQuad (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz) |
| static SCIP_Bool | removeZerosSafely (SCIP *scip, SCIP_Real minval, 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,) |
| static SCIP_Bool | chgQuadCoeffWithBound (SCIP *scip, SCIP_VAR *var, QUAD(SCIP_Real oldcoeff), SCIP_Real newcoeff, SCIP_Bool cutislocal,) |
| static SCIP_Bool | chgCoeffWithBoundSafely (SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal, 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_Real | scaleValSafely (SCIP *scip, SCIP_Real val, SCIP_Real scale, SCIP_Bool cutislocal, SCIP_VAR *var, SCIP_Real *rhschange, SCIP_Bool *success) |
| static SCIP_RETCODE | cutTightenCoefsSafely (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, 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) |
| SCIP_RETCODE | SCIPaggrRowAddRowSafely (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype, SCIP_Bool *success) |
| 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 | SCIPaggrRowClearSafely (SCIP_AGGRROW *aggrrow) |
| 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) |
| static SCIP_RETCODE | addOneRowSafely (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_Bool *rowused, SCIP_Bool *success, SCIP_Bool *lhsused) |
| 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) |
| static SCIP_RETCODE | postprocessCutSafely (SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, 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 | varSection (MIR_DATA *data, int probindex) |
| static SCIP_RETCODE | findBestLbSafely (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype) |
| static SCIP_RETCODE | findBestUbSafely (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype) |
| static SCIP_RETCODE | determineBestBoundsSafely (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real boundswitch, int 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 | findBestLb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, int *bestlbtype) |
| static SCIP_RETCODE | findBestUb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, int *bestubtype) |
| static SCIP_RETCODE | findMIRBestLb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype) |
| static SCIP_RETCODE | findMIRBestUb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestub, SCIP_Real *simplebound, int *bestubtype) |
| static SCIP_RETCODE | determineBestBounds (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, MIR_DATA *data, SCIP_Real boundswitch, int 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 void | doMIRBoundSubstitution (SCIP *scip, MIR_DATA *data, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused) |
| static void | performBoundSubstitutionSafely (SCIP *scip, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused) |
| static void | performBoundSubstitutionSimpleSafely (SCIP *scip, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused) |
| static void | performBoundSubstitution (SCIP *scip, int *cutinds, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *nnz, int varsign, int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused) |
| static void | performBoundSubstitutionSimple (SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int boundtype, SCIP_Real boundval, int probindex, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | cutsTransformMIRSafely (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 *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | cutsTransformMIR (SCIP *scip, MIR_DATA *data, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | cutsRoundMIRSafely (SCIP *scip, SCIP_Real *RESTRICT cutcoefs, SCIP_Real *RESTRICT cutrhs, int *RESTRICT cutinds, int *RESTRICT nnz, int *RESTRICT varsign, int *RESTRICT boundtype, SCIP_INTERVAL f0) |
| static SCIP_RETCODE | cutsRoundMIR (SCIP *scip, MIR_DATA *data, int *RESTRICT varsign, int *RESTRICT boundtype,) |
| static SCIP_RETCODE | cutsSubstituteMIRSafely (SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, SCIP_INTERVAL 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,) |
| static SCIP_RETCODE | calcMIRSafely (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) |
| SCIP_RETCODE | SCIPcalcMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, int vartypeusevbds, 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, int vartypeusevbds, 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 | cutsTransformKnapsackCover (SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *localbdsused, SCIP_Bool *success) |
| static SCIP_Bool | computeInitialKnapsackCover (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, int *cutinds, SCIP_Real cutrhs, int cutnnz, int *varsign, int *coverstatus, int *coverpos, SCIP_Real *covervals, int *coversize,) |
| static void | prepareLiftingData (SCIP *scip, SCIP_Real *cutcoefs, int *cutinds, QUAD(SCIP_Real cutrhs), int *coverpos, int coversize, QUAD(SCIP_Real coverweight), SCIP_Real *covervals, int *coverstatus, QUAD(SCIP_Real *abar), int *cplussize) |
| static SCIP_Real | evaluateLiftingFunctionKnapsack (SCIP *scip, QUAD(SCIP_Real x), QUAD(SCIP_Real abar), SCIP_Real *covervals, int coversize, int cplussize, SCIP_Real *scale) |
| SCIP_RETCODE | SCIPcalcKnapsackCover (SCIP *scip, SCIP_SOL *sol, 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, MIR_DATA *data, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused) |
| static SCIP_RETCODE | cutsRoundStrongCG (SCIP *scip, MIR_DATA *data, 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, int vartypeusevbds, 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 | ) |
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 189 of file cuts.c.
Referenced by cutsRoundMIR(), cutsRoundStrongCG(), doMIRBoundSubstitution(), performBoundSubstitution(), SCIPaggrRowAddCustomCons(), SCIPaggrRowAddObjectiveFunction(), SCIPcalcKnapsackCover(), varVecAddScaledRowCoefs(), varVecAddScaledRowCoefsQuad(), and varVecAddScaledRowCoefsQuadScale().
| #define MAXCMIRSCALE 1e+6 |
maximal scaling (scale/(1-f0)) allowed in c-MIR calculations
Definition at line 4079 of file cuts.c.
Referenced by calcMIRSafely(), computeMIREfficacy(), and SCIPcalcMIR().
| #define NSECTIONS 6 |
Definition at line 4088 of file cuts.c.
Referenced by cutsRoundMIR(), cutsRoundStrongCG(), cutsTransformMIR(), cutsTransformStrongCG(), SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
| #define MAXABSVBCOEF 1e+5 |
| #define MAXBOUND 1e+10 |
maximal value of normal bounds used for snf relaxation
Definition at line 9142 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 195 of file cuts.c.
References assert(), SCIP_Row::cols, i, SCIP_Row::len, NONZERO, NULL, RESTRICT, 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
This is the quad precision version of varVecAddScaledRowCoefs().
| 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 240 of file cuts.c.
References assert(), SCIP_Row::cols, i, SCIP_Row::len, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_HI, RESTRICT, SCIP_OKAY, SCIP_Real, SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIP_Row::vals, and SCIP_Col::var_probindex.
Referenced by addOneRow(), cutsSubstituteStrongCG(), and SCIPaggrRowAddRow().
|
static |
add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
This is the quad precision version of varVecAddScaledRowCoefs() with a quad precision scaling factor.
| 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 for adding given row to variable vector |
Definition at line 287 of file cuts.c.
References assert(), SCIP_Row::cols, i, SCIP_Row::len, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_HI, RESTRICT, SCIP_OKAY, SCIP_Real, SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIP_Row::vals, and SCIP_Col::var_probindex.
Referenced by cutsSubstituteMIR().
|
static |
add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date
In the safe variant, we need to transform all variables (implicitly) to nonnegative variables using their upper/lower bounds. When adding \(\lambda * (c^Tx \le d)\) to \(a^Tx \le b\), this results in:
\begin{align*} m_i & =a_i+\lambda c_i \\ U \cap L & = \emptyset \\ U & = \{ i : x_i \le u_i\} \\ L & = \{ i : x_i \ge l_i\} \\ \sum_{i \in U} \overline{m_i}x_i + \sum_{i \in L}\underline{m_i}x_i & \le b+ \lambda d + \sum_{i \in U, u_i > 0}(\overline{m_i}-\underline{m_i})u_i + \sum_{i \in L, l_i < 0}(\underline{m_i}-\overline{m_i})l_i \end{align*}
This methods sums up the left hand side, and stores the change of the rhs due to the variable bounds in rhschange.
| scip | scip data structure |
| 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 |
| rhschange | change in rhs due to variable conjugation |
| success | was the addition successful? |
Definition at line 352 of file cuts.c.
References assert(), SCIP_Row::cols, FALSE, i, SCIP_Interval::inf, SCIP_Row::len, NULL, REALABS, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPgetNVars(), SCIPinfinity(), SCIPintervalAddScalar(), SCIPintervalGetRoundingMode(), SCIPintervalMulScalar(), SCIPintervalSetBounds(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPisExact(), SCIPisInfinity(), SCIProwGetRowExact(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIP_Interval::sup, SCIP_RowExact::valsinterval, SCIP_Col::var, var, and SCIP_Col::var_probindex.
Referenced by addOneRowSafely(), cutsSubstituteMIRSafely(), and SCIPaggrRowAddRowSafely().
|
static |
calculates the cut efficacy for the given solution
| 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 452 of file cuts.c.
References assert(), FALSE, i, MAX, NULL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), sol, SQR, and vars.
Referenced by SCIPcalcFlowCover(), SCIPcalcKnapsackCover(), and SCIPcalcStrongCG().
calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
| 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 517 of file cuts.c.
References assert(), FALSE, i, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPisZero(), and SQR.
Referenced by SCIPaggrRowCalcEfficacyNorm().
|
static |
calculates the cut efficacy for the given solution; the cut coefs are stored densely
| 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 579 of file cuts.c.
References assert(), FALSE, i, MAX, NULL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), sol, SQR, and vars.
Referenced by calcMIRSafely().
|
static |
calculates the cut efficacy for the given solution; the cut coefs are stored densely and in quad precision
| 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 650 of file cuts.c.
References assert(), FALSE, i, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, SCIP_Real, SCIPerrorMessage, SCIPgetSolVal(), SCIPgetVars(), SCIPisZero(), sol, SQR, and vars.
Referenced by SCIPcalcKnapsackCover(), SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().
|
static |
safely (in the exact solving mode sense) 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, use global bounds.
| scip | SCIP data structure |
| minval | minimal absolute value of coefficients that should not be removed |
| 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 727 of file cuts.c.
References assert(), EPSZ, FALSE, i, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPepsilon(), SCIPgetVars(), SCIPintervalGetRoundingMode(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPisEQ(), SCIPisExact(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and vars.
Referenced by calcMIRSafely(), postprocessCutSafely(), and SCIPaggrRowRemoveZeros().
|
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, use global bounds.
| 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 822 of file cuts.c.
References EPSZ, FALSE, i, 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(), TRUE, and vars.
Referenced by postprocessCutQuad(), SCIPaggrRowRemoveZeros(), SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
|
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, use global bounds.
| 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 915 of file cuts.c.
References EPSZ, FALSE, i, QUAD, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, REALABS, SCIP_Bool, SCIP_Real, SCIPepsilon(), SCIPgetVars(), SCIPisEQ(), SCIPisInfinity(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and vars.
Referenced by postprocessCut(), and SCIPcalcFlowCover().
|
static |
compare absolute values of coefficients in quad precision
Definition at line 1007 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? pointer to adjust right hand side of cut |
Definition at line 1052 of file cuts.c.
References FALSE, QUAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumDD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
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? pointer to adjust right hand side of cut |
Definition at line 1097 of file cuts.c.
References FALSE, QUAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by cutTightenCoefsQuad().
|
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? |
| cutrhs | pointer to adjust right hand side of cut |
Definition at line 1142 of file cuts.c.
References assert(), FALSE, SCIP_Bool, SCIP_Real, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPintervalSubScalar(), SCIPisExact(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by cutTightenCoefsSafely().
|
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;
This is the quad precision version of cutTightenCoefs() below.
| 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 1207 of file cuts.c.
References assert(), chgQuadCoeffWithBound(), EPSISINT, FALSE, i, MAX, MIN, 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(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPquadprecEpsFloorQ, SCIPquadprecFloorQ, SCIPquadprecProdQD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPround(), SCIPsortDownInd(), SCIPsortInt(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and vars.
Referenced by postprocessCutQuad().
|
static |
multiplies a parameter for a variable in a row safely (using variable bounds and increasing the rhs)
| scip | SCIP structure |
| val | the value that should be scaled |
| scale | scaling factor |
| cutislocal | should local or global bounds be used |
| var | the variable that is relevant |
| rhschange | resulting change in rhs of row |
| success | was the operation successful? (false if no bounds) |
Definition at line 1585 of file cuts.c.
References assert(), FALSE, SCIP_Bool, SCIP_Real, SCIPdebugMessage, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPisExact(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by cutTightenCoefsSafely().
|
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;
This is the safe version of cutTightenCoefs() below.
| scip | SCIP data structure |
| cutislocal | is the cut local? |
| 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 |
| redundant | whether the cut was detected to be redundant |
Definition at line 1658 of file cuts.c.
References assert(), chgCoeffWithBoundSafely(), EPSISINT, FALSE, i, MAX, MIN, SCIP_Certificate::mirinfo, SCIP_Certificate::nmirinfos, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_TO_DBL, SCIP_MirInfo::scale, scaleValSafely(), SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPdebugPrintf, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetCertificate(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPinfinity(), SCIPintervalAdd(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPisCertified(), SCIPisExact(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPround(), SCIPsortDownInd(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, SCIP_MirInfo::unroundedrhs, and vars.
Referenced by postprocessCutSafely().
|
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;
| 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 2103 of file cuts.c.
References assert(), chgCoeffWithBound(), EPSISINT, FALSE, i, MAX, MIN, NULL, QUAD, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcalcIntegralScalar(), SCIPdebugMsg, SCIPfeastol(), SCIPfreeBufferArray, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisExact(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPquadprecEpsFloorQ, SCIPquadprecFloorQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPround(), SCIPsortDownInd(), SCIPsortInt(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and vars.
Referenced by postprocessCut().
|
static |
adds one row to the aggregation row
| 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 3257 of file cuts.c.
References assert(), SCIP_Row::constant, FALSE, i, 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, QUAD, 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(), SCIPquadprecProdDD, SCIPquadprecSumQQ, SCIPreallocBlockMemoryArray, SCIProwGetBasisStatus(), SCIProwGetLhs(), SCIProwGetRhs(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIP_AggrRow::slacksign, TRUE, SCIP_AggrRow::vals, and varVecAddScaledRowCoefsQuad().
Referenced by SCIPaggrRowSumRows().
|
static |
adds one row to the aggregation row
| 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 |
| rowused | was the row really added? |
| success | was the row added successfully? |
| lhsused | was the lhs or the rhs of the row used? |
Definition at line 3371 of file cuts.c.
References assert(), SCIP_Row::constant, FALSE, i, 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, QUAD_ASSIGN, QUAD_TO_DBL, 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(), SCIPintervalGetRoundingMode(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPisEQ(), SCIPisExact(), SCIPisFeasZero(), SCIPisInfinity(), SCIPreallocBlockMemoryArray, SCIProwExactGetRowRhs(), SCIProwExactHasFpRelax(), SCIProwGetBasisStatus(), SCIProwGetLhs(), SCIProwGetRhs(), SCIProwGetRowExact(), SCIProwIsLocal(), SCIProwIsModifiable(), SCIP_AggrRow::slacksign, TRUE, SCIP_AggrRow::vals, and varVecAddScaledRowCoefsSafely().
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 successful or cut is redundant |
Definition at line 3753 of file cuts.c.
References assert(), cutTightenCoefs(), FALSE, i, MAX, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, REALABS, removeZeros(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), and SCIPsumepsilon().
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 3822 of file cuts.c.
References assert(), cutTightenCoefsQuad(), FALSE, i, MAX, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_HI, QUAD_TO_DBL, REALABS, removeZerosQuad(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), and SCIPsumepsilon().
Referenced by SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
|
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 |
| cutrhs | right hand side of cut |
| success | pointer to return whether the cleanup was successful or if it is useless |
Definition at line 3888 of file cuts.c.
References assert(), cutTightenCoefsSafely(), FALSE, i, MAX, NULL, REALABS, removeZerosSafely(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfeastol(), SCIPisExact(), and SCIPsumepsilon().
Referenced by calcMIRSafely().
|
static |
Returns the section of a variable.
For now, this is equal to the variable type section of the variable in the problem.
| data | The MIR separation data |
| probindex | Problem index of a variable |
Definition at line 4124 of file cuts.c.
References assert(), MIR_Data::nbinimplvars, MIR_Data::nbinvars, MIR_Data::ncontimplvars, MIR_Data::ncontvars, MIR_Data::nintimplvars, MIR_Data::nintvars, NULL, and MIR_Data::nvars.
Referenced by cutsRoundMIR(), cutsRoundStrongCG(), doMIRBoundSubstitution(), findMIRBestLb(), findMIRBestUb(), SCIPcalcMIR(), SCIPcalcStrongCG(), and SCIPcutGenerationHeuristicCMIR().
|
static |
finds the best lower bound of the variable to use for MIR transformation.
Currently, we use a slightly different function for the exact MIR cuts than for the normal MIR cuts due to differences in how the codes can handle variable bound substitution. This function can only be used with the safe MIR code.
| 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? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
Definition at line 4164 of file cuts.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPgetVarClosestVlb(), SCIPisGE(), SCIPisGT(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbVars(), SCIPvarIsImpliedIntegral(), SCIPvarIsIntegral(), sol, and var.
Referenced by determineBestBoundsSafely().
|
static |
finds the best upper bound of the variable to use for MIR transformation. currently, we use a slightly different function for the exact MIR cuts than for the normal MIR cuts due to differences in how the codes can handle variable bound substitution. This function can only be used with the safe MIR code.
| 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? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
Definition at line 4233 of file cuts.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPgetVarClosestVub(), SCIPisLE(), SCIPisLT(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVubVars(), SCIPvarIsImpliedIntegral(), SCIPvarIsIntegral(), sol, and var.
Referenced by determineBestBoundsSafely().
|
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? (0: no, 1: only binary, 2: all) |
| 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 the best lower bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) |
| bestubtype | pointer to store type of best upper bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) |
| 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 4299 of file cuts.c.
References assert(), findBestLbSafely(), findBestUbSafely(), NULL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsIntegral(), sol, TRUE, and var.
Referenced by cutsTransformMIRSafely().
|
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? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
Definition at line 4498 of file cuts.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPgetVarClosestVlb(), SCIPisGE(), SCIPisGT(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbVars(), SCIPvarIsImpliedIntegral(), sol, and var.
Referenced by cutsTransformKnapsackCover(), 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? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
Definition at line 4561 of file cuts.c.
References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPgetVarClosestVub(), SCIPisLE(), SCIPisLT(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVubVars(), SCIPvarIsImpliedIntegral(), sol, and var.
Referenced by cutsTransformKnapsackCover(), determineBoundForSNF(), and SCIPcutGenerationHeuristicCMIR().
|
static |
finds the best lower bound of the variable to use for MIR transformation. Differs from findBestLB() in that it allows more variable bound substitutions based on the variable sections.
| scip | SCIP data structure |
| var | problem variable |
| sol | the solution that should be separated, or NULL for LP solution |
| data | the MIR data that specifies the variable sections |
| usevbds | should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
Definition at line 4626 of file cuts.c.
References assert(), i, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_REAL_MIN, SCIPgetSolVal(), SCIPisGE(), SCIPisGT(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetProbindex(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarIsActive(), SCIPvarIsBinary(), sol, var, and varSection().
Referenced by cutsTransformStrongCG(), and determineBestBounds().
|
static |
finds the best upper bound of the variable to use for MIR transformation. Differs from findBestUB() in that it allows more variable bound substitutions based on the variable sections.
| scip | SCIP data structure |
| var | problem variable |
| sol | the solution that should be separated, or NULL for LP solution |
| data | the MIR data that specifies the variable sections |
| usevbds | should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
Definition at line 4715 of file cuts.c.
References assert(), i, NULL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_REAL_MAX, SCIPgetSolVal(), SCIPisLE(), SCIPisLT(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), SCIPvarIsBinary(), sol, var, and varSection().
Referenced by cutsTransformStrongCG(), and determineBestBounds().
|
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 |
| data | the MIR data that specifies the variable sections |
| boundswitch | fraction of domain up to which lower bound is used in transformation |
| usevbds | should variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all) |
| 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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
| bestubtype | pointer to store type of best upper bound of variable (-2: local bound, -1: global bound, >= 0 variable bound index) |
| 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 4803 of file cuts.c.
References assert(), findMIRBestLb(), findMIRBestUb(), NULL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsIntegral(), sol, TRUE, and var.
Referenced by cutsTransformMIR(), and cutsTransformStrongCG().
|
static |
Performs bound substitution for a MIR cut
| scip | SCIP datastructure |
| data | the MIR data structure for this 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 |
| boundval | array of best bound to be used for the substitution for each nonzero index |
| probindex | problem index of variable to perform the substitution step for |
| localbdsused | pointer to updated whether a local bound was used for substitution |
Definition at line 5009 of file cuts.c.
References assert(), MIR_Data::cutcoefs, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_HI, SCIP_Bool, SCIP_Real, SCIPgetVars(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), MIR_Data::secindices, MIR_Data::secnnz, MIR_Data::totalnnz, var, and varSection().
Referenced by cutsTransformMIR(), and cutsTransformStrongCG().
|
static |
performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index
| scip | SCIP datastructure |
| cutcoefs | array of cut coefficients |
| cutrhs | pointer to right hand side of the 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 |
| boundval | array of best bound to be used for the substitution for each nonzero index |
| probindex | problem index of variable to perform the substitution step for |
| localbdsused | pointer to updated whether a local bound was used for substitution |
Definition at line 5099 of file cuts.c.
References assert(), SCIP_Bool, SCIP_Real, SCIPABORT, SCIPerrorMessage, SCIPintervalGetRoundingMode(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPisExact(), and SCIPisInfinity().
Referenced by cutsTransformMIRSafely().
|
static |
performs the bound substitution step with the simple bound for the variable with the given problem index
| scip | SCIP datastructure |
| cutcoefs | array of cut coefficients |
| cutrhs | pointer to right hand side of the cut |
| boundtype | stores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub |
| boundval | array of best bound to be used for the substitution for each nonzero index |
| probindex | problem index of variable to perform the substitution step for |
| localbdsused | pointer to updated whether a local bound was used for substitution |
Definition at line 5146 of file cuts.c.
References ABS, assert(), SCIP_Bool, SCIP_Real, SCIPintervalGetRoundingMode(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPisExact(), and SCIPisInfinity().
Referenced by cutsTransformMIRSafely().
|
static |
performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index
| scip | SCIP datastructure |
| cutinds | index array of nonzeros in the cut |
| cutcoefs | array of cut coefficients |
| nnz | pointer to number of nonzeros of the 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 |
| boundval | array of best bound to be used for the substitution for each nonzero index |
| probindex | problem index of variable to perform the substitution step for |
| localbdsused | pointer to updated whether a local bound was used for substitution |
Definition at line 5180 of file cuts.c.
References assert(), NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_HI, SCIP_Bool, SCIP_Real, SCIPgetVars(), SCIPisExact(), SCIPisInfinity(), SCIPquadprecProdQD, SCIPquadprecSumQQ, SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), and var.
Referenced by cutsTransformKnapsackCover().
|
static |
performs the bound substitution step with the simple bound for the variable with the given problem index
| scip | SCIP datastructure |
| cutcoefs | array of cut coefficients |
| boundtype | stores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub |
| boundval | array of best bound to be used for the substitution for each nonzero index |
| probindex | problem index of variable to perform the substitution step for |
| localbdsused | pointer to updated whether a local bound was used for substitution |
Definition at line 5261 of file cuts.c.
References ABS, assert(), QUAD, QUAD_ARRAY_LOAD, SCIP_Bool, SCIP_Real, SCIPisExact(), SCIPisInfinity(), SCIPquadprecProdQD, and SCIPquadprecSumQQ.
Referenced by cutsTransformKnapsackCover().
|
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 |
| 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 |
| 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 5320 of file cuts.c.
References assert(), determineBestBoundsSafely(), FALSE, i, SCIP_MirInfo::localbdused, SCIP_Certificate::mirinfo, SCIP_MirInfo::nlocalvars, SCIP_Certificate::nmirinfos, NULL, nvars, performBoundSubstitutionSafely(), performBoundSubstitutionSimpleSafely(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetCertificate(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPintervalGetRoundingMode(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPisCertified(), SCIPisExact(), SCIPisInfinity(), SCIPsortDownInt(), sol, TRUE, SCIP_MirInfo::upperused, and vars.
Referenced by calcMIRSafely().
|
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 datastructure |
| data | the MIR data structure for this cut |
| 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? |
| 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 |
| 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 5543 of file cuts.c.
References assert(), MIR_Data::cutcoefs, MIR_Data::cutinds, determineBestBounds(), doMIRBoundSubstitution(), EPSFRAC, EPSZ, FALSE, i, MIN, MIR_Data::ncontvars, MIR_Data::ncutinds, NSECTIONS, NULL, MIR_Data::nvars, nvars, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_SCALE, QUAD_TO_DBL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPerrorMessage, SCIPfrac(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPquadprecProdQQ, SCIPquadprecSumDD, SCIPquadprecSumQQ, SCIPsumepsilon(), MIR_Data::secindices, MIR_Data::secnnz, sol, MIR_Data::totalnnz, MIR_Data::usevbds, and MIR_Data::vars.
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 |
| 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 |
| 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) |
| f0 | fractional value of rhs |
Definition at line 5872 of file cuts.c.
References assert(), BMScopyMemoryArray, EPSZ, i, SCIP_Interval::inf, SCIP_MirInfo::localbdused, SCIP_Certificate::mirinfo, SCIP_Certificate::nmirinfos, NULL, QUAD_EPSILON, RESTRICT, SCIP_MirInfo::rhs, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPerrorMessage, SCIPgetCertificate(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPinfinity(), SCIPintervalAddScalar(), SCIPintervalDiv(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalMul(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSetRational(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPintervalSub(), SCIPintervalSubScalar(), SCIPisCertified(), SCIPisExact(), SCIPisInfinity(), SCIPisLE(), SCIPrationalAddProdReal(), SCIPrationalIsEQReal(), SCIPvarGetLbGlobal(), SCIPvarGetLbGlobalExact(), SCIPvarGetLbLocal(), SCIPvarGetLbLocalExact(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbGlobalExact(), SCIPvarGetUbLocal(), SCIPvarGetUbLocalExact(), SCIP_MirInfo::splitcoefficients, SCIP_Interval::sup, SCIP_MirInfo::upperused, var, and vars.
Referenced by calcMIRSafely().
|
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 |
| data | the MIR data structure for this 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) fractional value of rhs |
Definition at line 6710 of file cuts.c.
References assert(), MIR_Data::cutcoefs, MIR_Data::cutinds, EPSZ, i, MIR_Data::isenfint, MIR_Data::isimplint, MIR_Data::ncutinds, NONZERO, NSECTIONS, NULL, nvars, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, RESTRICT, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPepsilon(), SCIPisInfinity(), SCIPisLE(), SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), MIR_Data::secindices, MIR_Data::secnnz, MIR_Data::totalnnz, var, MIR_Data::vars, and varSection().
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 \cdot weight[r] \cdot 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 \leq f_0 \\ & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + (f_r - f_0)/(1 - f_0),& \mbox{if}\qquad f_r > f_0 \\ continuous:& \hat{a}_r = \tilde{a}_r = 0, & \mbox{if}\qquad a^\prime_r \geq 0 \\ & \hat{a}_r = \tilde{a}_r = a^\prime_r/(1 - f_0), & \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 |
| 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 |
| f0 | fractional value of rhs |
Definition at line 6953 of file cuts.c.
References SCIP_Certificate::aggrinfo, assert(), SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, EPSZ, FALSE, i, SCIP_Interval::inf, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, SCIP_Certificate::mirinfo, SCIP_Certificate::naggrinfos, SCIP_Row::name, SCIP_AggregationInfo::negslackweights, SCIP_Certificate::nmirinfos, SCIP_MirInfo::nrounddownslacks, SCIP_MirInfo::nslacks, NULL, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, r, SCIP_Row::rhs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcaptureRow(), SCIPdebugMessage, SCIPepsilon(), SCIPgetCertificate(), SCIPgetLPRows(), SCIPgetNLPRows(), SCIPinfinity(), SCIPintervalAddScalar(), SCIPintervalDiv(), SCIPintervalGetInf(), SCIPintervalGetRoundingMode(), SCIPintervalGetSup(), SCIPintervalMul(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeDownwards(), SCIPintervalSetRoundingModeUpwards(), SCIPintervalSub(), SCIPintervalSubScalar(), SCIPisCertified(), SCIPisExact(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIPrealIsExactlyIntegral(), SCIProwExactGetRowRhs(), SCIProwExactHasFpRelax(), SCIProwGetRowExact(), SCIP_MirInfo::slackcoefficients, SCIP_MirInfo::slackroundeddown, SCIP_MirInfo::slackrows, SCIP_MirInfo::slackscale, SCIP_MirInfo::slacksign, SCIP_MirInfo::slackusedcoef, SCIP_MirInfo::slackweight, SCIP_AggregationInfo::substfactor, SCIP_Interval::sup, TRUE, SCIP_Row::vals, and varVecAddScaledRowCoefsSafely().
Referenced by calcMIRSafely().
|
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 fractional value of rhs |
Definition at line 7477 of file cuts.c.
References assert(), SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, EPSZ, i, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, NULL, QUAD, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_TO_DBL, r, SCIP_Row::rhs, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPgetLPRows(), SCIPgetNLPRows(), SCIPisExact(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIPquadprecDivDQ, SCIPquadprecEpsCeilQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_Row::vals, and varVecAddScaledRowCoefsQuadScale().
Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().
|
static |
calculates an MIR cut out of the weighted sum of LP rows; The weights of modifiable rows are set to 0.0, because these rows cannot participate in an MIR cut.
scip is in one of the following stages:
See SCIP_STAGE for a complete list of all possible solving stages.
| scip | SCIP data structure |
| sol | the solution that should be separated, or NULL for LP solution |
| postprocess | apply a post-processing step to the resulting cut? |
| 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? |
| 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 |
| scale | additional scaling factor multiplied to the aggrrow; must be positive |
| aggrrow | aggrrow to compute MIR cut for |
| cutcoefs | array to store the non-zero coefficients in the cut if its efficacy improves cutefficacy |
| cutrhs | pointer to store the right hand side of the cut if its efficacy improves cutefficacy |
| cutinds | array to store the indices of non-zero coefficients in the cut if its efficacy improves cutefficacy |
| cutnnz | pointer to store the number of non-zeros in the cut if its efficacy improves cutefficacy |
| cutefficacy | pointer to store efficacy of cut, or NULL |
| cutrank | pointer to return rank of generated cut or NULL if it improves cutefficacy |
| cutislocal | pointer to store whether the generated cut is only valid locally if it improves cutefficacy |
| success | pointer to store whether the returned coefficients are a valid MIR cut and it improves cutefficacy |
Definition at line 7637 of file cuts.c.
References assert(), BMScopyMemoryArray, calcEfficacyDenseStorage(), cutsRoundMIRSafely(), cutsSubstituteMIRSafely(), cutsTransformMIRSafely(), FALSE, SCIP_MirInfo::frac, i, SCIP_AggrRow::inds, SCIP_Interval::inf, SCIP_AggrRow::local, MAXCMIRSCALE, SCIP_Certificate::mirinfo, SCIP_Certificate::nmirinfos, SCIP_AggrRow::nnz, SCIP_AggrRow::nrows, NULL, nvars, postprocessCutSafely(), QUAD_TO_DBL, SCIP_AggrRow::rank, REALABS, removeZerosSafely(), SCIP_MirInfo::rhs, SCIP_AggrRow::rowsinds, SCIP_AggrRow::rowweights, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCertificateMirInfo(), SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPgetCertificate(), SCIPgetNVars(), SCIPinfinity(), SCIPintervalGetRoundingMode(), SCIPintervalSet(), SCIPintervalSetRoundingMode(), SCIPintervalSetRoundingModeUpwards(), SCIPintervalSubScalar(), SCIPisCertified(), SCIPisEfficacious(), SCIPisExact(), SCIPisPositive(), SCIPrationalDiffReal(), SCIPrationalSetReal(), SCIPsumepsilon(), SCIP_AggrRow::slacksign, sol, SCIP_Interval::sup, and SCIP_AggrRow::vals.
Referenced by SCIPcalcMIR().
|
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 8257 of file cuts.c.
References assert(), i, MAX, MAXCMIRSCALE, nvars, RESTRICT, SCIP_Real, SCIPepsilon(), SCIPfloor(), SCIPisFeasZero(), and SQR.
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 9190 of file cuts.c.
References assert(), COPYSIGN, EPSZ, i, 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(), SCIPvarIsBinary(), sol, and var.
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 9319 of file cuts.c.
References assert(), COPYSIGN, EPSZ, i, 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(), SCIPvarIsBinary(), sol, and var.
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 (-2: local bound, -1: global bound, >= 0 variable bound index) |
| bestubtype | pointer to store type of best upper bound (-2: local bound, -1: global bound, >= 0 variable bound index) |
| 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 9447 of file cuts.c.
References assert(), EPSZ, FALSE, findBestLb(), findBestUb(), getClosestVlb(), getClosestVub(), MAXBOUND, QUAD, QUAD_ARRAY_LOAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Bool, 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(), sol, TRUE, var, and vars.
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 9627 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, assert(), determineBoundForSNF(), EPSZ, FALSE, i, 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(), sol, SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transcontvarsolvals, SNF_Relaxation::transrhs, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, TRUE, var, and vars.
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 10181 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, nvars, 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
Definition at line 10202 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 10222 of file cuts.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfeastol(), SCIPfreeBufferArray, SCIPisFeasGE(), SCIPisFeasLT(), SCIPisInfinity(), and SCIPselectWeightedDownRealRealInt().
Referenced by 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 10317 of file cuts.c.
References assert(), NULL, QUAD, QUAD_HI, QUAD_TO_DBL, SCIP_Real, and SCIPquadprecSumQD.
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 10833 of file cuts.c.
References assert(), BMSclearMemoryArray, buildFlowCover(), FALSE, MIN, SNF_Relaxation::ntransvars, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Bool, 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 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 11100 of file cuts.c.
References assert(), i, LiftingData::lambda, LiftingData::M, LiftingData::m, MAX, LiftingData::ml, LiftingData::mp, NULL, QUAD, QUAD_ASSIGN, QUAD_HI, QUAD_TO_DBL, LiftingData::r, r, SCIP_Real, SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPquadprecProdDD, SCIPquadprecSumDD, SCIPquadprecSumQD, and x.
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 11184 of file cuts.c.
References alpha, assert(), i, LiftingData::lambda, LiftingData::M, QUAD, QUAD_TO_DBL, LiftingData::r, 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 11221 of file cuts.c.
References assert(), LiftingData::d1, LiftingData::d2, FALSE, i, LiftingData::lambda, LiftingData::M, LiftingData::m, MIN, LiftingData::ml, LiftingData::mp, SNF_Relaxation::ntransvars, NULL, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, LiftingData::r, SCIP_Bool, SCIP_CALL, SCIP_INVALID, 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, TRUE, and valid.
Referenced by generateLiftedFlowCoverCut().
|
static |
destroy data used for the sequence independent lifting
Definition at line 11351 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 11364 of file cuts.c.
References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, alpha, assert(), computeLiftingData(), SCIP_Row::constant, LiftingData::d1, destroyLiftingData(), evaluateLiftingFunction(), getAlphaAndBeta(), i, SCIP_Row::integral, LiftingData::lambda, SCIP_Row::lhs, LiftingData::M, LiftingData::m, MIN, LiftingData::mp, SCIP_AggrRow::nrows, SNF_Relaxation::ntransvars, NULL, SNF_Relaxation::origbinvars, SNF_Relaxation::origcontvars, QUAD, QUAD_ASSIGN, QUAD_TO_DBL, LiftingData::r, SCIP_Row::rhs, SCIP_AggrRow::rowsinds, SCIP_AggrRow::rowweights, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPceil(), SCIPepsilon(), SCIPfloor(), SCIPgetLPRows(), SCIPgetRowMaxActivity(), SCIPgetRowMinActivity(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPquadprecSumDD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_AggrRow::slacksign, LiftingData::t, SNF_Relaxation::transvarcoefs, SNF_Relaxation::transvarvubcoefs, and varVecAddScaledRowCoefs().
Referenced by SCIPcalcFlowCover().
|
static |
Relax the row to a possibly fractional knapsack row containing no integer or continuous variables and only having positive coefficients for binary variables. General integer and continuous variables are complemented with variable or simple bounds such that their coefficient becomes positive and then it is relaxed to zero. All remaining binary variables are complemented with simple upper or lower bounds such that their coefficient becomes positive.
| scip | SCIP data structure |
| sol | the solution that should be separated, or NULL for LP solution |
| 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 |
| localbdsused | pointer to store whether local bounds were used in transformation |
| success | stores whether the row could successfully be transformed into a knapsack constraint. Returns FALSE in case a continuous or general integer variable is unbounded in the required direction. |
Definition at line 11769 of file cuts.c.
References assert(), BMSmoveMemoryArray, EPSZ, FALSE, findBestLb(), findBestUb(), i, NULL, performBoundSubstitution(), performBoundSubstitutionSimple(), QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisZero(), SCIPsortDownInt(), SCIPvarGetType(), SCIPvarIsImpliedIntegral(), sol, TRUE, and vars.
Referenced by SCIPcalcKnapsackCover().
|
static |
determines the initial cover for the given (fractional) knapsack row
| scip | SCIP datastructure |
| sol | the solution that should be separated, or NULL for LP solution |
| 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 |
| cutrhs | pointer to the right hand side of the cut |
| cutnnz | pointer to the number of non-zeros in the cut |
| varsign | sign of coefficients for each nonzero in the row be transformation |
| coverstatus | array to return the coverstatus for each variable in the knapsack row |
| coverpos | position of nonzero in the knapsack row for each variable in the cover |
| covervals | coefficient value of each variable in the cover |
| coversize | pointer to return number of variables in the cover; matches the length of the associated arrays pointer to return the weight of the cover; the weight is the sum of the coefficient values of variables in the cover |
Definition at line 11963 of file cuts.c.
References assert(), FALSE, QUAD, QUAD_ARRAY_LOAD, QUAD_ASSIGN, QUAD_TO_DBL, SCIP_Bool, SCIP_Real, SCIPdebugMsg, SCIPgetSolVal(), SCIPgetVars(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPquadprecSumQQ, SCIPsortDownRealInt(), sol, TRUE, and vars.
Referenced by SCIPcalcKnapsackCover().
|
static |
prepares the data needed to evaluate the lifting function
| scip | SCIP datastructure |
| 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 |
| coverpos | position of nonzero in the knapsack row for each variable in the cover |
| coversize | number of variables in the cover |
| covervals | coefficient value of each variable in the cover; on output stores the running sum of S^-(*) values |
| coverstatus | coverstatus for each variable in the cover. After calling this function variables in C^- will have the value -1, variables in C^+ the value 1, and all variables outside the cover keep the value 0. |
| cplussize | pointer to store the size of C^+ |
Definition at line 12054 of file cuts.c.
References QUAD, QUAD_ARRAY_LOAD, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_TO_DBL, SCIP_Real, SCIPdebugMsg, SCIPfeastol(), SCIPquadprecDivDQ, SCIPquadprecProdQD, SCIPquadprecSumQQ, and SCIPsortDownRealInt().
Referenced by SCIPcalcKnapsackCover().
|
static |
evaluate the lifting function based on the given values
| scip | SCIP datastructure |
| covervals | the running sum of S^-(*) values |
| coversize | the size of the cover |
| cplussize | the size of C^+ |
| scale | pointer to update the scale to integrality when a fractional value is returned |
Definition at line 12170 of file cuts.c.
References ABS, assert(), h, QUAD, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Real, SCIPdebugMsg, SCIPfloor(), SCIPisPositive(), SCIPquadprecProdQQ, SCIPquadprecSumQD, and x.
Referenced by SCIPcalcKnapsackCover().
|
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' \).
Differs from cutsTransformMIR for continuous variables for which the lower bound must be used when in case their coefficient is positive and the upper bound in case their coefficient is negative. This forces all continuous variable to have a positive coefficient in the transformed row.
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 datastructure |
| data | the MIR data structure for this cut |
| 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? |
| 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 12597 of file cuts.c.
References assert(), MIR_Data::cutcoefs, MIR_Data::cutinds, determineBestBounds(), doMIRBoundSubstitution(), EPSZ, FALSE, findMIRBestLb(), findMIRBestUb(), i, MIR_Data::isenfint, MIR_Data::isimplint, MIR_Data::ncutinds, NSECTIONS, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_EPSILON, QUAD_TO_DBL, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SCIPisInfinity(), MIR_Data::secindices, MIR_Data::secnnz, sol, MIR_Data::totalnnz, TRUE, MIR_Data::usevbds, and MIR_Data::vars.
Referenced by SCIPcalcStrongCG().
|
static |
Calculate fractionalities \( f_0 := b - down(b) \), \( f_j := a^\prime_j - down(a^\prime_j) \), integer \( k \geq 1 \) with \( 1/(k + 1) \leq f_0 < 1/k \) \( (\Rightarrow k = up(1/f_0) - 1) \) and integer \( 1 \leq p_j \leq k \) with \( f_0 + ((p_j - 1) \cdot (1 - f_0)/k) < f_j \leq f_0 + (p_j (1 - f_0)/k)\) \( (\Rightarrow p_j = up( k\,(f_j - f_0)/(1 - f_0) )) \) and derive strong CG cut \( \tilde{a} x^\prime \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) + p_j/(k + 1) &, if \qquad f_j > f_0 \\ continuous:& \tilde{a}_j = 0 &, if \qquad a^\prime_j \geq 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 datastructure |
| data | the MIR data structure for this 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 12884 of file cuts.c.
References assert(), MIR_Data::cutcoefs, MIR_Data::cutinds, EPSZ, i, MIR_Data::isenfint, MIR_Data::isimplint, MIR_Data::ncutinds, NONZERO, NSECTIONS, NULL, nvars, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, SCIP_Bool, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPceil(), SCIPepsilon(), SCIPisInfinity(), SCIPisLE(), SCIPquadprecDivDD, SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), MIR_Data::secindices, MIR_Data::secnnz, MIR_Data::totalnnz, var, MIR_Data::vars, and varSection().
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 \cdot weight[r] \cdot slacksign[r] \).
Depending on the slack's 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 \leq f_0 \\ & \hat{a}_r = \tilde{a}_r = down(a^\prime_r) + p_r/(k + 1), & if \qquad f_r > f_0 \\ continuous:& \hat{a}_r = \tilde{a}_r = 0, & if \qquad a^\prime_r \geq 0 \\ & \mbox{no strong CG cut found}, & 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 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 13124 of file cuts.c.
References assert(), SCIP_Row::cols, SCIP_Row::cols_index, SCIP_Row::constant, EPSZ, i, SCIP_Row::integral, SCIP_Row::len, SCIP_Row::lhs, NULL, QUAD, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_TO_DBL, r, SCIP_Row::rhs, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPceil(), SCIPepsilon(), SCIPfloor(), SCIPgetLPRows(), SCIPgetNLPRows(), SCIPisInfinity(), SCIPisLE(), SCIPisPositive(), SCIPisZero(), SCIPquadprecDivDD, SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_Row::vals, and varVecAddScaledRowCoefsQuad().
Referenced by SCIPcalcStrongCG().
1.16.1