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 (C) 2002-2022 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 nlhdlr_bilinear.h
17  * @ingroup NLHDLRS
18  * @brief bilinear nonlinear handler
19  * @author Benjamin Mueller
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #ifndef __SCIP_NLHDLR_BILINEAR_H__
25 #define __SCIP_NLHDLR_BILINEAR_H__
26 
27 #include "scip/scip.h"
28 #include "scip/pub_nlhdlr.h"
29 
30 #ifdef __cplusplus
31 extern "C" {
32 #endif
33 
34 /** includes bilinear nonlinear handler in nonlinear constraint handler
35  *
36  * @ingroup NlhdlrIncludes
37  */
38 SCIP_EXPORT
39 SCIP_RETCODE SCIPincludeNlhdlrBilinear(
40  SCIP* scip /**< SCIP data structure */
41  );
42 
43 /**@addtogroup NLHDLRS
44  * @{
45  *
46  * @name Bilinear nonlinear handler
47  *
48  * This nonlinear handler detects and collects bilinear terms and provides specialized propagation and estimation functionality.
49  *
50  * @{
51  */
52 
53 /** returns an array of expressions that have been detected by the bilinear nonlinear handler */
54 SCIP_EXPORT
55 SCIP_EXPR** SCIPgetExprsBilinear(
56  SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
57  );
58 
59 /** returns an array of nonlinear handler expressions data of expressions that have been detected by the bilinear nonlinear handler */
60 SCIP_EXPORT
61 SCIP_NLHDLREXPRDATA** SCIPgetExprsdataBilinear(
62  SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
63  );
64 
65 /** returns the total number of expressions that have been detected by the bilinear nonlinear handler */
66 SCIP_EXPORT
67 int SCIPgetNExprsBilinear(
68  SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
69  );
70 
71 /** 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$ */
72 SCIP_EXPORT
73 SCIP_RETCODE SCIPaddIneqBilinear(
74  SCIP* scip, /**< SCIP data structure */
75  SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
76  SCIP_EXPR* expr, /**< product expression */
77  SCIP_Real xcoef, /**< x coefficient */
78  SCIP_Real ycoef, /**< y coefficient */
79  SCIP_Real constant, /**< constant part */
80  SCIP_Bool* success /**< buffer to store whether inequality has been accepted */
81  );
82 
83 /** computes coefficients of linearization of a bilinear term in a reference point */
84 SCIP_EXPORT
85 void SCIPaddBilinLinearization(
86  SCIP* scip, /**< SCIP data structure */
87  SCIP_Real bilincoef, /**< coefficient of bilinear term */
88  SCIP_Real refpointx, /**< point where to linearize first variable */
89  SCIP_Real refpointy, /**< point where to linearize second variable */
90  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
91  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
92  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
93  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
94  );
95 
96 /** computes coefficients of McCormick under- or overestimation of a bilinear term */
97 SCIP_EXPORT
98 void SCIPaddBilinMcCormick(
99  SCIP* scip, /**< SCIP data structure */
100  SCIP_Real bilincoef, /**< coefficient of bilinear term */
101  SCIP_Real lbx, /**< lower bound on first variable */
102  SCIP_Real ubx, /**< upper bound on first variable */
103  SCIP_Real refpointx, /**< reference point for first variable */
104  SCIP_Real lby, /**< lower bound on second variable */
105  SCIP_Real uby, /**< upper bound on second variable */
106  SCIP_Real refpointy, /**< reference point for second variable */
107  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
108  SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
109  SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
110  SCIP_Real* linconstant, /**< buffer to add constant of linearization */
111  SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
112  );
113 
114 /** computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality
115  * involving only the variables of the bilinear term
116  *
117  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
118  * by Marco Locatelli
119  */
120 SCIP_EXPORT
121 void SCIPcomputeBilinEnvelope1(
122  SCIP* scip, /**< SCIP data structure */
123  SCIP_Real bilincoef, /**< coefficient of bilinear term */
124  SCIP_Real lbx, /**< lower bound on first variable */
125  SCIP_Real ubx, /**< upper bound on first variable */
126  SCIP_Real refpointx, /**< reference point for first variable */
127  SCIP_Real lby, /**< lower bound on second variable */
128  SCIP_Real uby, /**< upper bound on second variable */
129  SCIP_Real refpointy, /**< reference point for second variable */
130  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
131  SCIP_Real xcoef, /**< x coefficient of linear inequality; must be in {-1,0,1} */
132  SCIP_Real ycoef, /**< y coefficient of linear inequality */
133  SCIP_Real constant, /**< constant of linear inequality */
134  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
135  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
136  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
137  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
138  );
139 
140 /** computes coefficients of linearization of a bilinear term in a reference point when given two linear inequalities
141  * involving only the variables of the bilinear term
142  *
143  * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
144  * by Marco Locatelli
145  */
146 SCIP_EXPORT
147 void SCIPcomputeBilinEnvelope2(
148  SCIP* scip, /**< SCIP data structure */
149  SCIP_Real bilincoef, /**< coefficient of bilinear term */
150  SCIP_Real lbx, /**< lower bound on first variable */
151  SCIP_Real ubx, /**< upper bound on first variable */
152  SCIP_Real refpointx, /**< reference point for first variable */
153  SCIP_Real lby, /**< lower bound on second variable */
154  SCIP_Real uby, /**< upper bound on second variable */
155  SCIP_Real refpointy, /**< reference point for second variable */
156  SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
157  SCIP_Real alpha1, /**< x coefficient of linear inequality; must be in {-1,0,1} */
158  SCIP_Real beta1, /**< y coefficient of linear inequality */
159  SCIP_Real gamma1, /**< constant of linear inequality */
160  SCIP_Real alpha2, /**< x coefficient of linear inequality; must be in {-1,0,1} */
161  SCIP_Real beta2, /**< y coefficient of linear inequality */
162  SCIP_Real gamma2, /**< constant of linear inequality */
163  SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
164  SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
165  SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
166  SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
167  );
168 
169 /** @}
170  * @}
171  */
172 
173 #ifdef __cplusplus
174 }
175 #endif
176 
177 #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:2184
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
SCIP_Nlhdlr
Definition: struct_nlhdlr.h:34
SCIP_Expr
Definition: struct_expr.h:95
SCIP_Bool
#define SCIP_Bool
Definition: def.h:84
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:1752
SCIPgetExprsBilinear
SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1518
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:1550
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:1705
SCIPincludeNlhdlrBilinear
SCIP_RETCODE SCIPincludeNlhdlrBilinear(SCIP *scip)
Definition: nlhdlr_bilinear.c:1461
SCIPgetNExprsBilinear
int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr_bilinear.c:1534
SCIP_Real
#define SCIP_Real
Definition: def.h:177
SCIP_NLHDLREXPRDATA
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:404
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:1960
pub_nlhdlr.h
public functions of nonlinear handlers of nonlinear constraints
SCIPgetExprsdataBilinear
SCIP_NLHDLREXPRDATA ** SCIPgetExprsdataBilinear(SCIP_NLHDLR *nlhdlr)
scip.h
SCIP callable library.