Scippy

SCIP

Solving Constraint Integer Programs

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