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