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_linear.h
26   	 * @ingroup CONSHDLRS
27   	 * @brief  Constraint handler for linear constraints in their most general form, \f$lhs <= a^T x <= rhs\f$.
28   	 * @author Tobias Achterberg
29   	 * @author Timo Berthold
30   	 * @author Marc Pfetsch
31   	 * @author Kati Wolter
32   	 *
33   	 */
34   	
35   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36   	
37   	#ifndef __SCIP_CONS_LINEAR_H__
38   	#define __SCIP_CONS_LINEAR_H__
39   	
40   	#include "scip/def.h"
41   	#include "scip/type_cons.h"
42   	#include "scip/type_lp.h"
43   	#include "scip/type_misc.h"
44   	#include "scip/type_retcode.h"
45   	#include "scip/type_scip.h"
46   	#include "scip/type_sol.h"
47   	#include "scip/type_var.h"
48   	
49   	#ifdef __cplusplus
50   	extern "C" {
51   	#endif
52   	
53   	
54   	
55   	/*
56   	 * constraint specific interface methods
57   	 */
58   	
59   	/** creates the handler for linear constraints and includes it in SCIP
60   	 *
61   	 * @ingroup ConshdlrIncludes
62   	 * */
63   	SCIP_EXPORT
64   	SCIP_RETCODE SCIPincludeConshdlrLinear(
65   	   SCIP*                 scip                /**< SCIP data structure */
66   	   );
67   	
68   	/**@addtogroup CONSHDLRS
69   	 *
70   	 * @{
71   	 *
72   	 * @name Linear Constraints
73   	 *
74   	 * This constraint handler handles linear constraints in their most general form. That is,
75   	 * \f[
76   	 *   lhs \leq \sum_{i=1}^n a_i x_i \leq rhs
77   	 * \f]
78   	 * with \f$a_i \in Q, i = 1,\dots,n\f$, \f$lhs\in Q \cup \{-\infty\}\f$, \f$rhs\in Q \cup \{\infty\}\f$,
79   	 * and decision variables \f$x_i, i = 1,\dots,n\f$ which can be binary, integer, or continuous.
80   	 *
81   	 * Furthermore, this header offers the upgrade functionality of a general linear constraint into a more specific
82   	 * constraint, such as a knapsack constraint, via SCIP_DECL_LINCONSUPGD() and SCIPincludeLinconsUpgrade()
83   	 *
84   	 * @{
85   	 */
86   	
87   	typedef struct SCIP_LinConsUpgrade SCIP_LINCONSUPGRADE; /**< linear constraint update method */
88   	
89   	/** upgrading method for linear constraints into more specific constraints
90   	 *
91   	 *  input:
92   	 *  - scip            : SCIP main data structure
93   	 *  - cons            : the linear constraint to upgrade
94   	 *  - nvars           : number of variables in the constraint
95   	 *  - vars            : array with constraint variables
96   	 *  - vals            : array with constraint coefficients
97   	 *  - lhs             : left hand side of linear constraint
98   	 *  - rhs             : right hand side of linear constraint
99   	 *  - nposbin         : number of binary variables with positive coefficient
100  	 *  - nnegbin         : number of binary variables with negative coefficient
101  	 *  - nposint         : number of integer variables with positive coefficient
102  	 *  - nnegint         : number of integer variables with negative coefficient
103  	 *  - nposimpl        : number of implicit integer variables with positive coefficient (including implicit binary variables)
104  	 *  - nnegimpl        : number of implicit integer variables with negative coefficient (including implicit binary variables)
105  	 *  - nposimplbin     : number of implicit binary variables with positive coefficient
106  	 *  - nnegimplbin     : number of implicit binary variables with negative coefficient
107  	 *  - nposcont        : number of continuous variables with positive coefficient
108  	 *  - nnegcont        : number of continuous variables with negative coefficient
109  	 *  - ncoeffspone     : number of +1 coefficients
110  	 *  - ncoeffsnone     : number of -1 coefficients
111  	 *  - ncoeffspint     : number of positive integral coefficients other than +1
112  	 *  - ncoeffsnint     : number of negative integral coefficients other than -1
113  	 *  - ncoeffspfrac    : number of positive fractional coefficients
114  	 *  - ncoeffsnfrac    : number of negative fractional coefficients
115  	 *  - poscoeffsum     : sum of all positive coefficients
116  	 *  - negcoeffsum     : sum of all negative coefficients
117  	 *  - integral        : TRUE iff constraints activity value is always integral
118  	 *  - upgdcons        : pointer to store the upgraded constraint
119  	 */
120  	#define SCIP_DECL_LINCONSUPGD(x) SCIP_RETCODE x (SCIP* scip, SCIP_CONS* cons, int nvars, SCIP_VAR** vars, SCIP_Real* vals, SCIP_Real lhs, SCIP_Real rhs, \
121  	      int nposbin, int nnegbin, int nposint, int nnegint, int nposimpl, int nnegimpl, int nposimplbin, int nnegimplbin, int nposcont, int nnegcont, \
122  	      int ncoeffspone, int ncoeffsnone, int ncoeffspint, int ncoeffsnint, int ncoeffspfrac, int ncoeffsnfrac, \
123  	      SCIP_Real poscoeffsum, SCIP_Real negcoeffsum, SCIP_Bool integral, SCIP_CONS** upgdcons)
124  	
125  	/** includes a linear constraint update method into the linear constraint handler */
126  	SCIP_EXPORT
127  	SCIP_RETCODE SCIPincludeLinconsUpgrade(
128  	   SCIP*                 scip,               /**< SCIP data structure */
129  	   SCIP_DECL_LINCONSUPGD((*linconsupgd)),    /**< method to call for upgrading linear constraint */
130  	   int                   priority,           /**< priority of upgrading method */
131  	   const char*           conshdlrname        /**< name of the constraint handler */
132  	   );
133  	
134  	/** creates and captures a linear constraint
135  	 *
136  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
137  	 */
138  	SCIP_EXPORT
139  	SCIP_RETCODE SCIPcreateConsLinear(
140  	   SCIP*                 scip,               /**< SCIP data structure */
141  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
142  	   const char*           name,               /**< name of constraint */
143  	   int                   nvars,              /**< number of nonzeros in the constraint */
144  	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
145  	   SCIP_Real*            vals,               /**< array with coefficients of constraint entries */
146  	   SCIP_Real             lhs,                /**< left hand side of constraint */
147  	   SCIP_Real             rhs,                /**< right hand side of constraint */
148  	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
149  	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
150  	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
151  	                                              *   Usually set to TRUE. */
152  	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
153  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
154  	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
155  	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
156  	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
157  	                                              *   Usually set to TRUE. */
158  	   SCIP_Bool             local,              /**< is constraint only valid locally?
159  	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
160  	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)?
161  	                                              *   Usually set to FALSE. In column generation applications, set to TRUE if pricing
162  	                                              *   adds coefficients to this constraint. */
163  	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
164  	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
165  	                                              *   are separated as constraints. */
166  	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
167  	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
168  	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
169  	                                              *   if it may be moved to a more global node?
170  	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
171  	   );
172  	
173  	/** creates and captures a linear constraint
174  	 *  in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
175  	 *  method SCIPcreateConsLinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
176  	 *
177  	 *  @see SCIPcreateConsLinear() for information about the basic constraint flag configuration
178  	 *
179  	 *  @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
180  	 */
181  	SCIP_EXPORT
182  	SCIP_RETCODE SCIPcreateConsBasicLinear(
183  	   SCIP*                 scip,               /**< SCIP data structure */
184  	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
185  	   const char*           name,               /**< name of constraint */
186  	   int                   nvars,              /**< number of nonzeros in the constraint */
187  	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
188  	   SCIP_Real*            vals,               /**< array with coefficients of constraint entries */
189  	   SCIP_Real             lhs,                /**< left hand side of constraint */
190  	   SCIP_Real             rhs                 /**< right hand side of constraint */
191  	   );
192  	
193  	/** creates by copying and captures a linear constraint */
194  	SCIP_EXPORT
195  	SCIP_RETCODE SCIPcopyConsLinear(
196  	   SCIP*                 scip,               /**< target SCIP data structure */
197  	   SCIP_CONS**           cons,               /**< pointer to store the created target constraint */
198  	   SCIP*                 sourcescip,         /**< source SCIP data structure */
199  	   const char*           name,               /**< name of constraint */
200  	   int                   nvars,              /**< number of variables in source variable array */
201  	   SCIP_VAR**            sourcevars,         /**< source variables of the linear constraints */
202  	   SCIP_Real*            sourcecoefs,        /**< coefficient array of the linear constraint, or NULL if all coefficients are one */
203  	   SCIP_Real             lhs,                /**< left hand side of the linear constraint */
204  	   SCIP_Real             rhs,                /**< right hand side of the linear constraint */
205  	   SCIP_HASHMAP*         varmap,             /**< a SCIP_HASHMAP mapping variables of the source SCIP to corresponding
206  	                                              *   variables of the target SCIP */
207  	   SCIP_HASHMAP*         consmap,            /**< a hashmap to store the mapping of source constraints to the corresponding
208  	                                              *   target constraints */
209  	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP? */
210  	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing? */
211  	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing? */
212  	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility? */
213  	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing? */
214  	   SCIP_Bool             local,              /**< is constraint only valid locally? */
215  	   SCIP_Bool             modifiable,         /**< is constraint modifiable (subject to column generation)? */
216  	   SCIP_Bool             dynamic,            /**< is constraint subject to aging? */
217  	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup? */
218  	   SCIP_Bool             stickingatnode,     /**< should the constraint always be kept at the node where it was added, even
219  	                                              *   if it may be moved to a more global node? */
220  	   SCIP_Bool             global,             /**< create a global or a local copy? */
221  	   SCIP_Bool*            valid               /**< pointer to store if the copying was valid */
222  	   );
223  	
224  	/** adds coefficient to linear constraint (if it is not zero) */
225  	SCIP_EXPORT
226  	SCIP_RETCODE SCIPaddCoefLinear(
227  	   SCIP*                 scip,               /**< SCIP data structure */
228  	   SCIP_CONS*            cons,               /**< constraint data */
229  	   SCIP_VAR*             var,                /**< variable of constraint entry */
230  	   SCIP_Real             val                 /**< coefficient of constraint entry */
231  	   );
232  	
233  	/** changes coefficient of variable in linear constraint; deletes the variable if coefficient is zero; adds variable if
234  	 *  not yet contained in the constraint
235  	 *
236  	 *  @note This method may only be called during problem creation stage for an original constraint and variable.
237  	 *
238  	 *  @note This method requires linear time to search for occurences of the variable in the constraint data.
239  	 */
240  	SCIP_EXPORT
241  	SCIP_RETCODE SCIPchgCoefLinear(
242  	   SCIP*                 scip,               /**< SCIP data structure */
243  	   SCIP_CONS*            cons,               /**< constraint data */
244  	   SCIP_VAR*             var,                /**< variable of constraint entry */
245  	   SCIP_Real             val                 /**< new coefficient of constraint entry */
246  	   );
247  	
248  	/** deletes variable from linear constraint
249  	 *
250  	 *  @note This method may only be called during problem creation stage for an original constraint and variable.
251  	 *
252  	 *  @note This method requires linear time to search for occurences of the variable in the constraint data.
253  	 */
254  	SCIP_EXPORT
255  	SCIP_RETCODE SCIPdelCoefLinear(
256  	   SCIP*                 scip,               /**< SCIP data structure */
257  	   SCIP_CONS*            cons,               /**< constraint data */
258  	   SCIP_VAR*             var                 /**< variable of constraint entry */
259  	   );
260  	
261  	/** gets left hand side of linear constraint */
262  	SCIP_EXPORT
263  	SCIP_Real SCIPgetLhsLinear(
264  	   SCIP*                 scip,               /**< SCIP data structure */
265  	   SCIP_CONS*            cons                /**< constraint data */
266  	   );
267  	
268  	/** gets right hand side of linear constraint */
269  	SCIP_EXPORT
270  	SCIP_Real SCIPgetRhsLinear(
271  	   SCIP*                 scip,               /**< SCIP data structure */
272  	   SCIP_CONS*            cons                /**< constraint data */
273  	   );
274  	
275  	/** changes left hand side of linear constraint */
276  	SCIP_EXPORT
277  	SCIP_RETCODE SCIPchgLhsLinear(
278  	   SCIP*                 scip,               /**< SCIP data structure */
279  	   SCIP_CONS*            cons,               /**< constraint data */
280  	   SCIP_Real             lhs                 /**< new left hand side */
281  	   );
282  	
283  	/** changes right hand side of linear constraint */
284  	SCIP_EXPORT
285  	SCIP_RETCODE SCIPchgRhsLinear(
286  	   SCIP*                 scip,               /**< SCIP data structure */
287  	   SCIP_CONS*            cons,               /**< constraint data */
288  	   SCIP_Real             rhs                 /**< new right hand side */
289  	   );
290  	
291  	/** gets the number of variables in the linear constraint */
292  	SCIP_EXPORT
293  	int SCIPgetNVarsLinear(
294  	   SCIP*                 scip,               /**< SCIP data structure */
295  	   SCIP_CONS*            cons                /**< constraint data */
296  	   );
297  	
298  	/** gets the array of variables in the linear constraint; the user must not modify this array! */
299  	SCIP_EXPORT
300  	SCIP_VAR** SCIPgetVarsLinear(
301  	   SCIP*                 scip,               /**< SCIP data structure */
302  	   SCIP_CONS*            cons                /**< constraint data */
303  	   );
304  	
305  	/** gets the array of coefficient values in the linear constraint; the user must not modify this array! */
306  	SCIP_EXPORT
307  	SCIP_Real* SCIPgetValsLinear(
308  	   SCIP*                 scip,               /**< SCIP data structure */
309  	   SCIP_CONS*            cons                /**< constraint data */
310  	   );
311  	
312  	/** gets the activity of the linear constraint in the given solution
313  	 *
314  	 *  @note if the solution contains values at infinity, this method will return SCIP_INVALID in case the activity
315  	 *        comprises positive and negative infinity contributions
316  	 */
317  	SCIP_EXPORT
318  	SCIP_Real SCIPgetActivityLinear(
319  	   SCIP*                 scip,               /**< SCIP data structure */
320  	   SCIP_CONS*            cons,               /**< constraint data */
321  	   SCIP_SOL*             sol                 /**< solution, or NULL to use current node's solution */
322  	   );
323  	
324  	/** gets the feasibility of the linear constraint in the given solution */
325  	SCIP_EXPORT
326  	SCIP_Real SCIPgetFeasibilityLinear(
327  	   SCIP*                 scip,               /**< SCIP data structure */
328  	   SCIP_CONS*            cons,               /**< constraint data */
329  	   SCIP_SOL*             sol                 /**< solution, or NULL to use current node's solution */
330  	   );
331  	
332  	/** gets the dual solution of the linear constraint in the current LP */
333  	SCIP_EXPORT
334  	SCIP_Real SCIPgetDualsolLinear(
335  	   SCIP*                 scip,               /**< SCIP data structure */
336  	   SCIP_CONS*            cons                /**< constraint data */
337  	   );
338  	
339  	/** gets the dual Farkas value of the linear constraint in the current infeasible LP */
340  	SCIP_EXPORT
341  	SCIP_Real SCIPgetDualfarkasLinear(
342  	   SCIP*                 scip,               /**< SCIP data structure */
343  	   SCIP_CONS*            cons                /**< constraint data */
344  	   );
345  	
346  	/** returns the linear relaxation of the given linear constraint; may return NULL if no LP row was yet created;
347  	 *  the user must not modify the row!
348  	 */
349  	SCIP_EXPORT
350  	SCIP_ROW* SCIPgetRowLinear(
351  	   SCIP*                 scip,               /**< SCIP data structure */
352  	   SCIP_CONS*            cons                /**< constraint data */
353  	   );
354  	
355  	/** tries to automatically convert a linear constraint into a more specific and more specialized constraint */
356  	SCIP_EXPORT
357  	SCIP_RETCODE SCIPupgradeConsLinear(
358  	   SCIP*                 scip,               /**< SCIP data structure */
359  	   SCIP_CONS*            cons,               /**< source constraint to try to convert */
360  	   SCIP_CONS**           upgdcons            /**< pointer to store upgraded constraint, or NULL if not successful */
361  	   );
362  	
363  	/** performs linear constraint type classification as used for MIPLIB
364  	 *
365  	 *  iterates through all linear constraints and stores relevant statistics in the linear constraint statistics \p linconsstats.
366  	 *
367  	 *  @note only constraints are iterated that belong to the linear constraint handler. If the problem has been presolved already,
368  	 *  constraints that were upgraded to more special types such as, e.g., varbound constraints, will not be shown correctly anymore.
369  	 *  Similarly, if specialized constraints were created through the API, these are currently not present.
370  	 */
371  	SCIP_EXPORT
372  	SCIP_RETCODE SCIPclassifyConstraintTypesLinear(
373  	   SCIP*                 scip,               /**< SCIP data structure */
374  	   SCIP_LINCONSSTATS*    linconsstats        /**< linear constraint type classification */
375  	   );
376  	
377  	
378  	/** cleans up (multi-)aggregations and fixings from linear constraints */
379  	SCIP_EXPORT
380  	SCIP_RETCODE SCIPcleanupConssLinear(
381  	   SCIP*                 scip,               /**< SCIP data structure */
382  	   SCIP_Bool             onlychecked,        /**< should only checked constraints be cleaned up? */
383  	   SCIP_Bool*            infeasible          /**< pointer to return whether the problem was detected to be infeasible */
384  	   );
385  	
386  	/** @} */
387  	
388  	/** @} */
389  	
390  	#ifdef __cplusplus
391  	}
392  	#endif
393  	
394  	#endif
395