Scippy

SCIP

Solving Constraint Integer Programs

cons_nonlinear.h File Reference

Detailed Description

constraint handler for nonlinear constraints $\textrm{lhs} \leq \sum_{i=1}^n a_ix_i + \sum_{j=1}^m c_jf_j(x) \leq \textrm{rhs}$

Author
Stefan Vigerske

This constraint handler handles constraints of the form

\[ \textrm{lhs} \leq \sum_{i=1}^n a_ix_i + \sum_{j=1}^m c_jf_j(x) \leq \textrm{rhs}, \]

where $a_i$ and $c_j$ are coefficients and $f_j(x)$ are nonlinear functions (given as expression tree).

Constraints are enforced by separation, domain propagation, and spatial branching.

For convex or concave $f_j(x)$, cuts that separate on the convex hull of the function graph are implemented. For $f_j(x)$ 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 $f_j(x)$ 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.

#include "scip/scip.h"

Go to the source code of this file.

Macros

#define SCIP_DECL_NONLINCONSUPGD(x)
 
#define SCIP_DECL_EXPRGRAPHNODEREFORM(x)
 

Functions

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_RealSCIPgetLinearCoefsNonlinear (SCIP *scip, SCIP_CONS *cons)
 
int SCIPgetNExprtreesNonlinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPRTREE ** SCIPgetExprtreesNonlinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_RealSCIPgetExprtreeCoefsNonlinear (SCIP *scip, SCIP_CONS *cons)
 
SCIP_EXPRGRAPHNODESCIPgetExprgraphNodeNonlinear (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_EXPRGRAPHSCIPgetExprgraphNonlinear (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 

Macro Definition Documentation

#define SCIP_DECL_NONLINCONSUPGD (   x)
Value:
SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \
int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize)
struct SCIP_Cons SCIP_CONS
Definition: type_cons.h:47
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct Scip SCIP
Definition: type_scip.h:30

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:
SCIP_RETCODE x (SCIP* scip, \
SCIP_EXPRGRAPH* exprgraph, SCIP_EXPRGRAPHNODE* node, \
int* naddcons, SCIP_EXPRGRAPHNODE** reformnode)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
struct Scip SCIP
Definition: type_scip.h:30
struct SCIP_ExprGraph SCIP_EXPRGRAPH
Definition: type_expr.h:168
struct SCIP_ExprGraphNode SCIP_EXPRGRAPHNODE
Definition: type_expr.h:167

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.

Function Documentation

SCIP_RETCODE SCIPincludeConshdlrNonlinear ( SCIP scip)

creates the handler for nonlinear constraints and includes it in SCIP

Parameters
scipSCIP data structure
SCIP_RETCODE SCIPincludeNonlinconsUpgrade ( SCIP scip,
SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd))  ,
SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform))  ,
int  priority,
SCIP_Bool  active,
const char *  conshdlrname 
)

includes a nonlinear constraint upgrade method into the nonlinear constraint handler

Parameters
scipSCIP data structure
prioritypriority of upgrading method
activeshould the upgrading method by active by default?
conshdlrnamename 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nlinvarsnumber of linear variables in the constraint
linvarsarray with linear variables of constraint entries
lincoefsarray with coefficients of constraint linear entries
nexprtreesnumber of expression trees for nonlinear part of constraint
exprtreesexpression trees for nonlinear part of constraint
nonlincoefscoefficients for expression trees for nonlinear part, or NULL if all 1.0
lhsleft hand side of constraint
rhsright hand side of constraint
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.
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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nlinvarsnumber of linear variables in the constraint
linvarsarray with linear variables of constraint entries
lincoefsarray with coefficients of constraint linear entries
nexprtreesnumber of expression trees for nonlinear part of constraint
exprtreesexpression trees for nonlinear part of constraint
nonlincoefscoefficients for expression trees for nonlinear part, or NULL if all 1.0
lhsleft hand side of constraint
rhsright 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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nlinvarsnumber of linear variables in the constraint
linvarsarray with linear variables of constraint entries
lincoefsarray with coefficients of constraint linear entries
exprgraphnodeexpression graph node associated to nonlinear expression
lhsleft hand side of constraint
rhsright hand side of constraint
initialshould the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'.
separateshould the constraint be separated during LP processing? Usually set to TRUE.
enforceshould the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints.
checkshould the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints.
propagateshould the constraint be propagated during node processing? Usually set to TRUE.
localis constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints.
modifiableis constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint.
dynamicis constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are seperated as constraints.
removableshould the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'.
stickingatnodeshould the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.
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 
)

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
scipSCIP data structure
conspointer to hold the created constraint
namename of constraint
nlinvarsnumber of linear variables in the constraint
linvarsarray with linear variables of constraint entries
lincoefsarray with coefficients of constraint linear entries
exprgraphnodeexpression graph node associated to nonlinear expression
lhsleft hand side of constraint
rhsright hand side of constraint
SCIP_RETCODE SCIPaddLinearVarNonlinear ( SCIP scip,
SCIP_CONS cons,
SCIP_VAR var,
SCIP_Real  coef 
)

adds a linear variable with coefficient to a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
varvariable
coefcoefficient of variable
SCIP_RETCODE SCIPsetExprtreesNonlinear ( SCIP scip,
SCIP_CONS cons,
int  nexprtrees,
SCIP_EXPRTREE **  exprtrees,
SCIP_Real coefs 
)

sets the expression trees in a nonlinear constraint constraint must not be active yet

Parameters
scipSCIP data structure
consconstraint
nexprtreesnumber of expression trees
exprtreesnew expression trees, or NULL if nexprtrees is 0
coefscoefficients of expression trees, or NULL if all 1.0
SCIP_RETCODE SCIPaddExprtreesNonlinear ( SCIP scip,
SCIP_CONS cons,
int  nexprtrees,
SCIP_EXPRTREE **  exprtrees,
SCIP_Real coefs 
)

adds expression trees to a nonlinear constraint constraint must not be active yet

Parameters
scipSCIP data structure
consconstraint
nexprtreesnumber of expression trees
exprtreesnew expression trees, or NULL if nexprtrees is 0
coefscoefficients of expression trees, or NULL if all 1.0
SCIP_RETCODE SCIPgetNlRowNonlinear ( SCIP scip,
SCIP_CONS cons,
SCIP_NLROW **  nlrow 
)

gets the nonlinear constraint as a nonlinear row representation

Parameters
scipSCIP data structure
consconstraint
nlrowpointer 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
scipSCIP data structure
consconstraint
SCIP_VAR** SCIPgetLinearVarsNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the variables in the linear part of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_Real* SCIPgetLinearCoefsNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the coefficients in the linear part of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
int SCIPgetNExprtreesNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the number of expression trees of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_EXPRTREE** SCIPgetExprtreesNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the expression trees of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_Real* SCIPgetExprtreeCoefsNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the coefficients of the expression trees of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_EXPRGRAPHNODE* SCIPgetExprgraphNodeNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the expression graph node of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_Real SCIPgetLhsNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the left hand side of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_Real SCIPgetRhsNonlinear ( SCIP scip,
SCIP_CONS cons 
)

gets the right hand side of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
SCIP_RETCODE SCIPcheckCurvatureNonlinear ( SCIP scip,
SCIP_CONS cons 
)

check the function of a nonlinear constraint for convexity/concavity, if not done yet

Parameters
scipSCIP data structure
consconstraint
SCIP_RETCODE SCIPgetCurvatureNonlinear ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  checkcurv,
SCIP_EXPRCURV curvature 
)

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
scipSCIP data structure
consconstraint
checkcurvwhether to check constraint curvature, if not checked before
curvaturepointer to store curvature of constraint
SCIP_RETCODE SCIPgetExprtreeCurvaturesNonlinear ( SCIP scip,
SCIP_CONS cons,
SCIP_Bool  checkcurv,
SCIP_EXPRCURV **  curvatures 
)

gets the curvature of the expression trees (multiplied by their coefficient) of a nonlinear constraint

Parameters
scipSCIP data structure
consconstraint
checkcurvwhether to check constraint curvature, if not checked before
curvaturesbuffer to store curvatures of exprtrees
SCIP_RETCODE SCIPgetViolationNonlinear ( SCIP scip,
SCIP_CONS cons,
SCIP_SOL sol,
SCIP_Real violation 
)

computes the violation of a nonlinear constraint by a solution

Parameters
scipSCIP data structure
consconstraint
solsolution which violation to calculate, or NULL for LP solution
violationpointer to store violation of constraint
SCIP_EXPRGRAPH* SCIPgetExprgraphNonlinear ( SCIP scip,
SCIP_CONSHDLR conshdlr 
)

gets expression graph of nonlinear constraint handler

Parameters
scipSCIP data structure
conshdlrnonlinear constraint handler