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-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_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
93 SCIP_RETCODE SCIPincludeConshdlrLinear(
94  SCIP* scip /**< SCIP data structure */
95  );
96 
97 /** includes a linear constraint update method into the linear constraint handler */
98 extern
99 SCIP_RETCODE SCIPincludeLinconsUpgrade(
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
111 SCIP_RETCODE SCIPcreateConsLinear(
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
154 SCIP_RETCODE SCIPcreateConsBasicLinear(
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
167 SCIP_RETCODE SCIPcopyConsLinear(
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
198 SCIP_RETCODE SCIPaddCoefLinear(
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 /** gets left hand side of linear constraint */
206 extern
207 SCIP_Real SCIPgetLhsLinear(
208  SCIP* scip, /**< SCIP data structure */
209  SCIP_CONS* cons /**< constraint data */
210  );
211 
212 /** gets right hand side of linear constraint */
213 extern
214 SCIP_Real SCIPgetRhsLinear(
215  SCIP* scip, /**< SCIP data structure */
216  SCIP_CONS* cons /**< constraint data */
217  );
218 
219 /** changes left hand side of linear constraint */
220 extern
221 SCIP_RETCODE SCIPchgLhsLinear(
222  SCIP* scip, /**< SCIP data structure */
223  SCIP_CONS* cons, /**< constraint data */
224  SCIP_Real lhs /**< new left hand side */
225  );
226 
227 /** changes right hand side of linear constraint */
228 extern
229 SCIP_RETCODE SCIPchgRhsLinear(
230  SCIP* scip, /**< SCIP data structure */
231  SCIP_CONS* cons, /**< constraint data */
232  SCIP_Real rhs /**< new right hand side */
233  );
234 
235 /** gets the number of variables in the linear constraint */
236 extern
237 int SCIPgetNVarsLinear(
238  SCIP* scip, /**< SCIP data structure */
239  SCIP_CONS* cons /**< constraint data */
240  );
241 
242 /** gets the array of variables in the linear constraint; the user must not modify this array! */
243 extern
244 SCIP_VAR** SCIPgetVarsLinear(
245  SCIP* scip, /**< SCIP data structure */
246  SCIP_CONS* cons /**< constraint data */
247  );
248 
249 /** gets the array of coefficient values in the linear constraint; the user must not modify this array! */
250 extern
251 SCIP_Real* SCIPgetValsLinear(
252  SCIP* scip, /**< SCIP data structure */
253  SCIP_CONS* cons /**< constraint data */
254  );
255 
256 /** gets the activity of the linear constraint in the given solution */
257 extern
258 SCIP_Real SCIPgetActivityLinear(
259  SCIP* scip, /**< SCIP data structure */
260  SCIP_CONS* cons, /**< constraint data */
261  SCIP_SOL* sol /**< solution, or NULL to use current node's solution */
262  );
263 
264 /** gets the feasibility of the linear constraint in the given solution */
265 extern
266 SCIP_Real SCIPgetFeasibilityLinear(
267  SCIP* scip, /**< SCIP data structure */
268  SCIP_CONS* cons, /**< constraint data */
269  SCIP_SOL* sol /**< solution, or NULL to use current node's solution */
270  );
271 
272 /** gets the dual solution of the linear constraint in the current LP */
273 extern
274 SCIP_Real SCIPgetDualsolLinear(
275  SCIP* scip, /**< SCIP data structure */
276  SCIP_CONS* cons /**< constraint data */
277  );
278 
279 /** gets the dual Farkas value of the linear constraint in the current infeasible LP */
280 extern
281 SCIP_Real SCIPgetDualfarkasLinear(
282  SCIP* scip, /**< SCIP data structure */
283  SCIP_CONS* cons /**< constraint data */
284  );
285 
286 /** returns the linear relaxation of the given linear constraint; may return NULL if no LP row was yet created;
287  * the user must not modify the row!
288  */
289 extern
290 SCIP_ROW* SCIPgetRowLinear(
291  SCIP* scip, /**< SCIP data structure */
292  SCIP_CONS* cons /**< constraint data */
293  );
294 
295 /** tries to automatically convert a linear constraint into a more specific and more specialized constraint */
296 extern
297 SCIP_RETCODE SCIPupgradeConsLinear(
298  SCIP* scip, /**< SCIP data structure */
299  SCIP_CONS* cons, /**< source constraint to try to convert */
300  SCIP_CONS** upgdcons /**< pointer to store upgraded constraint, or NULL if not successful */
301  );
302 
303 #ifdef __cplusplus
304 }
305 #endif
306 
307 #endif
308