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 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 41 extern "C" { 42 #endif 43 44 typedef struct SCIP_Pricer SCIP_PRICER; /**< variable pricer data */ 45 typedef 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 181