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
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* 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 pub_misc_rowprep.h
* @brief preparation of a linear inequality to become a SCIP_ROW
* @ingroup PUBLICCOREAPI
* @author Stefan Vigerske
* @author Benjamin Mueller
* @author Felipe Serrano
*/
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
#ifndef __SCIP_PUB_MISC_ROWPREP_H__
#define __SCIP_PUB_MISC_ROWPREP_H__
#include "scip/type_misc.h"
#include "scip/type_cons.h"
#include "scip/type_lp.h"
#include "scip/type_sepa.h"
#include "scip/type_var.h"
#ifdef NDEBUG
#include "scip/struct_misc.h"
#endif
#ifdef __cplusplus
extern "C" {
#endif
/**@defgroup RowPrep Linear Inequality
* @ingroup DataStructures
* @brief a linear inequality that is prepared to become a SCIP_ROW
*
* This data structure helps to work around some limitations of SCIP_ROW's, in particular,
* that it rounds coefficients or sides close to integral values without the appropriate care.
* On the other hand, a SCIP_ROWPREP is limited to inequalities.
*
*@{
*/
/** creates a SCIP_ROWPREP datastructure
*
* Initial row represents 0 ≤ 0.
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcreateRowprep(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */
SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */
SCIP_Bool local /**< whether cut will be valid only locally */
);
/** frees a SCIP_ROWPREP datastructure */
SCIP_EXPORT
void SCIPfreeRowprep(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */
);
/** creates a copy of a SCIP_ROWPREP datastructure */
SCIP_EXPORT
SCIP_RETCODE SCIPcopyRowprep(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */
SCIP_ROWPREP* source /**< rowprep to copy */
);
/** gives number of terms in rowprep */
SCIP_EXPORT
int SCIProwprepGetNVars(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** gives variables of rowprep (feel free to modify) */
SCIP_EXPORT
SCIP_VAR** SCIProwprepGetVars(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** gives coefficients of rowprep (feel free to modify) */
SCIP_EXPORT
SCIP_Real* SCIProwprepGetCoefs(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** gives side of rowprep */
SCIP_EXPORT
SCIP_Real SCIProwprepGetSide(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** gives kind of inequality of rowprep */
SCIP_EXPORT
SCIP_SIDETYPE SCIProwprepGetSidetype(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** returns whether rowprep is locally valid only */
SCIP_EXPORT
SCIP_Bool SCIProwprepIsLocal(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** returns name of rowprep (feel free to modify) */
SCIP_EXPORT
char* SCIProwprepGetName(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** returns number of variables which coefficients were modified in cleanup */
SCIP_EXPORT
int SCIProwprepGetNModifiedVars(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** returns variables which coefficients were modified in cleanup */
SCIP_EXPORT
SCIP_VAR** SCIProwprepGetModifiedVars(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** resets rowprep to have 0 terms and side 0.0 */
SCIP_EXPORT
void SCIProwprepReset(
SCIP_ROWPREP* rowprep /**< rowprep */
);
/** adds constant value to side of rowprep */
SCIP_EXPORT
void SCIProwprepAddSide(
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_Real side /**< constant value to be added to side */
);
/** adds constant term to rowprep
*
* Substracts constant from side.
*/
SCIP_EXPORT
void SCIProwprepAddConstant(
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_Real constant /**< constant value to be added */
);
/** sets side type of rowprep */
SCIP_EXPORT
void SCIProwprepSetSidetype(
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_SIDETYPE sidetype /**< new side type */
);
/** sets whether rowprep is local */
SCIP_EXPORT
void SCIProwprepSetLocal(
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_Bool islocal /**< whether rowprep is local */
);
/** enables recording for where modifications were done in cleanup */
SCIP_EXPORT
void SCIProwprepRecordModifications(
SCIP_ROWPREP* rowprep /**< rowprep */
);
#ifdef NDEBUG
/* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and
* speed up the algorithms.
*/
#define SCIProwprepGetNVars(rowprep) (rowprep)->nvars
#define SCIProwprepGetVars(rowprep) (rowprep)->vars
#define SCIProwprepGetCoefs(rowprep) (rowprep)->coefs
#define SCIProwprepGetSide(rowprep) (rowprep)->side
#define SCIProwprepGetSidetype(rowprep) (rowprep)->sidetype
#define SCIProwprepIsLocal(rowprep) (rowprep)->local
#define SCIProwprepGetName(rowprep) (rowprep)->name
#define SCIProwprepGetNModifiedVars(rowprep) (rowprep)->nmodifiedvars
#define SCIProwprepGetModifiedVars(rowprep) (rowprep)->modifiedvars
#define SCIProwprepAddSide(rowprep, sideadd) ((rowprep)->side += (sideadd))
#define SCIProwprepAddConstant(rowprep, constant) SCIProwprepAddSide(rowprep, -(constant))
#define SCIProwprepSetSidetype(rowprep, sidetype_) (rowprep)->sidetype = sidetype_
#define SCIProwprepSetLocal(rowprep, islocal) (rowprep)->local = islocal
#define SCIProwprepRecordModifications(rowprep) (rowprep)->recordmodifications = TRUE
#endif
/** prints a rowprep */
SCIP_EXPORT
void SCIPprintRowprep(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep to be printed */
FILE* file /**< file to print to, or NULL for stdout */
);
/** prints a rowprep and values in solution */
SCIP_EXPORT
void SCIPprintRowprepSol(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep to be printed */
SCIP_SOL* sol, /**< solution for activity */
FILE* file /**< file to print to, or NULL for stdout */
);
/** ensures that rowprep has space for at least given number of additional terms
*
* Useful when knowing in advance how many terms will be added.
*/
SCIP_EXPORT
SCIP_RETCODE SCIPensureRowprepSize(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep */
int size /**< number of additional terms for which to alloc space in rowprep */
);
/** adds a term coef*var to a rowprep */
SCIP_EXPORT
SCIP_RETCODE SCIPaddRowprepTerm(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_VAR* var, /**< variable to add */
SCIP_Real coef /**< coefficient to add */
);
/** adds several terms coef*var to a rowprep */
SCIP_EXPORT
SCIP_RETCODE SCIPaddRowprepTerms(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep */
int nvars, /**< number of terms to add */
SCIP_VAR** vars, /**< variables to add */
SCIP_Real* coefs /**< coefficients to add */
);
/** computes violation of rowprep in a given solution
*
* Can return whether the violation value is reliable from a floating-point accuracy point of view.
* The value will not be deemed reliable when its calculation involved the subtraction of large numbers.
* To be precise, the violation of an inequality \f$ \sum_i a_ix_i \leq b \f$ in a solution \f$x^*\f$ is deemed
* reliable if \f$ |\sum_i a_ix^*_i - b| \geq 2^{-50} \max (|b|, \max_i |a_ix^*_i|) \f$.
*/
SCIP_EXPORT
SCIP_Real SCIPgetRowprepViolation(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_SOL* sol, /**< solution or NULL for LP solution */
SCIP_Bool* reliable /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */
);
/** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable
*
* @see SCIPgetRowprepViolation()
*/
SCIP_EXPORT
SCIP_Bool SCIPisRowprepViolationReliable(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep */
SCIP_SOL* sol /**< solution or NULL for LP solution */
);
/** Merge terms that use same variable and eliminate zero coefficients.
*
* Removes a variable if its bounds have a relative difference of below epsilon.
* Local bounds are checked for local rows, otherwise global bounds are used.
* If the bounds are not absolute equal, the bound that relaxes the row is used.
*
* Terms are sorted by variable (see SCIPvarComp()) after return.
*/
SCIP_EXPORT
void SCIPmergeRowprepTerms(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */
);
/** Cleans up and attempts to improve rowprep
*
* Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
* if this can be done by relaxing the row.
* Scales coefficients up to reach minimal violation, if possible.
* Scaling is omitted if violation is very small (\ref ROWPREP_SCALEUP_VIOLNONZERO) or
* maximal coefficient would become huge (\ref ROWPREP_SCALEUP_MAXMAXCOEF).
* Scales coefficients and side down if they are large and if the minimal violation is still reached.
* Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
* Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
*
* After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
* Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
*
* `success` is set to TRUE if and only if the rowprep satisfies the following:
* - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
* - the violation is at least `minviol`
* - the violation is reliable or `minviol` = 0
* - the absolute value of coefficients are below SCIPinfinity()
* - the absolute value of the side is below SCIPinfinity()
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcleanupRowprep(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */
SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */
SCIP_Real* viol, /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
);
/** Cleans up and attempts to improve rowprep without regard for violation
*
* Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
* if this can be done by relaxing the row.
* Scales coefficients and side to have maximal coefficient in `[1/maxcoefbound,maxcoefbound]`.
* Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
* Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
*
* After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
* Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
*
* `success` is set to TRUE if and only if the rowprep satisfies the following:
* - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
* - the absolute value of coefficients are below SCIPinfinity()
* - the absolute value of the side is below SCIPinfinity()
*
* In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation.
*/
SCIP_EXPORT
SCIP_RETCODE SCIPcleanupRowprep2(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */
SCIP_Real maxcoefbound, /**< bound on absolute value of largest coefficient */
SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
);
/** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible.
*
* Computes the minimal fractionality of all fractional coefficients and the side of the rowprep.
* If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon,
* if this will not put any coefficient or side above SCIPhugeValue().
*
* This function does not relax the rowprep.
*
* `success` is set to TRUE if the resulting rowprep can be turned into a SCIP_ROW, that is,
* all coefs and the side is below SCIPinfinity() and fractionalities are above epsilon.
* If `success` is set to FALSE, then the rowprep will not have been modified.
*
* @return The applied scaling factor, if `success` is set to TRUE.
*/
SCIP_EXPORT
SCIP_Real SCIPscaleupRowprep(
SCIP* scip, /**< SCIP data structure */
SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
SCIP_Real minscaleup, /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */
SCIP_Bool* success /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */
);
/** scales a rowprep by given factor (after some rounding)
*
* @return Exponent of actually applied scaling factor, if written as \f$2^x\f$.
*/
SCIP_EXPORT
int SCIPscaleRowprep(
SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */
SCIP_Real factor /**< suggested scale factor */
);
/** generates a SCIP_ROW from a rowprep, setting its origin to given constraint handler */
SCIP_EXPORT
SCIP_RETCODE SCIPgetRowprepRowConshdlr(
SCIP* scip, /**< SCIP data structure */
SCIP_ROW** row, /**< buffer to store pointer to new row */
SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
SCIP_CONSHDLR* conshdlr /**< constraint handler */
);
/** generates a SCIP_ROW from a rowprep, setting its origin to given constraint */
SCIP_EXPORT
SCIP_RETCODE SCIPgetRowprepRowCons(
SCIP* scip, /**< SCIP data structure */
SCIP_ROW** row, /**< buffer to store pointer to new row */
SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
SCIP_CONS* cons /**< constraint */
);
/** generates a SCIP_ROW from a rowprep, setting its origin to given separator */
SCIP_EXPORT
SCIP_RETCODE SCIPgetRowprepRowSepa(
SCIP* scip, /**< SCIP data structure */
SCIP_ROW** row, /**< buffer to store pointer to new row */
SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
SCIP_SEPA* sepa /**< separator */
);
/** @} */
#ifdef __cplusplus
}
#endif
#endif /* __SCIP_PUB_MISC_ROWPREP_H__ */