Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_bilinear.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 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file nlhdlr_bilinear.h
26  * @ingroup NLHDLRS
27  * @brief bilinear nonlinear handler
28  * @author Benjamin Mueller
29  */
30 
31 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32 
33 #ifndef __SCIP_NLHDLR_BILINEAR_H__
34 #define __SCIP_NLHDLR_BILINEAR_H__
35 
36 #include "scip/scip.h"
37 #include "scip/pub_nlhdlr.h"
38 
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42 
43 /** includes bilinear nonlinear handler in nonlinear constraint handler
44  *
45  * @ingroup NlhdlrIncludes
46  */
47 SCIP_EXPORT
48 SCIP_RETCODE SCIPincludeNlhdlrBilinear(
49  SCIP* scip /**< SCIP data structure */
50  );
51 
52 /**@addtogroup NLHDLRS
53  * @{
54  *
55  * @name Bilinear nonlinear handler
56  *
57  * This nonlinear handler detects and collects bilinear terms and provides specialized propagation and estimation functionality.
58  *
59  * @{
60  */
61 
62 /** returns an array of expressions that have been detected by the bilinear nonlinear handler */
63 SCIP_EXPORT
64 SCIP_EXPR** SCIPgetExprsBilinear(
65  SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
66  );
67 
68 /** returns an array of nonlinear handler expressions data of expressions that have been detected by the bilinear nonlinear handler */
69 SCIP_EXPORT
70 SCIP_NLHDLREXPRDATA** SCIPgetExprsdataBilinear(
71  SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
72  );
73 
74 /** returns the total number of expressions that have been detected by the bilinear nonlinear handler */
75 SCIP_EXPORT
76 int SCIPgetNExprsBilinear(
77  SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
78  );
79 
80 /** adds a globally valid inequality of the form \f$\text{xcoef}\cdot x \leq \text{ycoef} \cdot y + \text{constant}\f$ to a product expression of the form \f$x\cdot y\f$ */
81 SCIP_EXPORT
82 SCIP_RETCODE SCIPaddIneqBilinear(
83  SCIP* scip, /**< SCIP data structure */
84  SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
85  SCIP_EXPR* expr, /**< product expression */
86  SCIP_Real xcoef, /**< x coefficient */
87  SCIP_Real ycoef, /**< y coefficient */
88  SCIP_Real constant, /**< constant part */
89  SCIP_Bool* success /**< buffer to store whether inequality has been accepted */
90  );
91 
92 /** computes coefficients of linearization of a bilinear term in a reference point */
93 SCIP_EXPORT
94 void SCIPaddBilinLinearization(
95  SCIP* scip, /**< SCIP data structure */
96  SCIP_Real bilincoef, /**< coefficient of bilinear term */
97  SCIP_Real refpointx, /**< point where to linearize first variable */
98  SCIP_Real refpointy, /**< point where to linearize second variable */
99  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
100  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
101  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
102  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
103  );
104 
105 /** computes coefficients of McCormick under- or overestimation of a bilinear term */
106 SCIP_EXPORT
107 void SCIPaddBilinMcCormick(
108  SCIP* scip, /**< SCIP data structure */
109  SCIP_Real bilincoef, /**< coefficient of bilinear term */
110  SCIP_Real lbx, /**< lower bound on first variable */
111  SCIP_Real ubx, /**< upper bound on first variable */
112  SCIP_Real refpointx, /**< reference point for first variable */
113  SCIP_Real lby, /**< lower bound on second variable */
114  SCIP_Real uby, /**< upper bound on second variable */
115  SCIP_Real refpointy, /**< reference point for second variable */
116  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
117  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
118  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
119  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
120  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
121  );
122 
123 /** computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality
124  * involving only the variables of the bilinear term
125  *
126  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
127  * by Marco Locatelli
128  */
129 SCIP_EXPORT
130 void SCIPcomputeBilinEnvelope1(
131  SCIP* scip, /**< SCIP data structure */
132  SCIP_Real bilincoef, /**< coefficient of bilinear term */
133  SCIP_Real lbx, /**< lower bound on first variable */
134  SCIP_Real ubx, /**< upper bound on first variable */
135  SCIP_Real refpointx, /**< reference point for first variable */
136  SCIP_Real lby, /**< lower bound on second variable */
137  SCIP_Real uby, /**< upper bound on second variable */
138  SCIP_Real refpointy, /**< reference point for second variable */
139  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
140  SCIP_Real xcoef, /**< x coefficient of linear inequality; must be in {-1,0,1} */
141  SCIP_Real ycoef, /**< y coefficient of linear inequality */
142  SCIP_Real constant, /**< constant of linear inequality */
143  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
144  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
145  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
146  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
147  );
148 
149 /** computes coefficients of linearization of a bilinear term in a reference point when given two linear inequalities
150  * involving only the variables of the bilinear term
151  *
152  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
153  * by Marco Locatelli
154  */
155 SCIP_EXPORT
156 void SCIPcomputeBilinEnvelope2(
157  SCIP* scip, /**< SCIP data structure */
158  SCIP_Real bilincoef, /**< coefficient of bilinear term */
159  SCIP_Real lbx, /**< lower bound on first variable */
160  SCIP_Real ubx, /**< upper bound on first variable */
161  SCIP_Real refpointx, /**< reference point for first variable */
162  SCIP_Real lby, /**< lower bound on second variable */
163  SCIP_Real uby, /**< upper bound on second variable */
164  SCIP_Real refpointy, /**< reference point for second variable */
165  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
166  SCIP_Real alpha1, /**< x coefficient of linear inequality; must be in {-1,0,1} */
167  SCIP_Real beta1, /**< y coefficient of linear inequality */
168  SCIP_Real gamma1, /**< constant of linear inequality */
169  SCIP_Real alpha2, /**< x coefficient of linear inequality; must be in {-1,0,1} */
170  SCIP_Real beta2, /**< y coefficient of linear inequality */
171  SCIP_Real gamma2, /**< constant of linear inequality */
172  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
173  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
174  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
175  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
176  );
177 
178 /** @}
179  * @}
180  */
181 
182 #ifdef __cplusplus
183 }
184 #endif
185 
186 #endif /* __SCIP_NLHDLR_BILINEAR_H__ */
SCIPcomputeBilinEnvelope2
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)
Definition: nlhdlr_bilinear.c:2194
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Nlhdlr
Definition: struct_nlhdlr.h:43
SCIP_Expr
Definition: struct_expr.h:104
SCIP_Bool
#define SCIP_Bool
Definition: def.h:93
SCIPaddBilinMcCormick
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)
Definition: nlhdlr_bilinear.c:1762
SCIPgetExprsBilinear
SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1527
SCIPaddIneqBilinear
SCIP_RETCODE SCIPaddIneqBilinear(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_EXPR *expr, SCIP_Real xcoef, SCIP_Real ycoef, SCIP_Real constant, SCIP_Bool *success)
Definition: nlhdlr_bilinear.c:1559
SCIPaddBilinLinearization
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)
Definition: nlhdlr_bilinear.c:1715
SCIPincludeNlhdlrBilinear
SCIP_RETCODE SCIPincludeNlhdlrBilinear(SCIP *scip)
Definition: nlhdlr_bilinear.c:1470
SCIPgetNExprsBilinear
int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1543
SCIP_Real
#define SCIP_Real
Definition: def.h:186
SCIP_NLHDLREXPRDATA
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:413
SCIPcomputeBilinEnvelope1
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)
Definition: nlhdlr_bilinear.c:1970
pub_nlhdlr.h
public functions of nonlinear handlers of nonlinear constraints
SCIPgetExprsdataBilinear
SCIP_NLHDLREXPRDATA ** SCIPgetExprsdataBilinear(SCIP_NLHDLR *nlhdlr)
scip.h
SCIP callable library.