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

Definition in file cons_nonlinear.h.

#include "scip/def.h"
#include "scip/type_cons.h"
#include "nlpi/type_expr.h"
#include "scip/type_nlp.h"
#include "scip/type_retcode.h"
#include "scip/type_scip.h"
#include "scip/type_sol.h"
#include "scip/type_var.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)
Nonlinear Constraints
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.
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)
int	SCIPgetLinvarMayDecreaseNonlinear (SCIP *scip, SCIP_CONS *cons)
int	SCIPgetLinvarMayIncreaseNonlinear (SCIP *scip, SCIP_CONS *cons)
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)

Macro Definition Documentation

SCIP_DECL_NONLINCONSUPGD

#define SCIP_DECL_NONLINCONSUPGD

(

x

)

Value:

SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \
      int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize)

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 59 of file cons_nonlinear.h.

SCIP_DECL_EXPRGRAPHNODEREFORM

#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 86 of file cons_nonlinear.h.