Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

methods for nonlinear data

Functions

SCIP_EXPORT void SCIPaddSquareLinearization (SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
 
SCIP_EXPORT void SCIPaddSquareSecant (SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real refpoint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
 
SCIP_EXPORT void SCIPaddBilinLinearization (SCIP *scip, SCIP_Real bilincoef, SCIP_Real refpointx, SCIP_Real refpointy, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
 
SCIP_EXPORT void SCIPaddBilinMcCormick (SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
 
SCIP_EXPORT void SCIPcomputeBilinEnvelope1 (SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
 
SCIP_EXPORT void SCIPcomputeBilinEnvelope2 (SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real alpha1, SCIP_Real beta1, SCIP_Real gamma1, SCIP_Real alpha2, SCIP_Real beta2, SCIP_Real gamma2, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
 
SCIP_EXPORT SCIP_RETCODE SCIPcreateNlpiProb (SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
 
SCIP_EXPORT SCIP_RETCODE SCIPupdateNlpiProb (SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
 
SCIP_EXPORT SCIP_RETCODE SCIPaddNlpiProbRows (SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
 

Function Documentation

◆ SCIPaddSquareLinearization()

SCIP_EXPORT void SCIPaddSquareLinearization ( SCIP scip,
SCIP_Real  sqrcoef,
SCIP_Real  refpoint,
SCIP_Bool  isint,
SCIP_Real lincoef,
SCIP_Real linconstant,
SCIP_Bool success 
)

computes coefficients of linearization of a square term in a reference point

Parameters
scipSCIP data structure
sqrcoefcoefficient of square term
refpointpoint where to linearize
isintwhether corresponding variable is a discrete variable, and thus linearization could be moved
lincoefbuffer to add coefficient of linearization
linconstantbuffer to add constant of linearization
successbuffer to set to FALSE if linearization has failed due to large numbers

Definition at line 53 of file scip_nonlinear.c.

References FALSE, NULL, REALABS, SCIP_Real, SCIPfloor(), SCIPisInfinity(), and SCIPisIntegral().

Referenced by addBilinearTermToCut(), generateCutConvex(), and generateCutNonConvex().

◆ SCIPaddSquareSecant()

SCIP_EXPORT void SCIPaddSquareSecant ( SCIP scip,
SCIP_Real  sqrcoef,
SCIP_Real  lb,
SCIP_Real  ub,
SCIP_Real  refpoint,
SCIP_Real lincoef,
SCIP_Real linconstant,
SCIP_Bool success 
)

computes coefficients of secant of a square term

Parameters
scipSCIP data structure
sqrcoefcoefficient of square term
lblower bound on variable
ubupper bound on variable
refpointpoint for which to compute value of linearization
lincoefbuffer to add coefficient of secant
linconstantbuffer to add constant of secant
successbuffer to set to FALSE if secant has failed due to large numbers or unboundedness

Definition at line 121 of file scip_nonlinear.c.

References FALSE, NULL, REALABS, SCIP_Real, SCIPisGE(), SCIPisInfinity(), and SCIPisLE().

Referenced by addBilinearTermToCut(), and generateCutNonConvex().

◆ SCIPaddBilinLinearization()

SCIP_EXPORT void SCIPaddBilinLinearization ( SCIP scip,
SCIP_Real  bilincoef,
SCIP_Real  refpointx,
SCIP_Real  refpointy,
SCIP_Real lincoefx,
SCIP_Real lincoefy,
SCIP_Real linconstant,
SCIP_Bool success 
)

computes coefficients of linearization of a bilinear term in a reference point

Parameters
scipSCIP data structure
bilincoefcoefficient of bilinear term
refpointxpoint where to linearize first variable
refpointypoint where to linearize second variable
lincoefxbuffer to add coefficient of first variable in linearization
lincoefybuffer to add coefficient of second variable in linearization
linconstantbuffer to add constant of linearization
successbuffer to set to FALSE if linearization has failed due to large numbers

Definition at line 171 of file scip_nonlinear.c.

References FALSE, NULL, REALABS, SCIP_Real, and SCIPisInfinity().

Referenced by generateCutConvex().

◆ SCIPaddBilinMcCormick()

SCIP_EXPORT void SCIPaddBilinMcCormick ( SCIP scip,
SCIP_Real  bilincoef,
SCIP_Real  lbx,
SCIP_Real  ubx,
SCIP_Real  refpointx,
SCIP_Real  lby,
SCIP_Real  uby,
SCIP_Real  refpointy,
SCIP_Bool  overestimate,
SCIP_Real lincoefx,
SCIP_Real lincoefy,
SCIP_Real linconstant,
SCIP_Bool success 
)

computes coefficients of McCormick under- or overestimation of a bilinear term

Parameters
scipSCIP data structure
bilincoefcoefficient of bilinear term
lbxlower bound on first variable
ubxupper bound on first variable
refpointxreference point for first variable
lbylower bound on second variable
ubyupper bound on second variable
refpointyreference point for second variable
overestimatewhether to compute an overestimator instead of an underestimator
lincoefxbuffer to add coefficient of first variable in linearization
lincoefybuffer to add coefficient of second variable in linearization
linconstantbuffer to add constant of linearization
successbuffer to set to FALSE if linearization has failed due to large numbers

Definition at line 218 of file scip_nonlinear.c.

References FALSE, MAX, NULL, REALABS, SCIP_Real, SCIPdebugMsg, SCIPisGE(), SCIPisInfinity(), SCIPisLE(), and SCIPisRelEQ().

Referenced by addBilinearTermToCut(), and generateCutNonConvex().

◆ SCIPcomputeBilinEnvelope1()

SCIP_EXPORT void SCIPcomputeBilinEnvelope1 ( SCIP scip,
SCIP_Real  bilincoef,
SCIP_Real  lbx,
SCIP_Real  ubx,
SCIP_Real  refpointx,
SCIP_Real  lby,
SCIP_Real  uby,
SCIP_Real  refpointy,
SCIP_Bool  overestimate,
SCIP_Real  xcoef,
SCIP_Real  ycoef,
SCIP_Real  constant,
SCIP_Real *RESTRICT  lincoefx,
SCIP_Real *RESTRICT  lincoefy,
SCIP_Real *RESTRICT  linconstant,
SCIP_Bool *RESTRICT  success 
)

computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality involving only the variables of the bilinear term

Note
the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems" by Marco Locatelli
Parameters
scipSCIP data structure
bilincoefcoefficient of bilinear term
lbxlower bound on first variable
ubxupper bound on first variable
refpointxreference point for first variable
lbylower bound on second variable
ubyupper bound on second variable
refpointyreference point for second variable
overestimatewhether to compute an overestimator instead of an underestimator
xcoefx coefficient of linear inequality; must be in {-1,0,1}
ycoefy coefficient of linear inequality
constantconstant of linear inequality
lincoefxbuffer to store coefficient of first variable in linearization
lincoefybuffer to store coefficient of second variable in linearization
linconstantbuffer to store constant of linearization
successbuffer to store whether linearization was successful

Definition at line 427 of file scip_nonlinear.c.

References FALSE, NULL, QUAD, QUAD_SCALE, QUAD_TO_DBL, SCIP_INVALID, SCIP_Real, SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisZero(), SCIPquadprecDivDD, SCIPquadprecDivQQ, SCIPquadprecProdDD, SCIPquadprecProdQD, SCIPquadprecProdQQ, SCIPquadprecSquareQ, SCIPquadprecSumDD, SCIPquadprecSumQD, and SCIPquadprecSumQQ.

Referenced by updateBilinearRelaxation().

◆ SCIPcomputeBilinEnvelope2()

SCIP_EXPORT void SCIPcomputeBilinEnvelope2 ( SCIP scip,
SCIP_Real  bilincoef,
SCIP_Real  lbx,
SCIP_Real  ubx,
SCIP_Real  refpointx,
SCIP_Real  lby,
SCIP_Real  uby,
SCIP_Real  refpointy,
SCIP_Bool  overestimate,
SCIP_Real  xcoef1,
SCIP_Real  ycoef1,
SCIP_Real  constant1,
SCIP_Real  xcoef2,
SCIP_Real  ycoef2,
SCIP_Real  constant2,
SCIP_Real *RESTRICT  lincoefx,
SCIP_Real *RESTRICT  lincoefy,
SCIP_Real *RESTRICT  linconstant,
SCIP_Bool *RESTRICT  success 
)

computes coefficients of linearization of a bilinear term in a reference point when given two linear inequality involving only the variables of the bilinear term

Note
the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems" by Marco Locatelli
Parameters
scipSCIP data structure
bilincoefcoefficient of bilinear term
lbxlower bound on first variable
ubxupper bound on first variable
refpointxreference point for first variable
lbylower bound on second variable
ubyupper bound on second variable
refpointyreference point for second variable
overestimatewhether to compute an overestimator instead of an underestimator
xcoef1x coefficient of linear inequality; must be in {-1,0,1}
ycoef1y coefficient of linear inequality
constant1constant of linear inequality
xcoef2x coefficient of linear inequality; must be in {-1,0,1}
ycoef2y coefficient of linear inequality
constant2constant of linear inequality
lincoefxbuffer to store coefficient of first variable in linearization
lincoefybuffer to store coefficient of second variable in linearization
linconstantbuffer to store constant of linearization
successbuffer to store whether linearization was successful

Definition at line 826 of file scip_nonlinear.c.

References computeBilinEnvelope2(), FALSE, NULL, SCIP_INVALID, SCIP_Real, SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), and SCIPisRelEQ().

Referenced by updateBilinearRelaxation().

◆ SCIPcreateNlpiProb()

SCIP_EXPORT SCIP_RETCODE SCIPcreateNlpiProb ( SCIP scip,
SCIP_NLPI nlpi,
SCIP_NLROW **  nlrows,
int  nnlrows,
SCIP_NLPIPROBLEM nlpiprob,
SCIP_HASHMAP var2idx,
SCIP_HASHMAP nlrow2idx,
SCIP_Real nlscore,
SCIP_Real  cutoffbound,
SCIP_Bool  setobj,
SCIP_Bool  onlyconvex 
)

creates an NLP relaxation and stores it in a given NLPI problem; the function computes for each variable which the number of non-linearly occurrences and stores it in the nlscore array

Note
the first row corresponds always to the cutoff row (even if cutoffbound is SCIPinfinity(scip))
Parameters
scipSCIP data structure
nlpiinterface to NLP solver
nlrowsnonlinear rows
nnlrowstotal number of nonlinear rows
nlpiprobempty nlpi problem
var2idxempty hash map to store mapping between variables and indices in nlpi problem
nlrow2idxempty hash map to store mapping between variables and indices in nlpi problem, can be NULL
nlscorearray to store the score of each nonlinear variable (NULL if not needed)
cutoffboundcutoff bound
setobjshould the objective function be set?
onlyconvexfilter only for convex constraints

Definition at line 959 of file scip_nonlinear.c.

References BMSclearMemoryArray, SCIP_QuadElement::coef, FALSE, SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfreeBufferArray, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPinfinity(), SCIPisInfinity(), SCIPisZero(), SCIPnlpiAddConstraints(), SCIPnlpiAddVars(), SCIPnlpiSetObjective(), SCIPnlrowGetConstant(), SCIPnlrowGetCurvature(), SCIPnlrowGetExprtree(), SCIPnlrowGetLhs(), SCIPnlrowGetLinearCoefs(), SCIPnlrowGetLinearVars(), SCIPnlrowGetName(), SCIPnlrowGetNLinearVars(), SCIPnlrowGetNQuadElems(), SCIPnlrowGetQuadElems(), SCIPnlrowGetQuadVars(), SCIPnlrowGetRhs(), SCIPswapInts(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetObj(), SCIPvarGetUbLocal(), and TRUE.

Referenced by applyNlobbt(), computeInteriorPoint(), createAuxiliaryNonlinearSubproblem(), createNLP(), SCIP_DECL_RELAXEXEC(), and SCIP_DECL_SEPAEXECLP().

◆ SCIPupdateNlpiProb()

SCIP_EXPORT SCIP_RETCODE SCIPupdateNlpiProb ( SCIP scip,
SCIP_NLPI nlpi,
SCIP_NLPIPROBLEM nlpiprob,
SCIP_HASHMAP var2nlpiidx,
SCIP_VAR **  nlpivars,
int  nlpinvars,
SCIP_Real  cutoffbound 
)

updates bounds of each variable and the cutoff row in the nlpiproblem

Parameters
scipSCIP data structure
nlpiinterface to NLP solver
nlpiprobnlpi problem representing the convex NLP relaxation
var2nlpiidxmapping between variables and nlpi indices
nlpivarsarray containing all variables of the nlpi
nlpinvarstotal number of nlpi variables
cutoffboundnew cutoff bound

Definition at line 1290 of file scip_nonlinear.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPinfinity(), SCIPnlpiChgConsSides(), SCIPnlpiChgVarBounds(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by applyNlobbt(), SCIP_DECL_SEPAEXECLP(), and updateAuxiliaryNonlinearSubproblem().

◆ SCIPaddNlpiProbRows()

SCIP_EXPORT SCIP_RETCODE SCIPaddNlpiProbRows ( SCIP scip,
SCIP_NLPI nlpi,
SCIP_NLPIPROBLEM nlpiprob,
SCIP_HASHMAP var2idx,
SCIP_ROW **  rows,
int  nrows 
)

adds linear rows to the NLP relaxation

Parameters
scipSCIP data structure
nlpiinterface to NLP solver
nlpiprobnlpi problem
var2idxempty hash map to store mapping between variables and indices in nlpi problem
rowsrows to add
nrowstotal number of rows to add

Definition at line 1342 of file scip_nonlinear.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetVar(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetNVars(), SCIPhashmapExists(), SCIPhashmapGetImageInt(), SCIPnlpiAddConstraints(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetName(), SCIProwGetNNonz(), SCIProwGetRhs(), and SCIProwGetVals().

Referenced by applyNlobbt(), computeInteriorPoint(), SCIP_DECL_RELAXEXEC(), and SCIP_DECL_SEPAEXECLP().