|
constraint handler for nonlinear constraints
- Author
- Stefan Vigerske
This constraint handler handles constraints of the form
where and are coefficients and are nonlinear functions (given as expression tree).
Constraints are enforced by separation, domain propagation, and spatial branching.
For convex or concave , cuts that separate on the convex hull of the function graph are implemented. For that are not known to be convex or concave, a simple variant of linear estimation based on interval gradients is implemented.
Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated.
This header offers the upgrade functionality to upgrade a general nonlinear constraint into a more specific constraint via SCIP_DECL_NONLINCONSUPGD().
Furthermore, the definition of callbacks used to reformulate an expression graph is offered by SCIP_DECL_EXPRGRAPHNODEREFORM().
Further, the function representation is stored in an expression graph, which allows to propagate variable domains and constraint sides and offers a simple convexity check. During presolve, the expression graph is reformulated, whereby new variables and constraints are created such that for the remaining nonlinear constraints the functions are known to be convex or concave. See also
- Stefan Vigerske
Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming
PhD Thesis, Humboldt-University Berlin, 2012, submitted.
Definition in file cons_nonlinear.h.
Go to the source code of this file.
|
SCIP_RETCODE | SCIPincludeConshdlrNonlinear (SCIP *scip) |
|
SCIP_RETCODE | SCIPincludeNonlinconsUpgrade (SCIP *scip, SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)), SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)), int priority, SCIP_Bool active, const char *conshdlrname) |
|
SCIP_RETCODE | SCIPcreateConsNonlinear (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *nonlincoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) |
|
SCIP_RETCODE | SCIPcreateConsBasicNonlinear (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *nonlincoefs, SCIP_Real lhs, SCIP_Real rhs) |
|
SCIP_RETCODE | SCIPcreateConsNonlinear2 (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPRGRAPHNODE *exprgraphnode, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode) |
|
SCIP_RETCODE | SCIPcreateConsBasicNonlinear2 (SCIP *scip, SCIP_CONS **cons, const char *name, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPRGRAPHNODE *exprgraphnode, SCIP_Real lhs, SCIP_Real rhs) |
|
SCIP_RETCODE | SCIPaddLinearVarNonlinear (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real coef) |
|
SCIP_RETCODE | SCIPsetExprtreesNonlinear (SCIP *scip, SCIP_CONS *cons, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *coefs) |
|
SCIP_RETCODE | SCIPaddExprtreesNonlinear (SCIP *scip, SCIP_CONS *cons, int nexprtrees, SCIP_EXPRTREE **exprtrees, SCIP_Real *coefs) |
|
SCIP_RETCODE | SCIPgetNlRowNonlinear (SCIP *scip, SCIP_CONS *cons, SCIP_NLROW **nlrow) |
|
int | SCIPgetNLinearVarsNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_VAR ** | SCIPgetLinearVarsNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Real * | SCIPgetLinearCoefsNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
int | SCIPgetNExprtreesNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_EXPRTREE ** | SCIPgetExprtreesNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Real * | SCIPgetExprtreeCoefsNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_EXPRGRAPHNODE * | SCIPgetExprgraphNodeNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Real | SCIPgetLhsNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_Real | SCIPgetRhsNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_RETCODE | SCIPcheckCurvatureNonlinear (SCIP *scip, SCIP_CONS *cons) |
|
SCIP_RETCODE | SCIPgetCurvatureNonlinear (SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkcurv, SCIP_EXPRCURV *curvature) |
|
SCIP_RETCODE | SCIPgetExprtreeCurvaturesNonlinear (SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkcurv, SCIP_EXPRCURV **curvatures) |
|
SCIP_RETCODE | SCIPgetViolationNonlinear (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Real *violation) |
|
SCIP_EXPRGRAPH * | SCIPgetExprgraphNonlinear (SCIP *scip, SCIP_CONSHDLR *conshdlr) |
|
SCIP_RETCODE | SCIPcomputeHyperplaneThreePoints (SCIP *scip, SCIP_Real a1, SCIP_Real a2, SCIP_Real a3, SCIP_Real b1, SCIP_Real b2, SCIP_Real b3, SCIP_Real c1, SCIP_Real c2, SCIP_Real c3, SCIP_Real *alpha, SCIP_Real *beta, SCIP_Real *gamma_, SCIP_Real *delta) |
|
#define SCIP_DECL_NONLINCONSUPGD |
( |
|
x | ) |
|
Value: int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize) struct SCIP_Cons SCIP_CONS
enum SCIP_Retcode SCIP_RETCODE
upgrading method for nonlinear constraints into more specific constraints
the method might upgrade a nonlinear constraint into a set of upgrade constraints the caller provided an array upgdconss to store upgrade constraints the length of upgdconss is given by upgdconsssize if an upgrade is not possible, set *nupgdconss to zero if more than upgdconsssize many constraints shall replace cons, the function should return the required number as negated value in *nupgdconss i.e., if cons should be replaced by 3 constraints, the function should set *nupgdconss to -3 and return with SCIP_OKAY
input:
- scip : SCIP main data structure
- cons : the nonlinear constraint to upgrade
- nupgdconss : pointer to store number of constraints that replace this constraint
- upgdconss : array to store constraints that replace this constraint
- upgdconsssize : length of the provided upgdconss array
Definition at line 82 of file cons_nonlinear.h.
#define SCIP_DECL_EXPRGRAPHNODEREFORM |
( |
|
x | ) |
|
Value:enum SCIP_Retcode SCIP_RETCODE
struct SCIP_ExprGraph SCIP_EXPRGRAPH
struct SCIP_ExprGraphNode SCIP_EXPRGRAPHNODE
reformulation method for expression graph nodes
The method might reformulate a node in an expression graph by adding auxiliary constraints and/or variables. The caller provided an expression graph node which is to be reformulated. If the method takes action, it has to return the node that should replace the given node in *reformnode. The caller will then ensure that all parents of node will use *reformnode, so node may be freed. If the method does not do any reformulation, it shall return NULL in *reformnode. The counter naddcons can be used to setup the names of added variables/constraints. The method should increase this counter by the number of added constraints. The method has to ensure that the reformulated node, if still valid, has valid bound and curvature information.
input:
- scip : SCIP main data structure
- exprgraph : the expression graph which node to reformulate
- node : the expression graph node to reformulate
- naddcons : counter on number of added constraints so far
output:
- naddcons : to be increased by number of additionally added constraints
- reformnode : reformulated node to replace node with, or NULL if no reformulation
Definition at line 109 of file cons_nonlinear.h.
creates the handler for nonlinear constraints and includes it in SCIP
- Parameters
-
includes a nonlinear constraint upgrade method into the nonlinear constraint handler
- Parameters
-
scip | SCIP data structure |
priority | priority of upgrading method |
active | should the upgrading method by active by default? |
conshdlrname | name of the constraint handler |
SCIP_RETCODE SCIPcreateConsNonlinear |
( |
SCIP * |
scip, |
|
|
SCIP_CONS ** |
cons, |
|
|
const char * |
name, |
|
|
int |
nlinvars, |
|
|
SCIP_VAR ** |
linvars, |
|
|
SCIP_Real * |
lincoefs, |
|
|
int |
nexprtrees, |
|
|
SCIP_EXPRTREE ** |
exprtrees, |
|
|
SCIP_Real * |
nonlincoefs, |
|
|
SCIP_Real |
lhs, |
|
|
SCIP_Real |
rhs, |
|
|
SCIP_Bool |
initial, |
|
|
SCIP_Bool |
separate, |
|
|
SCIP_Bool |
enforce, |
|
|
SCIP_Bool |
check, |
|
|
SCIP_Bool |
propagate, |
|
|
SCIP_Bool |
local, |
|
|
SCIP_Bool |
modifiable, |
|
|
SCIP_Bool |
dynamic, |
|
|
SCIP_Bool |
removable, |
|
|
SCIP_Bool |
stickingatnode |
|
) |
| |
creates and captures a nonlinear constraint this variant takes expression trees as input
- Note
- the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
- Parameters
-
scip | SCIP data structure |
cons | pointer to hold the created constraint |
name | name of constraint |
nlinvars | number of linear variables in the constraint |
linvars | array with linear variables of constraint entries |
lincoefs | array with coefficients of constraint linear entries |
nexprtrees | number of expression trees for nonlinear part of constraint |
exprtrees | expression trees for nonlinear part of constraint |
nonlincoefs | coefficients for expression trees for nonlinear part, or NULL if all 1.0 |
lhs | left hand side of constraint |
rhs | right hand side of constraint |
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 seperated 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'. |
stickingatnode | should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data. |
SCIP_RETCODE SCIPcreateConsBasicNonlinear |
( |
SCIP * |
scip, |
|
|
SCIP_CONS ** |
cons, |
|
|
const char * |
name, |
|
|
int |
nlinvars, |
|
|
SCIP_VAR ** |
linvars, |
|
|
SCIP_Real * |
lincoefs, |
|
|
int |
nexprtrees, |
|
|
SCIP_EXPRTREE ** |
exprtrees, |
|
|
SCIP_Real * |
nonlincoefs, |
|
|
SCIP_Real |
lhs, |
|
|
SCIP_Real |
rhs |
|
) |
| |
creates and captures a nonlinear constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsNonlinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
this variant takes expression trees as input
- See also
- SCIPcreateConsNonlinear() for information about the basic constraint flag configuration
- Note
- the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
- Parameters
-
scip | SCIP data structure |
cons | pointer to hold the created constraint |
name | name of constraint |
nlinvars | number of linear variables in the constraint |
linvars | array with linear variables of constraint entries |
lincoefs | array with coefficients of constraint linear entries |
nexprtrees | number of expression trees for nonlinear part of constraint |
exprtrees | expression trees for nonlinear part of constraint |
nonlincoefs | coefficients for expression trees for nonlinear part, or NULL if all 1.0 |
lhs | left hand side of constraint |
rhs | right hand side of constraint |
SCIP_RETCODE SCIPcreateConsNonlinear2 |
( |
SCIP * |
scip, |
|
|
SCIP_CONS ** |
cons, |
|
|
const char * |
name, |
|
|
int |
nlinvars, |
|
|
SCIP_VAR ** |
linvars, |
|
|
SCIP_Real * |
lincoefs, |
|
|
SCIP_EXPRGRAPHNODE * |
exprgraphnode, |
|
|
SCIP_Real |
lhs, |
|
|
SCIP_Real |
rhs, |
|
|
SCIP_Bool |
initial, |
|
|
SCIP_Bool |
separate, |
|
|
SCIP_Bool |
enforce, |
|
|
SCIP_Bool |
check, |
|
|
SCIP_Bool |
propagate, |
|
|
SCIP_Bool |
local, |
|
|
SCIP_Bool |
modifiable, |
|
|
SCIP_Bool |
dynamic, |
|
|
SCIP_Bool |
removable, |
|
|
SCIP_Bool |
stickingatnode |
|
) |
| |
creates and captures a nonlinear constraint this variant takes a node of the expression graph as input and can only be used during presolving it is assumed that the nonlinear constraint will be added to the transformed problem short after creation the given exprgraphnode is captured in this method
- Note
- the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
- Parameters
-
scip | SCIP data structure |
cons | pointer to hold the created constraint |
name | name of constraint |
nlinvars | number of linear variables in the constraint |
linvars | array with linear variables of constraint entries |
lincoefs | array with coefficients of constraint linear entries |
exprgraphnode | expression graph node associated to nonlinear expression |
lhs | left hand side of constraint |
rhs | right hand side of constraint |
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 seperated 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'. |
stickingatnode | should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data. |
creates and captures a nonlinear constraint in its most basic version, i. e., all constraint flags are set to their basic value as explained for the method SCIPcreateConsNonlinear2(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
this variant takes a node of the expression graph as input and can only be used during presolving it is assumed that the nonlinear constraint will be added to the transformed problem short after creation the given exprgraphnode is captured in this method
- See also
- SCIPcreateConsNonlinear2() for information about the basic constraint flag configuration
- Note
- the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
- Parameters
-
scip | SCIP data structure |
cons | pointer to hold the created constraint |
name | name of constraint |
nlinvars | number of linear variables in the constraint |
linvars | array with linear variables of constraint entries |
lincoefs | array with coefficients of constraint linear entries |
exprgraphnode | expression graph node associated to nonlinear expression |
lhs | left hand side of constraint |
rhs | right hand side of constraint |
adds a linear variable with coefficient to a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
var | variable |
coef | coefficient of variable |
sets the expression trees in a nonlinear constraint constraint must not be active yet
- Parameters
-
scip | SCIP data structure |
cons | constraint |
nexprtrees | number of expression trees |
exprtrees | new expression trees, or NULL if nexprtrees is 0 |
coefs | coefficients of expression trees, or NULL if all 1.0 |
adds expression trees to a nonlinear constraint constraint must not be active yet
- Parameters
-
scip | SCIP data structure |
cons | constraint |
nexprtrees | number of expression trees |
exprtrees | new expression trees, or NULL if nexprtrees is 0 |
coefs | coefficients of expression trees, or NULL if all 1.0 |
gets the nonlinear constraint as a nonlinear row representation
- Parameters
-
scip | SCIP data structure |
cons | constraint |
nlrow | pointer to store nonlinear row |
int SCIPgetNLinearVarsNonlinear |
( |
SCIP * |
scip, |
|
|
SCIP_CONS * |
cons |
|
) |
| |
gets the number of variables in the linear term of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the variables in the linear part of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the coefficients in the linear part of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the number of expression trees of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the expression trees of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the coefficients of the expression trees of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the expression graph node of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the left hand side of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the right hand side of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
check the function of a nonlinear constraint for convexity/concavity, if not done yet
- Parameters
-
scip | SCIP data structure |
cons | constraint |
gets the curvature of the nonlinear function of a nonlinear constraint
The curvature is computed by summing up the curvature for each nonlinear summand. To get the curvature for single summands, use SCIPgetExprtreeCurvaturesNonlinear().
- Parameters
-
scip | SCIP data structure |
cons | constraint |
checkcurv | whether to check constraint curvature, if not checked before |
curvature | pointer to store curvature of constraint |
gets the curvature of the expression trees (multiplied by their coefficient) of a nonlinear constraint
- Parameters
-
scip | SCIP data structure |
cons | constraint |
checkcurv | whether to check constraint curvature, if not checked before |
curvatures | buffer to store curvatures of exprtrees |
computes the violation of a nonlinear constraint by a solution
- Parameters
-
scip | SCIP data structure |
cons | constraint |
sol | solution which violation to calculate, or NULL for LP solution |
violation | pointer to store violation of constraint |
gets expression graph of nonlinear constraint handler
- Parameters
-
scip | SCIP data structure |
conshdlr | nonlinear constraint handler |
SCIP_RETCODE SCIPcomputeHyperplaneThreePoints |
( |
SCIP * |
scip, |
|
|
SCIP_Real |
a1, |
|
|
SCIP_Real |
a2, |
|
|
SCIP_Real |
a3, |
|
|
SCIP_Real |
b1, |
|
|
SCIP_Real |
b2, |
|
|
SCIP_Real |
b3, |
|
|
SCIP_Real |
c1, |
|
|
SCIP_Real |
c2, |
|
|
SCIP_Real |
c3, |
|
|
SCIP_Real * |
alpha, |
|
|
SCIP_Real * |
beta, |
|
|
SCIP_Real * |
gamma_, |
|
|
SCIP_Real * |
delta |
|
) |
| |
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.
- Parameters
-
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 |
|