Scippy

SCIP

Solving Constraint Integer Programs

cons_bivariate.c File Reference

Detailed Description

constraint handler for bivariate nonlinear constraints $\textrm{lhs} \leq f(x,y) + c z \leq \textrm{rhs}$

Author
Martin Ballerstein
Dennis Michaels
Stefan Vigerske

Definition in file cons_bivariate.c.

#include <assert.h>
#include <math.h>
#include "scip/cons_bivariate.h"
#include "scip/cons_linear.h"
#include "scip/cons_quadratic.h"
#include "scip/cons_nonlinear.h"
#include "scip/heur_subnlp.h"
#include "scip/heur_trysol.h"
#include "scip/debug.h"
#include "nlpi/nlpi.h"
#include "nlpi/exprinterpret.h"

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "bivariate"
 
#define CONSHDLR_DESC   "constraint handler for constraints of the form lhs <= f(x,y) + c*z <= rhs where f(x,y) is a bivariate function"
 
#define CONSHDLR_SEPAPRIORITY   5
 
#define CONSHDLR_ENFOPRIORITY   -55
 
#define CONSHDLR_CHECKPRIORITY   -3600000
 
#define CONSHDLR_SEPAFREQ   1
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define INTERVALINFTY   1E+43
 
#define NEWTONMAXITER   1000
 
#define INITLPMAXVARVAL   1000.0
 
#define QUADCONSUPGD_PRIORITY   5000
 
#define NONLINCONSUPGD_PRIORITY   10000
 
#define infty2infty(infty1, infty2, val)   ((val) >= (infty1) ? (infty2) : (val))
 

Typedefs

typedef struct SepaData_ConvexConcave SEPADATA_CONVEXCONCAVE
 

Functions

static SCIP_DECL_EVENTEXEC (processLinearVarEvent)
 
static SCIP_RETCODE catchLinearVarEvents (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_RETCODE dropLinearVarEvents (SCIP *scip, SCIP_CONS *cons)
 
static SCIP_DECL_EVENTEXEC (processNonlinearVarEvent)
 
static SCIP_DECL_EXPRGRAPHVARADDED (exprgraphVarAdded)
 
static SCIP_DECL_EXPRGRAPHVARREMOVE (exprgraphVarRemove)
 
static SCIP_RETCODE lockLinearVariable (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
 
static SCIP_RETCODE unlockLinearVariable (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef)
 
static SCIP_RETCODE removeFixedVariables (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool *ischanged, SCIP_Bool *isupgraded)
 
static SCIP_RETCODE removeFixedNonlinearVariables (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 
static SCIP_RETCODE computeViolation (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_SOL *sol)
 
static SCIP_RETCODE computeViolations (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_CONS **maxviolcon)
 
static SCIP_RETCODE initSepaDataCreateVred (SCIP *scip, SCIP_EXPRTREE **vred, SCIP_EXPRTREE *f)
 
static SCIP_RETCODE initSepaData (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_CONS *cons)
 
static SCIP_RETCODE freeSepaData (SCIP *scip, SCIP_CONS *cons)
 
static void perturb (SCIP_Real *val, SCIP_Real lb, SCIP_Real ub, SCIP_Real amount)
 
static SCIP_RETCODE solveDerivativeEquation (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real targetvalue, SCIP_Real lb, SCIP_Real ub, SCIP_Real *val, SCIP_Bool *success)
 
static SCIP_RETCODE generateLinearizationCut (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_CONS *cons, SCIP_Real *x0y0, SCIP_Bool newxy, SCIP_ROW **row)
 
static SCIP_RETCODE generateEstimatingHyperplane (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Bool doover, SCIP_Real *x0y0, SCIP_Real *coefx, SCIP_Real *coefy, SCIP_Real *constant, SCIP_Bool *success)
 
static SCIP_RETCODE generateOverestimatingHyperplaneCut (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_CONS *cons, SCIP_Real *x0y0, SCIP_ROW **row)
 
static SCIP_RETCODE generateUnderestimatorParallelYFacets (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real *xyref, SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generateOrthogonal_lx_ly_Underestimator (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real *xyref, SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generateOrthogonal_lx_uy_Underestimator (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real *xyref, SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generateConvexConcaveUnderestimator (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_EXPRTREE *f_yfixed, SCIP_EXPRTREE *vred, SCIP_Real xyref[2], SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generateConvexConcaveEstimator (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_CONS *cons, SCIP_Real xyref[2], SCIP_SIDETYPE violside, SCIP_ROW **row)
 
static SCIP_RETCODE lifting (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real xval, SCIP_Real yval, SCIP_Real xlb, SCIP_Real xub, SCIP_Real ylb, SCIP_Real yub, int min_max, SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generate1ConvexIndefiniteUnderestimatorAtBoundary (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real xyref[2], SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real xyref[2], SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_EXPRTREE *f, SCIP_Real xyref[2], SCIP_Real cutcoeff[4], SCIP_Real *convenvvalue, SCIP_Bool *success)
 
static SCIP_RETCODE generate1ConvexIndefiniteUnderestimator (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_CONS *cons, SCIP_Real *xyref, SCIP_ROW **row)
 
static SCIP_RETCODE generateCut (SCIP *scip, SCIP_EXPRINT *exprinterpreter, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_SIDETYPE violside, SCIP_Real cutmaxrange, SCIP_ROW **row)
 
static SCIP_Bool isConvexLocal (SCIP *scip, SCIP_CONS *cons, SCIP_SIDETYPE side)
 
static SCIP_RETCODE separatePoint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_Real minefficacy, SCIP_Bool inenforcement, SCIP_RESULT *result, SCIP_Real *bestefficacy)
 
static SCIP_DECL_EVENTEXEC (processNewSolutionEvent)
 
static SCIP_RETCODE registerBranchingVariables (SCIP *scip, SCIP_CONS **conss, int nconss, int *nnotify)
 
static SCIP_RETCODE registerLargeLPValueVariableForBranching (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_VAR **brvar)
 
static SCIP_RETCODE enforceViolatedFixedNonlinear (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_Bool *reduceddom, SCIP_Bool *infeasible)
 
static SCIP_RETCODE propagateBoundsTightenVar (SCIP *scip, SCIP_VAR *var, SCIP_INTERVAL bounds, SCIP_CONS *cons, SCIP_RESULT *result, int *nchgbds)
 
static SCIP_RETCODE propagateBoundsCons (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_RESULT *result, int *nchgbds, SCIP_Bool *redundant)
 
static SCIP_RETCODE propagateBounds (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_RESULT *result, int *nchgbds, int *ndelconss)
 
static SCIP_RETCODE proposeFeasibleSolution (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool *success)
 
static SCIP_RETCODE createConsFromQuadTerm (SCIP *scip, SCIP_CONS *srccons, SCIP_CONS **cons, const char *name, SCIP_VAR *x, SCIP_VAR *y, SCIP_VAR *z, SCIP_Real coefxx, SCIP_Real coefx, SCIP_Real coefyy, SCIP_Real coefy, SCIP_Real coefxy, SCIP_Real coefz, SCIP_Real lhs, SCIP_Real rhs)
 
static SCIP_RETCODE createExprtreeFromMonomial (SCIP *scip, SCIP_VAR *x, SCIP_VAR *y, SCIP_Real coef, SCIP_Real p, SCIP_Real q, SCIP_EXPRTREE **exprtree, SCIP_Real *mult, SCIP_BIVAR_CONVEXITY *convextype)
 
static SCIP_RETCODE createConsFromMonomial (SCIP *scip, SCIP_CONS *srccons, SCIP_CONS **cons, const char *name, SCIP_VAR *x, SCIP_VAR *y, SCIP_VAR *z, SCIP_Real coef, SCIP_Real p, SCIP_Real q, SCIP_Real zcoef, SCIP_Real lhs, SCIP_Real rhs)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyBivariate)
 
static SCIP_DECL_CONSFREE (consFreeBivariate)
 
static SCIP_DECL_CONSINIT (consInitBivariate)
 
static SCIP_DECL_CONSEXIT (consExitBivariate)
 
static SCIP_DECL_CONSINITPRE (consInitpreBivariate)
 
static SCIP_DECL_CONSEXITPRE (consExitpreBivariate)
 
static SCIP_DECL_CONSINITSOL (consInitsolBivariate)
 
static SCIP_DECL_CONSEXITSOL (consExitsolBivariate)
 
static SCIP_DECL_CONSDELETE (consDeleteBivariate)
 
static SCIP_DECL_CONSTRANS (consTransBivariate)
 
static SCIP_DECL_CONSINITLP (consInitlpBivariate)
 
static SCIP_DECL_CONSSEPALP (consSepalpBivariate)
 
static SCIP_DECL_CONSSEPASOL (consSepasolBivariate)
 
static SCIP_DECL_CONSENFOLP (consEnfolpBivariate)
 
static SCIP_DECL_CONSENFOPS (consEnfopsBivariate)
 
static SCIP_DECL_CONSCHECK (consCheckBivariate)
 
static SCIP_DECL_CONSPROP (consPropBivariate)
 
static SCIP_DECL_CONSPRESOL (consPresolBivariate)
 
static SCIP_DECL_CONSLOCK (consLockBivariate)
 
static SCIP_DECL_CONSACTIVE (consActiveBivariate)
 
static SCIP_DECL_CONSDEACTIVE (consDeactiveBivariate)
 
static SCIP_DECL_CONSENABLE (consEnableBivariate)
 
static SCIP_DECL_CONSDISABLE (consDisableBivariate)
 
static SCIP_DECL_CONSPRINT (consPrintBivariate)
 
static SCIP_DECL_CONSCOPY (consCopyBivariate)
 
static SCIP_DECL_CONSGETVARS (consGetVarsBivariate)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsBivariate)
 
static SCIP_DECL_QUADCONSUPGD (quadconsUpgdBivariate)
 
static SCIP_DECL_EXPRGRAPHNODEREFORM (exprgraphnodeReformBivariate)
 
SCIP_RETCODE SCIPincludeConshdlrBivariate (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsBivariate (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_EXPRTREE *f, SCIP_BIVAR_CONVEXITY convextype, SCIP_VAR *z, SCIP_Real zcoef, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicBivariate (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_EXPRTREE *f, SCIP_BIVAR_CONVEXITY convextype, SCIP_VAR *z, SCIP_Real zcoef, SCIP_Real lhs, SCIP_Real rhs)
 
SCIP_VARSCIPgetLinearVarBivariate (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetLinearCoefBivariate (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPRTREESCIPgetExprtreeBivariate (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetLhsBivariate (SCIP *scip, SCIP_CONS *cons)
 
SCIP_Real SCIPgetRhsBivariate (SCIP *scip, SCIP_CONS *cons)
 

Macro Definition Documentation

#define CONSHDLR_NAME   "bivariate"
#define CONSHDLR_DESC   "constraint handler for constraints of the form lhs <= f(x,y) + c*z <= rhs where f(x,y) is a bivariate function"

Definition at line 40 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_SEPAPRIORITY   5

priority of the constraint handler for separation

Definition at line 41 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_ENFOPRIORITY   -55

priority of the constraint handler for constraint enforcing

Definition at line 42 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_CHECKPRIORITY   -3600000

priority of the constraint handler for checking feasibility

Definition at line 43 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_SEPAFREQ   1

frequency for separating cuts; zero means to separate only in the root node

Definition at line 44 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 45 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 46 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 49 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_DELAYSEPA   FALSE

should separation method be delayed, if other separators found cuts?

Definition at line 50 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_DELAYPROP   FALSE

should propagation method be delayed, if other propagators found reductions?

Definition at line 51 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_NEEDSCONS   TRUE

should the constraint handler be skipped, if no constraints are available?

Definition at line 52 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST

Definition at line 54 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 55 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define INTERVALINFTY   1E+43

value for infinity in interval operations

Definition at line 57 of file cons_bivariate.c.

Referenced by propagateBounds(), propagateBoundsCons(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_EXPRGRAPHVARADDED().

#define NEWTONMAXITER   1000

maximal number of iterations in newton method

Definition at line 58 of file cons_bivariate.c.

Referenced by solveDerivativeEquation().

#define INITLPMAXVARVAL   1000.0

maximal absolute value of variable for still generating a linearization cut at that point in initlp

Definition at line 59 of file cons_bivariate.c.

Referenced by SCIP_DECL_CONSINITLP().

#define QUADCONSUPGD_PRIORITY   5000

priority of the constraint handler for upgrading of quadratic constraints

Definition at line 61 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define NONLINCONSUPGD_PRIORITY   10000

priority of the constraint handler for upgrading of nonlinear constraints

Definition at line 62 of file cons_bivariate.c.

Referenced by SCIPincludeConshdlrBivariate().

#define infty2infty (   infty1,
  infty2,
  val 
)    ((val) >= (infty1) ? (infty2) : (val))

translate from one value of infinity to another

if val is >= infty1, then give infty2, else give val

Definition at line 147 of file cons_bivariate.c.

Referenced by propagateBoundsCons(), SCIP_DECL_EVENTEXEC(), and SCIP_DECL_EXPRGRAPHVARADDED().

Typedef Documentation

typedef struct SepaData_ConvexConcave SEPADATA_CONVEXCONCAVE

data structure to cache data used for separation of convex-concave constraints

Definition at line 83 of file cons_bivariate.c.

Function Documentation

static SCIP_DECL_EVENTEXEC ( processLinearVarEvent  )
static

processes bound tightening event

Definition at line 151 of file cons_bivariate.c.

References catchLinearVarEvents(), FALSE, NULL, SCIP_Bool, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_OKAY, and SCIPeventGetType().

Referenced by dropLinearVarEvents(), and separatePoint().

static SCIP_RETCODE catchLinearVarEvents ( SCIP scip,
SCIP_CONS cons 
)
static

catches variable bound change events on the linear variable in a bivariate constraint

Parameters
scipSCIP data structure
consconstraint for which to catch bound change events

Definition at line 166 of file cons_bivariate.c.

References dropLinearVarEvents(), FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_DISABLED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconsIsEnabled(), SCIPconsIsTransformed(), and SCIPisInfinity().

Referenced by removeFixedVariables(), SCIP_DECL_CONSENABLE(), and SCIP_DECL_EVENTEXEC().

static SCIP_RETCODE dropLinearVarEvents ( SCIP scip,
SCIP_CONS cons 
)
static

drops variable bound change events on the linear variable in a bivariate constraint

Parameters
scipSCIP data structure
consconstraint for which to catch bound change events

Definition at line 219 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_DECL_EVENTEXEC(), SCIP_EVENTTYPE_DISABLED, SCIP_EVENTTYPE_LBTIGHTENED, SCIP_EVENTTYPE_UBTIGHTENED, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdropVarEvent(), and SCIPisInfinity().

Referenced by catchLinearVarEvents(), removeFixedVariables(), and SCIP_DECL_CONSDISABLE().

static SCIP_DECL_EXPRGRAPHVARREMOVE ( exprgraphVarRemove  )
static

callback method for variable removal in expression graph

Definition at line 356 of file cons_bivariate.c.

References lockLinearVariable(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIPaddVarLocks(), SCIPdebugMessage, SCIPdropVarEvent(), and SCIPvarGetName().

Referenced by SCIP_DECL_EXPRGRAPHVARADDED().

static SCIP_RETCODE lockLinearVariable ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Real  coef 
)
static

locks linear variable in a constraint

Parameters
scipSCIP data structure
consconstraint where to lock a variable
varvariable to lock
coefcoefficient of variable in constraint

Definition at line 382 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPisInfinity(), SCIPlockVarCons(), and unlockLinearVariable().

Referenced by removeFixedVariables(), and SCIP_DECL_EXPRGRAPHVARREMOVE().

static SCIP_RETCODE unlockLinearVariable ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Real  coef 
)
static

unlocks linear variable in a constraint

Parameters
scipSCIP data structure
consconstraint where to unlock a variable
varvariable to unlock
coefcoefficient of variable in constraint

Definition at line 413 of file cons_bivariate.c.

References NULL, removeFixedVariables(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPisInfinity(), and SCIPunlockVarCons().

Referenced by lockLinearVariable(), and removeFixedVariables().

static SCIP_RETCODE removeFixedVariables ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS cons,
SCIP_Bool ischanged,
SCIP_Bool isupgraded 
)
static

resolves variable fixations and aggregations in a constraint

Parameters
scipSCIP data structure
conshdlrconstraint handler
consconstraint where to remove fixed variables
ischangedbuffer to store whether something was changed in the constraint
isupgradedbuffer to store whether the constraint has been upgraded (and deleted)

Definition at line 444 of file cons_bivariate.c.

References catchLinearVarEvents(), dropLinearVarEvents(), FALSE, lockLinearVariable(), NULL, removeFixedNonlinearVariables(), SCIP_CALL, SCIP_EXPR_CONST, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIP_STAGE_EXITPRESOLVE, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPaddCons(), SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsNonlinear(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPexprCreate(), SCIPexprCreateLinear(), SCIPexprFreeDeep(), SCIPexprReindexVars(), SCIPexprtreeCopy(), SCIPexprtreeFree(), SCIPexprtreeGetNVars(), SCIPexprtreeGetRoot(), SCIPexprtreeGetVars(), SCIPexprtreeSetVars(), SCIPexprtreeSubstituteVars(), SCIPgetProbvarSum(), SCIPgetStage(), SCIPisInfinity(), SCIPmarkDoNotMultaggrVar(), SCIPreleaseCons(), SCIPvarGetProbvar(), SCIPvarGetStatus(), SCIPvarIsActive(), TRUE, and unlockLinearVariable().

Referenced by SCIP_DECL_CONSEXITPRE(), SCIP_DECL_CONSPRESOL(), and unlockLinearVariable().

static SCIP_RETCODE removeFixedNonlinearVariables ( SCIP scip,
SCIP_CONSHDLR conshdlr 
)
static
static SCIP_RETCODE computeViolations ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
SCIP_SOL sol,
SCIP_CONS **  maxviolcon 
)
static

computes violation of a set of constraints

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints
nconssnumber of constraints
solsolution or NULL if LP solution should be used
maxviolconbuffer to store constraint with largest violation, or NULL if solution is feasible

Definition at line 907 of file cons_bivariate.c.

References computeViolation(), initSepaDataCreateVred(), MAX, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPfeastol(), and SCIPisGT().

Referenced by computeViolation(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

static SCIP_RETCODE initSepaDataCreateVred ( SCIP scip,
SCIP_EXPRTREE **  vred,
SCIP_EXPRTREE f 
)
static

setup vred(s;x0,y0,ylb,yub) for a given f(x,y) for computing a convex-concave underestimator vred(s;x0,y0,ylb,yub) = (yub-y0)/(yub-ylb) f((yub-ylb)/(yub-y0)x0 - (y0-ylb)/(yub-y0)*s, ylb) + (y0-ylb)/(yub-ylb) f(s,yub)

Parameters
scipSCIP data structure
vredbuffer where to store exprtree for vred
ffunction f(x,y) for which vred should be setup

Definition at line 955 of file cons_bivariate.c.

References initSepaData(), NULL, SCIP_CALL, SCIP_EXPR_DIV, SCIP_EXPR_MINUS, SCIP_EXPR_MUL, SCIP_EXPR_PARAM, SCIP_EXPR_PLUS, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPexprCopyDeep(), SCIPexprCreate(), SCIPexprCreateLinear(), SCIPexprFreeDeep(), SCIPexprGetOperator(), SCIPexprSubstituteVars(), SCIPexprtreeCreate(), and SCIPexprtreeGetRoot().

Referenced by computeViolations(), and initSepaData().

static SCIP_RETCODE freeSepaData ( SCIP scip,
SCIP_CONS cons 
)
static

frees separation data

Parameters
scipSCIP data structure
consconstraint

Definition at line 1211 of file cons_bivariate.c.

References NULL, perturb(), SCIP_BIVAR_CONVEX_CONCAVE, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), and SCIPexprtreeFree().

Referenced by initSepaData(), and SCIP_DECL_CONSEXITSOL().

static void perturb ( SCIP_Real val,
SCIP_Real  lb,
SCIP_Real  ub,
SCIP_Real  amount 
)
static

perturbs a value w.r.t. bounds

Parameters
valvalue to perturb on input; perturbed value on output
lblower bound
ubupper bound
amountrelative amount of perturbation

Definition at line 1260 of file cons_bivariate.c.

References MIN, NULL, SCIP_Real, and solveDerivativeEquation().

Referenced by freeSepaData(), generate1ConvexIndefiniteUnderestimator(), generateConvexConcaveUnderestimator(), generateLinearizationCut(), and solveDerivativeEquation().

static SCIP_RETCODE solveDerivativeEquation ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real  targetvalue,
SCIP_Real  lb,
SCIP_Real  ub,
SCIP_Real val,
SCIP_Bool success 
)
static

solves an equation f'(s) = constant for a univariate convex or concave function f with respect to bounds on s if there is no s between the bounds such that f'(s) = constant, then it returns the closest bound (and still claims success)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
fexpression tree for f(s)
targetvaluetarget value for derivative
lblower bound on variable
ubupper bound on variable
valbuffer to store solution value
successbuffer to indicate whether a solution has been found

Definition at line 1285 of file cons_bivariate.c.

References FALSE, generateLinearizationCut(), MAX, MIN, NEWTONMAXITER, NULL, perturb(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPexprintGrad(), SCIPexprintHessianDense(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetNVars(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFinite, SCIPisRelEQ(), SCIPisZero(), and TRUE.

Referenced by generateConvexConcaveUnderestimator(), generateOrthogonal_lx_ly_Underestimator(), generateOrthogonal_lx_uy_Underestimator(), generateUnderestimatorParallelYFacets(), and perturb().

static SCIP_RETCODE generateLinearizationCut ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_CONS cons,
SCIP_Real x0y0,
SCIP_Bool  newxy,
SCIP_ROW **  row 
)
static

generates a cut for f(x,y) + c*z <= rhs with f(x,y) being convex or 1-convex with x or y fixed or convex-concave with y fixed f(x0, y0) + <grad, (x,y)-(x0,y0)> + c*z <= rhs, where grad is gradient of f in (x0, y0)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
consconstraint
x0y0value of x and y variables where to generate cut
newxywhether the last evaluation of f(x,y) with the expression interpreter was at (x0, y0)
rowstorage for cut

Definition at line 1445 of file cons_bivariate.c.

References FALSE, generateEstimatingHyperplane(), NULL, perturb(), SCIP_BIVAR_1CONVEX_INDEFINITE, SCIP_BIVAR_ALLCONVEX, SCIP_BIVAR_CONVEX_CONCAVE, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPdebugMessage, SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeGetInterpreterData(), SCIPexprtreeGetVars(), SCIPgetNLPs(), SCIPinfinity(), SCIPisEQ(), SCIPisFinite, SCIPisInfinity(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by generateCut(), SCIP_DECL_CONSINITLP(), SCIP_DECL_EVENTEXEC(), and solveDerivativeEquation().

static SCIP_RETCODE generateEstimatingHyperplane ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Bool  doover,
SCIP_Real x0y0,
SCIP_Real coefx,
SCIP_Real coefy,
SCIP_Real constant,
SCIP_Bool success 
)
static

given a convex (concave, resp.) bivariate function, computes an over- (under-, resp.) estimating hyperplane does not succeed if some variable is unbounded or both variables are fixed

Parameters
scipSCIP data structure
exprinterpreterexpression interpreter
fbivariate function to compute under or overestimator for
dooverwhether to compute an overestimator (TRUE) or an underestimator (FALSE)
x0y0reference values for nonlinear variables
coefxcoefficient of x in estimator
coefycoefficient of y in estimator
constantconstant part of estimator
successpointer to indicate whether coefficients where successfully computed

Definition at line 1521 of file cons_bivariate.c.

References FALSE, generateOverestimatingHyperplaneCut(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcomputeHyperplaneThreePoints(), SCIPdebugMessage, SCIPexprintEval(), SCIPexprtreeGetVars(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasLE(), SCIPisFinite, SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisNegative(), SCIPisZero(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by generateConvexConcaveEstimator(), generateLinearizationCut(), and generateOverestimatingHyperplaneCut().

static SCIP_RETCODE generateOverestimatingHyperplaneCut ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_CONS cons,
SCIP_Real x0y0,
SCIP_ROW **  row 
)
static

generates a cut for lhs <= f(x,y) + c*z with f(x,y) being convex

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
consconstraint
x0y0reference values for nonlinear variables
rowstorage for cut

Definition at line 1767 of file cons_bivariate.c.

References FALSE, generateEstimatingHyperplane(), generateUnderestimatorParallelYFacets(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateRowCons(), SCIPdebugMessage, SCIPexprtreeGetVars(), SCIPinfinity(), SCIPisFinite, SCIPisInfinity(), and TRUE.

Referenced by generateCut(), generateEstimatingHyperplane(), and SCIP_DECL_CONSINITLP().

static SCIP_RETCODE generateUnderestimatorParallelYFacets ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real xyref,
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generates a linear underestimator for f(x,y) when the generators of the underestimating segment are contained in y=ylb and y=yub. Generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xyrefreference values for x and y
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 1819 of file cons_bivariate.c.

References FALSE, generateOrthogonal_lx_ly_Underestimator(), MAX, MIN, NULL, REALABS, SCIP_CALL, SCIP_EXPR_CONST, SCIP_EXPR_MUL, SCIP_EXPR_PLUS, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPexprCopyDeep(), SCIPexprCreate(), SCIPexprFreeDeep(), SCIPexprGetOperator(), SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprSubstituteVars(), SCIPexprtreeCreate(), SCIPexprtreeEval(), SCIPexprtreeFree(), SCIPexprtreeGetRoot(), SCIPexprtreeGetVars(), SCIPexprtreePrintWithNames(), SCIPgetMessagehdlr(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFinite, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), solveDerivativeEquation(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA(), generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB(), and generateOverestimatingHyperplaneCut().

static SCIP_RETCODE generateOrthogonal_lx_ly_Underestimator ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real xyref,
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y. The segmenent connects orthogonal facets: Either (x=l_x,y=l_y) or (x=u_x,y=u_y). generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xyrefreference values for x and y
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 2050 of file cons_bivariate.c.

References FALSE, generateOrthogonal_lx_uy_Underestimator(), MAX, MIN, NULL, REALABS, SCIP_CALL, SCIP_EXPR_CONST, SCIP_EXPR_DIV, SCIP_EXPR_MINUS, SCIP_EXPR_MUL, SCIP_EXPR_PLUS, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPexprCopyDeep(), SCIPexprCreate(), SCIPexprFreeDeep(), SCIPexprGetOperator(), SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprSubstituteVars(), SCIPexprtreeCreate(), SCIPexprtreeEval(), SCIPexprtreeFree(), SCIPexprtreeGetRoot(), SCIPexprtreeGetVars(), SCIPexprtreePrintWithNames(), SCIPgetMessagehdlr(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFinite, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), solveDerivativeEquation(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA(), and generateUnderestimatorParallelYFacets().

static SCIP_RETCODE generateOrthogonal_lx_uy_Underestimator ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real xyref,
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xyrefreference values for x and y
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 2444 of file cons_bivariate.c.

References FALSE, generateConvexConcaveUnderestimator(), MAX, MIN, NULL, REALABS, SCIP_CALL, SCIP_EXPR_CONST, SCIP_EXPR_DIV, SCIP_EXPR_MINUS, SCIP_EXPR_MUL, SCIP_EXPR_PLUS, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPexprCopyDeep(), SCIPexprCreate(), SCIPexprFreeDeep(), SCIPexprGetOperator(), SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprSubstituteVars(), SCIPexprtreeCreate(), SCIPexprtreeEval(), SCIPexprtreeFree(), SCIPexprtreeGetRoot(), SCIPexprtreeGetVars(), SCIPexprtreePrintWithNames(), SCIPgetMessagehdlr(), SCIPisEQ(), SCIPisFinite, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), solveDerivativeEquation(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB(), and generateOrthogonal_lx_ly_Underestimator().

static SCIP_RETCODE generateConvexConcaveUnderestimator ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_EXPRTREE f_yfixed,
SCIP_EXPRTREE vred,
SCIP_Real  xyref[2],
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generates a linear underestimator for f(x,y) with f(x,y) being STRICTLY convex in x and concave in y generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
f_yfixedfunction f(x;y) with x variable and y parameter
vredfunction vred(s;x0,y0,ylb,yub)
xyrefreference values for (x,y)
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 2834 of file cons_bivariate.c.

References FALSE, generateConvexConcaveEstimator(), MAX, MIN, NULL, perturb(), REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPexprintEval(), SCIPexprintGrad(), SCIPexprintNewParametrization(), SCIPexprtreeEval(), SCIPexprtreeGetVars(), SCIPexprtreePrint(), SCIPexprtreePrintWithNames(), SCIPexprtreeSetParams(), SCIPexprtreeSetParamVal(), SCIPgetMessagehdlr(), SCIPinfinity(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasLE(), SCIPisFinite, SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), solveDerivativeEquation(), and TRUE.

Referenced by generateConvexConcaveEstimator(), and generateOrthogonal_lx_uy_Underestimator().

static SCIP_RETCODE generateConvexConcaveEstimator ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_CONS cons,
SCIP_Real  xyref[2],
SCIP_SIDETYPE  violside,
SCIP_ROW **  row 
)
static

generates a cut for one side of lhs <= f(x,y) + c*z <= rhs with f(x,y) being convex in x and concave in y

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
consconstraint
xyrefreference values for nonlinear variables
violsidefor which side of constraint to find a cut
rowstorage for cut

Definition at line 3337 of file cons_bivariate.c.

References FALSE, generateConvexConcaveUnderestimator(), generateEstimatingHyperplane(), lifting(), NULL, SCIP_BIVAR_CONVEX_CONCAVE, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIP_STAGE_SOLVING, SCIPaddVarsToRow(), SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPcreateRowCons(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPexprtreeGetVars(), SCIPgetNLPs(), SCIPgetStage(), SCIPinfinity(), SCIPisFinite, SCIPisInfinity(), SCIPisPositive(), SCIPsnprintf(), and TRUE.

Referenced by generateConvexConcaveUnderestimator(), generateCut(), and SCIP_DECL_CONSINITLP().

static SCIP_RETCODE lifting ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real  xval,
SCIP_Real  yval,
SCIP_Real  xlb,
SCIP_Real  xub,
SCIP_Real  ylb,
SCIP_Real  yub,
int  min_max,
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

computes an underestimating hyperplane for functions that are convex in x and y if the point to cut off lies on the boundary

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xvalcurrent x value
yvalcurrent y value
xlblower bound x
xubupper bound x
ylblower bound y
yubupper bound y
min_maxmin=-1 max=1
cutcoeffreturns the lifting coefficient
convenvvaluevalue of the convex envelope at (xval,yval)
successbuffer to indicate whether lifting was successful

Definition at line 3504 of file cons_bivariate.c.

References FALSE, generate1ConvexIndefiniteUnderestimatorAtBoundary(), NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPexprintGrad(), SCIPisEQ(), SCIPisFinite, SCIPisInfinity(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimatorAtBoundary(), and generateConvexConcaveEstimator().

static SCIP_RETCODE generate1ConvexIndefiniteUnderestimatorAtBoundary ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real  xyref[2],
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generate a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y and the point to cut off lies on the boundary generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xyrefreference values for x and y
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 3594 of file cons_bivariate.c.

References FALSE, generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA(), lifting(), NULL, REALABS, SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPerrorMessage, SCIPexprintGrad(), SCIPexprtreeGetVars(), SCIPexprtreePrintWithNames(), SCIPgetMessagehdlr(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFinite, SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimator(), and lifting().

static SCIP_RETCODE generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real  xyref[2],
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y but indefinite This is for the case where the cone of the concave directions is (R_+ x R_-) union (R_- x R_+). We consider two cases: a) the underestimating segmenent connects parallel facets b) the underestimating segmenent connects orthogonal facets where x=l_x, y=l_y and x=u_x, y=u_y We ensure that the parallel facets are the horizontal with y=l_y and y=u_y We compute the objective value of the two problems. The smaller objective value corresponds to the convex envelope. The supporting hyperplane is then constructed at the this point.

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xyrefreference values for x and y
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 3788 of file cons_bivariate.c.

References FALSE, generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB(), generateOrthogonal_lx_ly_Underestimator(), generateUnderestimatorParallelYFacets(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPexprCreate(), SCIPexprFreeDeep(), SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeCopy(), SCIPexprtreeFree(), SCIPexprtreeGetVars(), SCIPexprtreePrintWithNames(), SCIPexprtreeSetVars(), SCIPexprtreeSubstituteVars(), SCIPgetMessagehdlr(), SCIPinfinity(), SCIPisFinite, SCIPisInfinity(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimator(), and generate1ConvexIndefiniteUnderestimatorAtBoundary().

static SCIP_RETCODE generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_EXPRTREE f,
SCIP_Real  xyref[2],
SCIP_Real  cutcoeff[4],
SCIP_Real convenvvalue,
SCIP_Bool success 
)
static

generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y but indefinite This is for the case where the cone of the concave directions is (R_+ x R_+) union (R_- x R_-). We consider two cases: a) the underestimating segmenent connects parallel facets b) the underestimating segmenent connects orthogonal facets where x=l_x, y=u_y and x=u_x, y=l_y We ensure that the parallel facets are the horizontal with y=l_y and y=u_y We compute the objective value of the two problems. The smaller objective value corresponds to the convex envelope. The supporting hyperplane is then constructed at the this point. Generates coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
ffunction f(x,y)
xyrefreference values for x and y
cutcoeffcut coefficients alpha, beta, gamma, delta
convenvvaluefunction value of the convex envelope
successbuffer to store whether coefficients were successfully computed

Definition at line 3988 of file cons_bivariate.c.

References FALSE, generate1ConvexIndefiniteUnderestimator(), generateOrthogonal_lx_uy_Underestimator(), generateUnderestimatorParallelYFacets(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPdebug, SCIPdebugMessage, SCIPdebugPrintf, SCIPexprCreate(), SCIPexprFreeDeep(), SCIPexprintCompile(), SCIPexprintGrad(), SCIPexprtreeCopy(), SCIPexprtreeFree(), SCIPexprtreeGetVars(), SCIPexprtreePrintWithNames(), SCIPexprtreeSetVars(), SCIPexprtreeSubstituteVars(), SCIPgetMessagehdlr(), SCIPinfinity(), SCIPisFinite, SCIPisGE(), SCIPisInfinity(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimator(), and generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA().

static SCIP_RETCODE generate1ConvexIndefiniteUnderestimator ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_CONS cons,
SCIP_Real xyref,
SCIP_ROW **  row 
)
static

generates a linear underestimator for f(x,y) with f(x,y) being convex in x and convex in y but indefinite generate coefficients cutcoeff = (alpha, beta, gamma, delta), such that alpha * x + beta * y - delta <= gamma * f(x,y)

  1. If the point lies on the boundary we apply the lifting technique.
  2. If the point lies in the interior we check the pattern of the concave directions and compute the corresponding underestimators.
Parameters
scipSCIP data structure
exprinterpreterexpressions interpreter
consconstraint
xyrefreference values for x and y
rowstorage for cut

Definition at line 4180 of file cons_bivariate.c.

References FALSE, generate1ConvexIndefiniteUnderestimatorAtBoundary(), generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternA(), generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB(), generateCut(), NULL, perturb(), REALABS, SCIP_BIVAR_1CONVEX_INDEFINITE, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPdebugMessage, SCIPexprintHessianDense(), SCIPexprtreeGetVars(), SCIPinfinity(), SCIPisFeasEQ(), SCIPisFinite, SCIPisInfinity(), SCIPisPositive(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by generate1ConvexIndefiniteUnderestimatorInTheInteriorPatternB(), generateCut(), and SCIP_DECL_CONSINITLP().

static SCIP_RETCODE generateCut ( SCIP scip,
SCIP_EXPRINT exprinterpreter,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_SIDETYPE  violside,
SCIP_Real  cutmaxrange,
SCIP_ROW **  row 
)
static
static SCIP_Bool isConvexLocal ( SCIP scip,
SCIP_CONS cons,
SCIP_SIDETYPE  side 
)
static

returns whether one side of a constraint function is convex w.r.t. local bounds i.e., if side == RIGHT, then returns whether constraint function is convex w.r.t. local bounds and if side == LEFT, then returns whether constraint function is concave w.r.t. local bounds

Parameters
scipSCIP data structure
consconstraint
sideconstraint side to consider

Definition at line 4528 of file cons_bivariate.c.

References FALSE, NULL, SCIP_BIVAR_1CONVEX_INDEFINITE, SCIP_BIVAR_ALLCONVEX, SCIP_BIVAR_CONVEX_CONCAVE, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPcolGetVar(), SCIPconsGetData(), SCIPexprtreeGetVars(), SCIPexprtreePrint(), SCIPgetMessagehdlr(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisEQ(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and separatePoint().

Referenced by generateCut(), and separatePoint().

static SCIP_RETCODE separatePoint ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
int  nusefulconss,
SCIP_SOL sol,
SCIP_Real  minefficacy,
SCIP_Bool  inenforcement,
SCIP_RESULT result,
SCIP_Real bestefficacy 
)
static

tries to separate solution or LP solution by a linear cut

assumes that constraint violations have been computed

Parameters
scipSCIP data structure
conshdlrquadratic constraints handler
conssconstraints
nconssnumber of constraints
nusefulconssnumber of constraints that seem to be useful
solsolution to separate, or NULL if LP solution should be used
minefficacyminimal efficacy of a cut if it should be added to the LP
inenforcementwhether we are in constraint enforcement
resultresult of separation
bestefficacybuffer to store best efficacy of a cut that was added to the LP, if found; or NULL if not of interest

Definition at line 4629 of file cons_bivariate.c.

References FALSE, generateCut(), isConvexLocal(), MAX, MIN, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_EVENTEXEC(), SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPABORT, SCIPaddCut(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebug, SCIPdebugMessage, SCIPepsilon(), SCIPerrorMessage, SCIPfeastol(), SCIPgetRelaxFeastolFactor(), SCIPgetRowLPFeasibility(), SCIPgetRowMaxCoef(), SCIPgetRowSolFeasibility(), SCIPisCutApplicable(), SCIPisGT(), SCIPmarkRowNotRemovableLocal(), SCIPreleaseRow(), SCIProwGetLhs(), and SCIProwGetRhs().

Referenced by isConvexLocal(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().

static SCIP_RETCODE registerBranchingVariables ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
int *  nnotify 
)
static

registers unfixed variables in nonlinear terms of violated constraints as external branching candidates We score the variables by their gap between the convex envelope and the bivariate function in the current (x,y). This value is given by the constraint violation, since we assume that cuts have been generated which support the convex envelope in the LP.

Parameters
scipSCIP data structure
conssconstraints to check
nconssnumber of constraints to check
nnotifycounter for number of notifications performed

Definition at line 4851 of file cons_bivariate.c.

References NULL, registerLargeLPValueVariableForBranching(), SCIP_BIVAR_1CONVEX_INDEFINITE, SCIP_BIVAR_ALLCONVEX, SCIP_BIVAR_CONVEX_CONCAVE, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPaddExternBranchCand(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMessage, SCIPexprtreeGetVars(), SCIPisEQ(), SCIPisFeasZero(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().

Referenced by SCIP_DECL_CONSENFOLP(), and SCIP_DECL_EVENTEXEC().

static SCIP_RETCODE registerLargeLPValueVariableForBranching ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
SCIP_VAR **  brvar 
)
static

registers a nonlinear variable from a violated constraint as branching candidate that has a large absolute value in the LP relaxation

Parameters
scipSCIP data structure
conssconstraints
nconssnumber of constraints
brvarbuffer to store branching variable

Definition at line 4962 of file cons_bivariate.c.

References enforceViolatedFixedNonlinear(), NULL, REALABS, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddExternBranchCand(), SCIPconsGetData(), SCIPexprtreeGetVars(), SCIPfeastol(), SCIPgetSolVal(), SCIPisEQ(), SCIPisGT(), SCIPvarGetLbLocal(), and SCIPvarGetUbLocal().

Referenced by registerBranchingVariables(), and SCIP_DECL_CONSENFOLP().

static SCIP_RETCODE enforceViolatedFixedNonlinear ( SCIP scip,
SCIP_CONS **  conss,
int  nconss,
SCIP_Bool reduceddom,
SCIP_Bool infeasible 
)
static

enforces violated bivariate constraints where both nonlinear variables can be assumed to be fixed apply a bound change to the remaining linear variable, or recognizing infeasibility

Parameters
scipSCIP data structure
conssconstraints
nconssnumber of constraints
reduceddomwhether a domain has been reduced
infeasiblewhether we detected infeasibility

Definition at line 5019 of file cons_bivariate.c.

References FALSE, NULL, propagateBoundsTightenVar(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPdebugMessage, SCIPevalExprtreeLocalBounds(), SCIPfeastol(), SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPisFeasGT(), SCIPisFeasLT(), SCIPisGT(), SCIPisInfinity(), SCIPisZero(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetName(), and TRUE.

Referenced by registerLargeLPValueVariableForBranching(), and SCIP_DECL_CONSENFOLP().

static SCIP_RETCODE propagateBoundsTightenVar ( SCIP scip,
SCIP_VAR var,
SCIP_INTERVAL  bounds,
SCIP_CONS cons,
SCIP_RESULT result,
int *  nchgbds 
)
static

tightens bounds on a variable to given interval

Parameters
scipSCIP data structure
varvariable which bounds to tighten
boundsnew bounds
consconstraint that is propagated
resultpointer where to update the result of the propagation call
nchgbdsbuffer where to add the the number of changed bounds

Definition at line 5146 of file cons_bivariate.c.

References FALSE, NULL, propagateBoundsCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_VARSTATUS_MULTAGGR, SCIPadjustedVarLb(), SCIPconsGetName(), SCIPdebugMessage, SCIPinfinity(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalIsNegativeInfinity(), SCIPintervalIsPositiveInfinity(), SCIPisInfinity(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), and SCIPvarGetUbLocal().

Referenced by enforceViolatedFixedNonlinear(), propagateBounds(), and propagateBoundsCons().

static SCIP_RETCODE propagateBoundsCons ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS cons,
SCIP_RESULT result,
int *  nchgbds,
SCIP_Bool redundant 
)
static

tightens bounds of z in a single bivariate constraint checks for redundancy and infeasibility

Parameters
scipSCIP data structure
conshdlrconstraint handler
consconstraint to process
resultpointer to store the result of the propagation call
nchgbdsbuffer where to add the the number of changed bounds
redundantbuffer where to store whether constraint has been found to be redundant

Definition at line 5218 of file cons_bivariate.c.

References FALSE, infty2infty, INTERVALINFTY, MAX, MIN, NULL, propagateBounds(), propagateBoundsTightenVar(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SUCCESS, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebugMessage, SCIPepsilon(), SCIPexprgraphGetNodeBounds(), SCIPexprgraphTightenNodeBounds(), SCIPinfinity(), SCIPinProbing(), SCIPintervalAdd(), SCIPintervalAreDisjoint(), SCIPintervalDivScalar(), SCIPintervalGetInf(), SCIPintervalGetSup(), SCIPintervalIsEmpty(), SCIPintervalIsSubsetEQ(), SCIPintervalMulScalar(), SCIPintervalSet(), SCIPintervalSetBounds(), SCIPintervalSub(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by propagateBounds(), and propagateBoundsTightenVar().

static SCIP_RETCODE propagateBounds ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
SCIP_RESULT result,
int *  nchgbds,
int *  ndelconss 
)
static

calls domain propagation for a set of constraints

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
resultpointer to store the result of the propagation calls
nchgbdsbuffer where to add the the number of changed bounds
ndelconssbuffer where to increase if a constraint was deleted (locally) due to redundancy

Definition at line 5334 of file cons_bivariate.c.

References FALSE, INTERVALINFTY, NULL, propagateBoundsCons(), propagateBoundsTightenVar(), proposeFeasibleSolution(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsDeleted(), SCIPconsIsEnabled(), SCIPdebugMessage, SCIPdelConsLocal(), SCIPexprgraphGetNodeBounds(), SCIPexprgraphGetNVars(), SCIPexprgraphGetVarNodes(), SCIPexprgraphGetVars(), SCIPexprgraphPropagateNodeBounds(), SCIPexprgraphPropagateVarBounds(), SCIPinProbing(), and TRUE.

Referenced by propagateBoundsCons(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

static SCIP_RETCODE proposeFeasibleSolution ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS **  conss,
int  nconss,
SCIP_SOL sol,
SCIP_Bool success 
)
static

Given a solution where every bivariate constraint is either feasible or can be made feasible by moving the linear variable, construct the corresponding feasible solution and pass it to the trysol heuristic. The method assumes that this is always possible and that not all constraints are feasible already.

Parameters
scipSCIP data structure
conshdlrconstraint handler
conssconstraints to process
nconssnumber of constraints
solsolution to process
successbuffer to store whether we succeeded to construct a solution that satisfies all provided constraints

Definition at line 5485 of file cons_bivariate.c.

References computeViolation(), createConsFromQuadTerm(), FALSE, MAX, MIN, NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_SOLVED, SCIPceil(), SCIPconsGetData(), SCIPconshdlrGetData(), SCIPcreateLPSol(), SCIPcreateSolCopy(), SCIPdebugMessage, SCIPfeastol(), SCIPfloor(), SCIPfreeSol(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetStage(), SCIPgetUpperbound(), SCIPheurPassSolTrySol(), SCIPincSolVal(), SCIPisGT(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisSumLT(), SCIPisZero(), SCIPunlinkSol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), and TRUE.

Referenced by propagateBounds(), and SCIP_DECL_CONSCHECK().

static SCIP_RETCODE createConsFromQuadTerm ( SCIP scip,
SCIP_CONS srccons,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR x,
SCIP_VAR y,
SCIP_VAR z,
SCIP_Real  coefxx,
SCIP_Real  coefx,
SCIP_Real  coefyy,
SCIP_Real  coefy,
SCIP_Real  coefxy,
SCIP_Real  coefz,
SCIP_Real  lhs,
SCIP_Real  rhs 
)
static

creates bivariate constraint from quadratic constraint data of the form lhs <= xsqrcoef * x^2 + xlincoef * x + ysqrcoef * y^2 + ylincoef * y + bilincoef * x*y + zcoef * z <= rhs

Parameters
scipSCIP data structure
srcconssource constraint to take attributes from
conspointer to store new constraint
namename of new constraint
xfirst nonlinear variable
ysecond nonlinear variable
zlinear variable, can be NULL
coefxxcoefficient of x^2
coefxcoefficient of x
coefyycoefficient of y^2
coefycoefficient of y
coefxycoefficient of x*y
coefzcoefficient of z
lhsleft-hand-side
rhsright-hand-side

Definition at line 5640 of file cons_bivariate.c.

References SCIP_QuadElement::coef, createExprtreeFromMonomial(), SCIP_QuadElement::idx1, SCIP_QuadElement::idx2, NULL, SCIP_BIVAR_1CONVEX_INDEFINITE, SCIP_BIVAR_ALLCONVEX, SCIP_BIVAR_CONVEX_CONCAVE, SCIP_CALL, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsBivariate(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPexprCreate(), SCIPexprCreateQuadratic(), SCIPexprtreeCreate(), SCIPexprtreeFree(), SCIPexprtreeSetVars(), and SCIPisLE().

Referenced by proposeFeasibleSolution(), and SCIP_DECL_QUADCONSUPGD().

static SCIP_RETCODE createExprtreeFromMonomial ( SCIP scip,
SCIP_VAR x,
SCIP_VAR y,
SCIP_Real  coef,
SCIP_Real  p,
SCIP_Real  q,
SCIP_EXPRTREE **  exprtree,
SCIP_Real mult,
SCIP_BIVAR_CONVEXITY convextype 
)
static

creates expression tree for monomial of the form coef * x^p * y^q with x >= 0 and y >= 0 and checks its convexity type

Parameters
scipSCIP data structure
xfirst variable
ysecond variable
coefmonomial coefficient
pexponent of x
qexponent of y
exprtreebuffer to store pointer to expression tree
multbuffer to store multiplicator for generated expression tree
convextypebuffer to store convexity type of expression tree

Definition at line 5806 of file cons_bivariate.c.

References createConsFromMonomial(), FALSE, NULL, SCIP_BIVAR_1CONVEX_INDEFINITE, SCIP_BIVAR_ALLCONVEX, SCIP_BIVAR_CONVEX_CONCAVE, SCIP_BIVAR_UNKNOWN, SCIP_Bool, SCIP_CALL, SCIP_EXPR_VARIDX, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPexprCreate(), SCIPexprCreateMonomial(), SCIPexprCreatePolynomial(), SCIPexprtreeCreate(), SCIPexprtreeSetVars(), SCIPisZero(), and TRUE.

Referenced by createConsFromMonomial(), and createConsFromQuadTerm().

static SCIP_RETCODE createConsFromMonomial ( SCIP scip,
SCIP_CONS srccons,
SCIP_CONS **  cons,
const char *  name,
SCIP_VAR x,
SCIP_VAR y,
SCIP_VAR z,
SCIP_Real  coef,
SCIP_Real  p,
SCIP_Real  q,
SCIP_Real  zcoef,
SCIP_Real  lhs,
SCIP_Real  rhs 
)
static

creates bivariate constraint from monomial of the form coef * x^p * y^q with x >= 0 and y >= 0 lhs <= coef * x^p * y^q + zcoef * z <= rhs

Parameters
scipSCIP data structure
srcconssource constraint to take attributes from, or NULL
conspointer to store new constraint
namename of new constraint
xfirst nonlinear variable
ysecond nonlinear variable
zlinear variable, can be NULL
coefmonomial coefficient
pexponent of x
qexponent of y
zcoefcoefficient of z
lhsleft-hand-side
rhsright-hand-side

Definition at line 5923 of file cons_bivariate.c.

References createExprtreeFromMonomial(), FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIP_Real, SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsBivariate(), SCIPdebugMessage, SCIPdebugPrintCons, SCIPexprtreeFree(), SCIPisLE(), SCIPisZero(), SCIPvarGetName(), and TRUE.

Referenced by createExprtreeFromMonomial(), and SCIP_DECL_EXPRGRAPHNODEREFORM().

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyBivariate  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 6000 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPincludeConshdlrBivariate(), and TRUE.

Referenced by createConsFromMonomial().

static SCIP_DECL_CONSFREE ( consFreeBivariate  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 6016 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSINIT(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPexprgraphFree(), SCIPexprgraphGetNVars(), SCIPexprintFree(), and SCIPfreeMemory.

Referenced by SCIP_DECL_CONSHDLRCOPY().

static SCIP_DECL_CONSINIT ( consInitBivariate  )
static

initialization method of constraint handler (called after problem was transformed)

Definition at line 6044 of file cons_bivariate.c.

References NULL, SCIP_DECL_CONSEXIT(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPfindHeur().

Referenced by SCIP_DECL_CONSFREE().

static SCIP_DECL_CONSEXIT ( consExitBivariate  )
static

deinitialization method of constraint handler (called before transformed problem is freed)

Definition at line 6062 of file cons_bivariate.c.

References NULL, SCIP_DECL_CONSINITPRE(), SCIP_OKAY, and SCIPconshdlrGetData().

Referenced by SCIP_DECL_CONSINIT().

static SCIP_DECL_CONSINITPRE ( consInitpreBivariate  )
static

presolving initialization method of constraint handler (called when presolving is about to begin)

Definition at line 6080 of file cons_bivariate.c.

References FALSE, NULL, SCIP_DECL_CONSEXITPRE(), SCIP_OKAY, and SCIPconsGetData().

Referenced by SCIP_DECL_CONSEXIT().

static SCIP_DECL_CONSEXITPRE ( consExitpreBivariate  )
static
static SCIP_DECL_CONSEXITSOL ( consExitsolBivariate  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 6283 of file cons_bivariate.c.

References CONSHDLR_NAME, freeSepaData(), NULL, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_EVENTTYPE_SOLFOUND, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdropEvent(), and SCIPfindEventhdlr().

Referenced by SCIP_DECL_CONSINITSOL().

static SCIP_DECL_CONSDELETE ( consDeleteBivariate  )
static

frees specific constraint data

Definition at line 6318 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPexprtreeFree(), and SCIPfreeMemory.

Referenced by SCIP_DECL_CONSEXITSOL().

static SCIP_DECL_CONSSEPALP ( consSepalpBivariate  )
static

separation method of constraint handler for LP solutions

Definition at line 6607 of file cons_bivariate.c.

References computeViolations(), FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSSEPASOL(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIPconshdlrGetData(), and separatePoint().

Referenced by SCIP_DECL_CONSINITLP().

static SCIP_DECL_CONSSEPASOL ( consSepasolBivariate  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 6635 of file cons_bivariate.c.

References computeViolations(), FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIPconshdlrGetData(), and separatePoint().

Referenced by SCIP_DECL_CONSSEPALP().

static SCIP_DECL_CONSCHECK ( consCheckBivariate  )
static
static SCIP_DECL_CONSPROP ( consPropBivariate  )
static

domain propagation method of constraint handler

Definition at line 6995 of file cons_bivariate.c.

References NULL, propagateBounds(), SCIP_CALL, SCIP_DECL_CONSPRESOL(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSCHECK().

static SCIP_DECL_CONSLOCK ( consLockBivariate  )
static

variable rounding lock method of constraint handler

Definition at line 7089 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSACTIVE(), SCIP_OKAY, SCIPaddVarLocks(), SCIPconsGetData(), and SCIPisInfinity().

Referenced by SCIP_DECL_CONSPRESOL().

static SCIP_DECL_CONSACTIVE ( consActiveBivariate  )
static
static SCIP_DECL_CONSDEACTIVE ( consDeactiveBivariate  )
static

constraint deactivation notification method of constraint handler

Definition at line 7175 of file cons_bivariate.c.

References NULL, SCIP_CALL, SCIP_DECL_CONSENABLE(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPdebugMessage, and SCIPexprgraphReleaseNode().

Referenced by SCIP_DECL_CONSACTIVE().

static SCIP_DECL_CONSENABLE ( consEnableBivariate  )
static
static SCIP_DECL_CONSDISABLE ( consDisableBivariate  )
static
static SCIP_DECL_CONSPRINT ( consPrintBivariate  )
static
static SCIP_DECL_CONSCOPY ( consCopyBivariate  )
static
static SCIP_DECL_CONSGETVARS ( consGetVarsBivariate  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 7393 of file cons_bivariate.c.

References FALSE, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), SCIPexprtreeGetVars(), and TRUE.

Referenced by SCIP_DECL_CONSCOPY().

static SCIP_DECL_CONSGETNVARS ( consGetNVarsBivariate  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 7419 of file cons_bivariate.c.

References SCIP_DECL_QUADCONSUPGD(), SCIP_OKAY, and TRUE.

Referenced by SCIP_DECL_CONSGETVARS().

static SCIP_DECL_QUADCONSUPGD ( quadconsUpgdBivariate  )
static

tries to upgrade a quadratic constraint into a bivariate constraint

Definition at line 7434 of file cons_bivariate.c.

References BMSclearMemoryArray, SCIP_BilinTerm::coef, createConsFromQuadTerm(), FALSE, SCIP_QuadVarTerm::lincoef, NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_EXPRGRAPHNODEREFORM(), SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PRESOLTIMING_FAST, SCIP_PRESOLTIMING_MEDIUM, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIPaddBilinTermQuadratic(), SCIPaddLinearVarQuadratic(), SCIPaddQuadVarLinearCoefQuadratic(), SCIPaddQuadVarQuadratic(), SCIPaddSquareCoefQuadratic(), SCIPaddVar(), SCIPallocBufferArray, SCIPcheckCurvatureQuadratic(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPcreateConsQuadratic(), SCIPcreateConsQuadratic2(), SCIPcreateVar(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugPrintCons, SCIPfindQuadVarTermQuadratic(), SCIPfreeBufferArray, SCIPgetBilinTermsQuadratic(), SCIPgetCoefsLinearVarsQuadratic(), SCIPgetLhsQuadratic(), SCIPgetLinearVarsQuadratic(), SCIPgetNBilinTermsQuadratic(), SCIPgetNLinearVarsQuadratic(), SCIPgetNQuadVarTermsQuadratic(), SCIPgetQuadVarTermsQuadratic(), SCIPgetRhsQuadratic(), SCIPinfinity(), SCIPisConcaveQuadratic(), SCIPisConvexQuadratic(), SCIPisInfinity(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsetConsChecked(), SCIPsetConsEnforced(), SCIPsnprintf(), SCIP_QuadVarTerm::sqrcoef, TRUE, SCIP_QuadVarTerm::var, SCIP_BilinTerm::var1, and SCIP_BilinTerm::var2.

Referenced by SCIP_DECL_CONSGETNVARS().

SCIP_RETCODE SCIPincludeConshdlrBivariate ( SCIP scip)

creates the handler for bivariate constraints and includes it in SCIP

Parameters
scipSCIP data structure

Definition at line 7860 of file cons_bivariate.c.

References BMSclearMemory, CONSHDLR_CHECKPRIORITY, CONSHDLR_DELAYPROP, CONSHDLR_DELAYSEPA, CONSHDLR_DESC, CONSHDLR_EAGERFREQ, CONSHDLR_ENFOPRIORITY, CONSHDLR_MAXPREROUNDS, CONSHDLR_NAME, CONSHDLR_NEEDSCONS, CONSHDLR_PRESOLTIMING, CONSHDLR_PROP_TIMING, CONSHDLR_PROPFREQ, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, FALSE, NONLINCONSUPGD_PRIORITY, NULL, QUADCONSUPGD_PRIORITY, SCIP_CALL, SCIP_OKAY, SCIPaddBoolParam(), SCIPaddCharParam(), SCIPaddIntParam(), SCIPaddRealParam(), SCIPallocMemory, SCIPblkmem(), SCIPcreateConsBivariate(), SCIPexprgraphCreate(), SCIPexprintCreate(), SCIPfeastol(), SCIPincludeConshdlrBasic(), SCIPincludeEventhdlrBasic(), SCIPincludeNonlinconsUpgrade(), SCIPincludeQuadconsUpgrade(), SCIPinfinity(), SCIPsetConshdlrActive(), SCIPsetConshdlrCopy(), SCIPsetConshdlrDeactive(), SCIPsetConshdlrDelete(), SCIPsetConshdlrDisable(), SCIPsetConshdlrEnable(), SCIPsetConshdlrExit(), SCIPsetConshdlrExitpre(), SCIPsetConshdlrExitsol(), SCIPsetConshdlrFree(), SCIPsetConshdlrGetNVars(), SCIPsetConshdlrGetVars(), SCIPsetConshdlrInit(), SCIPsetConshdlrInitlp(), SCIPsetConshdlrInitpre(), SCIPsetConshdlrInitsol(), SCIPsetConshdlrPresol(), SCIPsetConshdlrPrint(), SCIPsetConshdlrProp(), SCIPsetConshdlrSepa(), SCIPsetConshdlrTrans(), and TRUE.

Referenced by SCIP_DECL_CONSHDLRCOPY(), SCIP_DECL_EXPRGRAPHNODEREFORM(), and SCIPincludeDefaultPlugins().

SCIP_RETCODE SCIPcreateConsBivariate ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_EXPRTREE f,
SCIP_BIVAR_CONVEXITY  convextype,
SCIP_VAR z,
SCIP_Real  zcoef,
SCIP_Real  lhs,
SCIP_Real  rhs,
SCIP_Bool  initial,
SCIP_Bool  separate,
SCIP_Bool  enforce,
SCIP_Bool  check,
SCIP_Bool  propagate,
SCIP_Bool  local,
SCIP_Bool  modifiable,
SCIP_Bool  dynamic,
SCIP_Bool  removable,
SCIP_Bool  stickingatnode 
)

creates and captures a bivariate constraint

Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
fexpression tree specifying bivariate function f(x,y)
convextypekind of convexity of f(x,y)
zlinear variable in constraint
zcoefcoefficient of linear variable
lhsleft hand side of constraint
rhsright hand side of constraint
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.

Definition at line 7974 of file cons_bivariate.c.

References BMSclearMemory, CONSHDLR_NAME, FALSE, NULL, REALABS, SCIP_CALL, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPallocMemory, SCIPblkmem(), SCIPcreateCons(), SCIPcreateConsBasicBivariate(), SCIPerrorMessage, SCIPexprtreeCopy(), SCIPexprtreeGetNVars(), SCIPexprtreeGetVars(), SCIPfindConshdlr(), and SCIPisInfinity().

Referenced by createConsFromMonomial(), createConsFromQuadTerm(), SCIP_DECL_CONSCOPY(), SCIPcreateConsBasicBivariate(), and SCIPincludeConshdlrBivariate().

SCIP_RETCODE SCIPcreateConsBasicBivariate ( SCIP scip,
SCIP_CONS **  cons,
const char *  name,
SCIP_EXPRTREE f,
SCIP_BIVAR_CONVEXITY  convextype,
SCIP_VAR z,
SCIP_Real  zcoef,
SCIP_Real  lhs,
SCIP_Real  rhs 
)

creates and captures an absolute power constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsBivariate(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h

See also
SCIPcreateConsBivariate() for information about the basic constraint flag configuration
Note
the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
Parameters
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
fexpression tree specifying bivariate function f(x,y)
convextypekind of convexity of f(x,y)
zlinear variable in constraint
zcoefcoefficient of linear variable
lhsleft hand side of constraint
rhsright hand side of constraint

Definition at line 8058 of file cons_bivariate.c.

References FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPcreateConsBivariate(), SCIPgetLinearVarBivariate(), and TRUE.

Referenced by SCIPcreateConsBivariate().

SCIP_VAR* SCIPgetLinearVarBivariate ( SCIP scip,
SCIP_CONS cons 
)

gets the linear variable of a bivariate constraint, or NULL if no such variable

Parameters
scipSCIP data structure
consconstraint

Definition at line 8079 of file cons_bivariate.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetLinearCoefBivariate().

Referenced by SCIPcreateConsBasicBivariate(), SCIPwriteGms(), and SCIPwritePip().

SCIP_Real SCIPgetLinearCoefBivariate ( SCIP scip,
SCIP_CONS cons 
)

gets the coefficients of the linear variable of a bivariate constraint

Parameters
scipSCIP data structure
consconstraint

Definition at line 8091 of file cons_bivariate.c.

References NULL, SCIPconsGetData(), and SCIPgetExprtreeBivariate().

Referenced by SCIPgetLinearVarBivariate(), SCIPwriteGms(), and SCIPwritePip().

SCIP_EXPRTREE* SCIPgetExprtreeBivariate ( SCIP scip,
SCIP_CONS cons 
)

gets the expression tree of a bivariate constraint

Parameters
scipSCIP data structure
consconstraint

Definition at line 8103 of file cons_bivariate.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetLhsBivariate().

Referenced by SCIPgetLinearCoefBivariate(), SCIPwriteGms(), and SCIPwritePip().

SCIP_Real SCIPgetLhsBivariate ( SCIP scip,
SCIP_CONS cons 
)

gets the left hand side of a bivariate constraint

Parameters
scipSCIP data structure
consconstraint

Definition at line 8115 of file cons_bivariate.c.

References NULL, SCIP_Real, SCIPconsGetData(), and SCIPgetRhsBivariate().

Referenced by SCIPgetExprtreeBivariate(), SCIPwriteGms(), and SCIPwritePip().

SCIP_Real SCIPgetRhsBivariate ( SCIP scip,
SCIP_CONS cons 
)

gets the right hand side of a bivariate constraint

Parameters
scipSCIP data structure
consconstraint

Definition at line 8127 of file cons_bivariate.c.

References NULL, and SCIPconsGetData().

Referenced by SCIPgetLhsBivariate(), SCIPwriteGms(), and SCIPwritePip().