1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */ 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__ */ 187