Scippy

SCIP

Solving Constraint Integer Programs

scip_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-2019 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 visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip_nonlinear.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public methods for nonlinear functions
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Thorsten Koch
22  * @author Alexander Martin
23  * @author Marc Pfetsch
24  * @author Kati Wolter
25  * @author Gregor Hendel
26  * @author Robert Lion Gottwald
27  */
28 
29 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
30 
31 #ifndef __SCIP_SCIP_NONLINEAR_H__
32 #define __SCIP_SCIP_NONLINEAR_H__
33 
34 
35 #include "nlpi/type_nlpi.h"
36 #include "scip/def.h"
37 #include "scip/type_lp.h"
38 #include "scip/type_misc.h"
39 #include "scip/type_nlp.h"
40 #include "scip/type_retcode.h"
41 #include "scip/type_scip.h"
42 #include "scip/type_var.h"
43 
44 /* In debug mode, we include the SCIP's structure in scip.c, such that no one can access
45  * this structure except the interface methods in scip.c.
46  * In optimized mode, the structure is included in scip.h, because some of the methods
47  * are implemented as defines for performance reasons (e.g. the numerical comparisons).
48  * Additionally, the internal "set.h" is included, such that the defines in set.h are
49  * available in optimized mode.
50  */
51 #ifdef NDEBUG
52 #include "scip/struct_scip.h"
53 #include "scip/struct_stat.h"
54 #include "scip/set.h"
55 #include "scip/tree.h"
56 #include "scip/misc.h"
57 #include "scip/var.h"
58 #include "scip/cons.h"
59 #include "scip/solve.h"
60 #include "scip/debug.h"
61 #endif
62 
63 #ifdef __cplusplus
64 extern "C" {
65 #endif
66 
67 /**@addtogroup PublicNonlinearMethods
68  *
69  * @{
70  */
71 
72 /** computes coefficients of linearization of a square term in a reference point */
73 extern
75  SCIP* scip, /**< SCIP data structure */
76  SCIP_Real sqrcoef, /**< coefficient of square term */
77  SCIP_Real refpoint, /**< point where to linearize */
78  SCIP_Bool isint, /**< whether corresponding variable is a discrete variable, and thus linearization could be moved */
79  SCIP_Real* lincoef, /**< buffer to add coefficient of linearization */
80  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
81  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
82  );
83 
84 /** computes coefficients of secant of a square term */
85 extern
87  SCIP* scip, /**< SCIP data structure */
88  SCIP_Real sqrcoef, /**< coefficient of square term */
89  SCIP_Real lb, /**< lower bound on variable */
90  SCIP_Real ub, /**< upper bound on variable */
91  SCIP_Real refpoint, /**< point for which to compute value of linearization */
92  SCIP_Real* lincoef, /**< buffer to add coefficient of secant */
93  SCIP_Real* linconstant, /**< buffer to add constant of secant */
94  SCIP_Bool* success /**< buffer to set to FALSE if secant has failed due to large numbers or unboundedness */
95  );
96 
97 /** computes coefficients of linearization of a bilinear term in a reference point */
98 extern
100  SCIP* scip, /**< SCIP data structure */
101  SCIP_Real bilincoef, /**< coefficient of bilinear term */
102  SCIP_Real refpointx, /**< point where to linearize first variable */
103  SCIP_Real refpointy, /**< point where to linearize second variable */
104  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
105  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
106  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
107  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
108  );
109 
110 /** computes coefficients of McCormick under- or overestimation of a bilinear term */
111 extern
113  SCIP* scip, /**< SCIP data structure */
114  SCIP_Real bilincoef, /**< coefficient of bilinear term */
115  SCIP_Real lbx, /**< lower bound on first variable */
116  SCIP_Real ubx, /**< upper bound on first variable */
117  SCIP_Real refpointx, /**< reference point for first variable */
118  SCIP_Real lby, /**< lower bound on second variable */
119  SCIP_Real uby, /**< upper bound on second variable */
120  SCIP_Real refpointy, /**< reference point for second variable */
121  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
122  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
123  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
124  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
125  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
126  );
127 
128 /** computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality
129  * involving only the variables of the bilinear term
130  *
131  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
132  * by Marco Locatelli
133  */
134 extern
136  SCIP* scip, /**< SCIP data structure */
137  SCIP_Real bilincoef, /**< coefficient of bilinear term */
138  SCIP_Real lbx, /**< lower bound on first variable */
139  SCIP_Real ubx, /**< upper bound on first variable */
140  SCIP_Real refpointx, /**< reference point for first variable */
141  SCIP_Real lby, /**< lower bound on second variable */
142  SCIP_Real uby, /**< upper bound on second variable */
143  SCIP_Real refpointy, /**< reference point for second variable */
144  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
145  SCIP_Real xcoef, /**< x coefficient of linear inequality; must be in {-1,0,1} */
146  SCIP_Real ycoef, /**< y coefficient of linear inequality */
147  SCIP_Real constant, /**< constant of linear inequality */
148  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
149  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
150  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
151  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
152  );
153 
154 /** computes coefficients of linearization of a bilinear term in a reference point when given two linear inequality
155  * involving only the variables of the bilinear term
156  *
157  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
158  * by Marco Locatelli
159  *
160  */
161 extern
163  SCIP* scip, /**< SCIP data structure */
164  SCIP_Real bilincoef, /**< coefficient of bilinear term */
165  SCIP_Real lbx, /**< lower bound on first variable */
166  SCIP_Real ubx, /**< upper bound on first variable */
167  SCIP_Real refpointx, /**< reference point for first variable */
168  SCIP_Real lby, /**< lower bound on second variable */
169  SCIP_Real uby, /**< upper bound on second variable */
170  SCIP_Real refpointy, /**< reference point for second variable */
171  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
172  SCIP_Real alpha1, /**< x coefficient of linear inequality; must be in {-1,0,1} */
173  SCIP_Real beta1, /**< y coefficient of linear inequality */
174  SCIP_Real gamma1, /**< constant of linear inequality */
175  SCIP_Real alpha2, /**< x coefficient of linear inequality; must be in {-1,0,1} */
176  SCIP_Real beta2, /**< y coefficient of linear inequality */
177  SCIP_Real gamma2, /**< constant of linear inequality */
178  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
179  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
180  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
181  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
182  );
183 
184 /** creates an NLP relaxation and stores it in a given NLPI problem; the function computes for each variable which the
185  * number of non-linearly occurrences and stores it in the nlscore array
186  *
187  * @note the first row corresponds always to the cutoff row (even if cutoffbound is SCIPinfinity(scip))
188  **/
189 extern
191  SCIP* scip, /**< SCIP data structure */
192  SCIP_NLPI* nlpi, /**< interface to NLP solver */
193  SCIP_NLROW** nlrows, /**< nonlinear rows */
194  int nnlrows, /**< total number of nonlinear rows */
195  SCIP_NLPIPROBLEM* nlpiprob, /**< empty nlpi problem */
196  SCIP_HASHMAP* var2idx, /**< empty hash map to store mapping between variables and indices in nlpi
197  * problem */
198  SCIP_Real* nlscore, /**< array to store the score of each nonlinear variable (NULL if not
199  * needed) */
200  SCIP_Real cutoffbound, /**< cutoff bound */
201  SCIP_Bool setobj, /**< should the objective function be set? */
202  SCIP_Bool onlyconvex /**< filter only for convex constraints */
203  );
204 
205 /** updates bounds of each variable and the cutoff row in the nlpiproblem */
206 extern
208  SCIP* scip, /**< SCIP data structure */
209  SCIP_NLPI* nlpi, /**< interface to NLP solver */
210  SCIP_NLPIPROBLEM* nlpiprob, /**< nlpi problem representing the convex NLP relaxation */
211  SCIP_HASHMAP* var2nlpiidx, /**< mapping between variables and nlpi indices */
212  SCIP_VAR** nlpivars, /**< array containing all variables of the nlpi */
213  int nlpinvars, /**< total number of nlpi variables */
214  SCIP_Real cutoffbound /**< new cutoff bound */
215  );
216 
217 /** adds linear rows to the NLP relaxation */
218 extern
220  SCIP* scip, /**< SCIP data structure */
221  SCIP_NLPI* nlpi, /**< interface to NLP solver */
222  SCIP_NLPIPROBLEM* nlpiprob, /**< nlpi problem */
223  SCIP_HASHMAP* var2idx, /**< empty hash map to store mapping between variables and indices in nlpi
224  * problem */
225  SCIP_ROW** rows, /**< rows to add */
226  int nrows /**< total number of rows to add */
227  );
228 
229 /**@} */
230 
231 #ifdef __cplusplus
232 }
233 #endif
234 
235 #endif
internal methods for branch and bound tree
type definitions for miscellaneous datastructures
type definitions for NLP management
SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
#define RESTRICT
Definition: def.h:258
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
void SCIPaddBilinLinearization(SCIP *scip, SCIP_Real bilincoef, SCIP_Real refpointx, SCIP_Real refpointy, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
type definitions for return codes for SCIP methods
void SCIPcomputeBilinEnvelope2(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real alpha1, SCIP_Real beta1, SCIP_Real gamma1, SCIP_Real alpha2, SCIP_Real beta2, SCIP_Real gamma2, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
type definitions for LP management
void SCIPcomputeBilinEnvelope1(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
void SCIPaddBilinMcCormick(SCIP *scip, SCIP_Real bilincoef, SCIP_Real lbx, SCIP_Real ubx, SCIP_Real refpointx, SCIP_Real lby, SCIP_Real uby, SCIP_Real refpointy, SCIP_Bool overestimate, SCIP_Real *lincoefx, SCIP_Real *lincoefy, SCIP_Real *linconstant, SCIP_Bool *success)
type definitions for SCIP&#39;s main datastructure
SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
internal miscellaneous methods
internal methods for global SCIP settings
SCIP main data structure.
type definitions for problem variables
void SCIPaddSquareSecant(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real lb, SCIP_Real ub, SCIP_Real refpoint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
internal methods for problem variables
#define SCIP_Bool
Definition: def.h:69
SCIP_RETCODE SCIPupdateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
methods for debugging
datastructures for problem statistics
internal methods for main solving loop and node processing
#define SCIP_Real
Definition: def.h:157
internal methods for constraints and constraint handlers
common defines and data types used in all packages of SCIP
void SCIPaddSquareLinearization(SCIP *scip, SCIP_Real sqrcoef, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
type definitions for specific NLP solver interfaces