SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
49extern "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 */
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 */
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 */
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 */
93 SCIP_ROWPREP* rowprep /**< rowprep */
94 );
95
96/** gives variables of rowprep (feel free to modify) */
99 SCIP_ROWPREP* rowprep /**< rowprep */
100 );
101
102/** gives coefficients of rowprep (feel free to modify) */
104SCIP_Real* SCIProwprepGetCoefs(
105 SCIP_ROWPREP* rowprep /**< rowprep */
106 );
107
108/** gives side of rowprep */
110SCIP_Real SCIProwprepGetSide(
111 SCIP_ROWPREP* rowprep /**< rowprep */
112 );
113
114/** gives kind of inequality of rowprep */
117 SCIP_ROWPREP* rowprep /**< rowprep */
118 );
119
120/** returns whether rowprep is locally valid only */
122SCIP_Bool SCIProwprepIsLocal(
123 SCIP_ROWPREP* rowprep /**< rowprep */
124 );
125
126/** returns name of rowprep (feel free to modify) */
129 SCIP_ROWPREP* rowprep /**< rowprep */
130 );
131
132/** returns number of variables which coefficients were modified in cleanup */
135 SCIP_ROWPREP* rowprep /**< rowprep */
136 );
137
138/** returns variables which coefficients were modified in cleanup */
141 SCIP_ROWPREP* rowprep /**< rowprep */
142 );
143
144/** resets rowprep to have 0 terms and side 0.0 */
147 SCIP_ROWPREP* rowprep /**< rowprep */
148 );
149
150/** adds constant value to side of rowprep */
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 */
163 SCIP_ROWPREP* rowprep, /**< rowprep */
164 SCIP_Real constant /**< constant value to be added */
165 );
166
167/** sets side type of rowprep */
170 SCIP_ROWPREP* rowprep, /**< rowprep */
171 SCIP_SIDETYPE sidetype /**< new side type */
172 );
173
174/** sets whether rowprep is local */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
367SCIP_Real SCIPscaleupRowprep(
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 */
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 */
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 */
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 */
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__ */
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
void SCIProwprepReset(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
void SCIPmergeRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep)
int SCIProwprepGetNModifiedVars(SCIP_ROWPREP *rowprep)
SCIP_Real SCIPgetRowprepViolation(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Bool *reliable)
SCIP_Real SCIPscaleupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real minscaleup, SCIP_Bool *success)
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
SCIP_VAR ** SCIProwprepGetModifiedVars(SCIP_ROWPREP *rowprep)
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
void SCIProwprepSetSidetype(SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
SCIP_Bool SCIPisRowprepViolationReliable(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol)
SCIP_Bool SCIProwprepIsLocal(SCIP_ROWPREP *rowprep)
void SCIPprintRowprepSol(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, FILE *file)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
SCIP_SIDETYPE SCIProwprepGetSidetype(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPgetRowprepRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_SEPA *sepa)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetRowprepRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
int SCIPscaleRowprep(SCIP_ROWPREP *rowprep, SCIP_Real factor)
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
void SCIProwprepRecordModifications(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPaddRowprepTerms(SCIP *scip, SCIP_ROWPREP *rowprep, int nvars, SCIP_VAR **vars, SCIP_Real *coefs)
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
SCIP_RETCODE SCIPcopyRowprep(SCIP *scip, SCIP_ROWPREP **target, SCIP_ROWPREP *source)
SCIP_RETCODE SCIPcleanupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real minviol, SCIP_Real *viol, SCIP_Bool *success)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
static SCIP_SOL * sol
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
miscellaneous datastructures
type definitions for constraints and constraint handlers
type definitions for LP management
enum SCIP_SideType SCIP_SIDETYPE
Definition type_lp.h:67
type definitions for miscellaneous datastructures
enum SCIP_Retcode SCIP_RETCODE
type definitions for separators
type definitions for problem variables