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-2025 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
    40extern "C" {
    41#endif
    42
    43/** includes bilinear nonlinear handler in nonlinear constraint handler
    44 *
    45 * @ingroup NlhdlrIncludes
    46 */
    47SCIP_EXPORT
    48SCIP_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 */
    63SCIP_EXPORT
    64SCIP_EXPR** SCIPgetExprsBilinear(
    65 SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
    66 );
    67
    68/** returns the total number of expressions that have been detected by the bilinear nonlinear handler */
    69SCIP_EXPORT
    70int SCIPgetNExprsBilinear(
    71 SCIP_NLHDLR* nlhdlr /**< nonlinear handler */
    72 );
    73
    74/** 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$ */
    75SCIP_EXPORT
    76SCIP_RETCODE SCIPaddIneqBilinear(
    77 SCIP* scip, /**< SCIP data structure */
    78 SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
    79 SCIP_EXPR* expr, /**< product expression */
    80 SCIP_Real xcoef, /**< x coefficient */
    81 SCIP_Real ycoef, /**< y coefficient */
    82 SCIP_Real constant, /**< constant part */
    83 SCIP_Bool* success /**< buffer to store whether inequality has been accepted */
    84 );
    85
    86/** computes coefficients of linearization of a bilinear term in a reference point */
    87SCIP_EXPORT
    88void SCIPaddBilinLinearization(
    89 SCIP* scip, /**< SCIP data structure */
    90 SCIP_Real bilincoef, /**< coefficient of bilinear term */
    91 SCIP_Real refpointx, /**< point where to linearize first variable */
    92 SCIP_Real refpointy, /**< point where to linearize second variable */
    93 SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
    94 SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
    95 SCIP_Real* linconstant, /**< buffer to add constant of linearization */
    96 SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
    97 );
    98
    99/** computes coefficients of McCormick under- or overestimation of a bilinear term */
    100SCIP_EXPORT
    101void SCIPaddBilinMcCormick(
    102 SCIP* scip, /**< SCIP data structure */
    103 SCIP_Real bilincoef, /**< coefficient of bilinear term */
    104 SCIP_Real lbx, /**< lower bound on first variable */
    105 SCIP_Real ubx, /**< upper bound on first variable */
    106 SCIP_Real refpointx, /**< reference point for first variable */
    107 SCIP_Real lby, /**< lower bound on second variable */
    108 SCIP_Real uby, /**< upper bound on second variable */
    109 SCIP_Real refpointy, /**< reference point for second variable */
    110 SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
    111 SCIP_Real* lincoefx, /**< buffer to add coefficient of first variable in linearization */
    112 SCIP_Real* lincoefy, /**< buffer to add coefficient of second variable in linearization */
    113 SCIP_Real* linconstant, /**< buffer to add constant of linearization */
    114 SCIP_Bool* success /**< buffer to set to FALSE if linearization has failed due to large numbers */
    115 );
    116
    117/** computes coefficients of linearization of a bilinear term in a reference point when given a linear inequality
    118 * involving only the variables of the bilinear term
    119 *
    120 * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
    121 * by Marco Locatelli
    122 */
    123SCIP_EXPORT
    124void SCIPcomputeBilinEnvelope1(
    125 SCIP* scip, /**< SCIP data structure */
    126 SCIP_Real bilincoef, /**< coefficient of bilinear term */
    127 SCIP_Real lbx, /**< lower bound on first variable */
    128 SCIP_Real ubx, /**< upper bound on first variable */
    129 SCIP_Real refpointx, /**< reference point for first variable */
    130 SCIP_Real lby, /**< lower bound on second variable */
    131 SCIP_Real uby, /**< upper bound on second variable */
    132 SCIP_Real refpointy, /**< reference point for second variable */
    133 SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
    134 SCIP_Real xcoef, /**< x coefficient of linear inequality; must be in {-1,0,1} */
    135 SCIP_Real ycoef, /**< y coefficient of linear inequality */
    136 SCIP_Real constant, /**< constant of linear inequality */
    137 SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
    138 SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
    139 SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
    140 SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
    141 );
    142
    143/** computes coefficients of linearization of a bilinear term in a reference point when given two linear inequalities
    144 * involving only the variables of the bilinear term
    145 *
    146 * @note the formulas are extracted from "Convex envelopes of bivariate functions through the solution of KKT systems"
    147 * by Marco Locatelli
    148 */
    149SCIP_EXPORT
    150void SCIPcomputeBilinEnvelope2(
    151 SCIP* scip, /**< SCIP data structure */
    152 SCIP_Real bilincoef, /**< coefficient of bilinear term */
    153 SCIP_Real lbx, /**< lower bound on first variable */
    154 SCIP_Real ubx, /**< upper bound on first variable */
    155 SCIP_Real refpointx, /**< reference point for first variable */
    156 SCIP_Real lby, /**< lower bound on second variable */
    157 SCIP_Real uby, /**< upper bound on second variable */
    158 SCIP_Real refpointy, /**< reference point for second variable */
    159 SCIP_Bool overestimate, /**< whether to compute an overestimator instead of an underestimator */
    160 SCIP_Real xcoef1, /**< x coefficient of linear inequality; must be in {-1,0,1} */
    161 SCIP_Real ycoef1, /**< y coefficient of linear inequality */
    162 SCIP_Real constant1, /**< constant of linear inequality */
    163 SCIP_Real xcoef2, /**< x coefficient of linear inequality; must be in {-1,0,1} */
    164 SCIP_Real ycoef2, /**< y coefficient of linear inequality */
    165 SCIP_Real constant2, /**< constant of linear inequality */
    166 SCIP_Real* RESTRICT lincoefx, /**< buffer to store coefficient of first variable in linearization */
    167 SCIP_Real* RESTRICT lincoefy, /**< buffer to store coefficient of second variable in linearization */
    168 SCIP_Real* RESTRICT linconstant, /**< buffer to store constant of linearization */
    169 SCIP_Bool* RESTRICT success /**< buffer to store whether linearization was successful */
    170 );
    171
    172/** @}
    173 * @}
    174 */
    175
    176#ifdef __cplusplus
    177}
    178#endif
    179
    180#endif /* __SCIP_NLHDLR_BILINEAR_H__ */
    SCIP_Bool
    #define SCIP_Bool
    Definition: def.h:91
    SCIP_Real
    #define SCIP_Real
    Definition: def.h:156
    RESTRICT
    #define RESTRICT
    Definition: def.h:260
    SCIPgetNExprsBilinear
    int SCIPgetNExprsBilinear(SCIP_NLHDLR *nlhdlr)
    Definition: nlhdlr_bilinear.c:1628
    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 xcoef1, SCIP_Real ycoef1, SCIP_Real constant1, SCIP_Real xcoef2, SCIP_Real ycoef2, SCIP_Real constant2, SCIP_Real *RESTRICT lincoefx, SCIP_Real *RESTRICT lincoefy, SCIP_Real *RESTRICT linconstant, SCIP_Bool *RESTRICT success)
    Definition: nlhdlr_bilinear.c:2279
    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:1847
    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:2055
    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:1644
    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:1800
    SCIPgetExprsBilinear
    SCIP_EXPR ** SCIPgetExprsBilinear(SCIP_NLHDLR *nlhdlr)
    Definition: nlhdlr_bilinear.c:1612
    SCIPincludeNlhdlrBilinear
    SCIP_RETCODE SCIPincludeNlhdlrBilinear(SCIP *scip)
    Definition: nlhdlr_bilinear.c:1555
    pub_nlhdlr.h
    public functions of nonlinear handlers of nonlinear constraints
    scip.h
    SCIP callable library.
    SCIP_Expr
    Definition: struct_expr.h:106
    SCIP_Nlhdlr
    Definition: struct_nlhdlr.h:44
    SCIP_RETCODE
    enum SCIP_Retcode SCIP_RETCODE
    Definition: type_retcode.h:63