Scippy

SCIP

Solving Constraint Integer Programs

cons_linear.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-2016 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_linear.h
17  * @ingroup CONSHDLRS
18  * @brief Constraint handler for linear constraints in their most general form, \f$lhs <= a^T x <= rhs\f$.
19  * @author Tobias Achterberg
20  * @author Timo Berthold
21  * @author Marc Pfetsch
22  * @author Kati Wolter
23  *
24  * This constraint handler handles linear constraints in their most general form. That is,
25  * \f[
26  * lhs \leq \sum_{i=1}^n a_i x_i \leq rhs
27  * \f]
28  * 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$,
29  * and decision variables \f$x_i, i = 1,\dots,n\f$ which can be binary, integer, or continuous.
30  *
31  * Furthermore, this header offers the upgrade functionality of a general linear constraint into a more specific
32  * constraint, such as a knapsack constraint, via SCIP_DECL_LINCONSUPGD() and SCIPincludeLinconsUpgrade()
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/scip.h"
41 
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45 
46 typedef struct SCIP_LinConsUpgrade SCIP_LINCONSUPGRADE; /**< linear constraint update method */
47 
48 
49 
50 /** upgrading method for linear constraints into more specific constraints
51  *
52  * input:
53  * - scip : SCIP main data structure
54  * - cons : the linear constraint to upgrade
55  * - nvars : number of variables in the constraint
56  * - vars : array with constraint variables
57  * - vals : array with constraint coefficients
58  * - lhs : left hand side of linear constraint
59  * - rhs : right hand side of linear constraint
60  * - nposbin : number of binary variables with positive coefficient
61  * - nnegbin : number of binary variables with negative coefficient
62  * - nposint : number of integer variables with positive coefficient
63  * - nnegint : number of integer variables with negative coefficient
64  * - nposimpl : number of implicit integer variables with positive coefficient (including implicit binary variables)
65  * - nnegimpl : number of implicit integer variables with negative coefficient (including implicit binary variables)
66  * - nposimplbin : number of implicit binary variables with positive coefficient
67  * - nnegimplbin : number of implicit binary variables with negative coefficient
68  * - nposcont : number of continuous variables with positive coefficient
69  * - nnegcont : number of continuous variables with negative coefficient
70  * - ncoeffspone : number of +1 coefficients
71  * - ncoeffsnone : number of -1 coefficients
72  * - ncoeffspint : number of positive integral coefficients other than +1
73  * - ncoeffsnint : number of negative integral coefficients other than -1
74  * - ncoeffspfrac : number of positive fractional coefficients
75  * - ncoeffsnfrac : number of negative fractional coefficients
76  * - poscoeffsum : sum of all positive coefficients
77  * - negcoeffsum : sum of all negative coefficients
78  * - integral : TRUE iff constraints activity value is always integral
79  * - upgdcons : pointer to store the upgraded constraint
80  */
81 #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, \
82  int nposbin, int nnegbin, int nposint, int nnegint, int nposimpl, int nnegimpl, int nposimplbin, int nnegimplbin, int nposcont, int nnegcont, \
83  int ncoeffspone, int ncoeffsnone, int ncoeffspint, int ncoeffsnint, int ncoeffspfrac, int ncoeffsnfrac, \
84  SCIP_Real poscoeffsum, SCIP_Real negcoeffsum, SCIP_Bool integral, SCIP_CONS** upgdcons)
85 
86 
87 /*
88  * constraint specific interface methods
89  */
90 
91 /** creates the handler for linear constraints and includes it in SCIP */
92 extern
94  SCIP* scip /**< SCIP data structure */
95  );
96 
97 /** includes a linear constraint update method into the linear constraint handler */
98 extern
100  SCIP* scip, /**< SCIP data structure */
101  SCIP_DECL_LINCONSUPGD((*linconsupgd)), /**< method to call for upgrading linear constraint */
102  int priority, /**< priority of upgrading method */
103  const char* conshdlrname /**< name of the constraint handler */
104  );
105 
106 /** creates and captures a linear constraint
107  *
108  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
109  */
110 extern
112  SCIP* scip, /**< SCIP data structure */
113  SCIP_CONS** cons, /**< pointer to hold the created constraint */
114  const char* name, /**< name of constraint */
115  int nvars, /**< number of nonzeros in the constraint */
116  SCIP_VAR** vars, /**< array with variables of constraint entries */
117  SCIP_Real* vals, /**< array with coefficients of constraint entries */
118  SCIP_Real lhs, /**< left hand side of constraint */
119  SCIP_Real rhs, /**< right hand side of constraint */
120  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
121  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
122  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
123  * Usually set to TRUE. */
124  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
125  * TRUE for model constraints, FALSE for additional, redundant constraints. */
126  SCIP_Bool check, /**< should the constraint be checked for feasibility?
127  * TRUE for model constraints, FALSE for additional, redundant constraints. */
128  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
129  * Usually set to TRUE. */
130  SCIP_Bool local, /**< is constraint only valid locally?
131  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
132  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
133  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
134  * adds coefficients to this constraint. */
135  SCIP_Bool dynamic, /**< is constraint subject to aging?
136  * Usually set to FALSE. Set to TRUE for own cuts which
137  * are separated as constraints. */
138  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
139  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
140  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
141  * if it may be moved to a more global node?
142  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
143  );
144 
145 /** creates and captures a linear constraint
146  * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
147  * method SCIPcreateConsLinear(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
148  *
149  * @see SCIPcreateConsLinear() for information about the basic constraint flag configuration
150  *
151  * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
152  */
153 extern
155  SCIP* scip, /**< SCIP data structure */
156  SCIP_CONS** cons, /**< pointer to hold the created constraint */
157  const char* name, /**< name of constraint */
158  int nvars, /**< number of nonzeros in the constraint */
159  SCIP_VAR** vars, /**< array with variables of constraint entries */
160  SCIP_Real* vals, /**< array with coefficients of constraint entries */
161  SCIP_Real lhs, /**< left hand side of constraint */
162  SCIP_Real rhs /**< right hand side of constraint */
163  );
164 
165 /** creates by copying and captures a linear constraint */
166 extern
168  SCIP* scip, /**< target SCIP data structure */
169  SCIP_CONS** cons, /**< pointer to store the created target constraint */
170  SCIP* sourcescip, /**< source SCIP data structure */
171  const char* name, /**< name of constraint */
172  int nvars, /**< number of variables in source variable array */
173  SCIP_VAR** sourcevars, /**< source variables of the linear constraints */
174  SCIP_Real* sourcecoefs, /**< coefficient array of the linear constraint, or NULL if all coefficients are one */
175  SCIP_Real lhs, /**< left hand side of the linear constraint */
176  SCIP_Real rhs, /**< right hand side of the linear constraint */
177  SCIP_HASHMAP* varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to corresponding
178  * variables of the target SCIP */
179  SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
180  * target constraints */
181  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP? */
182  SCIP_Bool separate, /**< should the constraint be separated during LP processing? */
183  SCIP_Bool enforce, /**< should the constraint be enforced during node processing? */
184  SCIP_Bool check, /**< should the constraint be checked for feasibility? */
185  SCIP_Bool propagate, /**< should the constraint be propagated during node processing? */
186  SCIP_Bool local, /**< is constraint only valid locally? */
187  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)? */
188  SCIP_Bool dynamic, /**< is constraint subject to aging? */
189  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup? */
190  SCIP_Bool stickingatnode, /**< should the constraint always be kept at the node where it was added, even
191  * if it may be moved to a more global node? */
192  SCIP_Bool global, /**< create a global or a local copy? */
193  SCIP_Bool* valid /**< pointer to store if the copying was valid */
194  );
195 
196 /** adds coefficient to linear constraint (if it is not zero) */
197 extern
199  SCIP* scip, /**< SCIP data structure */
200  SCIP_CONS* cons, /**< constraint data */
201  SCIP_VAR* var, /**< variable of constraint entry */
202  SCIP_Real val /**< coefficient of constraint entry */
203  );
204 
205 /** changes coefficient of variable in linear constraint; deletes the variable if coefficient is zero; adds variable if
206  * not yet contained in the constraint
207  *
208  * @note This method may only be called during problem creation stage for an original constraint and variable.
209  *
210  * @note This method requires linear time to search for occurences of the variable in the constraint data.
211  */
212 extern
214  SCIP* scip, /**< SCIP data structure */
215  SCIP_CONS* cons, /**< constraint data */
216  SCIP_VAR* var, /**< variable of constraint entry */
217  SCIP_Real val /**< new coefficient of constraint entry */
218  );
219 
220 /** deletes variable from linear constraint
221  *
222  * @note This method may only be called during problem creation stage for an original constraint and variable.
223  *
224  * @note This method requires linear time to search for occurences of the variable in the constraint data.
225  */
226 extern
228  SCIP* scip, /**< SCIP data structure */
229  SCIP_CONS* cons, /**< constraint data */
230  SCIP_VAR* var /**< variable of constraint entry */
231  );
232 
233 /** gets left hand side of linear constraint */
234 extern
236  SCIP* scip, /**< SCIP data structure */
237  SCIP_CONS* cons /**< constraint data */
238  );
239 
240 /** gets right hand side of linear constraint */
241 extern
243  SCIP* scip, /**< SCIP data structure */
244  SCIP_CONS* cons /**< constraint data */
245  );
246 
247 /** changes left hand side of linear constraint */
248 extern
250  SCIP* scip, /**< SCIP data structure */
251  SCIP_CONS* cons, /**< constraint data */
252  SCIP_Real lhs /**< new left hand side */
253  );
254 
255 /** changes right hand side of linear constraint */
256 extern
258  SCIP* scip, /**< SCIP data structure */
259  SCIP_CONS* cons, /**< constraint data */
260  SCIP_Real rhs /**< new right hand side */
261  );
262 
263 /** gets the number of variables in the linear constraint */
264 extern
266  SCIP* scip, /**< SCIP data structure */
267  SCIP_CONS* cons /**< constraint data */
268  );
269 
270 /** gets the array of variables in the linear constraint; the user must not modify this array! */
271 extern
273  SCIP* scip, /**< SCIP data structure */
274  SCIP_CONS* cons /**< constraint data */
275  );
276 
277 /** gets the array of coefficient values in the linear constraint; the user must not modify this array! */
278 extern
280  SCIP* scip, /**< SCIP data structure */
281  SCIP_CONS* cons /**< constraint data */
282  );
283 
284 /** gets the activity of the linear constraint in the given solution
285  *
286  * @note if the solution contains values at infinity, this method will return SCIP_INVALID in case the activity
287  * comprises positive and negative infinity contributions
288  */
289 extern
291  SCIP* scip, /**< SCIP data structure */
292  SCIP_CONS* cons, /**< constraint data */
293  SCIP_SOL* sol /**< solution, or NULL to use current node's solution */
294  );
295 
296 /** gets the feasibility of the linear constraint in the given solution */
297 extern
299  SCIP* scip, /**< SCIP data structure */
300  SCIP_CONS* cons, /**< constraint data */
301  SCIP_SOL* sol /**< solution, or NULL to use current node's solution */
302  );
303 
304 /** gets the dual solution of the linear constraint in the current LP */
305 extern
307  SCIP* scip, /**< SCIP data structure */
308  SCIP_CONS* cons /**< constraint data */
309  );
310 
311 /** gets the dual Farkas value of the linear constraint in the current infeasible LP */
312 extern
314  SCIP* scip, /**< SCIP data structure */
315  SCIP_CONS* cons /**< constraint data */
316  );
317 
318 /** returns the linear relaxation of the given linear constraint; may return NULL if no LP row was yet created;
319  * the user must not modify the row!
320  */
321 extern
323  SCIP* scip, /**< SCIP data structure */
324  SCIP_CONS* cons /**< constraint data */
325  );
326 
327 /** tries to automatically convert a linear constraint into a more specific and more specialized constraint */
328 extern
330  SCIP* scip, /**< SCIP data structure */
331  SCIP_CONS* cons, /**< source constraint to try to convert */
332  SCIP_CONS** upgdcons /**< pointer to store upgraded constraint, or NULL if not successful */
333  );
334 
335 
336 #ifdef __cplusplus
337 }
338 #endif
339 
340 #endif
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_RETCODE SCIPincludeConshdlrLinear(SCIP *scip)
SCIP_RETCODE SCIPupgradeConsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **upgdcons)
struct SCIP_Cons SCIP_CONS
Definition: type_cons.h:48
int SCIPgetNVarsLinear(SCIP *scip, SCIP_CONS *cons)
struct SCIP_Row SCIP_ROW
Definition: type_lp.h:93
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
struct SCIP_HashMap SCIP_HASHMAP
Definition: type_misc.h:78
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIP_Real SCIPgetDualfarkasLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetFeasibilityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_RETCODE SCIPdelCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
struct Scip SCIP
Definition: type_scip.h:30
SCIP_ROW * SCIPgetRowLinear(SCIP *scip, SCIP_CONS *cons)
struct SCIP_Sol SCIP_SOL
Definition: type_sol.h:45
#define SCIP_Bool
Definition: def.h:53
SCIP_RETCODE SCIPchgCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
struct SCIP_Var SCIP_VAR
Definition: type_var.h:95
#define SCIP_DECL_LINCONSUPGD(x)
Definition: cons_linear.h:81
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPcopyConsLinear(SCIP *scip, SCIP_CONS **cons, SCIP *sourcescip, const char *name, int nvars, SCIP_VAR **sourcevars, SCIP_Real *sourcecoefs, SCIP_Real lhs, SCIP_Real rhs, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, 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_Bool global, SCIP_Bool *valid)
struct SCIP_LinConsUpgrade SCIP_LINCONSUPGRADE
Definition: cons_linear.h:46
SCIP_Real SCIPgetActivityLinear(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, 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)
#define SCIP_Real
Definition: def.h:127
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_Real * SCIPgetValsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
SCIP_VAR ** SCIPgetVarsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP callable library.