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