Scippy

    SCIP

    Solving Constraint Integer Programs

    type_pricer.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 type_pricer.h
    26 * @ingroup TYPEDEFINITIONS
    27 * @brief type definitions for variable pricers
    28 * @author Tobias Achterberg
    29 */
    30
    31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
    32
    33#ifndef __SCIP_TYPE_PRICER_H__
    34#define __SCIP_TYPE_PRICER_H__
    35
    36#include "scip/def.h"
    37#include "scip/type_retcode.h"
    38#include "scip/type_scip.h"
    39
    40#ifdef __cplusplus
    41extern "C" {
    42#endif
    43
    44typedef struct SCIP_Pricer SCIP_PRICER; /**< variable pricer data */
    45typedef struct SCIP_PricerData SCIP_PRICERDATA; /**< locally defined variable pricer data */
    46
    47
    48/** copy method for pricer plugins (called when SCIP copies plugins)
    49 *
    50 * input:
    51 * - scip : SCIP main data structure
    52 * - pricer : the variable pricer itself
    53 * - valid : was the copying process valid?
    54 */
    55#define SCIP_DECL_PRICERCOPY(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer, SCIP_Bool* valid)
    56
    57/** destructor of variable pricer to free user data (called when SCIP is exiting)
    58 *
    59 * input:
    60 * - scip : SCIP main data structure
    61 * - pricer : the variable pricer itself
    62 */
    63#define SCIP_DECL_PRICERFREE(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
    64
    65/** initialization method of variable pricer (called after problem was transformed and pricer is active)
    66 *
    67 * input:
    68 * - scip : SCIP main data structure
    69 * - pricer : the variable pricer itself
    70 */
    71#define SCIP_DECL_PRICERINIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
    72
    73/** deinitialization method of variable pricer (called before transformed problem is freed and pricer is active)
    74 *
    75 * input:
    76 * - scip : SCIP main data structure
    77 * - pricer : the variable pricer itself
    78 */
    79#define SCIP_DECL_PRICEREXIT(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
    80
    81/** solving process initialization method of variable pricer (called when branch and bound process is about to begin)
    82 *
    83 * This method is called when the presolving was finished and the branch and bound process is about to begin.
    84 * The variable pricer may use this call to initialize its branch and bound specific data.
    85 *
    86 * input:
    87 * - scip : SCIP main data structure
    88 * - pricer : the variable pricer itself
    89 */
    90#define SCIP_DECL_PRICERINITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
    91
    92/** solving process deinitialization method of variable pricer (called before branch and bound process data is freed)
    93 *
    94 * This method is called before the branch and bound process is freed.
    95 * The variable pricer should use this call to clean up its branch and bound data.
    96 *
    97 * input:
    98 * - scip : SCIP main data structure
    99 * - pricer : the variable pricer itself
    100 */
    101#define SCIP_DECL_PRICEREXITSOL(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer)
    102
    103/** reduced cost pricing method of variable pricer for feasible LPs
    104 *
    105 * Searches for variables that can contribute to improve the current LP's solution value.
    106 * In standard branch-and-price, these are variables with negative dual feasibility, that is negative
    107 * reduced costs for non-negative variables, positive reduced costs for non-positive variables,
    108 * and non-zero reduced costs for variables that can be negative and positive.
    109 *
    110 * The method is called in the LP solving loop after an LP was proven to be feasible.
    111 *
    112 * Whenever the pricer finds a variable with negative dual feasibility, it should call SCIPcreateVar()
    113 * and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate
    114 * methods of the constraint handlers to add the necessary variable entries to the constraints.
    115 *
    116 * In the usual case that the pricer either adds a new variable or ensures that there are no further variables with
    117 * negative dual feasibility, the result pointer should be set to SCIP_SUCCESS. Only if the pricer aborts pricing
    118 * without creating a new variable, but there might exist additional variables with negative dual feasibility, the
    119 * result pointer should be set to SCIP_DIDNOTRUN. In this case, which sometimes is referred to as "early branching",
    120 * the lp solution will not be used as a lower bound. The pricer can, however, store a valid lower bound in the
    121 * lowerbound pointer. If you use your own branching rule (e.g., to branch on constraints), make sure that it is able
    122 * to branch on pseudo solutions. Otherwise, SCIP will use its default branching rules (which all branch on
    123 * variables). This could disturb the pricing problem or branching might not even be possible, e.g., if all yet created
    124 * variables have already been fixed.
    125 *
    126 * input:
    127 * - scip : SCIP main data structure
    128 * - pricer : the variable pricer itself
    129 * - lowerbound : pointer to store a lower bound found by the pricer
    130 * - stopearly : should pricing be stopped, although new variables were added? (doing early branching)
    131 * - result : pointer to store the result of the pricer call
    132 *
    133 * possible return values for *result:
    134 * - SCIP_SUCCESS : at least one improving variable was found, or it is ensured that no such variable exists
    135 * - SCIP_DIDNOTRUN : the pricing process was aborted by the pricer, there is no guarantee that the current LP solution is
    136 * optimal
    137 *
    138 */
    139#define SCIP_DECL_PRICERREDCOST(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer, SCIP_Real* lowerbound, SCIP_Bool* stopearly, SCIP_RESULT* result)
    140
    141/** Farkas pricing method of variable pricer for infeasible LPs
    142 *
    143 * Searches for variables that can contribute to the feasibility of the current LP.
    144 * In standard branch-and-price, these are variables with positive Farkas values:
    145 *
    146 * The LP was proven infeasible, so we have an infeasibility proof by the dual Farkas multipliers y.
    147 * With the values of y, an implicit inequality y^T A x >= y^T b is associated, with b given
    148 * by the sides of the LP rows and the sign of y:
    149 * - if y_i is positive, b_i is the left hand side of the row,
    150 * - if y_i is negative, b_i is the right hand side of the row.
    151 *
    152 * y is chosen in a way, such that the valid inequality y^T A x >= y^T b is violated by all x,
    153 * especially by the (for this inequality least infeasible solution) x' defined by
    154 * x'_i := ub_i, if y^T A_i >= 0
    155 * x'_i := lb_i, if y^T A_i < 0.
    156 * Pricing in this case means to add variables i with positive Farkas value, i.e. y^T A_i x'_i > 0.
    157 *
    158 * The method is called in the LP solving loop after an LP was proven to be infeasible.
    159 *
    160 * Whenever the pricer finds a variable with positive Farkas value, it should call SCIPcreateVar()
    161 * and SCIPaddPricedVar() to add the variable to the problem. Furthermore, it should call the appropriate
    162 * methods of the constraint handlers to add the necessary variable entries to the constraints.
    163 *
    164 * input:
    165 * - scip : SCIP main data structure
    166 * - pricer : the variable pricer itself
    167 * - result : pointer to store the result of the pricer call
    168 *
    169 * possible return values for *result:
    170 * - SCIP_SUCCESS : at least one variable was found, which can contribute to the feasibility of the current LP,
    171 * or it is ensured that no such variable exists
    172 * - SCIP_DIDNOTRUN : the pricing process was aborted by the pricer, there is no guarantee that the current LP is indeed infeasible
    173 */
    174#define SCIP_DECL_PRICERFARKAS(x) SCIP_RETCODE x (SCIP* scip, SCIP_PRICER* pricer, SCIP_RESULT* result)
    175
    176#ifdef __cplusplus
    177}
    178#endif
    179
    180#endif
    def.h
    common defines and data types used in all packages of SCIP
    SCIP_Pricer
    Definition: struct_pricer.h:47
    SCIP_PRICERDATA
    struct SCIP_PricerData SCIP_PRICERDATA
    Definition: type_pricer.h:45
    type_retcode.h
    type definitions for return codes for SCIP methods
    type_scip.h
    type definitions for SCIP's main datastructure