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 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_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)

Macro Definition Documentation

#define SCIP_DECL_NONLINCONSUPGD ( x )

Value:

SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \

int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize)

SCIP_CONS

struct SCIP_Cons SCIP_CONS

Definition: type_cons.h:47

SCIP_RETCODE

enum SCIP_Retcode SCIP_RETCODE

Definition: type_retcode.h:53

SCIP

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)

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

scip	SCIP 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

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.

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

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

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

scip	SCIP data structure
cons	constraint
var	variable
coef	coefficient 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

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

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

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

SCIP_RETCODE SCIPgetNlRowNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_NLROW **	nlrow
	)

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

SCIP_VAR** SCIPgetLinearVarsNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the variables in the linear part of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_Real* SCIPgetLinearCoefsNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the coefficients in the linear part of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

int SCIPgetNExprtreesNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the number of expression trees of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_EXPRTREE** SCIPgetExprtreesNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the expression trees of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_Real* SCIPgetExprtreeCoefsNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the coefficients of the expression trees of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_EXPRGRAPHNODE* SCIPgetExprgraphNodeNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the expression graph node of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_Real SCIPgetLhsNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the left hand side of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_Real SCIPgetRhsNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

gets the right hand side of a nonlinear constraint

Parameters

scip	SCIP data structure
cons	constraint

SCIP_RETCODE SCIPcheckCurvatureNonlinear	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

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

Parameters

scip	SCIP data structure
cons	constraint

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

scip	SCIP data structure
cons	constraint
checkcurv	whether to check constraint curvature, if not checked before
curvature	pointer 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

scip	SCIP data structure
cons	constraint
checkcurv	whether to check constraint curvature, if not checked before
curvatures	buffer 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

scip	SCIP data structure
cons	constraint
sol	solution which violation to calculate, or NULL for LP solution
violation	pointer to store violation of constraint

SCIP_EXPRGRAPH* SCIPgetExprgraphNonlinear	(	SCIP *	scip,
		SCIP_CONSHDLR *	conshdlr
	)

gets expression graph of nonlinear constraint handler

Parameters

scip	SCIP data structure
conshdlr	nonlinear constraint handler

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

Function Documentation