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_setppc.h
26   	 * @ingroup CONSHDLRS
27   	 * @brief  Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
28   	 * @author Tobias Achterberg
29   	 * @author Michael Winkler
30   	 *
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#ifndef __SCIP_CONS_SETPPC_H__
36   	#define __SCIP_CONS_SETPPC_H__
37   	
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_var.h"
45   	
46   	#ifdef __cplusplus
47   	extern "C" {
48   	#endif
49   	
50   	
51   	/** creates the handler for set partitioning / packing / covering constraints and includes it in SCIP
52   	 *
53   	 * @ingroup ConshdlrIncludes
54   	 * */
55   	SCIP_EXPORT
56   	SCIP_RETCODE SCIPincludeConshdlrSetppc(
57   	   SCIP*                 scip                /**< SCIP data structure */
58   	   );
59   	
60   	/**@addtogroup CONSHDLRS
61   	 *
62   	 * @{
63   	 *
64   	 * @name Set Packing/Partitioning/Covering Constraints
65   	 *
66   	 * @{
67   	 *
68   	 * This constraint handler handles three special classes of linear constraints, namely
69   	 * set partitioning, set packing, and set covering constraints.
70   	 * For a set of binary variables \f$x_i, i=1,\dots,n\f$, a set partitioning constraint has the form
71   	 * \f[
72   	 *   \sum_{i=1}^n x_i = 1,
73   	 * \f]
74   	 * a set packing constraint has the form
75   	 * \f[
76   	 *   \sum_{i=1}^n x_i \le 1,
77   	 * \f]
78   	 * and a set covering constraint has the form
79   	 * \f[
80   	 *   \sum_{i=1}^n x_i \ge 1.
81   	 * \f]
82   	 */
83   	
84   	/** type of setppc constraint: set partitioning, set packing, or set covering */
85   	enum SCIP_SetppcType
86   	{
87   	   SCIP_SETPPCTYPE_PARTITIONING = 0,     /**< constraint is a set partitioning constraint: sum(x) == 1 */
88   	   SCIP_SETPPCTYPE_PACKING      = 1,     /**< constraint is a set packing constraint:      sum(x) <= 1 */
89   	   SCIP_SETPPCTYPE_COVERING     = 2      /**< constraint is a set covering constraint:     sum(x) >= 1 */
90   	};
91   	typedef enum SCIP_SetppcType SCIP_SETPPCTYPE;
92   	
93   	/** creates and captures a set partitioning constraint
94   	 *
95   	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
96   	 */
97   	SCIP_EXPORT
98   	SCIP_RETCODE SCIPcreateConsSetpart(
99   	   SCIP*                 scip,               /**< SCIP data structure */
100  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
101  	   const char*           name,               /**< name of constraint */
102  	   int                   nvars,              /**< number of variables in the constraint */
103  	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
104  	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
105  	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
106  	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
107  	                                              *   Usually set to TRUE. */
108  	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
109  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
110  	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
111  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
112  	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
113  	                                              *   Usually set to TRUE. */
114  	   SCIP_Bool             local,              /**< is constraint only valid locally?
115  	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
116  	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
117  	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
118  	                                              *   adds coefficients to this constraint. */
119  	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
120  	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
121  	                                              *   are separated as constraints. */
122  	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
123  	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
124  	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
125  	                                              *   if it may be moved to a more global node?
126  	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
127  	   );
128  	
129  	/** creates and captures a set partitioning constraint
130  	 *  in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
131  	 *  afterwards using SCIPsetConsFLAGNAME() in scip.h
132  	 *
133  	 *  @see SCIPcreateConsSetpart() for the default constraint flag configuration
134  	 *
135  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
136  	 */
137  	SCIP_EXPORT
138  	SCIP_RETCODE SCIPcreateConsBasicSetpart(
139  	   SCIP*                 scip,               /**< SCIP data structure */
140  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
141  	   const char*           name,               /**< name of constraint */
142  	   int                   nvars,              /**< number of variables in the constraint */
143  	   SCIP_VAR**            vars                /**< array with variables of constraint entries */
144  	   );
145  	
146  	/** creates and captures a set packing constraint
147  	 *
148  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
149  	 */
150  	SCIP_EXPORT
151  	SCIP_RETCODE SCIPcreateConsSetpack(
152  	   SCIP*                 scip,               /**< SCIP data structure */
153  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
154  	   const char*           name,               /**< name of constraint */
155  	   int                   nvars,              /**< number of variables in the constraint */
156  	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
157  	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
158  	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
159  	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
160  	                                              *   Usually set to TRUE. */
161  	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
162  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
163  	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
164  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
165  	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
166  	                                              *   Usually set to TRUE. */
167  	   SCIP_Bool             local,              /**< is constraint only valid locally?
168  	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
169  	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
170  	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
171  	                                              *   adds coefficients to this constraint. */
172  	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
173  	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
174  	                                              *   are separated as constraints. */
175  	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
176  	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
177  	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
178  	                                              *   if it may be moved to a more global node?
179  	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
180  	   );
181  	
182  	/** creates and captures a set packing constraint
183  	 *  in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
184  	 *  afterwards using SCIPsetConsFLAGNAME() in scip.h
185  	 *
186  	 *  @see SCIPcreateConsSetpack() for the default constraint flag configuration
187  	 *
188  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
189  	 */
190  	SCIP_EXPORT
191  	SCIP_RETCODE SCIPcreateConsBasicSetpack(
192  	   SCIP*                 scip,               /**< SCIP data structure */
193  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
194  	   const char*           name,               /**< name of constraint */
195  	   int                   nvars,              /**< number of variables in the constraint */
196  	   SCIP_VAR**            vars                /**< array with variables of constraint entries */
197  	   );
198  	
199  	/** creates and captures a set covering constraint
200  	 *
201  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
202  	 */
203  	SCIP_EXPORT
204  	SCIP_RETCODE SCIPcreateConsSetcover(
205  	   SCIP*                 scip,               /**< SCIP data structure */
206  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
207  	   const char*           name,               /**< name of constraint */
208  	   int                   nvars,              /**< number of variables in the constraint */
209  	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
210  	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
211  	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
212  	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
213  	                                              *   Usually set to TRUE. */
214  	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
215  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
216  	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
217  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
218  	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
219  	                                              *   Usually set to TRUE. */
220  	   SCIP_Bool             local,              /**< is constraint only valid locally?
221  	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
222  	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
223  	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
224  	                                              *   adds coefficients to this constraint. */
225  	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
226  	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
227  	                                              *   are separated as constraints. */
228  	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
229  	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
230  	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
231  	                                              *   if it may be moved to a more global node?
232  	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
233  	   );
234  	
235  	/** creates and captures a set packing constraint
236  	 *  in its most basic variant, i. e., with all constraint flags set to their default values, which can be set
237  	 *  afterwards using SCIPsetConsFLAGNAME() in scip.h
238  	 *
239  	 *  @see SCIPcreateConsSetpack() for the default constraint flag configuration
240  	 *
241  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
242  	 */
243  	SCIP_EXPORT
244  	SCIP_RETCODE SCIPcreateConsBasicSetcover(
245  	   SCIP*                 scip,               /**< SCIP data structure */
246  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
247  	   const char*           name,               /**< name of constraint */
248  	   int                   nvars,              /**< number of variables in the constraint */
249  	   SCIP_VAR**            vars                /**< array with variables of constraint entries */
250  	   );
251  	
252  	/** adds coefficient in set partitioning / packing / covering constraint */
253  	SCIP_EXPORT
254  	SCIP_RETCODE SCIPaddCoefSetppc(
255  	   SCIP*                 scip,               /**< SCIP data structure */
256  	   SCIP_CONS*            cons,               /**< constraint data */
257  	   SCIP_VAR*             var                 /**< variable to add to the constraint */
258  	   );
259  	
260  	/** gets number of variables in set partitioning / packing / covering constraint */
261  	SCIP_EXPORT
262  	int SCIPgetNVarsSetppc(
263  	   SCIP*                 scip,               /**< SCIP data structure */
264  	   SCIP_CONS*            cons                /**< constraint data */
265  	   );
266  	
267  	/** gets array of variables in set partitioning / packing / covering constraint */
268  	SCIP_EXPORT
269  	SCIP_VAR** SCIPgetVarsSetppc(
270  	   SCIP*                 scip,               /**< SCIP data structure */
271  	   SCIP_CONS*            cons                /**< constraint data */
272  	   );
273  	
274  	/** gets type of set partitioning / packing / covering constraint */
275  	SCIP_EXPORT
276  	SCIP_SETPPCTYPE SCIPgetTypeSetppc(
277  	   SCIP*                 scip,               /**< SCIP data structure */
278  	   SCIP_CONS*            cons                /**< constraint data */
279  	   );
280  	
281  	/** gets the dual solution of the set partitioning / packing / covering constraint in the current LP */
282  	SCIP_EXPORT
283  	SCIP_Real SCIPgetDualsolSetppc(
284  	   SCIP*                 scip,               /**< SCIP data structure */
285  	   SCIP_CONS*            cons                /**< constraint data */
286  	   );
287  	
288  	/** gets the dual Farkas value of the set partitioning / packing / covering constraint in the current infeasible LP */
289  	SCIP_EXPORT
290  	SCIP_Real SCIPgetDualfarkasSetppc(
291  	   SCIP*                 scip,               /**< SCIP data structure */
292  	   SCIP_CONS*            cons                /**< constraint data */
293  	   );
294  	
295  	/** returns the linear relaxation of the given set partitioning / packing / covering constraint; may return NULL if no
296  	 *  LP row was yet created; the user must not modify the row!
297  	 */
298  	SCIP_EXPORT
299  	SCIP_ROW* SCIPgetRowSetppc(
300  	   SCIP*                 scip,               /**< SCIP data structure */
301  	   SCIP_CONS*            cons                /**< constraint data */
302  	   );
303  	
304  	/** returns current number of variables fixed to one in the constraint  */
305  	SCIP_EXPORT
306  	int SCIPgetNFixedonesSetppc(
307  	   SCIP*                 scip,               /**< SCIP data structure */
308  	   SCIP_CONS*            cons                /**< constraint data */
309  	   );
310  	
311  	/** returns current number of variables fixed to zero in the constraint  */
312  	SCIP_EXPORT
313  	int SCIPgetNFixedzerosSetppc(
314  	   SCIP*                 scip,               /**< SCIP data structure */
315  	   SCIP_CONS*            cons                /**< constraint data */
316  	   );
317  	
318  	/** cleans up (multi-)aggregations and fixings from setppc constraints */
319  	SCIP_EXPORT
320  	SCIP_RETCODE SCIPcleanupConssSetppc(
321  	   SCIP*                 scip,               /**< SCIP data structure */
322  	   SCIP_Bool             onlychecked,        /**< should only checked constraints be cleaned up? */
323  	   SCIP_Bool*            infeasible,         /**< pointer to return whether problem was detected to be infeasible */
324  	   int*                  naddconss,          /**< pointer to count number of added (linear) constraints */
325  	   int*                  ndelconss,          /**< pointer to count number of deleted (setppc) constraints */
326  	   int*                  nchgcoefs,          /**< pointer to count number of changed coefficients */
327  	   int*                  nfixedvars          /**< pointer to count number of fixed variables */
328  	   );
329  	
330  	/** @} */
331  	
332  	/** @} */
333  	
334  	#ifdef __cplusplus
335  	}
336  	#endif
337  	
338  	#endif
339