constraint handler for nonlinear constraints specified by algebraic expressions
Definition in file cons_nonlinear.c.
#include <ctype.h>
#include "scip/cons_nonlinear.h"
#include "scip/nlhdlr.h"
#include "scip/expr_var.h"
#include "scip/expr_varidx.h"
#include "scip/expr_abs.h"
#include "scip/expr_sum.h"
#include "scip/expr_value.h"
#include "scip/expr_pow.h"
#include "scip/expr_trig.h"
#include "scip/nlhdlr_convex.h"
#include "scip/cons_linear.h"
#include "scip/cons_varbound.h"
#include "scip/cons_and.h"
#include "scip/cons_bounddisjunction.h"
#include "scip/heur_subnlp.h"
#include "scip/heur_trysol.h"
#include "scip/lapack_calls.h"
#include "scip/debug.h"
#include "scip/dialog_default.h"
#include "scip/scip_expr.h"
#include "scip/symmetry_graph.h"
#include "scip/prop_symmetry.h"
#include "symmetry/struct_symmetry.h"
#include "scip/pub_misc_sort.h"
Go to the source code of this file.
Data Structures | |
struct | EXPRENFO |
struct | CONSUPGRADE |
struct | BRANCHCAND |
#define CONSHDLR_NAME "nonlinear" |
Definition at line 83 of file cons_nonlinear.c.
#define CONSHDLR_DESC "handler for nonlinear constraints specified by algebraic expressions" |
Definition at line 84 of file cons_nonlinear.c.
#define CONSHDLR_ENFOPRIORITY 50 |
priority of the constraint handler for constraint enforcing
Definition at line 85 of file cons_nonlinear.c.
#define CONSHDLR_CHECKPRIORITY -4000010 |
priority of the constraint handler for checking feasibility
Definition at line 86 of file cons_nonlinear.c.
#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 87 of file cons_nonlinear.c.
#define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 89 of file cons_nonlinear.c.
#define CONSHDLR_SEPAPRIORITY 10 |
priority of the constraint handler for separation
Definition at line 92 of file cons_nonlinear.c.
#define CONSHDLR_SEPAFREQ 1 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 93 of file cons_nonlinear.c.
#define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 94 of file cons_nonlinear.c.
#define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 96 of file cons_nonlinear.c.
#define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 97 of file cons_nonlinear.c.
#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
propagation timing mask of the constraint handler
Definition at line 98 of file cons_nonlinear.c.
#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS |
presolving timing of the constraint handler (fast, medium, or exhaustive)
Definition at line 100 of file cons_nonlinear.c.
#define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 101 of file cons_nonlinear.c.
#define TABLE_NAME_NONLINEAR "cons_nonlinear" |
Definition at line 104 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_DESC_NONLINEAR "nonlinear constraint handler statistics" |
Definition at line 105 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_POSITION_NONLINEAR 14600 |
the position of the statistics table
Definition at line 106 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_EARLIEST_STAGE_NONLINEAR SCIP_STAGE_TRANSFORMED |
output of the statistics table is only printed from this stage onwards
Definition at line 107 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_NAME_NLHDLR "nlhdlr" |
Definition at line 110 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_DESC_NLHDLR "nonlinear handler statistics" |
Definition at line 111 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_POSITION_NLHDLR 14601 |
the position of the statistics table
Definition at line 112 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define TABLE_EARLIEST_STAGE_NLHDLR SCIP_STAGE_PRESOLVING |
output of the statistics table is only printed from this stage onwards
Definition at line 113 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define DIALOG_NAME "nlhdlrs" |
Definition at line 115 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define DIALOG_DESC "display nonlinear handlers" |
Definition at line 116 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define DIALOG_ISSUBMENU FALSE |
Definition at line 117 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define VERTEXPOLY_MAXPERTURBATION 1e-3 |
maximum perturbation
Definition at line 119 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define VERTEXPOLY_USEDUALSIMPLEX TRUE |
use dual or primal simplex algorithm?
Definition at line 120 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define VERTEXPOLY_RANDNUMINITSEED 20181029 |
seed for random number generator, which is used to move points away from the boundary
Definition at line 121 of file cons_nonlinear.c.
Referenced by computeVertexPolyhedralFacetLP().
#define VERTEXPOLY_ADJUSTFACETFACTOR 1e1 |
adjust resulting facets in checkRikun() up to a violation of this value times lpfeastol
Definition at line 122 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define BRANCH_RANDNUMINITSEED 20191229 |
seed for random number generator, which is used to select from several similar good branching candidates
Definition at line 124 of file cons_nonlinear.c.
Referenced by selectBranchingCandidate().
#define BILIN_MAXNAUXEXPRS 10 |
maximal number of auxiliary expressions per bilinear term
Definition at line 126 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define infty2infty | ( | infty1, | |
infty2, | |||
val ) |
translate from one value of infinity to another
if val is ≥ infty1, then give infty2, else give val
Definition at line 132 of file cons_nonlinear.c.
Referenced by SCIP_DECL_EXPR_INTEVALVAR(), and SCIP_DECL_EXPR_INTEVALVAR().
#define POWEROFTWO | ( | x | ) |
translates x to 2^x for non-negative integer x
Definition at line 135 of file cons_nonlinear.c.
Referenced by buildVertexPolyhedralSeparationLP(), computeVertexPolyhedralFacetLP(), computeVertexPolyhedralMaxFacetError(), and SCIPcomputeFacetVertexPolyhedralNonlinear().
#define ENFOLOG | ( | x | ) |
Definition at line 141 of file cons_nonlinear.c.
Referenced by analyzeViolation(), branching(), branchingIntegralOrNonlinear(), collectBranchingCandidates(), consEnfo(), consSepa(), enforceConstraint(), enforceConstraints(), enforceExpr(), enforceExprNlhdlr(), notifyNlhdlrNewsol(), registerBranchingCandidates(), SCIP_DECL_CONSEXIT(), SCIP_DECL_CONSINIT(), SCIPprocessRowprepNonlinear(), scoreBranchingCandidates(), and selectBranchingCandidate().
#define consInitpreNonlinear NULL |
presolving initialization method of constraint handler (called when presolving is about to begin)
Definition at line 11177 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define consRespropNonlinear NULL |
propagation conflict resolving method of constraint handler
Definition at line 11746 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define consDelvarsNonlinear NULL |
variable deletion of constraint handler
Definition at line 11967 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
#define consGetDiveBdChgsNonlinear NULL |
constraint handler method to suggest dive bound changes during the generic diving algorithm
Definition at line 12238 of file cons_nonlinear.c.
Referenced by SCIPincludeConshdlrNonlinear().
|
static |
propagate bounds of the expressions in a given expression tree (that is, updates activity intervals) and tries to tighten the bounds of the auxiliary variables accordingly
scip | SCIP data structure |
conshdlr | constraint handler |
rootexpr | expression |
tightenauxvars | should the bounds of auxiliary variables be tightened? |
infeasible | buffer to store whether the problem is infeasible (NULL if not needed) |
ntightenings | buffer to store the number of auxiliary variable tightenings (NULL if not needed) |
Definition at line 2167 of file cons_nonlinear.c.
References assert(), FALSE, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_LEAVEEXPR, SCIP_EXPRITER_VISITINGCHILD, SCIP_INTERVAL_INFINITY, SCIP_LONGINT_FORMAT, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_OKAY, SCIPABORT, SCIPceil(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPepsilon(), SCIPerrorMessage, SCIPexprGetActivity(), SCIPexprGetActivityTag(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprGetOwnerData(), SCIPexprhdlrGetName(), SCIPexprIsIntegral(), SCIPexpriterGetChildExprDFS(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPexpriterSkipDFS(), SCIPexprSetActivity(), SCIPfloor(), SCIPfreeExpriter(), SCIPgetVarExprVar(), SCIPintervalIntersectEps(), SCIPintervalIsEmpty(), SCIPintervalSetEmpty(), SCIPintervalSetEntire(), SCIPisExprVar(), SCIPisInfinity(), SCIPisRelEQ(), SCIPnlhdlrGetName(), SCIPnlhdlrHasIntEval(), SCIPprintExpr(), SCIPvarGetName(), SCIP_Interval::sup, tightenAuxVarBounds(), and TRUE.
Referenced by enforceConstraint(), presolveRedundantConss(), propConss(), and SCIP_DECL_EXPR_OWNEREVALACTIVITY().
|
static |
frees auxiliary variables of expression, if any
scip | SCIP data structure |
expr | expression which auxvar to free, if any |
Definition at line 386 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPaddVarLocks(), SCIPdebugMsg, SCIPexprGetOwnerData(), SCIPreleaseVar(), and SCIPvarGetName().
Referenced by freeEnfoData().
|
static |
frees data used for enforcement of expression, that is, nonlinear handlers
can also clear indicators whether expr needs enforcement methods, that is, free an associated auxiliary variable and reset the nactivityuses counts
scip | SCIP data structure |
expr | expression whose enforcement data will be released |
freeauxvar | whether aux var should be released and activity usage counts be reset |
Definition at line 422 of file cons_nonlinear.c.
References assert(), FALSE, freeAuxVar(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPexprGetOwnerData(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.
Referenced by deinitSolve(), detectNlhdlrs(), SCIP_DECL_EXPR_OWNERFREE(), and SCIPregisterExprUsageNonlinear().
|
static |
callback that frees data that this conshdlr stored in an expression
Definition at line 485 of file cons_nonlinear.c.
References assert(), freeEnfoData(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPgetVarExprVar(), SCIPhashmapGetImage(), SCIPhashmapRemove(), SCIPisExprVar(), TRUE, and var.
|
static |
Definition at line 537 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_OKAY, SCIPinfoMessage(), SCIPnlhdlrGetName(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetUbLocal().
|
static |
possibly reevaluates and then returns the activity of the expression
Reevaluate activity if currently stored is not up to date (some bound was changed since last evaluation).
Definition at line 578 of file cons_nonlinear.c.
References assert(), FALSE, forwardPropExpr(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPexprGetActivityTag().
|
static |
callback that creates data that this conshdlr wants to store in an expression
Definition at line 602 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPallocClearBlockMemory, SCIPconshdlrGetData(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPisExprVar(), and var.
|
static |
creates a variable expression or retrieves from hashmap in conshdlr data
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
expr | pointer where to store expression |
var | variable to be stored |
Definition at line 652 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcaptureExpr(), SCIPconshdlrGetData(), SCIPcreateExprVar(), SCIPhashmapGetImage(), and var.
Referenced by getBinaryProductExpr(), getBinaryProductExprDo(), reformulateFactorizedBinaryQuadratic(), SCIP_DECL_EXPR_MAPEXPR(), SCIP_DECL_EXPR_MAPEXPR(), and SCIPaddLinearVarNonlinear().
|
static |
Definition at line 685 of file cons_nonlinear.c.
References assert(), createExprVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIPgetVarExprVar(), and SCIPisExprVar().
|
static |
Definition at line 707 of file cons_nonlinear.c.
References assert(), createExprVar(), NULL, SCIP_CALL, SCIP_OKAY, SCIPgetTransformedVar(), SCIPgetVarExprVar(), SCIPisExprVar(), and var.
|
static |
stores all variable expressions into a given constraint
scip | SCIP data structure |
conshdlr | constraint handler |
consdata | constraint data |
Definition at line 737 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPconshdlrGetData(), SCIPgetExprNVars(), SCIPgetExprVarExprs(), SCIPgetNVars(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapInsert(), and SCIPreallocBlockMemoryArray.
Referenced by canonicalizeConstraints(), getConsRelViolation(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSGETNVARS(), SCIP_DECL_CONSGETVARS(), and SCIP_DECL_CONSINIT().
|
static |
frees all variable expression stored in storeVarExprs()
scip | SCIP data structure |
consdata | constraint data |
Definition at line 801 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemoryArrayNull, and SCIPreleaseExpr().
Referenced by canonicalizeConstraints(), SCIP_DECL_CONSDEACTIVE(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSEXIT(), and SCIPaddExprNonlinear().
|
static |
interval evaluation of variables as used in bound tightening
Returns slightly relaxed local variable bounds of a variable as interval. Does not relax beyond integer values, thus does not relax bounds on integer variables at all.
Definition at line 840 of file cons_nonlinear.c.
References assert(), EPSFRAC, EPSROUND, infty2infty, MAX, MIN, NULL, REALABS, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIP_VARTYPE_IMPLINT, SCIPABORT, SCIPerrorMessage, SCIPinfinity(), SCIPintervalSetBounds(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), and var.
|
static |
compares two nonlinear constraints by its index
Usable as compare operator in array sort functions.
Definition at line 967 of file cons_nonlinear.c.
References assert(), NULL, and SCIPconsGetData().
|
static |
processes variable fixing or bound change event
Definition at line 980 of file cons_nonlinear.c.
References assert(), c, EPSISINT, FALSE, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_EVENTTYPE_BOUNDRELAXED, SCIP_EVENTTYPE_BOUNDTIGHTENED, SCIP_EVENTTYPE_FORMAT, SCIP_EVENTTYPE_TYPECHANGED, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIP_VARTYPE_IMPLINT, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPeventGetNewtype(), SCIPeventGetType(), SCIPeventGetVar(), SCIPexprGetOwnerData(), SCIPexprSetActivity(), SCIPgetStage(), SCIPinProbing(), SCIPisExprVar(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIP_Interval::sup, and TRUE.
|
static |
registers event handler to catch variable events on variable
Additionally, the given constraint is stored in the ownerdata of the variable-expression. When an event occurs, all stored constraints are notified.
scip | SCIP data structure |
eventhdlr | event handler |
expr | variable expression |
cons | nonlinear constraint |
Definition at line 1096 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_EVENTTYPE_TYPECHANGED, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPensureBlockMemoryArray, SCIPexprGetOwnerData(), SCIPgetVarExprVar(), SCIPisExprVar(), and TRUE.
Referenced by catchVarEvents().
|
static |
catch variable events
scip | SCIP data structure |
eventhdlr | event handler |
cons | constraint for which to catch bound change events |
Definition at line 1151 of file cons_nonlinear.c.
References assert(), catchVarEvent(), i, SCIP_Interval::inf, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPexprGetActivityTag(), SCIPexprSetActivity(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPvarGetName(), SCIP_Interval::sup, and TRUE.
Referenced by canonicalizeConstraints(), SCIP_DECL_CONSENABLE(), and SCIP_DECL_CONSINIT().
|
static |
unregisters event handler to catch variable events on variable
The given constraint is removed from the constraints array in the ownerdata of the variable-expression. If this was the last constraint, then the event handler is unregistered for this variable.
scip | SCIP data structure |
eventhdlr | event handler |
expr | variable expression |
cons | expr constraint |
Definition at line 1217 of file cons_nonlinear.c.
References assert(), FALSE, NULL, SCIP_CALL, SCIP_ERROR, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_EVENTTYPE_TYPECHANGED, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIPconsGetName(), SCIPdropVarEvent(), SCIPerrorMessage, SCIPexprGetOwnerData(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPsortedvecFindPtr(), SCIPsortPtr(), SCIPvarGetName(), and TRUE.
Referenced by dropVarEvents().
|
static |
drop variable events
scip | SCIP data structure |
eventhdlr | event handler |
cons | constraint for which to drop bound change events |
Definition at line 1283 of file cons_nonlinear.c.
References assert(), dropVarEvent(), FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), and SCIPdebugMsg.
Referenced by canonicalizeConstraints(), SCIP_DECL_CONSDEACTIVE(), SCIP_DECL_CONSDISABLE(), and SCIP_DECL_CONSEXIT().
|
static |
creates and captures a nonlinear constraint
scip | SCIP data structure |
conshdlr | constraint handler |
cons | pointer to hold the created constraint |
name | name of constraint |
expr | expression of constraint (must not be NULL) |
lhs | left hand side of constraint |
rhs | right hand side of constraint |
copyexpr | whether to copy the expression or reuse the given expr (capture it) |
initial | should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'. |
separate | should the constraint be separated during LP processing? Usually set to TRUE. |
enforce | should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints. |
check | should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints. |
propagate | should the constraint be propagated during node processing? Usually set to TRUE. |
local | is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. |
modifiable | is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint. |
dynamic | is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints. |
removable | should 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'. |
Definition at line 1324 of file cons_nonlinear.c.
References assert(), FALSE, NULL, propagate, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_UNKNOWN, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_Real, SCIPallocClearBlockMemory, SCIPcaptureExpr(), SCIPconshdlrGetData(), SCIPcreateCons(), SCIPduplicateExpr(), SCIPerrorMessage, and SCIPgetDepth().
Referenced by SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), SCIP_DECL_CONSTRANS(), SCIPcreateConsNonlinear(), and SCIPcreateConsQuadraticNonlinear().
|
static |
returns absolute violation for auxvar relation in an expression w.r.t. original variables
Assume the expression is f(x), where x are original (i.e., not auxiliary) variables. Assume that f(x) is associated with auxiliary variable z.
If there are negative locks, then return the violation of z ≤ f(x) and sets violover
to TRUE. If there are positive locks, then return the violation of z ≥ f(x) and sets violunder
to TRUE. Of course, if there both negative and positive locks, then return the violation of z = f(x). If f could not be evaluated, then return SCIPinfinity() and set both violover
and violunder
to TRUE.
scip | SCIP data structure |
expr | expression |
sol | solution that has been evaluated |
violunder | buffer to store whether z >= f(x) is violated, or NULL |
violover | buffer to store whether z <= f(x) is violated, or NULL |
Definition at line 1415 of file cons_nonlinear.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPexprGetEvalValue(), SCIPexprGetOwnerData(), SCIPgetSolVal(), SCIPinfinity(), sol, and TRUE.
Referenced by analyzeViolation(), enforceExpr(), and SCIPgetExprAbsOrigViolationNonlinear().
|
static |
returns absolute violation for auxvar relation in an expression w.r.t. auxiliary variables
Assume the expression is f(w), where w are auxiliary variables that were introduced by some nlhdlr. Assume that f(w) is associated with auxiliary variable z.
If there are negative locks, then return the violation of z ≤ f(w) and sets violover
to TRUE. If there are positive locks, then return the violation of z ≥ f(w) and sets violunder
to TRUE. Of course, if there both negative and positive locks, then return the violation of z = f(w). If f could not be evaluated, then return SCIPinfinity() and set both violover
and violunder
to TRUE.
scip | SCIP data structure |
expr | expression |
auxvalue | value of f(w) |
sol | solution that has been evaluated |
violunder | buffer to store whether z >= f(w) is violated, or NULL |
violover | buffer to store whether z <= f(w) is violated, or NULL |
Definition at line 1481 of file cons_nonlinear.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_INVALID, SCIP_Real, SCIPexprGetOwnerData(), SCIPgetSolVal(), SCIPinfinity(), sol, and TRUE.
Referenced by analyzeViolation(), enforceExpr(), SCIPgetExprAbsAuxViolationNonlinear(), SCIPgetExprRelAuxViolationNonlinear(), and SCIPprocessRowprepNonlinear().
|
static |
computes violation of a constraint
scip | SCIP data structure |
cons | constraint |
sol | solution or NULL if LP solution should be used |
soltag | tag that uniquely identifies the solution (with its values), or 0. |
Definition at line 1538 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPevalExpr(), SCIPexprGetEvalValue(), SCIPinfinity(), SCIPisInfinity(), and sol.
Referenced by consEnfo(), consSepa(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOPS(), SCIPgetAbsViolationNonlinear(), and SCIPgetRelViolationNonlinear().
returns absolute violation of a constraint
cons | constraint |
Definition at line 1577 of file cons_nonlinear.c.
References assert(), MAX3, NULL, SCIP_Real, and SCIPconsGetData().
Referenced by analyzeViolation(), enforceConstraints(), getConsRelViolation(), isConsViolated(), registerBranchingCandidatesAllUnfixed(), SCIP_DECL_CONSCHECK(), and SCIPgetAbsViolationNonlinear().
|
static |
computes relative violation of a constraint
scip | SCIP data structure |
cons | constraint |
viol | buffer to store violation |
sol | solution or NULL if LP solution should be used |
soltag | tag that uniquely identifies the solution (with its values), or 0 |
Definition at line 1596 of file cons_nonlinear.c.
References assert(), getConsAbsViolation(), i, MAX, NULL, REALABS, SCIP_CALL, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPevalExprGradient(), SCIPexprGetDerivative(), SCIPexprGetDiffTag(), SCIPexprGetEvalValue(), SCIPisInfinity(), sol, and storeVarExprs().
Referenced by analyzeViolation(), collectBranchingCandidates(), enforceConstraints(), and SCIPgetRelViolationNonlinear().
returns whether constraint is currently violated
scip | SCIP data structure |
cons | constraint |
Definition at line 1696 of file cons_nonlinear.c.
References getConsAbsViolation(), SCIP_Bool, and SCIPfeastol().
Referenced by analyzeViolation(), collectBranchingCandidates(), consEnfo(), consSepa(), enforceConstraints(), registerBranchingCandidates(), registerBranchingCandidatesAllUnfixed(), SCIP_DECL_CONSCHECK(), and SCIP_DECL_CONSENFOPS().
checks for a linear variable that can be increased or decreased without harming feasibility
scip | SCIP data structure |
cons | constraint |
Definition at line 1706 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_LOCKTYPE_MODEL, SCIP_Real, SCIPconsGetData(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetVarExprVar(), SCIPisExprSum(), SCIPisExprVar(), SCIPisInfinity(), SCIPvarGetName(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), and var.
Referenced by initSolve(), SCIPgetLinvarMayDecreaseNonlinear(), and SCIPgetLinvarMayIncreaseNonlinear().
|
static |
Given a solution where every nonlinear constraint is either feasible or can be made feasible by moving a 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.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
sol | solution to process |
success | buffer to store whether we succeeded to construct a solution that satisfies all provided constraints |
Definition at line 1802 of file cons_nonlinear.c.
References assert(), c, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_SOLVED, SCIPceil(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPcreateLPSol(), SCIPcreateSolCopy(), SCIPdebugMsg, SCIPfeastol(), SCIPfloor(), SCIPfreeSol(), SCIPgetSolTransObj(), SCIPgetSolVal(), SCIPgetStage(), SCIPgetUpperbound(), SCIPheurGetName(), SCIPheurPassSolTrySol(), SCIPincSolVal(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPisSumLT(), SCIPisZero(), SCIPsolGetHeur(), SCIPunlinkSol(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), sol, TRUE, and var.
Referenced by SCIP_DECL_CONSCHECK().
|
static |
notify nonlinear handlers to add linearization in new solution that has been found
The idea is that nonlinear handlers add globally valid tight estimators in a given solution as cuts to the cutpool.
Essentially we want to ensure that the LP relaxation is tight in the new solution, if possible. As the nonlinear handlers define the extended formulation, they should know whether it is possible to generate a cut that is valid and supporting in the given solution. For example, for convex constraints, we achieve this by linearizing. For SOC, we also linearize, but on a a convex reformulation.
Since linearization may happen in auxiliary variables, we ensure that auxiliary variables are set to the eval-value of its expression, i.e., we change sol so it is also feasible in the extended formulation.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints |
nconss | number of constraints |
sol | reference point where to estimate |
solisbest | whether solution is best |
Definition at line 1959 of file cons_nonlinear.c.
References assert(), c, ENFOLOG, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_LEAVEEXPR, SCIP_INVALID, SCIP_Longint, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsEnabled(), SCIPconsIsSeparationEnabled(), SCIPcreateExpriter(), SCIPevalExpr(), SCIPexprGetEvalTag(), SCIPexprGetEvalValue(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetStagesDFS(), SCIPfreeExpriter(), SCIPgetExprNewSoltag(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPheurGetName(), SCIPinfoMessage(), SCIPprintCons(), SCIPsetSolVal(), SCIPsolGetHeur(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sol, and var.
Referenced by SCIP_DECL_EVENTEXEC().
|
static |
processes the event that a new primal solution has been found
Definition at line 2051 of file cons_nonlinear.c.
References assert(), notifyNlhdlrNewsol(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_FORMAT, SCIP_EVENTTYPE_SOLFOUND, SCIP_OKAY, SCIPconshdlrGetConss(), SCIPconshdlrGetData(), SCIPconshdlrGetNConss(), SCIPdebugMsg, SCIPeventGetSol(), SCIPeventGetType(), SCIPheurGetName(), SCIPsolGetHeur(), and sol.
|
static |
tightens the bounds of the auxiliary variable associated with an expression (or original variable if being a variable-expression) according to given bounds
The given bounds may very well be the exprs activity (when called from forwardPropExpr()), but can also be some tighter bounds (when called from SCIPtightenExprIntervalNonlinear()).
Nothing will happen if SCIP is not in presolve or solve.
scip | SCIP data structure |
conshdlr | constraint handler |
expr | expression whose auxvar is to be tightened |
bounds | bounds to be used for tightening (must not be empty) |
cutoff | buffer to store whether a cutoff was detected |
ntightenings | buffer to add the total number of tightenings, or NULL |
Definition at line 2096 of file cons_nonlinear.c.
References assert(), cutoff, FALSE, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPgetExprAuxVarNonlinear(), SCIPintervalIsEmpty(), SCIPisEQ(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIP_Interval::sup, and var.
Referenced by createAuxVar(), forwardPropExpr(), and SCIPtightenExprIntervalNonlinear().
|
static |
returns whether intersecting oldinterval
with newinterval
would provide a properly smaller interval
If subsetsufficient
is TRUE, then the intersection being smaller than oldinterval is sufficient.
If subsetsufficient
is FALSE, then we require
scip | SCIP data structure |
subsetsufficient | whether the intersection being a proper subset of oldinterval is sufficient |
newinterval | new interval |
oldinterval | old interval |
Definition at line 2465 of file cons_nonlinear.c.
References assert(), FALSE, SCIP_Interval::inf, MAX, MIN, NULL, SCIP_Bool, SCIP_INTERVAL_INFINITY, SCIPintervalIsEmpty(), SCIPintervalIsSubsetEQ(), SCIPisEQ(), SCIPisLbBetter(), SCIPisUbBetter(), SCIP_Interval::sup, and TRUE.
Referenced by SCIPtightenExprIntervalNonlinear().
|
static |
propagates bounds for each sub-expression in the reversepropqueue
by starting from the root expressions
The expression will be traversed in breadth first search by using this queue.
*infeasible
= TRUE will only empty the queue. scip | SCIP data structure |
conshdlr | constraint handler |
infeasible | buffer to update whether an expression's bounds were propagated to an empty interval |
ntightenings | buffer to store the number of (variable) tightenings |
Definition at line 2513 of file cons_nonlinear.c.
References assert(), c, FALSE, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_OKAY, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPexprGetActivity(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprGetOwnerData(), SCIPexprhdlrGetName(), SCIPexprhdlrHasReverseProp(), SCIPfreeBufferArray, SCIPgetExprBoundsNonlinear(), SCIPintervalIsEmpty(), SCIPintervalIsEntire(), SCIPnlhdlrGetName(), SCIPprintExpr(), SCIPqueueIsEmpty(), SCIPqueueRemove(), SCIPtightenExprIntervalNonlinear(), SCIP_Interval::sup, and TRUE.
Referenced by propConss(), and propExprDomains().
|
static |
calls domain propagation for a given set of constraints
The algorithm alternates calls of forward and reverse propagation. Forward propagation ensures that activity of expressions is up to date. Reverse propagation tries to derive tighter variable bounds by reversing the activity computation, using the constraints [lhs,rhs] interval as starting point.
The propagation algorithm works as follows:
TODO should we distinguish between expressions where activity information is used for separation and those where not, e.g., try less to propagate on convex constraints?
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to propagate |
nconss | total number of constraints |
force | force tightening even if below bound strengthening tolerance |
result | pointer to store the result |
nchgbds | buffer to add the number of changed bounds |
Definition at line 2674 of file cons_nonlinear.c.
References assert(), cutoff, FALSE, forwardPropExpr(), i, NULL, result, reversePropQueue(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_EXPRITER_BFS, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsPropagationEnabled(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPexprGetActivity(), SCIPexprGetOwnerData(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfreeExpriter(), SCIPintervalIsEmpty(), SCIPintervalSetBounds(), SCIPisInfinity(), SCIPqueueIsEmpty(), SCIPtightenExprIntervalNonlinear(), and TRUE.
Referenced by consEnfo(), SCIP_DECL_CONSENFOPS(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
|
static |
calls the reverseprop callbacks of all nlhdlrs in all expressions in all constraints using activity as bounds
This is meant to propagate any domain restrictions on functions onto variable bounds, if possible.
Assumes that activities are still valid and curpropboundstag does not need to be increased. Therefore, a good place to call this function is immediately after propConss() or after forwardPropExpr() if outside propagation.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to propagate |
nconss | total number of constraints |
result | pointer to store the result |
nchgbds | buffer to add the number of changed bounds |
Definition at line 2878 of file cons_nonlinear.c.
References assert(), c, cutoff, FALSE, NULL, result, reversePropQueue(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_EXPRITER_DFS, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsPropagationEnabled(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprGetActivity(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), and SCIPqueueIsEmpty().
Referenced by initSepa(), and SCIP_DECL_CONSPRESOL().
|
static |
propagates variable locks through expression and adds locks to variables
scip | SCIP data structure |
expr | expression |
nlockspos | number of positive locks |
nlocksneg | number of negative locks |
Definition at line 2991 of file cons_nonlinear.c.
References assert(), i, SCIP_EXPRITER_USERDATA::intvals, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_EXPRITER_VISITINGCHILD, SCIP_MONOTONE_CONST, SCIP_MONOTONE_DEC, SCIP_MONOTONE_INC, SCIP_MONOTONE_UNKNOWN, SCIP_OKAY, SCIPABORT, SCIPaddVarLocks(), SCIPallocBlockMemoryArray, SCIPcreateExpriter(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprGetOwnerData(), SCIPexprhdlrHasMonotonicity(), SCIPexpriterGetChildIdxDFS(), SCIPexpriterGetCurrent(), SCIPexpriterGetCurrentUserData(), SCIPexpriterGetNext(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetChildUserData(), SCIPexpriterSetCurrentUserData(), SCIPexpriterSetStagesDFS(), SCIPfreeBlockMemoryArray, SCIPfreeExpriter(), SCIPgetVarExprVar(), SCIPisExprVar(), and TRUE.
Referenced by addLocks().
|
static |
main function for adding locks to expressions and variables
Locks for a nonlinear constraint are used to update locks for all sub-expressions and variables. Locks of expressions depend on the monotonicity of expressions w.r.t. their children, e.g., consider the constraint \(x^2 \leq 1\) with \(x \in [-2,-1]\) implies an up-lock for the root expression (pow) and a down-lock for its child \(x\) because \(x^2\) is decreasing on [-2,-1]. Since the monotonicity (and thus the locks) might also depend on variable bounds, the function remembers the computed monotonicity information of each expression until all locks of an expression have been removed, which implies that updating the monotonicity information during the next locking of this expression does not break existing locks.
scip | SCIP data structure |
cons | nonlinear constraint |
nlockspos | number of positive rounding locks |
nlocksneg | number of negative rounding locks |
Definition at line 3144 of file cons_nonlinear.c.
References assert(), NULL, propagateLocks(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), and SCIPisInfinity().
Referenced by canonicalizeConstraints(), presolveMergeConss(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSDEACTIVE(), and SCIP_DECL_CONSLOCK().
|
static |
create a nonlinear row representation of a nonlinear constraint and stores them in consdata
scip | SCIP data structure |
cons | nonlinear constraint |
Definition at line 3192 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_CALL, SCIP_EXPRCURV_UNKNOWN, SCIP_OKAY, SCIP_Real, SCIPaddLinearCoefToNlRow(), SCIPappendExprSumExpr(), SCIPchgNlRowConstant(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPcreateExprSum(), SCIPcreateNlRow(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetVarExprVar(), SCIPisExprSum(), SCIPisExprVar(), SCIPreleaseExpr(), SCIPreleaseNlRow(), and SCIPsetNlRowExpr().
Referenced by initSolve(), and SCIPgetNlRowNonlinear().
|
static |
compares enfodata by enforcement priority of nonlinear handler
If handlers have same enforcement priority, then compare by detection priority, then by name.
Definition at line 3266 of file cons_nonlinear.c.
References assert(), NULL, SCIPnlhdlrGetDetectPriority(), SCIPnlhdlrGetEnfoPriority(), and SCIPnlhdlrGetName().
|
static |
install nlhdlrs in one expression
scip | SCIP data structure |
expr | expression for which to run detection routines |
cons | constraint for which expr == consdata->expr, otherwise NULL |
Definition at line 3291 of file cons_nonlinear.c.
References assert(), FALSE, h, NULL, SCIP_CALL, SCIP_ERROR, SCIP_NLHDLR_METHOD_ACTIVITY, SCIP_NLHDLR_METHOD_ALL, SCIP_NLHDLR_METHOD_NONE, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPallocBlockMemory, SCIPallocBlockMemoryArray, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPensureBlockMemoryArray, SCIPerrorMessage, SCIPexprGetHdlr(), SCIPexprGetOwnerData(), SCIPexprhdlrGetName(), SCIPgetStage(), SCIPnlhdlrGetName(), SCIPnlhdlrIsEnabled(), SCIPreallocBlockMemoryArray, SCIPsortDownPtr(), and TRUE.
Referenced by detectNlhdlrs().
|
static |
detect nlhdlrs that can handle the expressions
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints for which to run nlhdlr detect |
nconss | total number of constraints |
Definition at line 3456 of file cons_nonlinear.c.
References assert(), detectNlhdlr(), FALSE, freeEnfoData(), i, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIP_STAGE_INITSOLVE, SCIP_STAGE_PRESOLVING, SCIP_STAGE_SOLVING, SCIPcomputeExprIntegrality(), SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsPropagated(), SCIPconsIsSeparated(), SCIPcreateExpriter(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), SCIPgetDepth(), SCIPgetStage(), SCIPincrementCurBoundsTagNonlinear(), SCIPregisterExprUsageNonlinear(), and TRUE.
Referenced by initSolve().
|
static |
initializes (pre)solving data of constraints
This initializes data in a constraint that is used for separation, propagation, etc, and assumes that expressions will not be modified. In particular, this function
This function can be called in presolve and solve and can be called several times with different sets of constraints, e.g., it should be called in INITSOL and for constraints that are added during solve.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints |
nconss | number of constraints |
Definition at line 3606 of file cons_nonlinear.c.
References assert(), c, createNlRow(), detectNlhdlrs(), FALSE, findUnlockedLinearVar(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_CONCAVE, SCIP_EXPRCURV_CONVEX, SCIP_EXPRCURV_LINEAR, SCIP_OKAY, SCIP_STAGE_INITSOLVE, SCIP_STAGE_SOLVING, SCIPaddNlRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPdebugMsg, SCIPgetStage(), SCIPhasExprCurvature(), SCIPisInfinity(), SCIPisNLPConstructed(), SCIPsetNlRowCurvature(), and SCIPwarningMessage().
Referenced by canonicalizeConstraints(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_CONSINITSOL(), and SCIP_DECL_CONSLOCK().
|
static |
deinitializes (pre)solving data of constraints
This removes the initialization data created in initSolve().
This function can be called in presolve and solve.
TODO At the moment, it should not be called for a constraint if there are other constraints that use the same expressions but still require their nlhdlr. We should probably only decrement the auxvar and activity usage for the root expr and then proceed as in detectNlhdlrs(), i.e., free enfo data only where none is used.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints |
nconss | number of constraints |
Definition at line 3695 of file cons_nonlinear.c.
References assert(), c, FALSE, freeEnfoData(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRCURV_UNKNOWN, SCIP_EXPRITER_DFS, SCIP_EXPRITER_LEAVEEXPR, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPdelNlRow(), SCIPevalExprActivity(), SCIPexprGetActivityTag(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetStagesDFS(), SCIPfreeExpriter(), SCIPfreeExprQuadratic(), SCIPgetStage(), SCIPreleaseNlRow(), and TRUE.
Referenced by canonicalizeConstraints(), SCIP_DECL_CONSDEACTIVE(), SCIP_DECL_CONSEXITSOL(), and SCIP_DECL_CONSLOCK().
helper method to decide whether a given expression is product of at least two binary variables
scip | SCIP data structure |
expr | expression |
Definition at line 3777 of file cons_nonlinear.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_Real, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetCoefExprProduct(), SCIPgetVarExprVar(), SCIPisEQ(), SCIPisExprProduct(), SCIPisExprVar(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and var.
Referenced by getBilinearBinaryTerms(), and getBinaryProductExpr().
|
static |
helper method to collect all bilinear binary product terms
scip | SCIP data structure |
sumexpr | sum expression |
xs | array to collect first variable of each bilinear binary product |
ys | array to collect second variable of each bilinear binary product |
childidxs | array to store the index of the child of each stored bilinear binary product |
nterms | pointer to store the total number of bilinear binary terms |
Definition at line 3823 of file cons_nonlinear.c.
References assert(), i, isBinaryProduct(), nterms, NULL, SCIP_OKAY, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetVarExprVar(), SCIPisExprSum(), x, and y.
Referenced by getFactorizedBinaryQuadraticExpr().
|
static |
helper method to reformulate \(x_i \sum_j c_{ij} x_j\)
scip | SCIP data structure |
conshdlr | constraint handler |
cons | constraint |
facvar | variable that has been factorized |
vars | variables of sum_j c_ij x_j |
coefs | coefficients of sum_j c_ij x_j |
nvars | total number of variables in sum_j c_ij x_j |
newexpr | pointer to store the new expression |
naddconss | pointer to update the total number of added constraints (might be NULL) |
Definition at line 3873 of file cons_nonlinear.c.
References assert(), createExprVar(), i, MAX, MIN, NULL, nvars, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPconsGetName(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicVarbound(), SCIPcreateVarBasic(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPinfinity(), SCIPisIntegral(), SCIPisZero(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetName(), TRUE, and vars.
Referenced by getFactorizedBinaryQuadraticExpr().
|
static |
helper method to generate an expression for a sum of products of binary variables; note that the method captures the generated expression
scip | SCIP data structure |
conshdlr | constraint handler |
cons | constraint |
sumexpr | expression |
minterms | minimum number of terms in a the sum of x_i sum_j c_j x_j |
newexpr | pointer to store the expression that represents the binary quadratic |
naddconss | pointer to update the total number of added constraints (might be NULL) |
Definition at line 3996 of file cons_nonlinear.c.
References assert(), getBilinearBinaryTerms(), i, MIN, nterms, NULL, nvars, reformulateFactorizedBinaryQuadratic(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPcreateExprSum(), SCIPdebugMsg, SCIPduplicateBufferArray, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetNTotalVars(), SCIPgetNVars(), SCIPgetVars(), SCIPisExprSum(), SCIPreleaseExpr(), SCIPsortDownIntPtr(), SCIPvarGetIndex(), SCIPvarGetName(), TRUE, and vars.
Referenced by presolveBinaryProducts(), and replaceBinaryProducts().
|
static |
helper method to create an AND constraint or varbound constraints for a given binary product expression
scip | SCIP data structure |
conshdlr | constraint handler |
prodexpr | product expression |
newexpr | pointer to store the expression that represents the product |
naddconss | pointer to update the total number of added constraints (might be NULL) |
empathy4and | whether to use an AND constraint, if possible |
Definition at line 4194 of file cons_nonlinear.c.
References assert(), createExprVar(), i, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_IMPLINT, SCIPaddCons(), SCIPaddVar(), SCIPallocBufferArray, SCIPcreateConsBasicAnd(), SCIPcreateConsBasicLinear(), SCIPcreateConsBasicVarbound(), SCIPcreateVarBasic(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPgetVarExprVar(), SCIPinfinity(), SCIPisExprProduct(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetName(), vars, w, x, and y.
Referenced by getBinaryProductExpr().
|
static |
helper method to generate an expression for the product of binary variables; note that the method captures the generated expression
scip | SCIP data structure |
conshdlr | constraint handler |
exprmap | map to remember generated variables for visited product expressions |
prodexpr | product expression |
newexpr | pointer to store the expression that represents the product |
naddconss | pointer to update the total number of added constraints (might be NULL) |
nchgcoefs | pointer to update the total number of changed coefficients (might be NULL) |
Definition at line 4323 of file cons_nonlinear.c.
References assert(), c, createExprVar(), FALSE, getBinaryProductExprDo(), isBinaryProduct(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcaptureExpr(), SCIPcliqueHasVar(), SCIPconshdlrGetData(), SCIPcreateExprSum(), SCIPcreateExprValue(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetVarExprVar(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPreleaseExpr(), SCIPvarGetCliques(), SCIPvarGetNCliques(), TRUE, x, and y.
Referenced by replaceBinaryProducts().
|
static |
helper function to replace binary products in a given constraint
scip | SCIP data structure |
conshdlr | constraint handler |
cons | constraint |
exprmap | map to remember generated variables for visited product expressions |
it | expression iterator |
naddconss | pointer to update the total number of added constraints (might be NULL) |
nchgcoefs | pointer to update the total number of changed coefficients (might be NULL) |
Definition at line 4472 of file cons_nonlinear.c.
References assert(), FALSE, getBinaryProductExpr(), getFactorizedBinaryQuadraticExpr(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPexprGetNChildren(), SCIPexpriterGetChildExprDFS(), SCIPexpriterGetChildIdxDFS(), SCIPexpriterGetNext(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPreleaseExpr(), and SCIPreplaceExprChild().
Referenced by presolveBinaryProducts().
|
static |
reformulates products of binary variables during presolving in the following way:
Let \(\sum_{i,j} Q_{ij} x_i x_j\) be a subexpression that only contains binary variables. Each term \(x_i x_j\) is reformulated with the help of an extra (implicit integer) variable \(z_{ij}\) in {0,1}:
\[ z_{ij} \leq x_i, \qquad z_{ij} \leq x_j, \qquad x_i + x_j - z_{ij} \leq 1. \]
Before reformulating \(x_i x_j\) in this way, it is checked whether there is a clique that contains \(x_i\) and \(x_j\). These cliques allow for a better reformulation. There are four cases:
The reformulation using \(z_{ij}\) or the cliques is implemented in getBinaryProductExpr().
Introducing too many extra variables and constraints can have a negative impact on the performance (e.g., due to slow probing). For this reason, it is checked in getFactorizedBinaryQuadraticExpr() whether \(\sum_{i,j} Q_{ij} x_i x_j\) contains large (≥ reformbinprodsfac
parameter) lower sums of the form \(x_i \sum_j Q_{ij} x_j\). Such a lower sum is reformulated with only one extra variable w_i:
\begin{align} \text{maxact} & := \sum_j \max(0, Q_{ij}), \\ \text{minact} & := \sum_j \min(0, Q_{ij}), \\ \text{minact}\, x_i & \leq w_i, \\ w_i &\leq \text{maxact}\, x_i, \\ \text{minact} &\leq \sum_j Q_{ij} x_j - w_i + \text{minact}\, x_i \\ \text{maxact} &\geq \sum_j Q_{ij} x_j - w_i + \text{maxact}\, x_i \end{align}
We mark \(w_i\) to be implicit integer if all \(Q_{ij}\) are integer. After each replacement of a lower sum, it is checked whether there are enough terms left to factorize other binary variables. Lower sums with a larger number of terms are prioritized.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints |
nconss | total number of constraints |
naddconss | pointer to store the total number of added constraints (might be NULL) |
nchgcoefs | pointer to store the total number of changed coefficients (might be NULL) |
Definition at line 4576 of file cons_nonlinear.c.
References assert(), c, FALSE, getFactorizedBinaryQuadraticExpr(), NULL, replaceBinaryProducts(), SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_VISITINGCHILD, SCIP_OKAY, SCIPblkmem(), SCIPconsGetData(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexpriterInit(), SCIPexpriterSetStagesDFS(), SCIPfreeExpriter(), SCIPgetNBinVars(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPhashmapFree(), and SCIPreleaseExpr().
Referenced by canonicalizeConstraints().
|
static |
scales the sides of the constraint \(\ell \leq \sum_i c_i f_i(x) \leq r\).
Let \(n_+\) the number of positive coefficients \(c_i\) and \(n_-\) be the number of negative coefficients. Then scale by -1 if
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
cons | nonlinear constraint |
changed | buffer to store if the expression of cons changed |
Definition at line 4655 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcaptureExpr(), SCIPconsGetData(), SCIPcreateExprSum(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPisExprSum(), SCIPisInfinity(), SCIPreleaseExpr(), SCIPswapReals(), and TRUE.
Referenced by canonicalizeConstraints().
|
static |
forbid multiaggrations of variables that appear nonlinear in constraints
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints |
nconss | number of constraints |
Definition at line 4738 of file cons_nonlinear.c.
References assert(), c, FALSE, i, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), SCIPgetVarExprVar(), SCIPisExprSum(), SCIPisExprVar(), and SCIPmarkDoNotMultaggrVar().
Referenced by canonicalizeConstraints().
|
static |
simplifies expressions and replaces common subexpressions for a set of constraints
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints |
nconss | total number of constraints |
presoltiming | presolve timing (SCIP_PRESOLTIMING_ALWAYS if not in presolving) |
infeasible | buffer to store whether infeasibility has been detected |
ndelconss | counter to add number of deleted constraints, or NULL |
naddconss | counter to add number of added constraints, or NULL |
nchgcoefs | counter to add number of changed coefficients, or NULL |
Definition at line 4805 of file cons_nonlinear.c.
References addLocks(), assert(), catchVarEvents(), deinitSolve(), dropVarEvents(), FALSE, forbidNonlinearVariablesMultiaggration(), freeVarExprs(), i, initSolve(), NULL, presolveBinaryProducts(), scaleConsSides(), SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_RTOPOLOGIC, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_Real, SCIP_STAGE_PRESOLVING, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsDeleted(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPduplicateBufferArray, SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetStage(), SCIPgetValueExprValue(), SCIPisExprValue(), SCIPisFeasNegative(), SCIPisFeasPositive(), SCIPisInfinity(), SCIPnlhdlrResetNDetectionslast, SCIPreleaseExpr(), SCIPreplaceCommonSubexpressions(), SCIPsimplifyExpr(), SCIPsortPtr(), SCIPstartClock(), SCIPstopClock(), storeVarExprs(), and TRUE.
Referenced by SCIP_DECL_CONSEXITPRE(), and SCIP_DECL_CONSPRESOL().
|
static |
merges constraints that have the same root expression
scip | SCIP data structure |
conss | constraints to process |
nconss | number of constraints |
success | pointer to store whether at least one constraint could be deleted |
Definition at line 5077 of file cons_nonlinear.c.
References addLocks(), assert(), c, FALSE, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPdelCons(), SCIPfreeBufferArray, SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPisInfinity(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
interval evaluation of variables as used in redundancy check
Returns local variable bounds of a variable, relaxed by feastol, as interval.
Definition at line 5180 of file cons_nonlinear.c.
References assert(), infty2infty, NULL, SCIP_INTERVAL_INFINITY, SCIP_Real, SCIPfeastol(), SCIPinfinity(), SCIPintervalSetBounds(), SCIPisInfinity(), SCIPisRelEQ(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and var.
|
static |
removes constraints that are always feasible or very simple
Checks whether the activity of constraint functions is a subset of the constraint sides (relaxed by feastol). To compute the activity, we use forwardPropExpr(), but relax variable bounds by feastol, because solutions to be checked might violate variable bounds by up to feastol, too. This is the main reason why the redundancy check is not done in propConss(), which relaxes variable bounds by epsilon only.
Also removes constraints of the form lhs ≤ variable ≤ rhs.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to propagate |
nconss | total number of constraints |
cutoff | pointer to store whether infeasibility has been identified |
ndelconss | buffer to add the number of deleted constraints |
nchgbds | buffer to add the number of variable bound tightenings |
Definition at line 5243 of file cons_nonlinear.c.
References assert(), cutoff, FALSE, forwardPropExpr(), i, SCIP_Interval::inf, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPexprGetActivity(), SCIPexprGetActivityTag(), SCIPfeastol(), SCIPgetValueExprValue(), SCIPgetVarExprVar(), SCIPintervalIsEmpty(), SCIPintervalIsSubsetEQ(), SCIPintervalSetBounds(), SCIPisExprValue(), SCIPisExprVar(), SCIPisInfinity(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), SCIP_Interval::sup, TRUE, and var.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
tries to automatically convert a nonlinear constraint into a more specific and more specialized constraint
scip | SCIP data structure |
conshdlr | constraint handler data structure |
cons | source constraint to try to convert |
upgraded | buffer to store whether constraint was upgraded |
nupgdconss | buffer to increase if constraint was upgraded |
naddconss | buffer to increase with number of additional constraints created during upgrade |
Definition at line 5412 of file cons_nonlinear.c.
References assert(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddCons(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPdebugPrintCons, SCIPdelCons(), SCIPfreeBufferArray, SCIPreallocBufferArray, SCIPreleaseCons(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
returns whether the variable of a given variable expression is a candidate for presolveSingleLockedVars(), i.e., the variable is only contained in a single nonlinear constraint, has no objective coefficient, has finite variable bounds, and is not binary
scip | SCIP data structure |
expr | variable expression |
Definition at line 5519 of file cons_nonlinear.c.
References assert(), NULL, SCIP_Bool, SCIP_LOCKTYPE_MODEL, SCIP_VARTYPE_BINARY, SCIPexprGetOwnerData(), SCIPgetVarExprVar(), SCIPisEQ(), SCIPisExprVar(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetObj(), SCIPvarGetType(), SCIPvarGetUbGlobal(), and var.
Referenced by presolveSingleLockedVars().
|
static |
removes all variable expressions that are contained in a given expression from a hash map
scip | SCIP data structure |
expr | expression |
it | expression iterator |
exprcands | map to hash variable expressions |
Definition at line 5545 of file cons_nonlinear.c.
References SCIP_CALL, SCIP_OKAY, SCIPexpriterGetNext(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPhashmapExists(), SCIPhashmapRemove(), and SCIPisExprVar().
Referenced by presolveSingleLockedVars().
|
static |
presolving method to fix a variable \(x_i\) to one of its bounds if the variable is only contained in a single nonlinear constraint g(x) ≤ rhs (≥ lhs) if g() is concave (convex) in \(x_i\)
If a continuous variable has bounds [0,1], then the variable type is changed to be binary. Otherwise, a bound disjunction constraint is added.
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
cons | nonlinear constraint |
nchgvartypes | pointer to store the total number of changed variable types |
naddconss | pointer to store the total number of added constraints |
infeasible | pointer to store whether problem is infeasible |
Definition at line 5577 of file cons_nonlinear.c.
References assert(), FALSE, i, isSingleLockedCand(), NULL, removeSingleLockedVars(), SCIP_Bool, SCIP_BOUNDTYPE_LOWER, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPallocBufferArray, SCIPblkmem(), SCIPchgVarType(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPcreateConsBounddisjunction(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterInit(), SCIPexpriterSetStagesDFS(), SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetCoefsExprSum(), SCIPgetExponentExprPow(), SCIPgetVarExprVar(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapInsert(), SCIPisEQ(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprVar(), SCIPisInfinity(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), TRUE, valid, var, and vars.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
presolving method to check if there is a single linear continuous variable that can be made implicit integer
scip | SCIP data structure |
conshdlr | constraint handler |
conss | nonlinear constraints |
nconss | total number of nonlinear constraints |
nchgvartypes | pointer to update the total number of changed variable types |
infeasible | pointer to store whether problem is infeasible |
Definition at line 5781 of file cons_nonlinear.c.
References assert(), c, FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_IMPLINT, SCIPchgVarType(), SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexprIsIntegral(), SCIPexprSetIntegrality(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetNBinVars(), SCIPgetNContVars(), SCIPgetNIntVars(), SCIPgetVarExprVar(), SCIPisEQ(), SCIPisExprSum(), SCIPisExprVar(), SCIPisIntegral(), SCIPvarGetName(), SCIPvarIsIntegral(), and TRUE.
Referenced by SCIP_DECL_CONSPRESOL().
|
static |
creates auxiliary variable for a given expression
scip | SCIP data structure |
expr | expression |
Definition at line 5910 of file cons_nonlinear.c.
References assert(), cutoff, SCIP_Interval::inf, MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_INTERVAL_INFINITY, SCIP_INVALIDCALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPABORT, SCIPaddVar(), SCIPaddVarLocks(), SCIPconshdlrGetData(), SCIPcreateVarBasic(), SCIPdebugAddSolVal, SCIPdebugMsg, SCIPerrorMessage, SCIPexprGetActivity(), SCIPexprGetActivityTag(), SCIPexprGetEvalValue(), SCIPexprGetHdlr(), SCIPexprGetOwnerData(), SCIPexprhdlrGetName(), SCIPexprIsIntegral(), SCIPgetDepth(), SCIPgetStage(), SCIPinfinity(), SCIPintervalIsEmpty(), SCIPintervalSetEntire(), SCIPisExprValue(), SCIPisExprVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarMarkRelaxationOnly(), SCIP_Interval::sup, and tightenAuxVarBounds().
Referenced by initSepa().
|
static |
initializes separation for constraint
scip | SCIP data structure |
conshdlr | nonlinear constraints handler |
conss | constraints |
nconss | number of constraints |
infeasible | pointer to store whether the problem is infeasible or not |
Definition at line 6033 of file cons_nonlinear.c.
References assert(), c, createAuxVar(), FALSE, NULL, propExprDomains(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_EXPRITER_DFS, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPdebugMsg, SCIPevalExpr(), SCIPevalExprActivity(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), SCIPnlhdlrHasInitSepa(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.
Referenced by SCIP_DECL_CONSINITLP().
|
static |
returns whether we are ok to branch on auxiliary variables
Currently returns whether depth of node in B&B tree is at least value of constraints/nonlinear/branching/aux parameter.
scip | SCIP data structure |
conshdlr | constraint handler |
Definition at line 6215 of file cons_nonlinear.c.
References assert(), NULL, SCIP_Bool, SCIPconshdlrGetData(), and SCIPgetDepth().
Referenced by collectBranchingCandidates(), registerBranchingCandidates(), SCIPaddExprsViolScoreNonlinear(), and SCIPaddExprViolScoreNonlinear().
|
static |
gets weight of variable when splitting violation score onto several variables in an expression
scip | SCIP data structure |
conshdlr | expr constraint handler |
var | variable |
sol | current solution |
Definition at line 6232 of file cons_nonlinear.c.
References assert(), MAX, MIN, NULL, SCIP_INVALID, SCIP_Real, SCIPABORT, SCIPconshdlrGetData(), SCIPerrorMessage, SCIPgetSolVal(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), sol, and var.
Referenced by addExprsViolScore().
|
static |
adds violation-branching score to a set of expressions, thereby distributing the score
Each expression must either be a variable expression or have an aux-variable.
If unbounded variables are present, each unbounded var gets an even score. If no unbounded variables, then parameter constraints/nonlinear/branching/violsplit decides weight for each var.
scip | SCIP data structure |
exprs | expressions where to add branching score |
nexprs | number of expressions |
violscore | violation-branching score to add to expression |
sol | current solution |
success | buffer to store whether at least one violscore was added |
Definition at line 6285 of file cons_nonlinear.c.
References assert(), FALSE, getViolSplitWeight(), i, NULL, SCIP_Bool, SCIP_Real, SCIPaddExprViolScoreNonlinear(), SCIPdebugMsg, SCIPexprGetOwnerData(), SCIPgetExprAuxVarNonlinear(), SCIPisEQ(), SCIPisInfinity(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sol, TRUE, and var.
Referenced by SCIPaddExprsViolScoreNonlinear().
|
static |
adds violation-branching score to children of expression for given auxiliary variables
Iterates over the successors of expr
to find expressions that are associated with one of the given auxiliary variables. Adds violation-branching scores to all found exprs by means of SCIPaddExprsViolScoreNonlinear().
scip | SCIP data structure |
expr | expression where to start searching |
violscore | violation score to add to expression |
auxvars | auxiliary variables for which to find expression |
nauxvars | number of auxiliary variables |
sol | current solution (NULL for the LP solution) |
success | buffer to store whether at least one violscore was added |
Definition at line 6371 of file cons_nonlinear.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_BFS, SCIP_OKAY, SCIP_Real, SCIPaddExprsViolScoreNonlinear(), SCIPallocBufferArray, SCIPcreateExpriter(), SCIPdebugMsg, SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPgetExprAuxVarNonlinear(), SCIPsortedvecFindPtr(), SCIPsortPtr(), SCIPvarGetName(), and sol.
Referenced by SCIPprocessRowprepNonlinear().
|
static |
registers all unfixed variables in violated constraints as branching candidates
scip | SCIP data structure |
conshdlr | nonlinear constraints handler |
conss | constraints |
nconss | number of constraints |
nnotify | counter for number of notifications performed |
Definition at line 6436 of file cons_nonlinear.c.
References assert(), c, getConsAbsViolation(), i, isConsViolated(), NULL, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIPaddExternBranchCand(), SCIPconsGetData(), SCIPgetVarExprVar(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetUbLocal(), and var.
Referenced by consEnfo(), and SCIP_DECL_CONSENFOPS().
|
static |
registers all variables in violated constraints with branching scores as external branching candidates
scip | SCIP data structure |
conshdlr | nonlinear constraints handler |
conss | constraints |
nconss | number of constraints |
success | buffer to store whether at least one branching candidate was added |
Definition at line 6486 of file cons_nonlinear.c.
References assert(), branchAuxNonlinear(), c, ENFOLOG, FALSE, i, isConsViolated(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPaddExternBranchCand(), SCIPconsGetData(), SCIPcreateExpriter(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprViolScoreNonlinear(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), TRUE, and var.
Referenced by branching().
|
static |
collect branching candidates from violated constraints
Fills array with expressions that serve as branching candidates. Collects those expressions that have a branching score assigned and stores the score in the auxviol field of the branching candidate.
If branching on aux-variables is allowed, then iterate through expressions of violated constraints, otherwise iterate through variable-expressions only.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
maxrelconsviol | maximal scaled constraint violation |
sol | solution to enforce (NULL for the LP solution) |
soltag | tag of solution |
cands | array where to store candidates, must be at least SCIPgetNVars() long |
ncands | number of candidates found |
Definition at line 6621 of file cons_nonlinear.c.
References assert(), BRANCHCAND::auxviol, branchAuxNonlinear(), c, ENFOLOG, BRANCHCAND::expr, FALSE, BRANCHCAND::fractionality, getConsRelViolation(), i, isConsViolated(), NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprViolScoreNonlinear(), SCIPgetNVars(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPisEQ(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sol, BRANCHCAND::var, and var.
Referenced by branching(), and branchingIntegralOrNonlinear().
|
static |
computes a branching score for a variable that reflects how important branching on this variable would be for improving the dual bound from the LP relaxation
Assume the Lagrangian for the current LP is something of the form L(x,z,lambda) = c'x + sum_i lambda_i (a_i'x - z_i + b_i) + ... where x are the original variables, z the auxiliary variables, and a_i'x - z_i + b_i <= 0 are the rows of the LP.
Assume that a_i'x + b_i <= z_i was derived from some nonlinear constraint f(x) <= z and drop index i. If we could have used not only an estimator, but the actual function f(x), then this would have contributed lambda*(f(x) - z) to the Lagrangian function (though the value of z would be different). Using a lot of handwaving, we claim that lambda_i * (f(x) - a_i'x + b_i) is a value that can be used to quantity how much improving the estimator a'x + b <= z could change the dual bound. If an estimator depended on local bounds, then it could be improved by branching. We use row-is-local as proxy for estimator-depending-on-lower-bounds.
To score a variable, we then sum the values lambda_i * (f(x) - a_i'x + b_i) for all rows in which the variable appears. To scale, we divide by the LP objective value (if >1).
TODO if we branch only on original variables, we neglect here estimators that are build on auxiliary variables; these are affected by the bounds on original variables indirectly (through forward-propagation)
TODO if we branch also on auxiliary variables, then separating z from the x-variables in the row a'x+b <= z should happen; in effect, we should go from the row to the expression for which it was generated and consider only variables that would also be branching candidates
scip | SCIP data structure |
conshdlr | nonlinear constraints handler |
var | variable |
Definition at line 6801 of file cons_nonlinear.c.
References assert(), MAX, NULL, r, REALABS, SCIP_LPSOLSTAT_OPTIMAL, SCIP_Real, SCIP_VARSTATUS_COLUMN, SCIPcolGetNLPNonz(), SCIPcolGetRows(), SCIPcolIsInLP(), SCIPgetHugeValue(), SCIPgetLPObjval(), SCIPgetLPSolstat(), SCIPisFinite, SCIPisHugeValue(), SCIPisZero(), SCIProwGetDualsol(), SCIProwGetName(), SCIProwGetOriginConshdlr(), SCIPvarGetCol(), SCIPvarGetStatus(), and var.
Referenced by scoreBranchingCandidates().
|
static |
computes branching scores (including weighted score) for a set of candidates
For each candidate in the array, compute and store the various branching scores (violation, pseudo-costs, vartype, domainwidth). For pseudo-costs, it's possible that the score is not available, in which case cands[c].pscost will be set to SCIP_INVALID.
For each score, compute the maximum over all candidates.
Then compute for each candidate a "weighted" score using the weights as specified by parameters and the scores as previously computed, but scale each score to be in [0,1], i.e., divide each score by the maximum score of all candidates. Further divide by the sum of all weights where a score was available (even if the score was 0).
For example:
scip | SCIP data structure |
conshdlr | constraint handler |
cands | branching candidates |
ncands | number of candidates |
considerfracnl | whether to consider fractionality for spatial branching candidates |
sol | solution to enforce (NULL for the LP solution) |
Definition at line 6897 of file cons_nonlinear.c.
References assert(), BRANCHCAND::auxviol, c, BRANCHCAND::domain, BRANCHCAND::dual, ENFOLOG, BRANCHCAND::expr, BRANCHCAND::fractionality, getDualBranchscore(), MAX, NULL, BRANCHCAND::pscost, REALABS, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_INVALID, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIP_VARTYPE_INTEGER, SCIPadjustedVarLb(), SCIPadjustedVarUb(), SCIPconshdlrGetData(), SCIPepsilon(), SCIPerrorMessage, SCIPfeasCeil(), SCIPfeasFloor(), SCIPgetBranchingPoint(), SCIPgetBranchScore(), SCIPgetExprAuxVarNonlinear(), SCIPgetNObjVars(), SCIPgetSolVal(), SCIPgetVarPseudocostCountCurrentRun(), SCIPgetVarPseudocostVal(), SCIPinfinity(), SCIPinfoMessage(), SCIPisInfinity(), SCIPround(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbLocal(), sol, BRANCHCAND::var, var, BRANCHCAND::vartype, and BRANCHCAND::weighted.
Referenced by selectBranchingCandidate().
|
static |
compare two branching candidates by their weighted score
if weighted score is equal, use variable index of (aux)var if variables are the same, then use whether variable was added due to nonlinearity or fractionality
Definition at line 7234 of file cons_nonlinear.c.
References BRANCHCAND::expr, NULL, SCIPvarGetIndex(), var, and BRANCHCAND::weighted.
|
static |
picks a candidate from array of branching candidates
scip | SCIP data structure |
conshdlr | constraint handler |
cands | branching candidates |
ncands | number of candidates |
considerfracnl | whether to consider fractionality for spatial branching candidates |
sol | relaxation solution, NULL for LP |
selected | buffer to store selected branching candidates |
Definition at line 7249 of file cons_nonlinear.c.
References assert(), BRANCH_RANDNUMINITSEED, c, ENFOLOG, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPcreateRandom(), SCIPfreeBufferArray, SCIPinfoMessage(), SCIPrandomGetInt(), SCIPsortDown(), SCIPvarGetName(), scoreBranchingCandidates(), sol, TRUE, var, and BRANCHCAND::weighted.
Referenced by branching(), and branchingIntegralOrNonlinear().
|
static |
do spatial branching or register branching candidates
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
maxrelconsviol | maximal scaled constraint violation |
sol | solution to enforce (NULL for the LP solution) |
soltag | tag of solution |
result | pointer to store the result of branching |
Definition at line 7345 of file cons_nonlinear.c.
References assert(), collectBranchingCandidates(), ENFOLOG, BRANCHCAND::expr, NULL, registerBranchingCandidates(), result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_INFEASIBLE, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPallocBufferArray, SCIPbranchVarVal(), SCIPconshdlrGetData(), SCIPfreeBufferArray, SCIPgetBranchingPoint(), SCIPgetNLPBranchCands(), SCIPgetNVars(), SCIPinfoMessage(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), selectBranchingCandidate(), sol, and BRANCHCAND::var.
Referenced by enforceConstraints().
|
static |
call enforcement or estimate callback of nonlinear handler
Calls the enforcement callback, if available. Otherwise, calls the estimate callback, if available, and constructs a cut from the estimator.
If cut is weak, but estimator is not tight, tries to add branching candidates.
scip | SCIP main data structure |
conshdlr | constraint handler |
cons | nonlinear constraint |
nlhdlr | nonlinear handler |
expr | expression |
nlhdlrexprdata | nonlinear handler data of expression |
sol | solution to be separated (NULL for the LP solution) |
auxvalue | current value of expression w.r.t. auxiliary variables as obtained from EVALAUX |
overestimate | whether the expression needs to be over- or underestimated |
separated | whether another nonlinear handler already added a cut for this expression |
allowweakcuts | whether we allow for weak cuts |
inenforcement | whether we are in enforcement (and not just separation) |
branchcandonly | only collect branching candidates, do not separate or propagate |
result | pointer to store the result |
Definition at line 7426 of file cons_nonlinear.c.
References assert(), ENFOLOG, FALSE, NULL, r, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SIDETYPE_LEFT, SCIP_SIDETYPE_RIGHT, SCIPaddRowprepTerm(), SCIPcreatePtrarray(), SCIPfreePtrarray(), SCIPfreeRowprep(), SCIPgetExprAuxVarNonlinear(), SCIPgetPtrarrayMaxIdx(), SCIPgetPtrarrayMinIdx(), SCIPgetPtrarrayVal(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPnlhdlrGetName(), SCIPnlhdlrHasEstimate(), SCIPprocessRowprepNonlinear(), SCIProwprepGetSidetype(), and sol.
Referenced by enforceExpr().
|
static |
tries to enforce violation in an expression by separation, bound tightening, or finding a branching candidate
if not inenforcement, then we should be called by consSepa(), and thus only try separation
scip | SCIP data structure |
conshdlr | nonlinear constraints handler |
cons | nonlinear constraint |
expr | expression |
sol | solution to separate, or NULL if LP solution should be used |
soltag | tag of solution |
allowweakcuts | whether we allow weak cuts |
inenforcement | whether we are in enforcement (and not just separation) |
branchcandonly | only collect branching candidates, do not separate or propagate |
result | pointer to store the result of the enforcing call |
Definition at line 7533 of file cons_nonlinear.c.
References assert(), ENFOLOG, enforceExprNlhdlr(), FALSE, getExprAbsAuxViolation(), getExprAbsOrigViolation(), NULL, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_Longint, SCIP_NLHDLR_METHOD_SEPAABOVE, SCIP_NLHDLR_METHOD_SEPABELOW, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconshdlrGetData(), SCIPevalExpr(), SCIPexprGetActivity(), SCIPexprGetEvalValue(), SCIPexprGetHdlr(), SCIPexprGetOwnerData(), SCIPexprhdlrGetName(), SCIPfeastol(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPisInfinity(), SCIPnlhdlrGetName(), SCIPprintExpr(), sol, and TRUE.
Referenced by enforceConstraint().
|
static |
helper function to enforce a single constraint
scip | SCIP data structure |
conshdlr | constraint handler |
cons | constraint to process |
sol | solution to enforce (NULL for the LP solution) |
soltag | tag of solution |
it | expression iterator that we can just use here |
allowweakcuts | whether to allow weak cuts in this round |
inenforcement | whether to we are in enforcement, and not just separation |
branchcandonly | only collect branching candidates, do not separate or propagate |
result | pointer to update with result of the enforcing call |
success | buffer to store whether some enforcement took place |
Definition at line 7747 of file cons_nonlinear.c.
References assert(), ENFOLOG, enforceExpr(), FALSE, forwardPropExpr(), NULL, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_Longint, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPinfoMessage(), SCIPprintExpr(), sol, and TRUE.
Referenced by enforceConstraints().
|
static |
try to separate violated constraints and, if in enforcement, register branching scores
If branchcandonly=TRUE, then do not separate or propagate, but register branching scores only.
Sets result to
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
sol | solution to enforce (NULL for the LP solution) |
soltag | tag of solution |
inenforcement | whether we are in enforcement, and not just separation |
branchcandonly | only collect branching candidates, do not separate or propagate |
maxrelconsviol | largest scaled violation among all violated expr-constraints, only used if in enforcement |
result | pointer to store the result of the enforcing call |
Definition at line 7867 of file cons_nonlinear.c.
References assert(), branching(), c, ENFOLOG, enforceConstraint(), FALSE, getConsAbsViolation(), getConsRelViolation(), i, isConsViolated(), NULL, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_EXPRITER_DFS, SCIP_INFEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsEnabled(), SCIPconsIsSeparationEnabled(), SCIPcreateExpriter(), SCIPexpriterInit(), SCIPfreeExpriter(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfoMessage(), SCIPprintCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sol, TRUE, and var.
Referenced by branchingIntegralOrNonlinear(), consEnfo(), and consSepa().
|
static |
decide whether to branch on fractional integer or nonlinear variable
The routine collects spatial branching candidates by a call to enforceConstraints(branchcandonly=TRUE) and collectBranchingCandidates(). Then it adds fractional integer variables to the candidate list. Variables that are candidate for both spatial branching and fractionality are considered as two separate candidates. selectBranchingCandidate() then selects a variable for branching from the joined candidate list. If the selected variable is a fractional integer one, then branchintegral=TRUE is returned, otherwise FALSE. Some shortcuts exist for cases where there are no candidates of the one kind or the other.
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
soltag | tag of LP solution |
maxrelconsviol | maximal scaled constraint violation |
branchintegral | buffer to store whether to branch on fractional integer variables first |
cutoff | buffer to store whether infeasibility has been detected |
Definition at line 7998 of file cons_nonlinear.c.
References assert(), BRANCHCAND::auxviol, c, collectBranchingCandidates(), cutoff, ENFOLOG, enforceConstraints(), BRANCHCAND::expr, FALSE, BRANCHCAND::fractionality, lpcands, lpcandsfrac, nlpcands, NULL, result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_ERROR, SCIP_INFEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIP_VARTYPE_INTEGER, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArray, SCIPgetLPBranchCands(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNLPBranchCands(), SCIPgetNVars(), SCIPinfoMessage(), SCIPvarGetName(), SCIPvarGetType(), selectBranchingCandidate(), TRUE, and BRANCHCAND::var.
Referenced by consEnfo().
|
static |
decide whether to consider spatial branching before integrality has been enforced
This decides whether we are still at a phase where we always want to branch on fractional integer variables if any (return TRUE), or whether branchingIntegralOrNonlinear() should be used (return FALSE).
This essentially checks whether the average pseudo cost count exceeds the value of parameter branchmixfractional.
scip | SCIP data structure |
conshdlr | constraint handler |
sol | solution to be enforced |
Definition at line 8110 of file cons_nonlinear.c.
References assert(), FALSE, i, nbinvars, nintvars, NULL, SCIP_Bool, SCIP_BRANCHDIR_DOWNWARDS, SCIP_BRANCHDIR_UPWARDS, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIPconshdlrGetData(), SCIPgetAvgPseudocostCount(), SCIPgetLPSolstat(), SCIPgetNBinVars(), SCIPgetNIntVars(), SCIPgetNLPBranchCands(), SCIPgetSolVal(), SCIPgetVars(), SCIPisFeasIntegral(), SCIPisInfinity(), SCIPvarIsIntegral(), sol, TRUE, and vars.
Referenced by consEnfo().
|
static |
collect (and print (if debugging enfo)) information on violation in expressions
assumes that constraint violations have been computed
scip | SCIP data structure |
conss | constraints |
nconss | number of constraints |
sol | solution to separate, or NULL if LP solution should be used |
soltag | tag of solution |
maxabsconsviol | buffer to store maximal absolute violation of constraints |
maxrelconsviol | buffer to store maximal relative violation of constraints |
minauxviol | buffer to store minimal (nonzero) violation of auxiliaries |
maxauxviol | buffer to store maximal violation of auxiliaries (violation in "extended formulation") |
maxvarboundviol | buffer to store maximal violation of variable bounds |
Definition at line 8185 of file cons_nonlinear.c.
References assert(), c, ENFOLOG, FALSE, getConsAbsViolation(), getConsRelViolation(), getExprAbsAuxViolation(), getExprAbsOrigViolation(), isConsViolated(), MAX, MIN, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_Longint, SCIP_NLHDLR_METHOD_SEPABOTH, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsEnabled(), SCIPconsIsSeparationEnabled(), SCIPcreateExpriter(), SCIPexprGetActivity(), SCIPexprGetEvalValue(), SCIPexprGetOwnerData(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPfreeExpriter(), SCIPgetSolVal(), SCIPgetVarExprVar(), SCIPinfinity(), SCIPinfoMessage(), SCIPisExprVar(), SCIPisInfinity(), SCIPnlhdlrGetName(), SCIPprintExpr(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), sol, and var.
Referenced by consEnfo().
|
static |
enforcement of constraints called by enfolp and enforelax
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
sol | solution to enforce (NULL for the LP solution) |
result | pointer to store the result of the enforcing call |
Definition at line 8361 of file cons_nonlinear.c.
References analyzeViolation(), assert(), branchingIntegralFirst(), branchingIntegralOrNonlinear(), c, computeViolation(), cutoff, ENFOLOG, enforceConstraints(), FALSE, isConsViolated(), MAX, MIN, NULL, propConss(), registerBranchingCandidatesAllUnfixed(), result, SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIP_SOLVELP, SCIPconshdlrGetData(), SCIPepsilon(), SCIPgetCurrentNode(), SCIPgetExprNewSoltag(), SCIPgetLPFeastol(), SCIPgetNLPBranchCands(), SCIPinfoMessage(), SCIPisPositive(), SCIPisZero(), SCIPnodeGetNumber(), SCIPsetLPFeastol(), sol, and TRUE.
Referenced by SCIP_DECL_CONSENFOLP(), and SCIP_DECL_CONSENFORELAX().
|
static |
separation for all violated constraints to be used by SEPA callbacks
scip | SCIP data structure |
conshdlr | constraint handler |
conss | constraints to process |
nconss | number of constraints |
sol | solution to enforce (NULL for the LP solution) |
result | pointer to store the result of the enforcing call |
Definition at line 8587 of file cons_nonlinear.c.
References assert(), c, computeViolation(), ENFOLOG, enforceConstraints(), FALSE, isConsViolated(), NULL, result, SCIP_Bool, SCIP_CALL, SCIP_DIDNOTFIND, SCIP_INVALID, SCIP_Longint, SCIP_OKAY, SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsEnabled(), SCIPconsIsSeparationEnabled(), SCIPgetCurrentNode(), SCIPgetExprNewSoltag(), SCIPinfoMessage(), SCIPnodeGetNumber(), sol, and TRUE.
Referenced by SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
|
static |
hash key retrieval function for bilinear term entries
Definition at line 8637 of file cons_nonlinear.c.
|
static |
returns TRUE iff the bilinear term entries are equal
Definition at line 8653 of file cons_nonlinear.c.
References assert(), NULL, SCIPvarCompare(), SCIP_ConsNonlinear_BilinTerm::x, and SCIP_ConsNonlinear_BilinTerm::y.
|
static |
returns the hash value of the key
Definition at line 8671 of file cons_nonlinear.c.
References assert(), NULL, SCIPhashTwo, SCIPvarCompare(), SCIPvarGetIndex(), SCIP_ConsNonlinear_BilinTerm::x, and SCIP_ConsNonlinear_BilinTerm::y.
|
static |
compare two auxiliary expressions
Compares auxiliary variables, followed by coefficients, and then constants.
Definition at line 8687 of file cons_nonlinear.c.
References SCIP_ConsNonlinear_Auxexpr::auxvar, SCIP_ConsNonlinear_Auxexpr::coefs, SCIP_ConsNonlinear_Auxexpr::cst, i, and SCIPvarCompare().
|
static |
scip | SCIP data structure |
conshdlrdata | nonlinear constraint handler data |
term | bilinear term |
auxexpr | auxiliary expression to add |
added | pointer to store whether auxexpr has been added |
Definition at line 8712 of file cons_nonlinear.c.
References assert(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_BilinTerm::auxexprssize, SCIP_ConsNonlinear_BilinTerm::exprs, FALSE, i, SCIP_ConsNonlinear_BilinTerm::nauxexprs, NULL, SCIP_ConsNonlinear_Auxexpr::overestimate, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPensureBlockMemoryArray, SCIPsortedvecFindPtr(), TRUE, and SCIP_ConsNonlinear_Auxexpr::underestimate.
Referenced by SCIPinsertBilinearTermImplicitNonlinear().
|
static |
iterates through all expressions of all nonlinear constraints and adds the corresponding bilinear terms to the hash table
scip | SCIP data structure |
conshdlr | constraint handler |
conss | nonlinear constraints |
nconss | total number of nonlinear constraints |
Definition at line 8766 of file cons_nonlinear.c.
References assert(), c, FALSE, NULL, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPcreateExpriter(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterRestartDFS(), SCIPexpriterSetStagesDFS(), SCIPfreeExpriter(), SCIPgetExponentExprPow(), SCIPgetExprAuxVarNonlinear(), SCIPgetExprNLocksNegNonlinear(), SCIPgetExprNLocksPosNonlinear(), SCIPinsertBilinearTermExistingNonlinear(), SCIPisExprPower(), SCIPisExprProduct(), x, and y.
Referenced by SCIP_DECL_CONSINITLP(), and SCIPcollectBilinTermsNonlinear().
|
static |
store x, y and the locks in a new bilinear term
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
x | the first variable |
y | the second variable |
nlockspos | number of positive locks of the bilinear term |
nlocksneg | number of negative locks of the bilinear term |
idx | pointer to store the position of the term in bilinterms array |
existing | whether the term exists explicitly in the problem |
Definition at line 8841 of file cons_nonlinear.c.
References assert(), SCIP_ConsNonlinear_BilinTerm::aux, SCIP_ConsNonlinear_BilinTerm::auxexprssize, SCIP_ConsNonlinear_BilinTerm::existing, SCIP_ConsNonlinear_BilinTerm::exprs, SCIP_ConsNonlinear_BilinTerm::nauxexprs, SCIP_ConsNonlinear_BilinTerm::nlocksneg, SCIP_ConsNonlinear_BilinTerm::nlockspos, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPblkmem(), SCIPcaptureVar(), SCIPconshdlrGetData(), SCIPensureBlockMemoryArray, SCIPgetBilinTermIdxNonlinear(), SCIPhashtableCreate(), SCIPhashtableInsert(), SCIPswapPointers(), SCIPvarCompare(), SCIP_ConsNonlinear_BilinTerm::var, SCIP_ConsNonlinear_BilinTerm::x, x, SCIP_ConsNonlinear_BilinTerm::y, and y.
Referenced by SCIPinsertBilinearTermExistingNonlinear(), and SCIPinsertBilinearTermImplicitNonlinear().
|
static |
frees array of bilinear terms and hash table
scip | SCIP data structure |
conshdlrdata | constraint handler data |
Definition at line 8934 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPfreeBlockMemoryArrayNull, SCIPhashtableFree(), and SCIPreleaseVar().
Referenced by SCIP_DECL_CONSEXITSOL().
|
static |
builds LP used to compute facets of the convex envelope of vertex-polyhedral functions
scip | SCIP data structure |
nvars | number of (unfixed) variables in vertex-polyhedral functions |
lp | pointer to store created LP |
Definition at line 9004 of file cons_nonlinear.c.
References a, assert(), i, NULL, nvars, obj, POWEROFTWO, SCIP_CALL, SCIP_MAXVERTEXPOLYDIM, SCIP_OBJSEN_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetMessagehdlr(), SCIPlpiChgSides(), SCIPlpiCreate(), SCIPlpiInfinity(), and SCIPlpiLoadColLP().
Referenced by computeVertexPolyhedralFacetLP().
|
static |
the given facet might not be a valid under(over)estimator, because of numerics and bad fixings; we compute \(\max_{v \in V} f(v) - (\alpha v + \beta) \) ( \(\max_{v \in V} \alpha v + \beta - f(v) \)) where \( V \) is the set of vertices of the domain
scip | SCIP data structure |
overestimate | whether we check for an over or underestimator |
funvals | array containing the evaluation of the function at all corners, length: 2^nvars |
box | box for which facet was computed, length: 2*nallvars |
nallvars | number of all variables |
nvars | number of unfixed variables |
nonfixedpos | indices of unfixed variables, length: nvars |
facetcoefs | current facet candidate's coefficients, length: nallvars |
facetconstant | current facet candidate's constant, length: nallvars |
Definition at line 9115 of file cons_nonlinear.c.
References assert(), i, MAX, NULL, nvars, POWEROFTWO, SCIP_Bool, SCIP_Real, and SCIPdebugMsg.
Referenced by SCIPcomputeFacetVertexPolyhedralNonlinear().
|
static |
computes a facet of the convex or concave envelope of a vertex polyhedral function by solving an LP
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
overestimate | whether to compute facet of concave (TRUE) or convex (FALSE) envelope |
xstar | point to be separated |
box | box where to compute facet: should be lb_1, ub_1, lb_2, ub_2... |
nallvars | half of the length of box |
nonfixedpos | indices of nonfixed variables |
funvals | values of function in all corner points (w.r.t. nonfixed variables) |
nvars | number of nonfixed variables |
targetvalue | target value: no need to compute facet if value in xstar would be worse than this value |
success | buffer to store whether a facet could be computed successfully |
facetcoefs | buffer to store coefficients of facet defining inequality; must be an zero'ed array of length at least nallvars |
facetconstant | buffer to store constant part of facet defining inequality |
Definition at line 9203 of file cons_nonlinear.c.
References assert(), buildVertexPolyhedralSeparationLP(), FALSE, i, MAX, MIN, NULL, nvars, POWEROFTWO, REALABS, SCIP_Bool, SCIP_CALL, SCIP_LPERROR, SCIP_LPPAR_DUALFEASTOL, SCIP_LPPAR_FEASTOL, SCIP_LPPAR_LPINFO, SCIP_LPPAR_LPITLIM, SCIP_LPPAR_OBJLIM, SCIP_MAXVERTEXPOLYDIM, SCIP_OBJSEN_MAXIMIZE, SCIP_OBJSEN_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPcreateRandom(), SCIPdebugMsg, SCIPdebugMsgPrint, SCIPepsilon(), SCIPfeastol(), SCIPfreeBufferArray, SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPlpiChgObj(), SCIPlpiChgObjsen(), SCIPlpiChgSides(), SCIPlpiGetNCols(), SCIPlpiGetNRows(), SCIPlpiGetSol(), SCIPlpiIsDualFeasible(), SCIPlpiSetIntpar(), SCIPlpiSetRealpar(), SCIPlpiSolveDual(), SCIPlpiSolvePrimal(), SCIPrandomGetReal(), TRUE, and VERTEXPOLY_RANDNUMINITSEED.
Referenced by SCIPcomputeFacetVertexPolyhedralNonlinear().
|
static |
computes a facet of the convex or concave envelope of a univariate vertex polyhedral function
In other words, compute the line that passes through two given points.
scip | SCIP data structure |
left | left coordinate |
right | right coordinate |
funleft | value of function in left coordinate |
funright | value of function in right coordinate |
success | buffer to store whether a facet could be computed successfully |
facetcoef | buffer to store coefficient of facet defining inequality |
facetconstant | buffer to store constant part of facet defining inequality |
Definition at line 9459 of file cons_nonlinear.c.
References assert(), NULL, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPisFinite, SCIPisInfinity(), SCIPisLE(), and TRUE.
Referenced by SCIPcomputeFacetVertexPolyhedralNonlinear().
|
static |
given three points, constructs coefficient of equation for hyperplane generated by these three points
Three points a, b, and c are given. Computes coefficients alpha, beta, gamma, and delta, such that a, b, and c, satisfy alpha * x1 + beta * x2 + gamma * x3 = delta and gamma >= 0.0.
scip | SCIP data structure |
a1 | first coordinate of a |
a2 | second coordinate of a |
a3 | third coordinate of a |
b1 | first coordinate of b |
b2 | second coordinate of b |
b3 | third coordinate of b |
c1 | first coordinate of c |
c2 | second coordinate of c |
c3 | third coordinate of c |
alpha | coefficient of first coordinate |
beta | coefficient of second coordinate |
gamma_ | coefficient of third coordinate |
delta | constant right-hand side |
Definition at line 9495 of file cons_nonlinear.c.
References alpha, assert(), NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPbuffer(), SCIPdebugMsg, SCIPisInfinity(), SCIPisRelEQ(), SCIPlapackSolveLinearEquations(), and x.
Referenced by computeVertexPolyhedralFacetBivariate().
|
static |
computes a facet of the convex or concave envelope of a bivariate vertex polyhedral function
scip | SCIP data structure |
overestimate | whether to compute facet of concave (TRUE) or convex (FALSE) envelope |
p1 | first vertex of box |
p2 | second vertex of box |
p3 | third vertex of box |
p4 | forth vertex of box |
p1val | value in p1 |
p2val | value in p2 |
p3val | value in p3 |
p4val | value in p4 |
xstar | point to be separated |
targetvalue | target value: no need to compute facet if value in xstar would be worse than this value |
success | buffer to store whether a facet could be computed successfully |
facetcoefs | buffer to store coefficients of facet defining inequality; must be an array of length at least 2 |
facetconstant | buffer to store constant part of facet defining inequality |
Definition at line 9606 of file cons_nonlinear.c.
References alpha, assert(), computeHyperplaneThreePoints(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPisFinite, SCIPisNegative(), SCIPisZero(), and TRUE.
Referenced by SCIPcomputeFacetVertexPolyhedralNonlinear().
|
static |
ensures that we can store information about open expressions (i.e., not fully encoded in the symmetry detection graph yet) in an array
scip | SCIP pointer |
openidx | address of openidx array |
nelems | number of elements that need to be stored |
maxnelems | pointer to store maximum number that can be stored |
Definition at line 9749 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBufferArray.
Referenced by addSymmetryInformation().
|
static |
ensures that we can store information about local variables in an array
scip | SCIP pointer |
vars | address of variable array |
vals | address of value array |
nelems | number of elements that need to be stored |
maxnelems | pointer to store maximum number that can be stored |
Definition at line 9777 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcalcMemGrowSize(), SCIPreallocBufferArray, and vars.
Referenced by addSymmetryInformation(), tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperatorSum(), and tryAddGadgetEvenOperatorVariable().
|
static |
tries to add gadget for finding signed permutations of bilinear products
If a product has exactly two children being variables, negating both simultanteoulsy is a signed permutation.
scip | SCIP pointer |
expr | product expression for which gadget is tried to be added |
cons | constraint containing product expression |
graph | symmetry detection graph to be extended by gadget |
parentidx | index of parent node in symmetry detection graph for gadget |
hasparentcoef | whether the parent gives a coefficient to the expression |
parentcoef | the parent coefficient (if it exists) |
consvars | pointer to allocated array to store temporary variables |
consvals | pointer to allocated arrat to store temporary values |
maxnconsvars | pointer to maximum number consvars/consvals can hold |
handledexprs | hashset to store handled expressions |
success | pointer to store whether gadget could be added successfully |
Definition at line 9812 of file cons_nonlinear.c.
References assert(), ensureLocVarsArraySize(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPblkmem(), SCIPconsIsTransformed(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPfreeSymDataExpr(), SCIPgetSymActiveVariables(), SCIPgetSymDataExpr(), SCIPgetSymExprdataConstants(), SCIPgetSymExprdataNConstants(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphNNodes(), SCIPgetSymgraphVarnodeidx(), SCIPgetSymOpNodeType(), SCIPgetVarExprVar(), SCIPhashsetInsert(), SCIPisExprProduct(), SCIPisExprVar(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SYM_SYMTYPE_SIGNPERM, and TRUE.
Referenced by addSymmetryInformation().
|
static |
returns whether an operator is even and, if yes, stores data about operator
scip | SCIP pointer |
expr | expression corresponding to operator |
hasvalue | pointer to store whether even operator has a value needed for symmetry computation |
value | pointer to store value for symmetry computation |
Definition at line 9953 of file cons_nonlinear.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPfreeSymDataExpr(), SCIPgetSymDataExpr(), SCIPgetSymExprdataConstants(), SCIPgetSymExprdataNConstants(), SCIPisEQ(), SCIPisExprAbs(), SCIPisExprCos(), SCIPisExprPower(), SCIPisExprSignpower(), SCIPisIntegral(), SCIPisLE(), and TRUE.
Referenced by tryAddGadgetEvenOperator().
returns whether a variable is centered at 0
scip | SCIP pointer |
var | variable to be checked |
Definition at line 10030 of file cons_nonlinear.c.
References assert(), FALSE, NULL, SCIP_Bool, SCIPisEQ(), SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), TRUE, and var.
Referenced by tryAddGadgetEvenOperatorSum(), and tryAddGadgetEvenOperatorVariable().
|
static |
tries to add gadget for finding signed permutation of even univariate operators with variable child
scip | SCIP pointer |
evenopexpr | even operator expression for which gadget is tried to be added |
child | child expression of evenopexpr |
cons | constraint containing expression |
graph | symmetry detection graph to be extended by gadget |
parentidx | index of parent node in symmetry detection graph for gadget |
hasparentcoef | whether the parent gives a coefficient to the expression |
parentcoef | the parent coefficient (if it exists) |
hassymval | whether evenopexpr has a value needed for symmetry detection |
symval | value needed for symmetry detection (if hassymval is TRUE) |
consvars | pointer to allocated array to store temporary variables |
consvals | pointer to allocated arrat to store temporary values |
maxnconsvars | pointer to maximum number consvars/consvals can hold |
success | pointer to store whether gadget could be added successfully |
Definition at line 10052 of file cons_nonlinear.c.
References assert(), ensureLocVarsArraySize(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPconsIsTransformed(), SCIPexprGetHdlr(), SCIPexprhdlrGetName(), SCIPgetSymActiveVariables(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphVarnodeidx(), SCIPgetSymOpNodeType(), SCIPgetVarExprVar(), SCIPisExprVar(), SCIPisZero(), SYM_SYMTYPE_SIGNPERM, TRUE, var, and varIsCenteredAt0().
Referenced by tryAddGadgetEvenOperator().
|
static |
tries to add gadget for finding signed permutation of even univariate operators with sum child
scip | SCIP pointer |
evenopexpr | even operator expression for which gadget is tried to be added |
child | child expression of evenopexpr |
cons | constraint containing expression |
graph | symmetry detection graph to be extended by gadget |
parentidx | index of parent node in symmetry detection graph for gadget |
hasparentcoef | whether the parent gives a coefficient to the expression |
parentcoef | the parent coefficient (if it exists) |
hassymval | whether evenopexpr has a value needed for symmetry detection |
symval | value needed for symmetry detection (if hassymval is TRUE) |
consvars | pointer to allocated array to store temporary variables |
consvals | pointer to allocated arrat to store temporary values |
maxnconsvars | pointer to maximum number consvars/consvals can hold |
handledexprs | hashset to store handled expressions |
success | pointer to store whether gadget could be added successfully |
Definition at line 10137 of file cons_nonlinear.c.
References ABS, assert(), ensureLocVarsArraySize(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPblkmem(), SCIPconsIsTransformed(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPgetCoefsExprSum(), SCIPgetConstantExprSum(), SCIPgetSymActiveVariables(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphVarnodeidx(), SCIPgetSymOpNodeType(), SCIPgetVarExprVar(), SCIPhashsetInsert(), SCIPisExprSum(), SCIPisExprVar(), SCIPisZero(), SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_SIGNPERM, TRUE, var, and varIsCenteredAt0().
Referenced by tryAddGadgetEvenOperator().
|
static |
tries to add gadget for finding signed permutations of even univariate operators
We handle two cases. First, if a univariate operator is even and has a variable as child, negating the child is signed permutation. Second, the univariate operator is even and has a weighted sum of two variables as child.
scip | SCIP pointer |
expr | expression for which gadget is tried to be added |
cons | constraint containing expression |
graph | symmetry detection graph to be extended by gadget |
parentidx | index of parent node in symmetry detection graph for gadget |
hasparentcoef | whether the parent gives a coefficient to the expression |
parentcoef | the parent coefficient (if it exists) |
consvars | pointer to allocated array to store temporary variables |
consvals | pointer to allocated arrat to store temporary values |
maxnconsvars | pointer to maximum number consvars/consvals can hold |
handledexprs | hashset to store handled expressions |
success | pointer to store whether gadget could be added successfully |
Definition at line 10279 of file cons_nonlinear.c.
References assert(), FALSE, isEvenOperator(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPgetSymgraphNNodes(), SCIPhashsetInsert(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPisExprVaridx(), tryAddGadgetEvenOperatorSum(), and tryAddGadgetEvenOperatorVariable().
Referenced by addSymmetryInformation().
|
static |
compares two variable pointers
Definition at line 10347 of file cons_nonlinear.c.
References assert(), NULL, SCIPvarGetIndex(), and vars.
gets domain center of a variable which has not semi-infinite domain
scip | SCIP pointer |
var | variable |
Definition at line 10371 of file cons_nonlinear.c.
References assert(), SCIP_Real, SCIPisInfinity(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), and var.
Referenced by tryAddGadgetSquaredDifference().
|
static |
tries to add gadget for finding signed permutations for squared differences in a sum expression
scip | SCIP pointer |
sumexpr | sum expression |
cons | constraint containing the sum expression |
graph | symmetry detection graph to be extended by gadget |
sumnodeidx | index of sum node in symmetry detection graph for gadget |
consvars | pointer to allocated array to store temporary variables |
consvals | pointer to allocated arrat to store temporary values |
maxnconsvars | pointer to maximum number consvars/consvals can hold |
handledexprs | hashset to store handled expressions |
Definition at line 10392 of file cons_nonlinear.c.
References assert(), FALSE, getDomainCenter(), i, nterms, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPallocBufferArray, SCIPallocClearBufferArray, SCIPblkmem(), SCIPconsIsTransformed(), SCIPexprGetChildren(), SCIPexprGetNChildren(), SCIPfreeBufferArray, SCIPfreeBufferArrayNull, SCIPfreeSymDataExpr(), SCIPgetCoefsExprSum(), SCIPgetSymActiveVariables(), SCIPgetSymDataExpr(), SCIPgetSymExprdataConstants(), SCIPgetSymExprdataNConstants(), SCIPgetSymgraphNegatedVarnodeidx(), SCIPgetSymgraphVarnodeidx(), SCIPgetVarExprVar(), SCIPhashsetInsert(), SCIPisEQ(), SCIPisExprPower(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprVar(), SCIPisInfinity(), SCIPround(), SCIPsort(), SCIPvarGetIndex(), SCIPvarGetLbGlobal(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SYM_CONSOPTYPE_SQDIFF, SYM_SYMTYPE_SIGNPERM, TRUE, and var.
Referenced by addSymmetryInformation().
|
static |
adds symmetry information of constraint to a symmetry detection graph
scip | SCIP pointer |
symtype | type of symmetries that need to be added |
cons | constraint |
graph | symmetry detection graph |
success | pointer to store whether symmetry information could be added |
Definition at line 10653 of file cons_nonlinear.c.
References assert(), ensureLocVarsArraySize(), ensureOpenArraySizeSymdetect(), FALSE, i, NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_ENTEREXPR, SCIP_EXPRITER_LEAVEEXPR, SCIP_OKAY, SCIP_Real, SCIPaddSymgraphConsnode(), SCIPaddSymgraphEdge(), SCIPaddSymgraphOpnode(), SCIPaddSymgraphValnode(), SCIPaddSymgraphVarAggregation(), SCIPallocBufferArray, SCIPblkmem(), SCIPconsIsTransformed(), SCIPcreateExpriter(), SCIPexprGetChildren(), SCIPexprGetHdlr(), SCIPexprGetNChildren(), SCIPexprhdlrGetName(), SCIPexprhdlrHasGetSymData(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterGetParentDFS(), SCIPexpriterGetStageDFS(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfreeBufferArray, SCIPfreeExpriter(), SCIPfreeSymDataExpr(), SCIPgetCoefsExprSum(), SCIPgetCoefSymData(), SCIPgetConstantExprSum(), SCIPgetExprNonlinear(), SCIPgetLhsNonlinear(), SCIPgetNVars(), SCIPgetRhsNonlinear(), SCIPgetSymActiveVariables(), SCIPgetSymDataExpr(), SCIPgetSymExprdataConstants(), SCIPgetSymExprdataNConstants(), SCIPgetSymOpNodeType(), SCIPgetValueExprValue(), SCIPgetVarExprVar(), SCIPhashsetCreate(), SCIPhashsetExists(), SCIPhashsetFree(), SCIPhashsetInsert(), SCIPhashsetIsEmpty(), SCIPhashsetRemove(), SCIPisEQ(), SCIPisExprProduct(), SCIPisExprSum(), SCIPisExprValue(), SCIPisExprVar(), SCIPisZero(), SYM_CONSOPTYPE_COEF, SYM_CONSOPTYPE_SUM, SYM_SYMTYPE_SIGNPERM, TRUE, tryAddGadgetBilinearProductSignedPerm(), tryAddGadgetEvenOperator(), and tryAddGadgetSquaredDifference().
Referenced by SCIP_DECL_CONSGETPERMSYMGRAPH(), and SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH().
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 10963 of file cons_nonlinear.c.
References assert(), CONSHDLR_NAME, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfindConshdlr(), SCIPincludeConshdlrNonlinear(), TRUE, and valid.
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 10997 of file cons_nonlinear.c.
References assert(), i, NULL, SCIP_CALL, SCIP_MAXVERTEXPOLYDIM, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrSetData(), SCIPfreeBlockMemory, SCIPfreeBlockMemoryArrayNull, SCIPfreeClock(), SCIPfreeRandom(), SCIPhashmapFree(), SCIPhashmapGetNElements(), SCIPlpiFree(), SCIPnlhdlrFree(), and SCIPqueueFree().
|
static |
initialization method of constraint handler (called after problem was transformed)
Definition at line 11052 of file cons_nonlinear.c.
References assert(), catchVarEvents(), ENFOLOG, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPfindHeur(), SCIPresetClock(), SCIPsortDownPtr(), and storeVarExprs().
|
static |
deinitialization method of constraint handler (called before transformed problem is freed)
Definition at line 11107 of file cons_nonlinear.c.
References assert(), dropVarEvents(), ENFOLOG, freeVarExprs(), i, NULL, SCIP_CALL, SCIP_MAXVERTEXPOLYDIM, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPduplicateBufferArray, SCIPfreeBufferArray, SCIPfreeRandom(), SCIPlpiFree(), and SCIPsortDownPtr().
|
static |
presolving deinitialization method of constraint handler (called after presolving has been finished)
Definition at line 11183 of file cons_nonlinear.c.
References canonicalizeConstraints(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_PRESOLTIMING_ALWAYS, SCIP_STATUS_INFEASIBLE, SCIPenableNLP(), and SCIPgetStatus().
|
static |
solving process initialization method of constraint handler (called when branch and bound process is about to begin)
Definition at line 11213 of file cons_nonlinear.c.
References assert(), i, initSolve(), NULL, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_STATUS_INFEASIBLE, SCIP_STATUS_INFORUNBD, SCIP_STATUS_OPTIMAL, SCIP_STATUS_UNBOUNDED, SCIPABORT, SCIPconshdlrGetData(), SCIPerrorMessage, SCIPgetCharParam(), SCIPgetStatus(), and SCIPnlhdlrResetNDetectionslast.
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 11259 of file cons_nonlinear.c.
References assert(), bilinearTermsFree(), CONSHDLR_NAME, deinitSolve(), FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_SOLFOUND, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdropEvent(), and SCIPfindEventhdlr().
|
static |
frees specific constraint data
Definition at line 11292 of file cons_nonlinear.c.
References assert(), freeVarExprs(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPreleaseExpr(), and SCIPreleaseNlRow().
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 11321 of file cons_nonlinear.c.
References assert(), createCons(), FALSE, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPduplicateExpr(), and SCIPreleaseExpr().
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 11350 of file cons_nonlinear.c.
References assert(), bilinearTermsInsertAll(), CONSHDLR_NAME, initSepa(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_SOLFOUND, SCIP_OKAY, SCIPcatchEvent(), SCIPconshdlrGetData(), and SCIPfindEventhdlr().
|
static |
separation method of constraint handler for LP solutions
Definition at line 11389 of file cons_nonlinear.c.
References consSepa(), NULL, result, SCIP_CALL, and SCIP_OKAY.
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 11399 of file cons_nonlinear.c.
References consSepa(), result, SCIP_CALL, SCIP_OKAY, and sol.
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 11409 of file cons_nonlinear.c.
References consEnfo(), NULL, result, SCIP_CALL, and SCIP_OKAY.
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 11419 of file cons_nonlinear.c.
References consEnfo(), result, SCIP_CALL, SCIP_OKAY, and sol.
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 11429 of file cons_nonlinear.c.
References c, computeViolation(), isConsViolated(), NULL, propConss(), registerBranchingCandidatesAllUnfixed(), result, SCIP_CALL, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_Longint, SCIP_OKAY, SCIP_REDUCEDDOM, SCIP_SOLVELP, SCIPconshdlrGetData(), SCIPdebugMsg, SCIPgetExprNewSoltag(), and TRUE.
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 11482 of file cons_nonlinear.c.
References assert(), c, computeViolation(), FALSE, getConsAbsViolation(), isConsViolated(), MAX, NULL, proposeFeasibleSolution(), result, SCIP_Bool, SCIP_CALL, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_Longint, SCIP_LPSOLSTAT_UNBOUNDEDRAY, SCIP_OKAY, SCIP_Real, SCIP_SOLORIGIN_LPSOL, SCIP_STAGE_SOLVING, SCIP_STAGE_TRANSFORMED, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPfeastol(), SCIPgetExprNewSoltag(), SCIPgetLPSolstat(), SCIPgetStage(), SCIPinfoMessage(), SCIPisInfinity(), SCIPprintCons(), SCIPsolGetOrigin(), SCIPupdateStartpointHeurSubNlp(), and sol.
|
static |
domain propagation method of constraint handler
Definition at line 11594 of file cons_nonlinear.c.
References assert(), FALSE, propConss(), result, SCIP_CALL, and SCIP_OKAY.
|
static |
presolving method of constraint handler
Definition at line 11609 of file cons_nonlinear.c.
References assert(), c, canonicalizeConstraints(), FALSE, NULL, presolveImplint(), presolveMergeConss(), presolveRedundantConss(), presolveSingleLockedVars(), presolveUpgrade(), propConss(), propExprDomains(), result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_MEDIUM, SCIP_REDUCEDDOM, SCIP_SUCCESS, SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPdebugMsg, SCIPisPresolveFinished(), and TRUE.
|
static |
variable rounding lock method of constraint handler
Definition at line 11752 of file cons_nonlinear.c.
References addLocks(), assert(), deinitSolve(), FALSE, initSolve(), NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPexprGetOwnerData(), and TRUE.
|
static |
constraint activation notification method of constraint handler
Definition at line 11798 of file cons_nonlinear.c.
References addLocks(), assert(), FALSE, initSolve(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EXPRITER_DFS, SCIP_EXPRITER_VISITINGCHILD, SCIP_OKAY, SCIP_STAGE_EXITPRESOLVE, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_TRANSFORMED, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconsIsChecked(), SCIPcreateExpriter(), SCIPexpriterGetChildExprDFS(), SCIPexpriterGetChildIdxDFS(), SCIPexpriterGetCurrent(), SCIPexpriterGetNext(), SCIPexpriterInit(), SCIPexpriterIsEnd(), SCIPexpriterSetStagesDFS(), SCIPfreeExpriter(), SCIPgetStage(), SCIPgetVarExprVar(), SCIPhashmapGetImage(), SCIPisExprVar(), SCIPreleaseExpr(), SCIPreplaceCommonSubexpressions(), SCIPreplaceExprChild(), SCIPsimplifyExpr(), storeVarExprs(), and TRUE.
|
static |
constraint deactivation notification method of constraint handler
Definition at line 11890 of file cons_nonlinear.c.
References addLocks(), assert(), deinitSolve(), dropVarEvents(), freeVarExprs(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_EXITSOLVE, SCIP_STAGE_TRANSFORMED, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconsIsChecked(), and SCIPgetStage().
|
static |
constraint enabling notification method of constraint handler
Definition at line 11923 of file cons_nonlinear.c.
References assert(), catchVarEvents(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_TRANSFORMED, SCIPconshdlrGetData(), and SCIPgetStage().
|
static |
constraint disabling notification method of constraint handler
Definition at line 11941 of file cons_nonlinear.c.
References assert(), dropVarEvents(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_STAGE_TRANSFORMED, SCIPconshdlrGetData(), and SCIPgetStage().
|
static |
constraint display method of constraint handler
Definition at line 11973 of file cons_nonlinear.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPinfoMessage(), SCIPisEQ(), SCIPisInfinity(), and SCIPprintExpr().
|
static |
constraint copying method of constraint handler
Definition at line 12006 of file cons_nonlinear.c.
References assert(), CONSHDLR_NAME, createCons(), FALSE, NULL, propagate, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPcopyExpr(), SCIPfindConshdlr(), SCIPreleaseExpr(), and valid.
|
static |
constraint parsing method of constraint handler
Definition at line 12046 of file cons_nonlinear.c.
References assert(), createCons(), FALSE, NULL, propagate, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIP_Real, SCIPconsGetName(), SCIPdebugMsg, SCIPerrorMessage, SCIPinfinity(), SCIPisInfinity(), SCIPparseExpr(), SCIPparseReal(), SCIPreleaseExpr(), SCIPskipSpace(), and TRUE.
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 12180 of file cons_nonlinear.c.
References assert(), FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPgetVarExprVar(), storeVarExprs(), TRUE, and vars.
|
static |
constraint method of constraint handler which returns the number of variables (if possible)
Definition at line 12211 of file cons_nonlinear.c.
References assert(), NULL, nvars, SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), storeVarExprs(), and TRUE.
|
static |
constraint handler method which returns the permutation symmetry detection graph of a constraint (if possible)
Definition at line 12243 of file cons_nonlinear.c.
References addSymmetryInformation(), SCIP_CALL, SCIP_OKAY, and SYM_SYMTYPE_PERM.
|
static |
constraint handler method which returns the signed permutation symmetry detection graph of a constraint (if possible)
Definition at line 12252 of file cons_nonlinear.c.
References addSymmetryInformation(), SCIP_CALL, SCIP_OKAY, and SYM_SYMTYPE_SIGNPERM.
|
static |
output method of statistics table to output file stream 'file'
Definition at line 12261 of file cons_nonlinear.c.
References assert(), CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPfindConshdlr(), SCIPgetClockTime(), and SCIPinfoMessage().
|
static |
output method of statistics table to output file stream 'file'
Definition at line 12291 of file cons_nonlinear.c.
References assert(), CONSHDLR_NAME, NULL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetMaxNActiveConss(), SCIPfindConshdlr(), and SCIPnlhdlrPrintStatistics().
|
static |
execution method of display nlhdlrs dialog
Definition at line 12314 of file cons_nonlinear.c.
References assert(), CONSHDLR_NAME, FALSE, i, NULL, SCIP_CALL, SCIP_OKAY, SCIPconshdlrGetData(), SCIPdialoghdlrAddHistory(), SCIPdialoghdlrGetRoot(), SCIPdialogMessage(), SCIPfindConshdlr(), SCIPnlhdlrGetDesc(), SCIPnlhdlrGetDetectPriority(), SCIPnlhdlrGetEnfoPriority(), SCIPnlhdlrGetName(), and SCIPnlhdlrIsEnabled().