Scippy

SCIP

Solving Constraint Integer Programs

pub_misc_rowprep.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-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 pub_misc_rowprep.h
26  * @brief preparation of a linear inequality to become a SCIP_ROW
27  * @ingroup PUBLICCOREAPI
28  * @author Stefan Vigerske
29  * @author Benjamin Mueller
30  * @author Felipe Serrano
31  */
32 
33 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34 
35 #ifndef __SCIP_PUB_MISC_ROWPREP_H__
36 #define __SCIP_PUB_MISC_ROWPREP_H__
37 
38 #include "scip/type_misc.h"
39 #include "scip/type_cons.h"
40 #include "scip/type_lp.h"
41 #include "scip/type_sepa.h"
42 #include "scip/type_var.h"
43 
44 #ifdef NDEBUG
45 #include "scip/struct_misc.h"
46 #endif
47 
48 #ifdef __cplusplus
49 extern "C" {
50 #endif
51 
52 /**@defgroup RowPrep Linear Inequality
53  * @ingroup DataStructures
54  * @brief a linear inequality that is prepared to become a SCIP_ROW
55  *
56  * This data structure helps to work around some limitations of SCIP_ROW's, in particular,
57  * that it rounds coefficients or sides close to integral values without the appropriate care.
58  * On the other hand, a SCIP_ROWPREP is limited to inequalities.
59  *
60  *@{
61  */
62 
63 /** creates a SCIP_ROWPREP datastructure
64  *
65  * Initial row represents 0 ≤ 0.
66  */
67 SCIP_EXPORT
69  SCIP* scip, /**< SCIP data structure */
70  SCIP_ROWPREP** rowprep, /**< buffer to store pointer to rowprep */
71  SCIP_SIDETYPE sidetype, /**< whether cut will be or lower-equal or larger-equal type */
72  SCIP_Bool local /**< whether cut will be valid only locally */
73  );
74 
75 /** frees a SCIP_ROWPREP datastructure */
76 SCIP_EXPORT
77 void SCIPfreeRowprep(
78  SCIP* scip, /**< SCIP data structure */
79  SCIP_ROWPREP** rowprep /**< pointer that stores pointer to rowprep */
80  );
81 
82 /** creates a copy of a SCIP_ROWPREP datastructure */
83 SCIP_EXPORT
85  SCIP* scip, /**< SCIP data structure */
86  SCIP_ROWPREP** target, /**< buffer to store pointer of rowprep copy */
87  SCIP_ROWPREP* source /**< rowprep to copy */
88  );
89 
90 /** gives number of terms in rowprep */
91 SCIP_EXPORT
93  SCIP_ROWPREP* rowprep /**< rowprep */
94  );
95 
96 /** gives variables of rowprep (feel free to modify) */
97 SCIP_EXPORT
99  SCIP_ROWPREP* rowprep /**< rowprep */
100  );
101 
102 /** gives coefficients of rowprep (feel free to modify) */
103 SCIP_EXPORT
105  SCIP_ROWPREP* rowprep /**< rowprep */
106  );
107 
108 /** gives side of rowprep */
109 SCIP_EXPORT
111  SCIP_ROWPREP* rowprep /**< rowprep */
112  );
113 
114 /** gives kind of inequality of rowprep */
115 SCIP_EXPORT
117  SCIP_ROWPREP* rowprep /**< rowprep */
118  );
119 
120 /** returns whether rowprep is locally valid only */
121 SCIP_EXPORT
123  SCIP_ROWPREP* rowprep /**< rowprep */
124  );
125 
126 /** returns name of rowprep (feel free to modify) */
127 SCIP_EXPORT
128 char* SCIProwprepGetName(
129  SCIP_ROWPREP* rowprep /**< rowprep */
130  );
131 
132 /** returns number of variables which coefficients were modified in cleanup */
133 SCIP_EXPORT
135  SCIP_ROWPREP* rowprep /**< rowprep */
136  );
137 
138 /** returns variables which coefficients were modified in cleanup */
139 SCIP_EXPORT
141  SCIP_ROWPREP* rowprep /**< rowprep */
142  );
143 
144 /** resets rowprep to have 0 terms and side 0.0 */
145 SCIP_EXPORT
146 void SCIProwprepReset(
147  SCIP_ROWPREP* rowprep /**< rowprep */
148  );
149 
150 /** adds constant value to side of rowprep */
151 SCIP_EXPORT
152 void SCIProwprepAddSide(
153  SCIP_ROWPREP* rowprep, /**< rowprep */
154  SCIP_Real side /**< constant value to be added to side */
155  );
156 
157 /** adds constant term to rowprep
158  *
159  * Substracts constant from side.
160  */
161 SCIP_EXPORT
163  SCIP_ROWPREP* rowprep, /**< rowprep */
164  SCIP_Real constant /**< constant value to be added */
165  );
166 
167 /** sets side type of rowprep */
168 SCIP_EXPORT
170  SCIP_ROWPREP* rowprep, /**< rowprep */
171  SCIP_SIDETYPE sidetype /**< new side type */
172  );
173 
174 /** sets whether rowprep is local */
175 SCIP_EXPORT
177  SCIP_ROWPREP* rowprep, /**< rowprep */
178  SCIP_Bool islocal /**< whether rowprep is local */
179  );
180 
181 /** enables recording for where modifications were done in cleanup */
182 SCIP_EXPORT
184  SCIP_ROWPREP* rowprep /**< rowprep */
185  );
186 
187 #ifdef NDEBUG
188 /* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and
189  * speed up the algorithms.
190  */
191 #define SCIProwprepGetNVars(rowprep) (rowprep)->nvars
192 #define SCIProwprepGetVars(rowprep) (rowprep)->vars
193 #define SCIProwprepGetCoefs(rowprep) (rowprep)->coefs
194 #define SCIProwprepGetSide(rowprep) (rowprep)->side
195 #define SCIProwprepGetSidetype(rowprep) (rowprep)->sidetype
196 #define SCIProwprepIsLocal(rowprep) (rowprep)->local
197 #define SCIProwprepGetName(rowprep) (rowprep)->name
198 #define SCIProwprepGetNModifiedVars(rowprep) (rowprep)->nmodifiedvars
199 #define SCIProwprepGetModifiedVars(rowprep) (rowprep)->modifiedvars
200 #define SCIProwprepAddSide(rowprep, sideadd) ((rowprep)->side += (sideadd))
201 #define SCIProwprepAddConstant(rowprep, constant) SCIProwprepAddSide(rowprep, -(constant))
202 #define SCIProwprepSetSidetype(rowprep, sidetype_) (rowprep)->sidetype = sidetype_
203 #define SCIProwprepSetLocal(rowprep, islocal) (rowprep)->local = islocal
204 #define SCIProwprepRecordModifications(rowprep) (rowprep)->recordmodifications = TRUE
205 #endif
206 
207 /** prints a rowprep */
208 SCIP_EXPORT
209 void SCIPprintRowprep(
210  SCIP* scip, /**< SCIP data structure */
211  SCIP_ROWPREP* rowprep, /**< rowprep to be printed */
212  FILE* file /**< file to print to, or NULL for stdout */
213  );
214 
215 /** prints a rowprep and values in solution */
216 SCIP_EXPORT
218  SCIP* scip, /**< SCIP data structure */
219  SCIP_ROWPREP* rowprep, /**< rowprep to be printed */
220  SCIP_SOL* sol, /**< solution for activity */
221  FILE* file /**< file to print to, or NULL for stdout */
222  );
223 
224 /** ensures that rowprep has space for at least given number of additional terms
225  *
226  * Useful when knowing in advance how many terms will be added.
227  */
228 SCIP_EXPORT
230  SCIP* scip, /**< SCIP data structure */
231  SCIP_ROWPREP* rowprep, /**< rowprep */
232  int size /**< number of additional terms for which to alloc space in rowprep */
233  );
234 
235 /** adds a term coef*var to a rowprep */
236 SCIP_EXPORT
238  SCIP* scip, /**< SCIP data structure */
239  SCIP_ROWPREP* rowprep, /**< rowprep */
240  SCIP_VAR* var, /**< variable to add */
241  SCIP_Real coef /**< coefficient to add */
242  );
243 
244 /** adds several terms coef*var to a rowprep */
245 SCIP_EXPORT
247  SCIP* scip, /**< SCIP data structure */
248  SCIP_ROWPREP* rowprep, /**< rowprep */
249  int nvars, /**< number of terms to add */
250  SCIP_VAR** vars, /**< variables to add */
251  SCIP_Real* coefs /**< coefficients to add */
252  );
253 
254 /** computes violation of rowprep in a given solution
255  *
256  * Can return whether the violation value is reliable from a floating-point accuracy point of view.
257  * The value will not be deemed reliable when its calculation involved the subtraction of large numbers.
258  * 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
259  * reliable if \f$ |\sum_i a_ix^*_i - b| \geq 2^{-50} \max (|b|, \max_i |a_ix^*_i|) \f$.
260  */
261 SCIP_EXPORT
263  SCIP* scip, /**< SCIP data structure */
264  SCIP_ROWPREP* rowprep, /**< rowprep */
265  SCIP_SOL* sol, /**< solution or NULL for LP solution */
266  SCIP_Bool* reliable /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */
267  );
268 
269 /** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable
270  *
271  * @see SCIPgetRowprepViolation()
272  */
273 SCIP_EXPORT
275  SCIP* scip, /**< SCIP data structure */
276  SCIP_ROWPREP* rowprep, /**< rowprep */
277  SCIP_SOL* sol /**< solution or NULL for LP solution */
278  );
279 
280 /** Merge terms that use same variable and eliminate zero coefficients.
281  *
282  * Removes a variable if its bounds have a relative difference of below epsilon.
283  * Local bounds are checked for local rows, otherwise global bounds are used.
284  * If the bounds are not absolute equal, the bound that relaxes the row is used.
285  *
286  * Terms are sorted by variable (see SCIPvarComp()) after return.
287  */
288 SCIP_EXPORT
290  SCIP* scip, /**< SCIP data structure */
291  SCIP_ROWPREP* rowprep /**< rowprep to be cleaned up */
292  );
293 
294 /** Cleans up and attempts to improve rowprep
295  *
296  * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
297  * if this can be done by relaxing the row.
298  * Scales coefficients up to reach minimal violation, if possible.
299  * Scaling is omitted if violation is very small (\ref ROWPREP_SCALEUP_VIOLNONZERO) or
300  * maximal coefficient would become huge (\ref ROWPREP_SCALEUP_MAXMAXCOEF).
301  * Scales coefficients and side down if they are large and if the minimal violation is still reached.
302  * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
303  * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
304  *
305  * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
306  * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
307  *
308  * `success` is set to TRUE if and only if the rowprep satisfies the following:
309  * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
310  * - the violation is at least `minviol`
311  * - the violation is reliable or `minviol` = 0
312  * - the absolute value of coefficients are below SCIPinfinity()
313  * - the absolute value of the side is below SCIPinfinity()
314  */
315 SCIP_EXPORT
317  SCIP* scip, /**< SCIP data structure */
318  SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
319  SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */
320  SCIP_Real minviol, /**< minimal absolute violation the row should achieve (w.r.t. sol) */
321  SCIP_Real* viol, /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
322  SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
323  );
324 
325 /** Cleans up and attempts to improve rowprep without regard for violation
326  *
327  * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
328  * if this can be done by relaxing the row.
329  * Scales coefficients and side to have maximal coefficient in `[1/maxcoefbound,maxcoefbound]`.
330  * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
331  * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
332  *
333  * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
334  * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
335  *
336  * `success` is set to TRUE if and only if the rowprep satisfies the following:
337  * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
338  * - the absolute value of coefficients are below SCIPinfinity()
339  * - the absolute value of the side is below SCIPinfinity()
340  *
341  * In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation.
342  */
343 SCIP_EXPORT
345  SCIP* scip, /**< SCIP data structure */
346  SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
347  SCIP_SOL* sol, /**< solution that we try to cut off, or NULL for LP solution */
348  SCIP_Real maxcoefbound, /**< bound on absolute value of largest coefficient */
349  SCIP_Bool* success /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
350  );
351 
352 /** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible.
353  *
354  * Computes the minimal fractionality of all fractional coefficients and the side of the rowprep.
355  * If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon,
356  * if this will not put any coefficient or side above SCIPhugeValue().
357  *
358  * This function does not relax the rowprep.
359  *
360  * `success` is set to TRUE if the resulting rowprep can be turned into a SCIP_ROW, that is,
361  * all coefs and the side is below SCIPinfinity() and fractionalities are above epsilon.
362  * If `success` is set to FALSE, then the rowprep will not have been modified.
363  *
364  * @return The applied scaling factor, if `success` is set to TRUE.
365  */
366 SCIP_EXPORT
368  SCIP* scip, /**< SCIP data structure */
369  SCIP_ROWPREP* rowprep, /**< rowprep to be cleaned */
370  SCIP_Real minscaleup, /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */
371  SCIP_Bool* success /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */
372  );
373 
374 /** scales a rowprep by given factor (after some rounding)
375  *
376  * @return Exponent of actually applied scaling factor, if written as \f$2^x\f$.
377  */
378 SCIP_EXPORT
379 int SCIPscaleRowprep(
380  SCIP_ROWPREP* rowprep, /**< rowprep to be scaled */
381  SCIP_Real factor /**< suggested scale factor */
382  );
383 
384 /** generates a SCIP_ROW from a rowprep, setting its origin to given constraint handler */
385 SCIP_EXPORT
387  SCIP* scip, /**< SCIP data structure */
388  SCIP_ROW** row, /**< buffer to store pointer to new row */
389  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
390  SCIP_CONSHDLR* conshdlr /**< constraint handler */
391  );
392 
393 /** generates a SCIP_ROW from a rowprep, setting its origin to given constraint */
394 SCIP_EXPORT
396  SCIP* scip, /**< SCIP data structure */
397  SCIP_ROW** row, /**< buffer to store pointer to new row */
398  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
399  SCIP_CONS* cons /**< constraint */
400  );
401 
402 /** generates a SCIP_ROW from a rowprep, setting its origin to given separator */
403 SCIP_EXPORT
405  SCIP* scip, /**< SCIP data structure */
406  SCIP_ROW** row, /**< buffer to store pointer to new row */
407  SCIP_ROWPREP* rowprep, /**< rowprep to be turned into a row */
408  SCIP_SEPA* sepa /**< separator */
409  );
410 
411 /** @} */
412 
413 #ifdef __cplusplus
414 }
415 #endif
416 
417 #endif /* __SCIP_PUB_MISC_ROWPREP_H__ */
void SCIProwprepRecordModifications(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:782
type definitions for miscellaneous datastructures
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: misc_rowprep.c:792
SCIP_RETCODE SCIPcopyRowprep(SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
Definition: misc_rowprep.c:597
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:687
miscellaneous datastructures
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_SIDETYPE SCIProwprepGetSidetype(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:667
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:878
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
type definitions for LP management
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:647
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:627
SCIP_Bool SCIProwprepIsLocal(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:677
SCIP_Real SCIPscaleupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real minscaleup, SCIP_Bool *success)
void SCIProwprepSetSidetype(SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
Definition: misc_rowprep.c:760
SCIP_Bool SCIPisRowprepViolationReliable(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
void SCIProwprepReset(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:717
SCIP_RETCODE SCIPgetRowprepRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:581
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
Definition: misc_rowprep.c:737
type definitions for problem variables
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *reliable)
Definition: misc_rowprep.c:963
SCIP_VAR ** SCIProwprepGetModifiedVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:707
int SCIProwprepGetNModifiedVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:697
#define SCIP_Bool
Definition: def.h:93
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:751
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
int SCIPscaleRowprep(SCIP_ROWPREP *rowprep, SCIP_Real factor)
void SCIPprintRowprepSol(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, FILE *file)
Definition: misc_rowprep.c:817
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:657
type definitions for separators
#define SCIP_Real
Definition: def.h:186
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:561
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:904
SCIP_RETCODE SCIPcleanupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real minviol, SCIP_Real *viol, SCIP_Bool *success)
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:771
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
Definition: misc_rowprep.c:929
type definitions for constraints and constraint handlers
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:637
enum SCIP_SideType SCIP_SIDETYPE
Definition: type_lp.h:67