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 cons_knapsack.h 26 * @ingroup CONSHDLRS 27 * @brief Constraint handler for knapsack constraints of the form \f$a^T x \le b\f$, x binary and \f$a \ge 0\f$. 28 * @author Tobias Achterberg 29 * @author Kati Wolter 30 * @author Michael Winkler 31 * 32 */ 33 34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/ 35 36 #ifndef __SCIP_CONS_KNAPSACK_H__ 37 #define __SCIP_CONS_KNAPSACK_H__ 38 39 #include "scip/def.h" 40 #include "scip/type_cons.h" 41 #include "scip/type_lp.h" 42 #include "scip/type_retcode.h" 43 #include "scip/type_scip.h" 44 #include "scip/type_sepa.h" 45 #include "scip/type_sol.h" 46 #include "scip/type_var.h" 47 48 #ifdef __cplusplus 49 extern "C" { 50 #endif 51 52 /** creates the handler for knapsack constraints and includes it in SCIP 53 * 54 * @ingroup ConshdlrIncludes 55 * */ 56 SCIP_EXPORT 57 SCIP_RETCODE SCIPincludeConshdlrKnapsack( 58 SCIP* scip /**< SCIP data structure */ 59 ); 60 61 /**@addtogroup CONSHDLRS 62 * 63 * @{ 64 * 65 * @name Knapsack Constraints 66 * 67 * @{ 68 * 69 * This constraint handler handles a special type of linear constraints, namely knapsack constraints. 70 * A knapsack constraint has the form 71 * \f[ 72 * \sum_{i=1}^n a_i x_i \leq b 73 * \f] 74 * with non-negative integer coefficients \f$a_i\f$, integer right-hand side \f$b\f$, and binary variables \f$x_i\f$. 75 */ 76 77 /** creates and captures a knapsack constraint 78 * 79 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 80 */ 81 SCIP_EXPORT 82 SCIP_RETCODE SCIPcreateConsKnapsack( 83 SCIP* scip, /**< SCIP data structure */ 84 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 85 const char* name, /**< name of constraint */ 86 int nvars, /**< number of items in the knapsack */ 87 SCIP_VAR** vars, /**< array with item variables */ 88 SCIP_Longint* weights, /**< array with item weights */ 89 SCIP_Longint capacity, /**< capacity of knapsack (right hand side of inequality) */ 90 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? 91 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */ 92 SCIP_Bool separate, /**< should the constraint be separated during LP processing? 93 * Usually set to TRUE. */ 94 SCIP_Bool enforce, /**< should the constraint be enforced during node processing? 95 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 96 SCIP_Bool check, /**< should the constraint be checked for feasibility? 97 * TRUE for model constraints, FALSE for additional, redundant constraints. */ 98 SCIP_Bool propagate, /**< should the constraint be propagated during node processing? 99 * Usually set to TRUE. */ 100 SCIP_Bool local, /**< is constraint only valid locally? 101 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */ 102 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? 103 * Usually set to FALSE. In column generation applications, set to TRUE if pricing 104 * adds coefficients to this constraint. */ 105 SCIP_Bool dynamic, /**< is constraint subject to aging? 106 * Usually set to FALSE. Set to TRUE for own cuts which 107 * are separated as constraints. */ 108 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? 109 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */ 110 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even 111 * if it may be moved to a more global node? 112 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */ 113 ); 114 115 /** creates and captures a knapsack constraint 116 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the 117 * method SCIPcreateConsKnapsack(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h 118 * 119 * @see SCIPcreateConsKnapsack() for information about the basic constraint flag configuration 120 * 121 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons() 122 */ 123 SCIP_EXPORT 124 SCIP_RETCODE SCIPcreateConsBasicKnapsack( 125 SCIP* scip, /**< SCIP data structure */ 126 SCIP_CONS** cons, /**< pointer to hold the created constraint */ 127 const char* name, /**< name of constraint */ 128 int nvars, /**< number of items in the knapsack */ 129 SCIP_VAR** vars, /**< array with item variables */ 130 SCIP_Longint* weights, /**< array with item weights */ 131 SCIP_Longint capacity /**< capacity of knapsack */ 132 ); 133 134 /** adds new item to knapsack constraint */ 135 SCIP_EXPORT 136 SCIP_RETCODE SCIPaddCoefKnapsack( 137 SCIP* scip, /**< SCIP data structure */ 138 SCIP_CONS* cons, /**< constraint data */ 139 SCIP_VAR* var, /**< item variable */ 140 SCIP_Longint weight /**< item weight */ 141 ); 142 143 /** gets the capacity of the knapsack constraint */ 144 SCIP_EXPORT 145 SCIP_Longint SCIPgetCapacityKnapsack( 146 SCIP* scip, /**< SCIP data structure */ 147 SCIP_CONS* cons /**< constraint data */ 148 ); 149 150 /** changes capacity of the knapsack constraint 151 * 152 * @note This method can only be called during problem creation stage (SCIP_STAGE_PROBLEM) 153 */ 154 SCIP_EXPORT 155 SCIP_RETCODE SCIPchgCapacityKnapsack( 156 SCIP* scip, /**< SCIP data structure */ 157 SCIP_CONS* cons, /**< constraint data */ 158 SCIP_Longint capacity /**< new capacity of knapsack */ 159 ); 160 161 /** gets the number of items in the knapsack constraint */ 162 SCIP_EXPORT 163 int SCIPgetNVarsKnapsack( 164 SCIP* scip, /**< SCIP data structure */ 165 SCIP_CONS* cons /**< constraint data */ 166 ); 167 168 /** gets the array of variables in the knapsack constraint; the user must not modify this array! */ 169 SCIP_EXPORT 170 SCIP_VAR** SCIPgetVarsKnapsack( 171 SCIP* scip, /**< SCIP data structure */ 172 SCIP_CONS* cons /**< constraint data */ 173 ); 174 175 /** gets the array of weights in the knapsack constraint; the user must not modify this array! */ 176 SCIP_EXPORT 177 SCIP_Longint* SCIPgetWeightsKnapsack( 178 SCIP* scip, /**< SCIP data structure */ 179 SCIP_CONS* cons /**< constraint data */ 180 ); 181 182 /** gets the dual solution of the knapsack constraint in the current LP */ 183 SCIP_EXPORT 184 SCIP_Real SCIPgetDualsolKnapsack( 185 SCIP* scip, /**< SCIP data structure */ 186 SCIP_CONS* cons /**< constraint data */ 187 ); 188 189 /** gets the dual Farkas value of the knapsack constraint in the current infeasible LP */ 190 SCIP_EXPORT 191 SCIP_Real SCIPgetDualfarkasKnapsack( 192 SCIP* scip, /**< SCIP data structure */ 193 SCIP_CONS* cons /**< constraint data */ 194 ); 195 196 /** returns the linear relaxation of the given knapsack constraint; may return NULL if no LP row was yet created; 197 * the user must not modify the row! 198 */ 199 SCIP_EXPORT 200 SCIP_ROW* SCIPgetRowKnapsack( 201 SCIP* scip, /**< SCIP data structure */ 202 SCIP_CONS* cons /**< constraint data */ 203 ); 204 205 /** solves knapsack problem in maximization form exactly using dynamic programming; 206 * if needed, one can provide arrays to store all selected items and all not selected items 207 * 208 * @note in case you provide the solitems or nonsolitems array you also have to provide the counter part, as well 209 * 210 * @note the algorithm will first compute a greedy solution and terminate 211 * if the greedy solution is proven to be optimal. 212 * The dynamic programming algorithm runs with a time and space complexity 213 * of O(nitems * capacity). 214 */ 215 SCIP_EXPORT 216 SCIP_RETCODE SCIPsolveKnapsackExactly( 217 SCIP* scip, /**< SCIP data structure */ 218 int nitems, /**< number of available items */ 219 SCIP_Longint* weights, /**< item weights */ 220 SCIP_Real* profits, /**< item profits */ 221 SCIP_Longint capacity, /**< capacity of knapsack */ 222 int* items, /**< item numbers */ 223 int* solitems, /**< array to store items in solution, or NULL */ 224 int* nonsolitems, /**< array to store items not in solution, or NULL */ 225 int* nsolitems, /**< pointer to store number of items in solution, or NULL */ 226 int* nnonsolitems, /**< pointer to store number of items not in solution, or NULL */ 227 SCIP_Real* solval, /**< pointer to store optimal solution value, or NULL */ 228 SCIP_Bool* success /**< pointer to store if an error occured during solving 229 * (normally a memory problem) */ 230 ); 231 232 /** solves knapsack problem in maximization form approximately by solving the LP-relaxation of the problem using Dantzig's 233 * method and rounding down the solution; if needed, one can provide arrays to store all selected items and all not 234 * selected items 235 */ 236 SCIP_EXPORT 237 SCIP_RETCODE SCIPsolveKnapsackApproximately( 238 SCIP* scip, /**< SCIP data structure */ 239 int nitems, /**< number of available items */ 240 SCIP_Longint* weights, /**< item weights */ 241 SCIP_Real* profits, /**< item profits */ 242 SCIP_Longint capacity, /**< capacity of knapsack */ 243 int* items, /**< item numbers */ 244 int* solitems, /**< array to store items in solution, or NULL */ 245 int* nonsolitems, /**< array to store items not in solution, or NULL */ 246 int* nsolitems, /**< pointer to store number of items in solution, or NULL */ 247 int* nnonsolitems, /**< pointer to store number of items not in solution, or NULL */ 248 SCIP_Real* solval /**< pointer to store optimal solution value, or NULL */ 249 ); 250 251 /** separates different classes of valid inequalities for the 0-1 knapsack problem */ 252 SCIP_EXPORT 253 SCIP_RETCODE SCIPseparateKnapsackCuts( 254 SCIP* scip, /**< SCIP data structure */ 255 SCIP_CONS* cons, /**< originating constraint of the knapsack problem, or NULL */ 256 SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */ 257 SCIP_VAR** vars, /**< variables in knapsack constraint */ 258 int nvars, /**< number of variables in knapsack constraint */ 259 SCIP_Longint* weights, /**< weights of variables in knapsack constraint */ 260 SCIP_Longint capacity, /**< capacity of knapsack */ 261 SCIP_SOL* sol, /**< primal SCIP solution to separate, NULL for current LP solution */ 262 SCIP_Bool usegubs, /**< should GUB information be used for separation? */ 263 SCIP_Bool* cutoff, /**< pointer to store whether a cutoff has been detected */ 264 int* ncuts /**< pointer to add up the number of found cuts */ 265 ); 266 267 /* relaxes given general linear constraint into a knapsack constraint and separates lifted knapsack cover inequalities */ 268 SCIP_EXPORT 269 SCIP_RETCODE SCIPseparateRelaxedKnapsack( 270 SCIP* scip, /**< SCIP data structure */ 271 SCIP_CONS* cons, /**< originating constraint of the knapsack problem, or NULL */ 272 SCIP_SEPA* sepa, /**< originating separator of the knapsack problem, or NULL */ 273 int nknapvars, /**< number of variables in the continuous knapsack constraint */ 274 SCIP_VAR** knapvars, /**< variables in the continuous knapsack constraint */ 275 SCIP_Real* knapvals, /**< coefficients of the variables in the continuous knapsack constraint */ 276 SCIP_Real valscale, /**< -1.0 if lhs of row is used as rhs of c. k. constraint, +1.0 otherwise */ 277 SCIP_Real rhs, /**< right hand side of the continuous knapsack constraint */ 278 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */ 279 SCIP_Bool* cutoff, /**< pointer to store whether a cutoff was found */ 280 int* ncuts /**< pointer to add up the number of found cuts */ 281 ); 282 283 /** cleans up (multi-)aggregations and fixings from knapsack constraints */ 284 SCIP_EXPORT 285 SCIP_RETCODE SCIPcleanupConssKnapsack( 286 SCIP* scip, /**< SCIP data structure */ 287 SCIP_Bool onlychecked, /**< should only checked constraints be cleaned up? */ 288 SCIP_Bool* infeasible /**< pointer to return whether the problem was detected to be infeasible */ 289 ); 290 291 /** @} */ 292 293 /** @} */ 294 295 #ifdef __cplusplus 296 } 297 #endif 298 299 #endif 300