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-2020 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 scipopt.org. */
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 Leona 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 #ifdef __cplusplus
45 extern "C" {
46 #endif
47 
48 /**@addtogroup PublicNonlinearMethods
49  *
50  * @{
51  */
52 
53 /** computes coefficients of linearization of a square term in a reference point */
56  SCIP* scip, /**< SCIP data structure */
57  SCIP_Real sqrcoef, /**< coefficient of square term */
58  SCIP_Real refpoint, /**< point where to linearize */
59  SCIP_Bool isint, /**< whether corresponding variable is a discrete variable, and thus linearization could be moved */
60  SCIP_Real* lincoef, /**< buffer to add coefficient of linearization */
61  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
62  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
63  );
64 
65 /** computes coefficients of secant of a square term */
68  SCIP* scip, /**< SCIP data structure */
69  SCIP_Real sqrcoef, /**< coefficient of square term */
70  SCIP_Real lb, /**< lower bound on variable */
71  SCIP_Real ub, /**< upper bound on variable */
72  SCIP_Real refpoint, /**< point for which to compute value of linearization */
73  SCIP_Real* lincoef, /**< buffer to add coefficient of secant */
74  SCIP_Real* linconstant, /**< buffer to add constant of secant */
75  SCIP_Bool* success /**< buffer to set to FALSE if secant has failed due to large numbers or unboundedness */
76  );
77 
78 /** computes coefficients of linearization of a bilinear term in a reference point */
81  SCIP* scip, /**< SCIP data structure */
82  SCIP_Real bilincoef, /**< coefficient of bilinear term */
83  SCIP_Real refpointx, /**< point where to linearize first variable */
84  SCIP_Real refpointy, /**< point where to linearize second variable */
85  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
86  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
87  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
88  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
89  );
90 
91 /** computes coefficients of McCormick under- or overestimation of a bilinear term */
94  SCIP* scip, /**< SCIP data structure */
95  SCIP_Real bilincoef, /**< coefficient of bilinear term */
96  SCIP_Real lbx, /**< lower bound on first variable */
97  SCIP_Real ubx, /**< upper bound on first variable */
98  SCIP_Real refpointx, /**< reference point for first variable */
99  SCIP_Real lby, /**< lower bound on second variable */
100  SCIP_Real uby, /**< upper bound on second variable */
101  SCIP_Real refpointy, /**< reference point for second variable */
102  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
103  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
104  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
105  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
106  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
107  );
108 
109 /** computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality
110  * involving only the variables of the bilinear term
111  *
112  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
113  * by Marco Locatelli
114  */
117  SCIP* scip, /**< SCIP data structure */
118  SCIP_Real bilincoef, /**< coefficient of bilinear term */
119  SCIP_Real lbx, /**< lower bound on first variable */
120  SCIP_Real ubx, /**< upper bound on first variable */
121  SCIP_Real refpointx, /**< reference point for first variable */
122  SCIP_Real lby, /**< lower bound on second variable */
123  SCIP_Real uby, /**< upper bound on second variable */
124  SCIP_Real refpointy, /**< reference point for second variable */
125  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
126  SCIP_Real xcoef, /**< x coefficient of linear inequality; must be in {-1,0,1} */
127  SCIP_Real ycoef, /**< y coefficient of linear inequality */
128  SCIP_Real constant, /**< constant of linear inequality */
129  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
130  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
131  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
132  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
133  );
134 
135 /** computes coefficients of linearization of a bilinear term in a reference point when given two linear inequality
136  * involving only the variables of the bilinear term
137  *
138  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
139  * by Marco Locatelli
140  *
141  */
144  SCIP* scip, /**< SCIP data structure */
145  SCIP_Real bilincoef, /**< coefficient of bilinear term */
146  SCIP_Real lbx, /**< lower bound on first variable */
147  SCIP_Real ubx, /**< upper bound on first variable */
148  SCIP_Real refpointx, /**< reference point for first variable */
149  SCIP_Real lby, /**< lower bound on second variable */
150  SCIP_Real uby, /**< upper bound on second variable */
151  SCIP_Real refpointy, /**< reference point for second variable */
152  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
153  SCIP_Real alpha1, /**< x coefficient of linear inequality; must be in {-1,0,1} */
154  SCIP_Real beta1, /**< y coefficient of linear inequality */
155  SCIP_Real gamma1, /**< constant of linear inequality */
156  SCIP_Real alpha2, /**< x coefficient of linear inequality; must be in {-1,0,1} */
157  SCIP_Real beta2, /**< y coefficient of linear inequality */
158  SCIP_Real gamma2, /**< constant of linear inequality */
159  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
160  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
161  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
162  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
163  );
164 
165 /** creates an NLP relaxation and stores it in a given NLPI problem; the function computes for each variable which the
166  * number of non-linearly occurrences and stores it in the nlscore array
167  *
168  * @note the first row corresponds always to the cutoff row (even if cutoffbound is SCIPinfinity(scip))
169  **/
172  SCIP* scip, /**< SCIP data structure */
173  SCIP_NLPI* nlpi, /**< interface to NLP solver */
174  SCIP_NLROW** nlrows, /**< nonlinear rows */
175  int nnlrows, /**< total number of nonlinear rows */
176  SCIP_NLPIPROBLEM* nlpiprob, /**< empty nlpi problem */
177  SCIP_HASHMAP* var2idx, /**< empty hash map to store mapping between variables and indices in nlpi
178  * problem */
179  SCIP_HASHMAP* nlrow2idx, /**< empty hash map to store mapping between variables and indices in nlpi
180  * problem, can be NULL */
181  SCIP_Real* nlscore, /**< array to store the score of each nonlinear variable (NULL if not
182  * needed) */
183  SCIP_Real cutoffbound, /**< cutoff bound */
184  SCIP_Bool setobj, /**< should the objective function be set? */
185  SCIP_Bool onlyconvex /**< filter only for convex constraints */
186  );
187 
188 /** updates bounds of each variable and the cutoff row in the nlpiproblem */
191  SCIP* scip, /**< SCIP data structure */
192  SCIP_NLPI* nlpi, /**< interface to NLP solver */
193  SCIP_NLPIPROBLEM* nlpiprob, /**< nlpi problem representing the convex NLP relaxation */
194  SCIP_HASHMAP* var2nlpiidx, /**< mapping between variables and nlpi indices */
195  SCIP_VAR** nlpivars, /**< array containing all variables of the nlpi */
196  int nlpinvars, /**< total number of nlpi variables */
197  SCIP_Real cutoffbound /**< new cutoff bound */
198  );
199 
200 /** adds linear rows to the NLP relaxation */
203  SCIP* scip, /**< SCIP data structure */
204  SCIP_NLPI* nlpi, /**< interface to NLP solver */
205  SCIP_NLPIPROBLEM* nlpiprob, /**< nlpi problem */
206  SCIP_HASHMAP* var2idx, /**< empty hash map to store mapping between variables and indices in nlpi
207  * problem */
208  SCIP_ROW** rows, /**< rows to add */
209  int nrows /**< total number of rows to add */
210  );
211 
212 /**@} */
213 
214 #ifdef __cplusplus
215 }
216 #endif
217 
218 #endif
type definitions for miscellaneous datastructures
type definitions for NLP management
#define SCIP_EXPORT
Definition: def.h:100
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
type definitions for return codes for SCIP methods
SCIP_EXPORT 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)
SCIP_EXPORT 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 LP management
SCIP_EXPORT 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)
SCIP_EXPORT 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 SCIP&#39;s main datastructure
SCIP_EXPORT SCIP_RETCODE SCIPcreateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLROW **nlrows, int nnlrows, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_HASHMAP *nlrow2idx, SCIP_Real *nlscore, SCIP_Real cutoffbound, SCIP_Bool setobj, SCIP_Bool onlyconvex)
type definitions for problem variables
#define SCIP_Bool
Definition: def.h:70
SCIP_EXPORT SCIP_RETCODE SCIPupdateNlpiProb(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2nlpiidx, SCIP_VAR **nlpivars, int nlpinvars, SCIP_Real cutoffbound)
#define SCIP_Real
Definition: def.h:163
common defines and data types used in all packages of SCIP
SCIP_EXPORT 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)
SCIP_EXPORT 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)
SCIP_EXPORT SCIP_RETCODE SCIPaddNlpiProbRows(SCIP *scip, SCIP_NLPI *nlpi, SCIP_NLPIPROBLEM *nlpiprob, SCIP_HASHMAP *var2idx, SCIP_ROW **rows, int nrows)
type definitions for specific NLP solver interfaces