Scippy

SCIP

Solving Constraint Integer Programs

cons_nonlinear.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2014 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_nonlinear.h
17  * @ingroup CONSHDLRS
18  * @brief constraint handler for nonlinear constraints \f$\textrm{lhs} \leq \sum_{i=1}^n a_ix_i + \sum_{j=1}^m c_jf_j(x) \leq \textrm{rhs}\f$
19  * @author Stefan Vigerske
20  *
21  * This constraint handler handles constraints of the form
22  * \f[
23  * \textrm{lhs} \leq \sum_{i=1}^n a_ix_i + \sum_{j=1}^m c_jf_j(x) \leq \textrm{rhs},
24  * \f]
25  * where \f$a_i\f$ and \f$c_j\f$ are coefficients and
26  * \f$f_j(x)\f$ are nonlinear functions (given as expression tree).
27  *
28  * Constraints are enforced by separation, domain propagation, and spatial branching.
29  *
30  * For convex or concave \f$f_j(x)\f$, cuts that separate on the convex hull of the function graph are implemented.
31  * For \f$f_j(x)\f$ that are not known to be convex or concave, a simple variant of linear estimation based on interval gradients is implemented.
32  *
33  * Branching is performed for variables in nonconvex terms, if the relaxation solution cannot be separated.
34  *
35  * This header offers the upgrade functionality to upgrade a general nonlinear constraint into a more specific constraint
36  * via SCIP_DECL_NONLINCONSUPGD().
37  *
38  * Furthermore, the definition of callbacks used to reformulate an expression graph is offered by
39  * SCIP_DECL_EXPRGRAPHNODEREFORM().
40  *
41  * Further, the function representation is stored in an expression graph, which allows to propagate variable domains
42  * and constraint sides and offers a simple convexity check.
43  * During presolve, the expression graph is reformulated, whereby new variables and constraints are created
44  * such that for the remaining nonlinear constraints the functions \f$f_j(x)\f$ are known to be convex or concave.
45  * See also
46  *
47  * @par
48  * Stefan Vigerske@n
49  * Decomposition of Multistage Stochastic Programs and a Constraint Integer Programming Approach to Mixed-Integer Nonlinear Programming@n
50  * PhD Thesis, Humboldt-University Berlin, 2012, submitted.
51  */
52 
53 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
54 
55 #ifndef __SCIP_CONS_NONLINEAR_H__
56 #define __SCIP_CONS_NONLINEAR_H__
57 
58 #include "scip/scip.h"
59 
60 #ifdef __cplusplus
61 extern "C" {
62 #endif
63 
64 /** upgrading method for nonlinear constraints into more specific constraints
65  *
66  * the method might upgrade a nonlinear constraint into a set of upgrade constraints
67  * the caller provided an array upgdconss to store upgrade constraints
68  * the length of upgdconss is given by upgdconsssize
69  * if an upgrade is not possible, set *nupgdconss to zero
70  * if more than upgdconsssize many constraints shall replace cons, the function
71  * should return the required number as negated value in *nupgdconss
72  * i.e., if cons should be replaced by 3 constraints, the function should set
73  * *nupgdconss to -3 and return with SCIP_OKAY
74  *
75  * input:
76  * - scip : SCIP main data structure
77  * - cons : the nonlinear constraint to upgrade
78  * - nupgdconss : pointer to store number of constraints that replace this constraint
79  * - upgdconss : array to store constraints that replace this constraint
80  * - upgdconsssize : length of the provided upgdconss array
81  */
82 #define SCIP_DECL_NONLINCONSUPGD(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, \
83  int* nupgdconss, SCIP_CONS** upgdconss, int upgdconsssize)
84 
85 /** reformulation method for expression graph nodes
86  *
87  * The method might reformulate a node in an expression graph by adding
88  * auxiliary constraints and/or variables.
89  * The caller provided an expression graph node which is to be reformulated.
90  * If the method takes action, it has to return the node that should replace
91  * the given node in *reformnode. The caller will then ensure that all parents of
92  * node will use *reformnode, so node may be freed.
93  * If the method does not do any reformulation, it shall return NULL in *reformnode.
94  * The counter naddcons can be used to setup the names of added variables/constraints.
95  * The method should increase this counter by the number of added constraints.
96  * The method has to ensure that the reformulated node, if still valid,
97  * has valid bound and curvature information.
98  *
99  * input:
100  * - scip : SCIP main data structure
101  * - exprgraph : the expression graph which node to reformulate
102  * - node : the expression graph node to reformulate
103  * - naddcons : counter on number of added constraints so far
104  *
105  * output:
106  * - naddcons : to be increased by number of additionally added constraints
107  * - reformnode : reformulated node to replace node with, or NULL if no reformulation
108  */
109 #define SCIP_DECL_EXPRGRAPHNODEREFORM(x) SCIP_RETCODE x (SCIP* scip, \
110  SCIP_EXPRGRAPH* exprgraph, SCIP_EXPRGRAPHNODE* node, \
111  int* naddcons, SCIP_EXPRGRAPHNODE** reformnode)
112 
113 /** creates the handler for nonlinear constraints and includes it in SCIP */
114 extern
115 SCIP_RETCODE SCIPincludeConshdlrNonlinear(
116  SCIP* scip /**< SCIP data structure */
117  );
118 
119 /** includes a nonlinear constraint upgrade method into the nonlinear constraint handler */
120 extern
121 SCIP_RETCODE SCIPincludeNonlinconsUpgrade(
122  SCIP* scip, /**< SCIP data structure */
123  SCIP_DECL_NONLINCONSUPGD((*nonlinconsupgd)),/**< method to call for upgrading nonlinear constraint, or NULL */
124  SCIP_DECL_EXPRGRAPHNODEREFORM((*nodereform)),/**< method to call for reformulating expression graph node, or NULL */
125  int priority, /**< priority of upgrading method */
126  SCIP_Bool active, /**< should the upgrading method by active by default? */
127  const char* conshdlrname /**< name of the constraint handler */
128  );
129 
130 /** creates and captures a nonlinear constraint
131  * this variant takes expression trees as input
132  *
133  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
134  */
135 extern
136 SCIP_RETCODE SCIPcreateConsNonlinear(
137  SCIP* scip, /**< SCIP data structure */
138  SCIP_CONS** cons, /**< pointer to hold the created constraint */
139  const char* name, /**< name of constraint */
140  int nlinvars, /**< number of linear variables in the constraint */
141  SCIP_VAR** linvars, /**< array with linear variables of constraint entries */
142  SCIP_Real* lincoefs, /**< array with coefficients of constraint linear entries */
143  int nexprtrees, /**< number of expression trees for nonlinear part of constraint */
144  SCIP_EXPRTREE** exprtrees, /**< expression trees for nonlinear part of constraint */
145  SCIP_Real* nonlincoefs, /**< coefficients for expression trees for nonlinear part, or NULL if all 1.0 */
146  SCIP_Real lhs, /**< left hand side of constraint */
147  SCIP_Real rhs, /**< right hand side of constraint */
148  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
149  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
150  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
151  * Usually set to TRUE. */
152  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
153  * TRUE for model constraints, FALSE for additional, redundant constraints. */
154  SCIP_Bool check, /**< should the constraint be checked for feasibility?
155  * TRUE for model constraints, FALSE for additional, redundant constraints. */
156  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
157  * Usually set to TRUE. */
158  SCIP_Bool local, /**< is constraint only valid locally?
159  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
160  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
161  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
162  * adds coefficients to this constraint. */
163  SCIP_Bool dynamic, /**< is constraint subject to aging?
164  * Usually set to FALSE. Set to TRUE for own cuts which
165  * are seperated as constraints. */
166  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
167  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
168  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
169  * if it may be moved to a more global node?
170  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
171  );
172 
173 /** creates and captures a nonlinear constraint
174  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
175  * method SCIPcreateConsNonlinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
176  *
177  * this variant takes expression trees as input
178  *
179  * @see SCIPcreateConsNonlinear() for information about the basic constraint flag configuration
180  *
181  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
182  */
183 extern
184 SCIP_RETCODE SCIPcreateConsBasicNonlinear(
185  SCIP* scip, /**< SCIP data structure */
186  SCIP_CONS** cons, /**< pointer to hold the created constraint */
187  const char* name, /**< name of constraint */
188  int nlinvars, /**< number of linear variables in the constraint */
189  SCIP_VAR** linvars, /**< array with linear variables of constraint entries */
190  SCIP_Real* lincoefs, /**< array with coefficients of constraint linear entries */
191  int nexprtrees, /**< number of expression trees for nonlinear part of constraint */
192  SCIP_EXPRTREE** exprtrees, /**< expression trees for nonlinear part of constraint */
193  SCIP_Real* nonlincoefs, /**< coefficients for expression trees for nonlinear part, or NULL if all 1.0 */
194  SCIP_Real lhs, /**< left hand side of constraint */
195  SCIP_Real rhs /**< right hand side of constraint */
196  );
197 
198 /** creates and captures a nonlinear constraint
199  * this variant takes a node of the expression graph as input and can only be used during presolving
200  * it is assumed that the nonlinear constraint will be added to the transformed problem short after creation
201  * the given exprgraphnode is captured in this method
202  *
203  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
204  */
205 extern
206 SCIP_RETCODE SCIPcreateConsNonlinear2(
207  SCIP* scip, /**< SCIP data structure */
208  SCIP_CONS** cons, /**< pointer to hold the created constraint */
209  const char* name, /**< name of constraint */
210  int nlinvars, /**< number of linear variables in the constraint */
211  SCIP_VAR** linvars, /**< array with linear variables of constraint entries */
212  SCIP_Real* lincoefs, /**< array with coefficients of constraint linear entries */
213  SCIP_EXPRGRAPHNODE* exprgraphnode, /**< expression graph node associated to nonlinear expression */
214  SCIP_Real lhs, /**< left hand side of constraint */
215  SCIP_Real rhs, /**< right hand side of constraint */
216  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
217  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
218  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
219  * Usually set to TRUE. */
220  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
221  * TRUE for model constraints, FALSE for additional, redundant constraints. */
222  SCIP_Bool check, /**< should the constraint be checked for feasibility?
223  * TRUE for model constraints, FALSE for additional, redundant constraints. */
224  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
225  * Usually set to TRUE. */
226  SCIP_Bool local, /**< is constraint only valid locally?
227  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
228  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
229  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
230  * adds coefficients to this constraint. */
231  SCIP_Bool dynamic, /**< is constraint subject to aging?
232  * Usually set to FALSE. Set to TRUE for own cuts which
233  * are seperated as constraints. */
234  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
235  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
236  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
237  * if it may be moved to a more global node?
238  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
239  );
240 
241 /** creates and captures a nonlinear constraint
242  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
243  * method SCIPcreateConsNonlinear2(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
244  *
245  * this variant takes a node of the expression graph as input and can only be used during presolving
246  * it is assumed that the nonlinear constraint will be added to the transformed problem short after creation
247  * the given exprgraphnode is captured in this method
248  *
249  * @see SCIPcreateConsNonlinear2() for information about the basic constraint flag configuration
250  *
251  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
252  */
253 extern
254 SCIP_RETCODE SCIPcreateConsBasicNonlinear2(
255  SCIP* scip, /**< SCIP data structure */
256  SCIP_CONS** cons, /**< pointer to hold the created constraint */
257  const char* name, /**< name of constraint */
258  int nlinvars, /**< number of linear variables in the constraint */
259  SCIP_VAR** linvars, /**< array with linear variables of constraint entries */
260  SCIP_Real* lincoefs, /**< array with coefficients of constraint linear entries */
261  SCIP_EXPRGRAPHNODE* exprgraphnode, /**< expression graph node associated to nonlinear expression */
262  SCIP_Real lhs, /**< left hand side of constraint */
263  SCIP_Real rhs /**< right hand side of constraint */
264  );
265 
266 /** adds a linear variable with coefficient to a nonlinear constraint */
267 extern
268 SCIP_RETCODE SCIPaddLinearVarNonlinear(
269  SCIP* scip, /**< SCIP data structure */
270  SCIP_CONS* cons, /**< constraint */
271  SCIP_VAR* var, /**< variable */
272  SCIP_Real coef /**< coefficient of variable */
273  );
274 
275 /** sets the expression trees in a nonlinear constraint
276  * constraint must not be active yet
277  */
278 extern
279 SCIP_RETCODE SCIPsetExprtreesNonlinear(
280  SCIP* scip, /**< SCIP data structure */
281  SCIP_CONS* cons, /**< constraint */
282  int nexprtrees, /**< number of expression trees */
283  SCIP_EXPRTREE** exprtrees, /**< new expression trees, or NULL if nexprtrees is 0 */
284  SCIP_Real* coefs /**< coefficients of expression trees, or NULL if all 1.0 */
285  );
286 
287 /** adds expression trees to a nonlinear constraint
288  * constraint must not be active yet
289  */
290 extern
291 SCIP_RETCODE SCIPaddExprtreesNonlinear(
292  SCIP* scip, /**< SCIP data structure */
293  SCIP_CONS* cons, /**< constraint */
294  int nexprtrees, /**< number of expression trees */
295  SCIP_EXPRTREE** exprtrees, /**< new expression trees, or NULL if nexprtrees is 0 */
296  SCIP_Real* coefs /**< coefficients of expression trees, or NULL if all 1.0 */
297  );
298 
299 /** gets the nonlinear constraint as a nonlinear row representation */
300 extern
301 SCIP_RETCODE SCIPgetNlRowNonlinear(
302  SCIP* scip, /**< SCIP data structure */
303  SCIP_CONS* cons, /**< constraint */
304  SCIP_NLROW** nlrow /**< pointer to store nonlinear row */
305  );
306 
307 /** gets the number of variables in the linear term of a nonlinear constraint */
308 extern
309 int SCIPgetNLinearVarsNonlinear(
310  SCIP* scip, /**< SCIP data structure */
311  SCIP_CONS* cons /**< constraint */
312  );
313 
314 /** gets the variables in the linear part of a nonlinear constraint */
315 extern
316 SCIP_VAR** SCIPgetLinearVarsNonlinear(
317  SCIP* scip, /**< SCIP data structure */
318  SCIP_CONS* cons /**< constraint */
319  );
320 
321 /** gets the coefficients in the linear part of a nonlinear constraint */
322 extern
323 SCIP_Real* SCIPgetLinearCoefsNonlinear(
324  SCIP* scip, /**< SCIP data structure */
325  SCIP_CONS* cons /**< constraint */
326  );
327 
328 /** gets the number of expression trees of a nonlinear constraint */
329 extern
330 int SCIPgetNExprtreesNonlinear(
331  SCIP* scip, /**< SCIP data structure */
332  SCIP_CONS* cons /**< constraint */
333  );
334 
335 /** gets the expression trees of a nonlinear constraint */
336 extern
337 SCIP_EXPRTREE** SCIPgetExprtreesNonlinear(
338  SCIP* scip, /**< SCIP data structure */
339  SCIP_CONS* cons /**< constraint */
340  );
341 
342 /** gets the coefficients of the expression trees of a nonlinear constraint */
343 extern
344 SCIP_Real* SCIPgetExprtreeCoefsNonlinear(
345  SCIP* scip, /**< SCIP data structure */
346  SCIP_CONS* cons /**< constraint */
347  );
348 
349 /** gets the expression graph node of a nonlinear constraint */
350 extern
351 SCIP_EXPRGRAPHNODE* SCIPgetExprgraphNodeNonlinear(
352  SCIP* scip, /**< SCIP data structure */
353  SCIP_CONS* cons /**< constraint */
354  );
355 
356 /** gets the left hand side of a nonlinear constraint */
357 extern
358 SCIP_Real SCIPgetLhsNonlinear(
359  SCIP* scip, /**< SCIP data structure */
360  SCIP_CONS* cons /**< constraint */
361  );
362 
363 /** gets the right hand side of a nonlinear constraint */
364 extern
365 SCIP_Real SCIPgetRhsNonlinear(
366  SCIP* scip, /**< SCIP data structure */
367  SCIP_CONS* cons /**< constraint */
368  );
369 
370 /** check the function of a nonlinear constraint for convexity/concavity, if not done yet */
371 extern
372 SCIP_RETCODE SCIPcheckCurvatureNonlinear(
373  SCIP* scip, /**< SCIP data structure */
374  SCIP_CONS* cons /**< constraint */
375  );
376 
377 /** gets the curvature of the nonlinear function of a nonlinear constraint
378  *
379  * The curvature is computed by summing up the curvature for each nonlinear summand.
380  * To get the curvature for single summands, use SCIPgetExprtreeCurvaturesNonlinear().
381  */
382 extern
383 SCIP_RETCODE SCIPgetCurvatureNonlinear(
384  SCIP* scip, /**< SCIP data structure */
385  SCIP_CONS* cons, /**< constraint */
386  SCIP_Bool checkcurv, /**< whether to check constraint curvature, if not checked before */
387  SCIP_EXPRCURV* curvature /**< pointer to store curvature of constraint */
388  );
389 
390 /** gets the curvature of the expression trees (multiplied by their coefficient) of a nonlinear constraint */
391 extern
392 SCIP_RETCODE SCIPgetExprtreeCurvaturesNonlinear(
393  SCIP* scip, /**< SCIP data structure */
394  SCIP_CONS* cons, /**< constraint */
395  SCIP_Bool checkcurv, /**< whether to check constraint curvature, if not checked before */
396  SCIP_EXPRCURV** curvatures /**< buffer to store curvatures of exprtrees */
397  );
398 
399 /** computes the violation of a nonlinear constraint by a solution */
400 extern
401 SCIP_RETCODE SCIPgetViolationNonlinear(
402  SCIP* scip, /**< SCIP data structure */
403  SCIP_CONS* cons, /**< constraint */
404  SCIP_SOL* sol, /**< solution which violation to calculate, or NULL for LP solution */
405  SCIP_Real* violation /**< pointer to store violation of constraint */
406  );
407 
408 /** gets expression graph of nonlinear constraint handler */
409 extern
410 SCIP_EXPRGRAPH* SCIPgetExprgraphNonlinear(
411  SCIP* scip, /**< SCIP data structure */
412  SCIP_CONSHDLR* conshdlr /**< nonlinear constraint handler */
413  );
414 
415 #ifdef __cplusplus
416 }
417 #endif
418 
419 #endif
420