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
44 SCIP_RETCODE SCIPincludeConshdlrKnapsack(
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
53 SCIP_RETCODE SCIPcreateConsKnapsack(
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
95 SCIP_RETCODE SCIPcreateConsBasicKnapsack(
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
107 SCIP_RETCODE SCIPaddCoefKnapsack(
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
116 SCIP_Longint SCIPgetCapacityKnapsack(
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
126 SCIP_RETCODE SCIPchgCapacityKnapsack(
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
134 int SCIPgetNVarsKnapsack(
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
141 SCIP_VAR** SCIPgetVarsKnapsack(
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
148 SCIP_Longint* SCIPgetWeightsKnapsack(
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
155 SCIP_Real SCIPgetDualsolKnapsack(
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
162 SCIP_Real SCIPgetDualfarkasKnapsack(
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
171 SCIP_ROW* SCIPgetRowKnapsack(
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
180 SCIP_RETCODE SCIPsolveKnapsackExactly(
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
200 SCIP_RETCODE SCIPsolveKnapsackApproximately(
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
216 SCIP_RETCODE SCIPseparateKnapsackCuts(
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
232 SCIP_RETCODE SCIPseparateRelaxedKnapsack(
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
251