SCIP Doxygen Documentation
Loading...
Searching...
No Matches

Detailed Description

methods for aggregation of rows

Author
Jakob Witzig
Leona Gottwald
Marc Pfetsch

Definition in file cuts.c.

#include "blockmemshell/memory.h"
#include "scip/cuts.h"
#include "scip/dbldblarith.h"
#include "scip/lp.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_select.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_var.h"
#include "scip/scip_cut.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_prob.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_var.h"
#include "scip/struct_lp.h"
#include "scip/struct_scip.h"
#include "scip/struct_set.h"

Go to the source code of this file.

Data Structures

struct  LiftingData
struct  SNF_Relaxation

Macros

#define NONZERO(x)
#define MAXCMIRSCALE   1e+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_Real calcEfficacy (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
static SCIP_Real calcEfficacyNormQuad (SCIP *scip, SCIP_Real *vals, int *inds, int nnz)
static SCIP_Real calcEfficacyDenseStorageQuad (SCIP *scip, SCIP_SOL *sol, SCIP_Real *cutcoefs, SCIP_Real cutrhs, int *cutinds, int cutnnz)
static SCIP_Bool removeZerosQuad (SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz)
static SCIP_Bool removeZeros (SCIP *scip, SCIP_Real minval, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz)
static SCIP_DECL_SORTINDCOMP (compareAbsCoefsQuad)
static SCIP_DECL_SORTINDCOMP (compareAbsCoefs)
static SCIP_Bool chgCoeffWithBound (SCIP *scip, SCIP_VAR *var, SCIP_Real oldcoeff, SCIP_Real newcoeff, SCIP_Bool cutislocal,)
static SCIP_Bool chgQuadCoeffWithBound (SCIP *scip, SCIP_VAR *var, QUAD(SCIP_Real oldcoeff), SCIP_Real newcoeff, SCIP_Bool cutislocal,)
static SCIP_RETCODE cutTightenCoefsQuad (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant)
static SCIP_RETCODE cutTightenCoefs (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *cutnnz, SCIP_Bool *redundant)
SCIP_Bool SCIPcutsTightenCoefficients (SCIP *scip, SCIP_Bool cutislocal, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, int *nchgcoefs)
SCIP_RETCODE SCIPaggrRowCreate (SCIP *scip, SCIP_AGGRROW **aggrrow)
void SCIPaggrRowFree (SCIP *scip, SCIP_AGGRROW **aggrrow)
void SCIPaggrRowPrint (SCIP *scip, SCIP_AGGRROW *aggrrow, FILE *file)
SCIP_RETCODE SCIPaggrRowCopy (SCIP *scip, SCIP_AGGRROW **aggrrow, SCIP_AGGRROW *source)
SCIP_RETCODE SCIPaggrRowAddRow (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
void SCIPaggrRowCancelVarWithBound (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_VAR *var, int pos, SCIP_Bool *valid)
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
SCIP_RETCODE SCIPaggrRowAddCustomCons (SCIP *scip, SCIP_AGGRROW *aggrrow, int *inds, SCIP_Real *vals, int len, SCIP_Real rhs, SCIP_Real weight, int rank, SCIP_Bool local)
void SCIPaggrRowClear (SCIP_AGGRROW *aggrrow)
SCIP_Real SCIPaggrRowCalcEfficacyNorm (SCIP *scip, SCIP_AGGRROW *aggrrow)
static SCIP_RETCODE addOneRow (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *rowtoolong)
SCIP_RETCODE SCIPaggrRowSumRows (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real *weights, int *rowinds, int nrowinds, SCIP_Bool sidetypebasis, SCIP_Bool allowlocal, int negslack, int maxaggrlen, SCIP_Bool *valid)
static SCIP_RETCODE postprocessCut (SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, SCIP_Real *cutrhs, SCIP_Bool *success)
static SCIP_RETCODE postprocessCutQuad (SCIP *scip, SCIP_Bool cutislocal, int *cutinds, SCIP_Real *cutcoefs, int *nnz, QUAD(SCIP_Real *cutrhs), SCIP_Bool *success)
void SCIPaggrRowRemoveZeros (SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
int SCIPaggrRowGetNRows (SCIP_AGGRROW *aggrrow)
int * SCIPaggrRowGetRowInds (SCIP_AGGRROW *aggrrow)
SCIP_RealSCIPaggrRowGetRowWeights (SCIP_AGGRROW *aggrrow)
SCIP_Bool SCIPaggrRowHasRowBeenAdded (SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
int * SCIPaggrRowGetInds (SCIP_AGGRROW *aggrrow)
int SCIPaggrRowGetNNz (SCIP_AGGRROW *aggrrow)
int SCIPaggrRowGetRank (SCIP_AGGRROW *aggrrow)
SCIP_Bool SCIPaggrRowIsLocal (SCIP_AGGRROW *aggrrow)
SCIP_Real SCIPaggrRowGetRhs (SCIP_AGGRROW *aggrrow)
static SCIP_RETCODE findBestLb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, int usevbds, SCIP_Bool allowlocal, SCIP_Real *bestlb, SCIP_Real *simplebound, int *bestlbtype)
static SCIP_RETCODE findBestUb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, 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, 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 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 cutsTransformMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
static SCIP_RETCODE cutsRoundMIR (SCIP *scip, SCIP_Real *RESTRICT cutcoefs, QUAD(SCIP_Real *RESTRICT cutrhs), int *RESTRICT cutinds, int *RESTRICT nnz, int *RESTRICT varsign, int *RESTRICT boundtype,)
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,)
SCIP_RETCODE SCIPcalcMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
static SCIP_Real computeMIREfficacy (SCIP *scip, SCIP_Real *RESTRICT coefs, SCIP_Real *RESTRICT solvals, SCIP_Real rhs, SCIP_Real contactivity, SCIP_Real contsqrnorm, SCIP_Real delta, int nvars, SCIP_Real minfrac, SCIP_Real maxfrac)
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
static SCIP_RETCODE getClosestVlb (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *rowcoefs, int8_t *binvarused, SCIP_Real bestsub, SCIP_Real rowcoef, SCIP_Real *closestvlb, int *closestvlbidx)
static SCIP_RETCODE getClosestVub (SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *rowcoefs, int8_t *binvarused, SCIP_Real bestslb, SCIP_Real rowcoef, SCIP_Real *closestvub, int *closestvubidx)
static SCIP_RETCODE determineBoundForSNF (SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars, SCIP_Real *rowcoefs, int *rowinds, int varposinrow, int8_t *binvarused, SCIP_Bool allowlocal, SCIP_Real boundswitch, SCIP_Real *bestlb, SCIP_Real *bestub, SCIP_Real *bestslb, SCIP_Real *bestsub, int *bestlbtype, int *bestubtype, int *bestslbtype, int *bestsubtype, SCIP_BOUNDTYPE *selectedbounds, SCIP_Bool *freevariable)
static SCIP_RETCODE constructSNFRelaxation (SCIP *scip, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_Real *rowcoefs, QUAD(SCIP_Real rowrhs), int *rowinds, int nnz, SNF_RELAXATION *snf, SCIP_Bool *success, SCIP_Bool *localbdsused)
static SCIP_RETCODE allocSNFRelaxation (SCIP *scip, SNF_RELAXATION *snf, int nvars)
static void destroySNFRelaxation (SCIP *scip, SNF_RELAXATION *snf)
static SCIP_RETCODE SCIPsolveKnapsackApproximatelyLT (SCIP *scip, int nitems, SCIP_Real *weights, SCIP_Real *profits, SCIP_Real capacity, int *items, int *solitems, int *nonsolitems, int *nsolitems, int *nnonsolitems, SCIP_Real *solval)
static void buildFlowCover (SCIP *scip, int *coefs, SCIP_Real *vubcoefs, SCIP_Real rhs, int *solitems, int *nonsolitems, int nsolitems, int nnonsolitems, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, QUAD(SCIP_Real *flowcoverweight), SCIP_Real *lambda)
static SCIP_RETCODE getFlowCover (SCIP *scip, SNF_RELAXATION *snf, int *nflowcovervars, int *nnonflowcovervars, int *flowcoverstatus, SCIP_Real *lambda, SCIP_Bool *found)
static SCIP_Real evaluateLiftingFunction (SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real x)
static void getAlphaAndBeta (SCIP *scip, LIFTINGDATA *liftingdata, SCIP_Real vubcoef, int *alpha, SCIP_Real *beta)
static SCIP_RETCODE computeLiftingData (SCIP *scip, SNF_RELAXATION *snf, int *transvarflowcoverstatus, SCIP_Real lambda, LIFTINGDATA *liftingdata, SCIP_Bool *valid)
static void destroyLiftingData (SCIP *scip, LIFTINGDATA *liftingdata)
static SCIP_RETCODE generateLiftedFlowCoverCut (SCIP *scip, SNF_RELAXATION *snf, SCIP_AGGRROW *aggrrow, int *flowcoverstatus, SCIP_Real lambda, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *nnz, SCIP_Bool *success)
SCIP_RETCODE SCIPcalcFlowCover (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
static SCIP_RETCODE 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, SCIP_SOL *sol, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, SCIP_Bool *freevariable, SCIP_Bool *localbdsused)
static SCIP_RETCODE cutsRoundStrongCG (SCIP *scip, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, int *varsign, int *boundtype, QUAD(SCIP_Real f0), SCIP_Real k)
static SCIP_RETCODE cutsSubstituteStrongCG (SCIP *scip, SCIP_Real *weights, int *slacksign, int *rowinds, int nrowinds, SCIP_Real scale, SCIP_Real *cutcoefs, QUAD(SCIP_Real *cutrhs), int *cutinds, int *nnz, QUAD(SCIP_Real f0), SCIP_Real k)
SCIP_RETCODE SCIPcalcStrongCG (SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_Real scale, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)

Macro Definition Documentation

◆ NONZERO

#define NONZERO ( x)
Value:
(COPYSIGN(1e-100, (x)) + (x))
SCIP_VAR ** x
#define COPYSIGN
Definition def.h:257

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 123 of file cuts.c.

Referenced by cutsRoundMIR(), performBoundSubstitution(), SCIPaggrRowAddCustomCons(), SCIPaggrRowAddObjectiveFunction(), SCIPcalcKnapsackCover(), SCIPcalcStrongCG(), varVecAddScaledRowCoefs(), varVecAddScaledRowCoefsQuad(), and varVecAddScaledRowCoefsQuadScale().

◆ MAXCMIRSCALE

#define MAXCMIRSCALE   1e+6

maximal scaling (scale/(1-f0)) allowed in c-MIR calculations

Definition at line 2592 of file cuts.c.

Referenced by computeMIREfficacy(), and SCIPcalcMIR().

◆ NO_EXACT_KNAPSACK

#define NO_EXACT_KNAPSACK

Definition at line 4902 of file cuts.c.

◆ MAXABSVBCOEF

#define MAXABSVBCOEF   1e+5

maximal absolute coefficient in variable bounds used for snf relaxation

Definition at line 4912 of file cuts.c.

◆ MAXBOUND

#define MAXBOUND   1e+10

maximal value of normal bounds used for snf relaxation

Definition at line 4913 of file cuts.c.

Referenced by determineBoundForSNF().

Typedef Documentation

◆ LIFTINGDATA

typedef struct LiftingData LIFTINGDATA

structure that contains all data required to perform the sequence independent lifting

◆ SNF_RELAXATION

structure that contains all the data that defines the single-node-flow relaxation of an aggregation row

Function Documentation

◆ varVecAddScaledRowCoefs()

SCIP_RETCODE varVecAddScaledRowCoefs ( int *RESTRICT inds,
SCIP_Real *RESTRICT vals,
int *RESTRICT nnz,
SCIP_ROW * row,
SCIP_Real scale )
static

add a scaled row to a dense vector indexed over the problem variables and keep the index of non-zeros up-to-date

Parameters
indspointer to array with variable problem indices of non-zeros in variable vector
valsarray with values of variable vector
nnznumber of non-zeros coefficients of variable vector
rowrow coefficients to add to variable vector
scalescale for adding given row to variable vector

Definition at line 129 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().

◆ varVecAddScaledRowCoefsQuad()

SCIP_RETCODE varVecAddScaledRowCoefsQuad ( int *RESTRICT inds,
SCIP_Real *RESTRICT vals,
int *RESTRICT nnz,
SCIP_ROW * row,
SCIP_Real scale )
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().

Parameters
indspointer to array with variable problem indices of non-zeros in variable vector
valsarray with values of variable vector
nnznumber of non-zeros coefficients of variable vector
rowrow coefficients to add to variable vector
scalescale for adding given row to variable vector

Definition at line 174 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().

◆ varVecAddScaledRowCoefsQuadScale()

SCIP_RETCODE varVecAddScaledRowCoefsQuadScale ( int *RESTRICT inds,
SCIP_Real *RESTRICT vals,
int *RESTRICT nnz,
SCIP_ROW * 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

This is the quad precision version of varVecAddScaledRowCoefs() with a quad precision scaling factor.

Parameters
indspointer to array with variable problem indices of non-zeros in variable vector
valsarray with values of variable vector
nnznumber of non-zeros coefficients of variable vector
rowrow coefficients to add to variable vector scale for adding given row to variable vector

Definition at line 221 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().

◆ calcEfficacy()

SCIP_Real calcEfficacy ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real * cutcoefs,
SCIP_Real cutrhs,
int * cutinds,
int cutnnz )
static

calculates the cut efficacy for the given solution

Parameters
scipSCIP data structure
solsolution to calculate the efficacy for (NULL for LP solution)
cutcoefsarray of the non-zero coefficients in the cut
cutrhsthe right hand side of the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe number of non-zeros in the cut

Definition at line 269 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().

◆ calcEfficacyNormQuad()

SCIP_Real calcEfficacyNormQuad ( SCIP * scip,
SCIP_Real * vals,
int * inds,
int nnz )
static

calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter

Parameters
scipSCIP data structure
valsarray of the non-zero coefficients in the vector; this is a quad precision array!
indsarray of the problem indices of variables with a non-zero coefficient in the vector
nnzthe number of non-zeros in the vector

Definition at line 334 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().

◆ calcEfficacyDenseStorageQuad()

SCIP_Real calcEfficacyDenseStorageQuad ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real * cutcoefs,
SCIP_Real cutrhs,
int * cutinds,
int cutnnz )
static

calculates the cut efficacy for the given solution; the cut coefs are stored densely and in quad precision

Parameters
scipSCIP data structure
solsolution to calculate the efficacy for (NULL for LP solution)
cutcoefsarray of the non-zero coefficients in the cut; this is a quad precision array!
cutrhsthe right hand side of the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe number of non-zeros in the cut

Definition at line 396 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().

◆ removeZerosQuad()

SCIP_Bool removeZerosQuad ( SCIP * scip,
SCIP_Real minval,
SCIP_Bool cutislocal,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * cutnnz )
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.

Parameters
scipSCIP data structure
minvalminimal absolute value of coefficients that should not be removed
cutislocalis the cut local?
cutcoefsarray of the non-zero coefficients in the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe number of non-zeros in the cut

Definition at line 471 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().

◆ removeZeros()

SCIP_Bool removeZeros ( SCIP * scip,
SCIP_Real minval,
SCIP_Bool cutislocal,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * cutnnz )
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.

Parameters
scipSCIP data structure
minvalminimal absolute value of coefficients that should not be removed
cutislocalis the cut local?
cutcoefsarray of the non-zero coefficients in the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe number of non-zeros in the cut

Definition at line 564 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().

◆ SCIP_DECL_SORTINDCOMP() [1/2]

SCIP_DECL_SORTINDCOMP ( compareAbsCoefsQuad )
static

compare absolute values of coefficients in quad precision

Definition at line 656 of file cuts.c.

References QUAD, QUAD_ARRAY_LOAD, QUAD_TO_DBL, REALABS, and SCIP_Real.

◆ SCIP_DECL_SORTINDCOMP() [2/2]

SCIP_DECL_SORTINDCOMP ( compareAbsCoefs )
static

compare absolute values of coefficients

Definition at line 680 of file cuts.c.

References REALABS, and SCIP_Real.

◆ chgCoeffWithBound()

SCIP_Bool chgCoeffWithBound ( SCIP * scip,
SCIP_VAR * var,
SCIP_Real oldcoeff,
SCIP_Real newcoeff,
SCIP_Bool cutislocal )
static

change given coefficient to new given value, adjust right hand side using the variables bound; returns TRUE if the right hand side would need to be changed to infinity and FALSE otherwise

Parameters
scipSCIP data structure
varvariable the coefficient belongs to
oldcoeffold coefficient value
newcoeffnew coefficient value
cutislocalis the cut local? pointer to adjust right hand side of cut

Definition at line 701 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().

◆ chgQuadCoeffWithBound()

SCIP_Bool chgQuadCoeffWithBound ( SCIP * scip,
SCIP_VAR * var,
QUAD(SCIP_Real oldcoeff) ,
SCIP_Real newcoeff,
SCIP_Bool cutislocal )
static

change given (quad) coefficient to new given value, adjust right hand side using the variables bound; returns TRUE if the right hand side would need to be changed to infinity and FALSE otherwise

Parameters
scipSCIP data structure
varvariable the coefficient belongs to
newcoeffnew coefficient value
cutislocalis the cut local? pointer to adjust right hand side of cut

Definition at line 746 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().

◆ cutTightenCoefsQuad()

SCIP_RETCODE cutTightenCoefsQuad ( SCIP * scip,
SCIP_Bool cutislocal,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * cutnnz,
SCIP_Bool * redundant )
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.

Parameters
scipSCIP data structure
cutislocalis the cut local?
cutcoefsarray of the non-zero coefficients in the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe number of non-zeros in the cut
redundantwhether the cut was detected to be redundant

Definition at line 793 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(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and vars.

Referenced by postprocessCutQuad().

◆ cutTightenCoefs()

SCIP_RETCODE cutTightenCoefs ( SCIP * scip,
SCIP_Bool cutislocal,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * cutnnz,
SCIP_Bool * redundant )
static

scales the cut and then tightens the coefficients of the given cut based on the maximal activity; see cons_linear.c consdataTightenCoefs() for details; the cut is given in a semi-sparse array;

Parameters
scipSCIP data structure
cutislocalis the cut local?
cutcoefsarray of the non-zero coefficients in the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutnnzthe number of non-zeros in the cut
redundantpointer to return whtether the cut was detected to be redundant

Definition at line 1168 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(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisPositive(), SCIPquadprecEpsFloorQ, SCIPquadprecFloorQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPround(), SCIPsortDownInd(), SCIPsumepsilon(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and vars.

Referenced by postprocessCut().

◆ addOneRow()

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

Adds one row to the aggregation row. Differs from SCIPaggrRowAddRow() by providing some additional parameters required for SCIPaggrRowSumRows()

Parameters
scipSCIP data structure
aggrrowthe aggregation row
rowthe row to add
weightweight of row to add
sidetypebasischoose sidetypes of row (lhs/rhs) based on basis information?
allowlocalshould local rows allowed to be used?
negslackshould negative slack variables allowed to be used? (0: no, 1: only for integral rows, 2: yes)
maxaggrlenmaximal length of aggregation row
rowtoolongis the aggregated row too long

Definition at line 2170 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().

◆ postprocessCut()

SCIP_RETCODE postprocessCut ( SCIP * scip,
SCIP_Bool cutislocal,
int * cutinds,
SCIP_Real * cutcoefs,
int * nnz,
SCIP_Real * cutrhs,
SCIP_Bool * success )
static

checks for cut redundancy and performs activity based coefficient tightening; removes coefficients that are zero with QUAD_EPSILON tolerance and uses variable bounds to remove small coefficients (relative to the maximum absolute coefficient)

Parameters
scipSCIP data structure
cutislocalis the cut a local cut
cutindsvariable problem indices of non-zeros in cut
cutcoefsnon-zeros coefficients of cut
nnznumber non-zeros coefficients of cut
cutrhsright hand side of cut
successpointer to return whether post-processing was succesful or cut is redundant

Definition at line 2343 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().

◆ postprocessCutQuad()

SCIP_RETCODE postprocessCutQuad ( SCIP * scip,
SCIP_Bool cutislocal,
int * cutinds,
SCIP_Real * cutcoefs,
int * nnz,
QUAD(SCIP_Real * cutrhs) ,
SCIP_Bool * success )
static

checks for cut redundancy and performs activity based coefficient tightening; removes coefficients that are zero with QUAD_EPSILON tolerance and uses variable bounds to remove small coefficients (relative to the maximum absolute coefficient). The cutcoefs must be a quad precision array, i.e. allocated with size QUAD_ARRAY_SIZE(nvars) and accessed with QUAD_ARRAY_LOAD and QUAD_ARRAY_STORE macros.

Parameters
scipSCIP data structure
cutislocalis the cut a local cut
cutindsvariable problem indices of non-zeros in cut
cutcoefsnon-zeros coefficients of cut
nnznumber non-zeros coefficients of cut
successpointer to return whether the cleanup was successful or if it is useless

Definition at line 2412 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().

◆ findBestLb()

SCIP_RETCODE findBestLb ( SCIP * scip,
SCIP_VAR * var,
SCIP_SOL * sol,
int usevbds,
SCIP_Bool allowlocal,
SCIP_Real * bestlb,
SCIP_Real * simplebound,
int * bestlbtype )
static

finds the best lower bound of the variable to use for MIR transformation

Parameters
scipSCIP data structure
varproblem variable
solthe solution that should be separated, or NULL for LP solution
usevbdsshould variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all)
allowlocalshould local information allowed to be used, resulting in a local cut?
bestlbpointer to store best bound value
simpleboundpointer to store simple bound value
bestlbtypepointer to store best bound type

Definition at line 2596 of file cuts.c.

References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPgetVarClosestVlb(), SCIPisGE(), SCIPisGT(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetVlbVars(), sol, and var.

Referenced by cutsTransformKnapsackCover(), cutsTransformStrongCG(), determineBestBounds(), determineBoundForSNF(), and SCIPcutGenerationHeuristicCMIR().

◆ findBestUb()

SCIP_RETCODE findBestUb ( SCIP * scip,
SCIP_VAR * var,
SCIP_SOL * sol,
int usevbds,
SCIP_Bool allowlocal,
SCIP_Real * bestub,
SCIP_Real * simplebound,
int * bestubtype )
static

finds the best upper bound of the variable to use for MIR transformation

Parameters
scipSCIP data structure
varproblem variable
solthe solution that should be separated, or NULL for LP solution
usevbdsshould variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all)
allowlocalshould local information allowed to be used, resulting in a local cut?
bestubpointer to store best bound value
simpleboundpointer to store simple bound
bestubtypepointer to store best bound type

Definition at line 2657 of file cuts.c.

References assert(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPgetVarClosestVub(), SCIPisLE(), SCIPisLT(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVubVars(), sol, and var.

Referenced by cutsTransformKnapsackCover(), cutsTransformStrongCG(), determineBestBounds(), determineBoundForSNF(), and SCIPcutGenerationHeuristicCMIR().

◆ determineBestBounds()

SCIP_RETCODE determineBestBounds ( 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

determine the best bounds with respect to the given solution for complementing the given variable

Parameters
scipSCIP data structure
varvariable to determine best bound for
solthe solution that should be separated, or NULL for LP solution
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation? (0: no, 1: only binary, 2: all)
allowlocalshould local information allowed to be used, resulting in a local cut?
fixintegralrhsshould complementation tried to be adjusted such that rhs gets fractional?
ignoresolshould the LP solution be ignored? (eg, apply MIR to dualray)
boundsfortransbounds 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
boundtypesfortranstype of bounds that should be used for transformed variables; NULL for using closest bound for all variables
bestlbpointer to store best lower bound of variable
bestubpointer to store best upper bound of variable
bestlbtypepointer to store type of best lower bound of variable
bestubtypepointer to store type of best upper bound of variable
selectedboundpointer to store whether the lower bound or the upper bound should be preferred
freevariablepointer to store if this is a free variable

Definition at line 2718 of file cuts.c.

References assert(), findBestLb(), findBestUb(), NULL, REALABS, SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPisInfinity(), SCIPisLE(), SCIPisLT(), SCIPisNegative(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetLPSol(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), sol, TRUE, and var.

Referenced by cutsTransformMIR(), and cutsTransformStrongCG().

◆ performBoundSubstitution()

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

performs the bound substitution step with the given variable or simple bounds for the variable with the given problem index

Parameters
scipSCIP datastructure
cutindsindex array of nonzeros in the cut
cutcoefsarray of cut coefficients
nnzpointer to number of nonzeros of the cut
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
boundvalarray of best bound to be used for the substitution for each nonzero index
probindexproblem index of variable to perform the substitution step for
localbdsusedpointer to updated whether a local bound was used for substitution

Definition at line 2917 of file cuts.c.

References assert(), 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(), and var.

Referenced by cutsTransformKnapsackCover(), cutsTransformMIR(), and cutsTransformStrongCG().

◆ performBoundSubstitutionSimple()

void performBoundSubstitutionSimple ( SCIP * scip,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int boundtype,
SCIP_Real boundval,
int probindex,
SCIP_Bool * localbdsused )
static

performs the bound substitution step with the simple bound for the variable with the given problem index

Parameters
scipSCIP datastructure
cutcoefsarray of cut coefficients
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
boundvalarray of best bound to be used for the substitution for each nonzero index
probindexproblem index of variable to perform the substitution step for
localbdsusedpointer to updated whether a local bound was used for substitution

Definition at line 2997 of file cuts.c.

References ABS, assert(), QUAD, QUAD_ARRAY_LOAD, SCIP_Bool, SCIP_Real, SCIPisInfinity(), SCIPquadprecProdQD, and SCIPquadprecSumQQ.

Referenced by cutsTransformKnapsackCover(), cutsTransformMIR(), and cutsTransformStrongCG().

◆ cutsTransformMIR()

SCIP_RETCODE cutsTransformMIR ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real boundswitch,
SCIP_Bool usevbds,
SCIP_Bool allowlocal,
SCIP_Bool fixintegralrhs,
SCIP_Bool ignoresol,
int * boundsfortrans,
SCIP_BOUNDTYPE * boundtypesfortrans,
SCIP_Real minfrac,
SCIP_Real maxfrac,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * nnz,
int * varsign,
int * boundtype,
SCIP_Bool * freevariable,
SCIP_Bool * localbdsused )
static

Transform equation \( a \cdot x = b; lb \leq x \leq ub \) into standard form \( a^\prime \cdot x^\prime = b,\; 0 \leq x^\prime \leq ub' \).

Transform variables (lb or ub):

\[\begin{array}{llll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \mbox{if lb is used in transformation},\\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if ub is used in transformation}, \end{array} \]

and move the constant terms \( a_j\, lb_j \) or \( a_j\, ub_j \) to the rhs.

Transform variables (vlb or vub):

\[\begin{array}{llll} x^\prime_j := x_j - (bl_j\, zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \mbox{if vlb is used in transf.} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \mbox{if vub is used in transf.} \end{array} \]

move the constant terms \( a_j\, dl_j \) or \( a_j\, du_j \) to the rhs, and update the coefficient of the VLB variable:

\[\begin{array}{ll} a_{zl_j} := a_{zl_j} + a_j\, bl_j,& \mbox{or} \\ a_{zu_j} := a_{zu_j} + a_j\, bu_j & \end{array} \]

Parameters
scipSCIP data structure
solthe solution that should be separated, or NULL for LP solution
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
fixintegralrhsshould complementation tried to be adjusted such that rhs gets fractional?
ignoresolshould the LP solution be ignored? (eg, apply MIR to dualray)
boundsfortransbounds 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
boundtypesfortranstype of bounds that should be used for transformed variables; NULL for using closest bound for all variables
minfracminimal fractionality of rhs to produce MIR cut for
maxfracmaximal fractionality of rhs to produce MIR cut for
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
freevariablestores whether a free variable was found in MIR row -> invalid summation
localbdsusedpointer to store whether local bounds were used in transformation

Definition at line 3052 of file cuts.c.

References assert(), determineBestBounds(), EPSFRAC, EPSZ, FALSE, i, NULL, nvars, performBoundSubstitution(), performBoundSubstitutionSimple(), 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, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisGE(), SCIPisGT(), SCIPisInfinity(), SCIPquadprecProdQQ, SCIPquadprecSumDD, SCIPquadprecSumQQ, SCIPsortDownInt(), SCIPsumepsilon(), SCIPvarGetLPSol(), sol, and vars.

Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().

◆ cutsRoundMIR()

SCIP_RETCODE cutsRoundMIR ( SCIP * scip,
SCIP_Real *RESTRICT cutcoefs,
QUAD(SCIP_Real *RESTRICT cutrhs) ,
int *RESTRICT cutinds,
int *RESTRICT nnz,
int *RESTRICT varsign,
int *RESTRICT boundtype )
static

Calculate fractionalities \( f_0 := b - down(b), f_j := a^\prime_j - down(a^\prime_j) \), and derive MIR cut \( \tilde{a} \cdot x' \leq down(b) \)

\[\begin{array}{rll} integers :& \tilde{a}_j = down(a^\prime_j), & if \qquad f_j \leq f_0 \\ & \tilde{a}_j = down(a^\prime_j) + (f_j - f_0)/(1 - f_0),& if \qquad f_j > f_0 \\ continuous:& \tilde{a}_j = 0, & if \qquad a^\prime_j \geq 0 \\ & \tilde{a}_j = a^\prime_j/(1 - f_0), & if \qquad a^\prime_j < 0 \end{array} \]

Transform inequality back to \( \hat{a} \cdot x \leq rhs \):

(lb or ub):

\[\begin{array}{lllll} x^\prime_j := x_j - lb_j,& x_j = x^\prime_j + lb_j,& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{if lb was used in transformation}, \\ x^\prime_j := ub_j - x_j,& x_j = ub_j - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{if ub was used in transformation}, \end{array} \]

and move the constant terms

\[\begin{array}{cl} -\tilde{a}_j \cdot lb_j = -\hat{a}_j \cdot lb_j,& \mbox{or} \\ \tilde{a}_j \cdot ub_j = -\hat{a}_j \cdot ub_j & \end{array} \]

to the rhs.

(vlb or vub):

\[\begin{array}{lllll} x^\prime_j := x_j - (bl_j \cdot zl_j + dl_j),& x_j = x^\prime_j + (bl_j\, zl_j + dl_j),& a^\prime_j = a_j,& \hat{a}_j := \tilde{a}_j,& \mbox{(vlb)} \\ x^\prime_j := (bu_j\, zu_j + du_j) - x_j,& x_j = (bu_j\, zu_j + du_j) - x^\prime_j,& a^\prime_j = -a_j,& \hat{a}_j := -\tilde{a}_j,& \mbox{(vub)} \end{array} \]

move the constant terms

\[\begin{array}{cl} -\tilde{a}_j\, dl_j = -\hat{a}_j\, dl_j,& \mbox{or} \\ \tilde{a}_j\, du_j = -\hat{a}_j\, du_j & \end{array} \]

to the rhs, and update the VB variable coefficients:

\[\begin{array}{ll} \hat{a}_{zl_j} := \hat{a}_{zl_j} - \tilde{a}_j\, bl_j = \hat{a}_{zl_j} - \hat{a}_j\, bl_j,& \mbox{or} \\ \hat{a}_{zu_j} := \hat{a}_{zu_j} + \tilde{a}_j\, bu_j = \hat{a}_{zu_j} - \hat{a}_j\, bu_j & \end{array} \]

Parameters
scipSCIP data structure
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub) fractional value of rhs

Definition at line 3408 of file cuts.c.

References assert(), BMScopyMemoryArray, EPSZ, i, NONZERO, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, RESTRICT, SCIP_OKAY, SCIP_Real, SCIPepsilon(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisLE(), SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsActive(), var, and vars.

Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().

◆ cutsSubstituteMIR()

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

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.

Parameters
scipSCIP data structure
weightsrow weights in row summation
slacksignstores the sign of the row's slack variable in summation
rowindssparsity pattern of used rows
nrowindsnumber of used rows
scaleadditional scaling factor multiplied to all rows
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut fractional value of rhs

Definition at line 3719 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(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIPquadprecDivDQ, SCIPquadprecEpsCeilQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIP_Row::vals, and varVecAddScaledRowCoefsQuadScale().

Referenced by SCIPcalcMIR(), and SCIPcutGenerationHeuristicCMIR().

◆ computeMIREfficacy()

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 )
static

compute the efficacy of the MIR cut for the given values without computing the cut. This is used for the CMIR cut generation heuristic.

Parameters
scipSCIP datastructure
coefsarray with coefficients in row
solvalssolution values of variables in the row
rhsright hand side of MIR cut
contactivityaggregated activity of continuous variables in the row
contsqrnormsquared norm of continuous variables
deltadelta value to compute the violation for
nvarsnumber of variables in the row, i.e. the size of coefs and solvals arrays
minfracminimal fractionality of rhs to produce MIR cut for
maxfracmaximal fractionality of rhs to produce MIR cut for

Definition at line 4130 of file cuts.c.

References assert(), i, MAX, MAXCMIRSCALE, nvars, RESTRICT, SCIP_Real, SCIPepsilon(), SCIPfloor(), SCIPisFeasZero(), and SQR.

Referenced by SCIPcutGenerationHeuristicCMIR().

◆ getClosestVlb()

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

get solution value and index of variable lower bound (with binary variable) which is closest to the current LP solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the given variable

Parameters
scipSCIP data structure
vargiven active problem variable
solsolution to use for variable bound; NULL for LP solution
rowcoefs(dense) array of coefficients of row
binvarusedarray 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)
bestsubclosest simple upper bound of given variable
rowcoefcoefficient of given variable in current row
closestvlbpointer to store the LP sol value of the closest variable lower bound
closestvlbidxpointer to store the index of the closest vlb; -1 if no vlb was found

Definition at line 4961 of file cuts.c.

References assert(), COPYSIGN, EPSZ, i, MAXABSVBCOEF, nbinvars, 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().

◆ getClosestVub()

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

get LP solution value and index of variable upper bound (with binary variable) which is closest to the current LP solution value of a given variable; candidates have to meet certain criteria in order to ensure the nonnegativity of the variable upper bound imposed on the real variable in the 0-1 single node flow relaxation associated with the given variable

Parameters
scipSCIP data structure
vargiven active problem variable
solsolution to use for variable bound; NULL for LP solution
rowcoefs(dense) array of coefficients of row
binvarusedarray 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)
bestslbclosest simple lower bound of given variable
rowcoefcoefficient of given variable in current row
closestvubpointer to store the LP sol value of the closest variable upper bound
closestvubidxpointer to store the index of the closest vub; -1 if no vub was found

Definition at line 5091 of file cuts.c.

References assert(), COPYSIGN, EPSZ, i, MAXABSVBCOEF, nbinvars, 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().

◆ determineBoundForSNF()

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

determines the bounds to use for constructing the single-node-flow relaxation of a variable in the given row.

Parameters
scipSCIP data structure
solsolution to use for variable bound; NULL for LP solution
varsarray of problem variables
rowcoefs(dense) array of variable coefficients in the row
rowindsarray with positions of non-zero values in the rowcoefs array
varposinrowposition of variable in the rowinds array for which the bounds should be determined
binvarusedarray 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)
allowlocalshould local information allowed to be used, resulting in a local cut?
boundswitchfraction of domain up to which lower bound is used in transformation
bestlbpointer to store best lower bound for transformation
bestubpointer to store best upper bound for transformation
bestslbpointer to store best simple lower bound for transformation
bestsubpointer to store best simple upper bound for transformation
bestlbtypepointer to store type of best lower bound
bestubtypepointer to store type of best upper bound
bestslbtypepointer to store type of best simple lower bound
bestsubtypepointer to store type of best simple upper bound
selectedboundspointer to store the preferred bound for the transformation
freevariablepointer to store if variable is a free variable

Definition at line 5219 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().

◆ constructSNFRelaxation()

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

construct a 0-1 single node flow relaxation (with some additional simple constraints) of a mixed integer set corresponding to the given aggrrow a * x <= rhs

Parameters
scipSCIP data structure
solthe solution that should be separated, or NULL for LP solution
boundswitchfraction of domain up to which lower bound is used in transformation
allowlocalshould local information allowed to be used, resulting in a local cut?
rowcoefsarray of coefficients of row
rowindsarray of variables problem indices for non-zero coefficients in row
nnznumber of non-zeros in row
snfstores the sign of the transformed variable in summation
successstores whether the transformation was valid
localbdsusedpointer to store whether local bounds were used in transformation

Definition at line 5400 of file cuts.c.

References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, assert(), determineBoundForSNF(), EPSZ, FALSE, i, MAX, nbinvars, 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().

◆ allocSNFRelaxation()

SCIP_RETCODE allocSNFRelaxation ( SCIP * scip,
SNF_RELAXATION * snf,
int nvars )
static

allocate buffer arrays for storing the single-node-flow relaxation

Parameters
scipSCIP data structure
snfpointer to snf relaxation to be destroyed
nvarsnumber of active problem variables

Definition at line 5953 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().

◆ destroySNFRelaxation()

void destroySNFRelaxation ( SCIP * scip,
SNF_RELAXATION * snf )
static

free buffer arrays for storing the single-node-flow relaxation

Parameters
scipSCIP data structure
snfpointer to snf relaxation to be destroyed

Definition at line 5974 of file cuts.c.

References SNF_Relaxation::aggrcoefsbin, SNF_Relaxation::aggrcoefscont, SNF_Relaxation::aggrconstants, SNF_Relaxation::origbinvars, SNF_Relaxation::origcontvars, SCIPfreeBufferArray, SNF_Relaxation::transbinvarsolvals, SNF_Relaxation::transcontvarsolvals, SNF_Relaxation::transvarcoefs, and SNF_Relaxation::transvarvubcoefs.

Referenced by SCIPcalcFlowCover().

◆ SCIPsolveKnapsackApproximatelyLT()

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

solve knapsack problem in maximization form with "<" constraint approximately by greedy; if needed, one can provide arrays to store all selected items and all not selected items

Parameters
scipSCIP data structure
nitemsnumber of available items
weightsitem weights
profitsitem profits
capacitycapacity of knapsack
itemsitem numbers
solitemsarray to store items in solution, or NULL
nonsolitemsarray to store items not in solution, or NULL
nsolitemspointer to store number of items in solution, or NULL
nnonsolitemspointer to store number of items not in solution, or NULL
solvalpointer to store optimal solution value, or NULL

Definition at line 5994 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().

◆ buildFlowCover()

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

build the flow cover which corresponds to the given exact or approximate solution of KP^SNF; given unfinished flow cover contains variables which have been fixed in advance

Parameters
scipSCIP data structure
coefscoefficient of all real variables in N1&N2
vubcoefscoefficient in vub of all real variables in N1&N2
rhsright hand side of 0-1 single node flow constraint
solitemsitems in knapsack
nonsolitemsitems not in knapsack
nsolitemsnumber of items in knapsack
nnonsolitemsnumber of items not in knapsack
nflowcovervarspointer to store number of variables in flow cover
nnonflowcovervarspointer to store number of variables not in flow cover
flowcoverstatuspointer to store whether variable is in flow cover (+1) or not (-1)
lambdapointer to store lambda

Definition at line 6089 of file cuts.c.

References assert(), NULL, QUAD, QUAD_HI, QUAD_TO_DBL, SCIP_Real, and SCIPquadprecSumQD.

Referenced by getFlowCover().

◆ getFlowCover()

SCIP_RETCODE getFlowCover ( SCIP * scip,
SNF_RELAXATION * snf,
int * nflowcovervars,
int * nnonflowcovervars,
int * flowcoverstatus,
SCIP_Real * lambda,
SCIP_Bool * found )
static

get a flow cover \((C1, C2)\) for a given 0-1 single node flow set \({(x,y) in {0,1}^n x R^n : sum_{j in N1} y_j - sum_{j in N2} y_j <= b, 0 <= y_j <= u_j x_j}\), i.e., get sets \( C1 \subset N1 \) and \( C2 \subset N2 \) with \( \sum_{j in C1} u_j - sum_{j in C2} u_j = b + lambda \) and \( lambda > 0 \)

Parameters
scipSCIP data structure
snfthe 0-1 single node flow relaxation
nflowcovervarspointer to store number of variables in flow cover
nnonflowcovervarspointer to store number of variables not in flow cover
flowcoverstatuspointer to store whether variable is in flow cover (+1) or not (-1)
lambdapointer to store lambda
foundpointer to store whether a cover was found

Definition at line 6605 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().

◆ evaluateLiftingFunction()

SCIP_Real evaluateLiftingFunction ( SCIP * scip,
LIFTINGDATA * liftingdata,
SCIP_Real x )
static

evaluate the super-additive lifting function for the lifted simple generalized flowcover inequalities for a given value \( x \in \{ u_j \mid j \in C- \} \).

Parameters
scipSCIP data structure
liftingdatalifting data to use
xvalue where to evaluate lifting function

Definition at line 6872 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().

◆ getAlphaAndBeta()

void getAlphaAndBeta ( SCIP * scip,
LIFTINGDATA * liftingdata,
SCIP_Real vubcoef,
int * alpha,
SCIP_Real * beta )
static

computes

\[(\alpha_j, \beta_j) = \begin{cases} (0, 0) &\quad\text{if} M_i \leq u_j \leq M_{i+1} - \lambda \\ (1, M_i - i \lambda) &\quad\text{if} M_i − \lambda < u_j < M_i \\ \end{cases} \]

Parameters
scipSCIP data structure
liftingdatapointer to lifting function struct
vubcoefvub coefficient to get alpha and beta for
alphaget alpha coefficient for lifting
betaget beta coefficient for lifting

Definition at line 6956 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().

◆ computeLiftingData()

SCIP_RETCODE computeLiftingData ( SCIP * scip,
SNF_RELAXATION * snf,
int * transvarflowcoverstatus,
SCIP_Real lambda,
LIFTINGDATA * liftingdata,
SCIP_Bool * valid )
static

compute relevant data for performing the sequence independent lifting

Parameters
scipSCIP data structure
snfpointer to SNF relaxation
transvarflowcoverstatuspointer to store whether non-binary var is in L2 (2) or not (-1 or 1)
lambdalambda
liftingdatapointer to lifting function struct
validis the lifting data valid

Definition at line 6993 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().

◆ destroyLiftingData()

void destroyLiftingData ( SCIP * scip,
LIFTINGDATA * liftingdata )
static

destroy data used for the sequence independent lifting

Parameters
scipSCIP data structure
liftingdatapointer to lifting function struct

Definition at line 7123 of file cuts.c.

References LiftingData::M, LiftingData::m, and SCIPfreeBufferArray.

Referenced by generateLiftedFlowCoverCut().

◆ generateLiftedFlowCoverCut()

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 )
static

store the simple lifted flowcover cut defined by the given data in the given arrays the array for storing the cut coefficients must be all zeros

Parameters
scipSCIP data structure
snfpointer to SNF relaxation
aggrrowaggrrow used to construct SNF relaxation
flowcoverstatuspointer to store whether variable is in flow cover (+1) or not (-1)
lambdalambda
cutcoefsarray of coefficients of cut
cutrhspointer to right hand side of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
successwas the cut successfully generated

Definition at line 7136 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().

◆ cutsTransformKnapsackCover()

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

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.

Parameters
scipSCIP data structure
solthe solution that should be separated, or NULL for LP solution
allowlocalshould local information allowed to be used, resulting in a local cut?
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
localbdsusedpointer to store whether local bounds were used in transformation
successstores 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 7541 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, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisZero(), SCIPsortDownInt(), SCIPvarGetType(), sol, TRUE, and vars.

Referenced by SCIPcalcKnapsackCover().

◆ computeInitialKnapsackCover()

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

determines the initial cover for the given (fractional) knapsack row

Parameters
scipSCIP datastructure
solthe solution that should be separated, or NULL for LP solution
cutcoefsarray of the non-zero coefficients in the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
cutrhspointer to the right hand side of the cut
cutnnzpointer to the number of non-zeros in the cut
varsignsign of coefficients for each nonzero in the row be transformation
coverstatusarray to return the coverstatus for each variable in the knapsack row
coverposposition of nonzero in the knapsack row for each variable in the cover
covervalscoefficient value of each variable in the cover
coversizepointer 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 7740 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().

◆ prepareLiftingData()

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

prepares the data needed to evaluate the lifting function

Parameters
scipSCIP datastructure
cutcoefsarray of the non-zero coefficients in the cut
cutindsarray of the problem indices of variables with a non-zero coefficient in the cut
coverposposition of nonzero in the knapsack row for each variable in the cover
coversizenumber of variables in the cover
covervalscoefficient value of each variable in the cover; on output stores the running sum of S^-(*) values
coverstatuscoverstatus 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.
cplussizepointer to store the size of C^+

Definition at line 7831 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().

◆ evaluateLiftingFunctionKnapsack()

SCIP_Real evaluateLiftingFunctionKnapsack ( SCIP * scip,
QUAD(SCIP_Real x) ,
QUAD(SCIP_Real abar) ,
SCIP_Real * covervals,
int coversize,
int cplussize,
SCIP_Real * scale )
static

evaluate the lifting function based on the given values

Parameters
scipSCIP datastructure
covervalsthe running sum of S^-(*) values
coversizethe size of the cover
cplussizethe size of C^+
scalepointer to update the scale to integrality when a fractional value is returned

Definition at line 7947 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().

◆ cutsTransformStrongCG()

SCIP_RETCODE cutsTransformStrongCG ( SCIP * scip,
SCIP_SOL * sol,
SCIP_Real boundswitch,
SCIP_Bool usevbds,
SCIP_Bool allowlocal,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * nnz,
int * varsign,
int * boundtype,
SCIP_Bool * freevariable,
SCIP_Bool * localbdsused )
static

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} \]

Parameters
scipSCIP data structure
solthe solution that should be separated, or NULL for LP solution
boundswitchfraction of domain up to which lower bound is used in transformation
usevbdsshould variable bounds be used in bound transformation?
allowlocalshould local information allowed to be used, resulting in a local cut?
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable: vlb/vub_idx, or -1 for global lb/ub, or -2 for local lb/ub
freevariablestores whether a free variable was found in MIR row -> invalid summation
localbdsusedpointer to store whether local bounds were used in transformation

Definition at line 8374 of file cuts.c.

References assert(), determineBestBounds(), EPSZ, FALSE, findBestLb(), findBestUb(), i, NULL, nvars, performBoundSubstitution(), performBoundSubstitutionSimple(), 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, SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPsortDownInt(), sol, TRUE, and vars.

Referenced by SCIPcalcStrongCG().

◆ cutsRoundStrongCG()

SCIP_RETCODE cutsRoundStrongCG ( SCIP * scip,
SCIP_Real * cutcoefs,
QUAD(SCIP_Real * cutrhs) ,
int * cutinds,
int * nnz,
int * varsign,
int * boundtype,
QUAD(SCIP_Real f0) ,
SCIP_Real k )
static

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} \]

Parameters
scipSCIP data structure
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
varsignstores the sign of the transformed variable in summation
boundtypestores the bound used for transformed variable (vlb/vub_idx or -1 for lb/ub)
kfactor to strengthen strongcg cut

Definition at line 8598 of file cuts.c.

References assert(), BMScopyMemoryArray, bound, EPSZ, i, NULL, QUAD, QUAD_ARRAY_LOAD, QUAD_ARRAY_STORE, QUAD_ASSIGN, QUAD_ASSIGN_Q, QUAD_EPSILON, QUAD_HI, QUAD_SCALE, QUAD_TO_DBL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPceil(), SCIPepsilon(), SCIPgetNContVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisInfinity(), SCIPisLE(), SCIPquadprecDivDD, SCIPquadprecDivDQ, SCIPquadprecEpsFloorQ, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSumQD, SCIPquadprecSumQQ, SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), var, and vars.

Referenced by SCIPcalcStrongCG().

◆ cutsSubstituteStrongCG()

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 )
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.

Parameters
scipSCIP datastructure
weightsrow weights in row summation
slacksignstores the sign of the row's slack variable in summation
rowindssparsity pattern of used rows
nrowindsnumber of used rows
scaleadditional scaling factor multiplied to all rows
cutcoefsarray of coefficients of cut
cutindsarray of variables problem indices for non-zero coefficients in cut
nnznumber of non-zeros in cut
kfactor to strengthen strongcg cut

Definition at line 8809 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().