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