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
68   	SCIP_RETCODE SCIPcreateRowprep(
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
84   	SCIP_RETCODE SCIPcopyRowprep(
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
92   	int SCIProwprepGetNVars(
93   	   SCIP_ROWPREP*         rowprep             /**< rowprep */
94   	   );
95   	
96   	/** gives variables of rowprep (feel free to modify) */
97   	SCIP_EXPORT
98   	SCIP_VAR** SCIProwprepGetVars(
99   	   SCIP_ROWPREP*         rowprep             /**< rowprep */
100  	   );
101  	
102  	/** gives coefficients of rowprep (feel free to modify) */
103  	SCIP_EXPORT
104  	SCIP_Real* SCIProwprepGetCoefs(
105  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
106  	   );
107  	
108  	/** gives side of rowprep */
109  	SCIP_EXPORT
110  	SCIP_Real SCIProwprepGetSide(
111  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
112  	   );
113  	
114  	/** gives kind of inequality of rowprep */
115  	SCIP_EXPORT
116  	SCIP_SIDETYPE SCIProwprepGetSidetype(
117  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
118  	   );
119  	
120  	/** returns whether rowprep is locally valid only */
121  	SCIP_EXPORT
122  	SCIP_Bool SCIProwprepIsLocal(
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
134  	int SCIProwprepGetNModifiedVars(
135  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
136  	   );
137  	
138  	/** returns variables which coefficients were modified in cleanup */
139  	SCIP_EXPORT
140  	SCIP_VAR** SCIProwprepGetModifiedVars(
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  	/** sets coefficient idx of rowprep */
151  	SCIP_EXPORT
152  	void SCIProwprepSetCoef(
153  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
154  	   int                   idx,                /**< index of coef to set */
155  	   SCIP_Real             newcoef             /**< new coefficient */
156  	   );
157  	
158  	/** adds constant value to side of rowprep */
159  	SCIP_EXPORT
160  	void SCIProwprepAddSide(
161  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
162  	   SCIP_Real             side                /**< constant value to be added to side */
163  	   );
164  	
165  	/** adds constant term to rowprep
166  	 *
167  	 * Substracts constant from side.
168  	 */
169  	SCIP_EXPORT
170  	void SCIProwprepAddConstant(
171  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
172  	   SCIP_Real             constant            /**< constant value to be added */
173  	   );
174  	
175  	/** sets side type of rowprep */
176  	SCIP_EXPORT
177  	void SCIProwprepSetSidetype(
178  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
179  	   SCIP_SIDETYPE         sidetype            /**< new side type */
180  	   );
181  	
182  	/** sets whether rowprep is local */
183  	SCIP_EXPORT
184  	void SCIProwprepSetLocal(
185  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
186  	   SCIP_Bool             islocal             /**< whether rowprep is local */
187  	   );
188  	
189  	/** enables recording for where modifications were done in cleanup */
190  	SCIP_EXPORT
191  	void SCIProwprepRecordModifications(
192  	   SCIP_ROWPREP*         rowprep             /**< rowprep */
193  	   );
194  	
195  	#ifdef NDEBUG
196  	/* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and
197  	 * speed up the algorithms.
198  	 */
199  	#define SCIProwprepGetNVars(rowprep)  (rowprep)->nvars
200  	#define SCIProwprepGetVars(rowprep)   (rowprep)->vars
201  	#define SCIProwprepGetCoefs(rowprep)  (rowprep)->coefs
202  	#define SCIProwprepGetSide(rowprep)   (rowprep)->side
203  	#define SCIProwprepGetSidetype(rowprep) (rowprep)->sidetype
204  	#define SCIProwprepIsLocal(rowprep)   (rowprep)->local
205  	#define SCIProwprepGetName(rowprep)   (rowprep)->name
206  	#define SCIProwprepGetNModifiedVars(rowprep) (rowprep)->nmodifiedvars
207  	#define SCIProwprepGetModifiedVars(rowprep) (rowprep)->modifiedvars
208  	#define SCIProwprepSetCoef(rowprep, idx, newcoef) ((rowprep)->coefs[idx] = (newcoef))
209  	#define SCIProwprepAddSide(rowprep, sideadd)  ((rowprep)->side += (sideadd))
210  	#define SCIProwprepAddConstant(rowprep, constant)  SCIProwprepAddSide(rowprep, -(constant))
211  	#define SCIProwprepSetSidetype(rowprep, sidetype_) (rowprep)->sidetype = sidetype_
212  	#define SCIProwprepSetLocal(rowprep, islocal) (rowprep)->local = islocal
213  	#define SCIProwprepRecordModifications(rowprep) (rowprep)->recordmodifications = TRUE
214  	#endif
215  	
216  	/** prints a rowprep */
217  	SCIP_EXPORT
218  	void SCIPprintRowprep(
219  	   SCIP*                 scip,               /**< SCIP data structure */
220  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be printed */
221  	   FILE*                 file                /**< file to print to, or NULL for stdout */
222  	   );
223  	
224  	/** prints a rowprep and values in solution */
225  	SCIP_EXPORT
226  	void SCIPprintRowprepSol(
227  	   SCIP*                 scip,               /**< SCIP data structure */
228  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be printed */
229  	   SCIP_SOL*             sol,                /**< solution for activity */
230  	   FILE*                 file                /**< file to print to, or NULL for stdout */
231  	   );
232  	
233  	/** ensures that rowprep has space for at least given number of additional terms
234  	 *
235  	 * Useful when knowing in advance how many terms will be added.
236  	 */
237  	SCIP_EXPORT
238  	SCIP_RETCODE SCIPensureRowprepSize(
239  	   SCIP*                 scip,               /**< SCIP data structure */
240  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
241  	   int                   size                /**< number of additional terms for which to alloc space in rowprep */
242  	   );
243  	
244  	/** adds a term coef*var to a rowprep */
245  	SCIP_EXPORT
246  	SCIP_RETCODE SCIPaddRowprepTerm(
247  	   SCIP*                 scip,               /**< SCIP data structure */
248  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
249  	   SCIP_VAR*             var,                /**< variable to add */
250  	   SCIP_Real             coef                /**< coefficient to add */
251  	   );
252  	
253  	/** adds several terms coef*var to a rowprep */
254  	SCIP_EXPORT
255  	SCIP_RETCODE SCIPaddRowprepTerms(
256  	   SCIP*                 scip,               /**< SCIP data structure */
257  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
258  	   int                   nvars,              /**< number of terms to add */
259  	   SCIP_VAR**            vars,               /**< variables to add */
260  	   SCIP_Real*            coefs               /**< coefficients to add */
261  	   );
262  	
263  	/** computes violation of rowprep in a given solution
264  	 *
265  	 * Can return whether the violation value is reliable from a floating-point accuracy point of view.
266  	 * The value will not be deemed reliable when its calculation involved the subtraction of large numbers.
267  	 * 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
268  	 * reliable if \f$ |\sum_i a_ix^*_i - b| \geq 2^{-50} \max (|b|, \max_i |a_ix^*_i|) \f$.
269  	 */
270  	SCIP_EXPORT
271  	SCIP_Real SCIPgetRowprepViolation(
272  	   SCIP*                 scip,               /**< SCIP data structure */
273  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
274  	   SCIP_SOL*             sol,                /**< solution or NULL for LP solution */
275  	   SCIP_Bool*            reliable            /**< buffer to store whether computed violation is reliable (numerically), or NULL if not of interest */
276  	   );
277  	
278  	/** computes violation of rowprep in a given solution and reports whether that value seem numerically reliable
279  	 *
280  	 * @see SCIPgetRowprepViolation()
281  	 */
282  	SCIP_EXPORT
283  	SCIP_Bool SCIPisRowprepViolationReliable(
284  	   SCIP*                 scip,               /**< SCIP data structure */
285  	   SCIP_ROWPREP*         rowprep,            /**< rowprep */
286  	   SCIP_SOL*             sol                 /**< solution or NULL for LP solution */
287  	   );
288  	
289  	/** Merge terms that use same variable and eliminate zero coefficients.
290  	 *
291  	 * Removes a variable if its bounds have a relative difference of below epsilon.
292  	 * Local bounds are checked for local rows, otherwise global bounds are used.
293  	 * If the bounds are not absolute equal, the bound that relaxes the row is used.
294  	 *
295  	 * Terms are sorted by variable (see SCIPvarComp()) after return.
296  	 */
297  	SCIP_EXPORT
298  	void SCIPmergeRowprepTerms(
299  	   SCIP*                 scip,               /**< SCIP data structure */
300  	   SCIP_ROWPREP*         rowprep             /**< rowprep to be cleaned up */
301  	   );
302  	
303  	/** Cleans up and attempts to improve rowprep
304  	 *
305  	 * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
306  	 * if this can be done by relaxing the row.
307  	 * Scales coefficients up to reach minimal violation, if possible.
308  	 * Scaling is omitted if violation is very small (\ref ROWPREP_SCALEUP_VIOLNONZERO) or
309  	 * maximal coefficient would become huge (\ref ROWPREP_SCALEUP_MAXMAXCOEF).
310  	 * Scales coefficients and side down if they are large and if the minimal violation is still reached.
311  	 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
312  	 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
313  	 *
314  	 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
315  	 * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
316  	 *
317  	 * `success` is set to TRUE if and only if the rowprep satisfies the following:
318  	 * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
319  	 * - the violation is at least `minviol`
320  	 * - the violation is reliable or `minviol` = 0
321  	 * - the absolute value of coefficients are below SCIPinfinity()
322  	 * - the absolute value of the side is below SCIPinfinity()
323  	 */
324  	SCIP_EXPORT
325  	SCIP_RETCODE SCIPcleanupRowprep(
326  	   SCIP*                 scip,               /**< SCIP data structure */
327  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be cleaned */
328  	   SCIP_SOL*             sol,                /**< solution that we try to cut off, or NULL for LP solution */
329  	   SCIP_Real             minviol,            /**< minimal absolute violation the row should achieve (w.r.t. sol) */
330  	   SCIP_Real*            viol,               /**< buffer to store absolute violation of cleaned up cut in sol, or NULL if not of interest */
331  	   SCIP_Bool*            success             /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
332  	   );
333  	
334  	/** Cleans up and attempts to improve rowprep without regard for violation
335  	 *
336  	 * Drops small or large coefficients if their ratio is beyond separating/maxcoefratiofacrowprep / numerics/feastol,
337  	 * if this can be done by relaxing the row.
338  	 * Scales coefficients and side to have maximal coefficient in `[1/maxcoefbound,maxcoefbound]`.
339  	 * Rounds coefficients close to integral values to integrals, if this can be done by relaxing the row.
340  	 * Rounds side within epsilon of 0 to 0.0 or +/-1.1*epsilon, whichever relaxes the row least.
341  	 *
342  	 * After return, the terms in the rowprep will be sorted by absolute value of coefficient, in decreasing order.
343  	 * Thus, the coefratio can be obtained via `REALABS(rowprep->coefs[0]) / REALABS(rowprep->coefs[rowprep->nvars-1])` (if nvars>0).
344  	 *
345  	 * `success` is set to TRUE if and only if the rowprep satisfies the following:
346  	 * - the coefratio is below separating/maxcoefratiofacrowprep / numerics/feastol
347  	 * - the absolute value of coefficients are below SCIPinfinity()
348  	 * - the absolute value of the side is below SCIPinfinity()
349  	 *
350  	 * In difference to SCIPcleanupRowprep(), this function does not scale up the row to increase the absolute violation.
351  	 */
352  	SCIP_EXPORT
353  	SCIP_RETCODE SCIPcleanupRowprep2(
354  	   SCIP*                 scip,               /**< SCIP data structure */
355  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be cleaned */
356  	   SCIP_SOL*             sol,                /**< solution that we try to cut off, or NULL for LP solution */
357  	   SCIP_Real             maxcoefbound,       /**< bound on absolute value of largest coefficient */
358  	   SCIP_Bool*            success             /**< buffer to store whether cut cleanup was successful, or NULL if not of interest */
359  	   );
360  	
361  	/** Scales up a rowprep to increase coefficients/sides that are within epsilon to an integer value, if possible.
362  	 *
363  	 * Computes the minimal fractionality of all fractional coefficients and the side of the rowprep.
364  	 * If this fractionality is below epsilon, the rowprep is scaled up such that the fractionality exceeds epsilon,
365  	 * if this will not put any coefficient or side above SCIPhugeValue().
366  	 *
367  	 * This function does not relax the rowprep.
368  	 *
369  	 * `success` is set to TRUE if the resulting rowprep can be turned into a SCIP_ROW, that is,
370  	 * all coefs and the side is below SCIPinfinity() and fractionalities are above epsilon.
371  	 * If `success` is set to FALSE, then the rowprep will not have been modified.
372  	 *
373  	 * @return The applied scaling factor, if `success` is set to TRUE.
374  	 */
375  	SCIP_EXPORT
376  	SCIP_Real SCIPscaleupRowprep(
377  	   SCIP*                 scip,               /**< SCIP data structure */
378  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be cleaned */
379  	   SCIP_Real             minscaleup,         /**< minimal factor by which to scale up row, or <= 1.0 if to be ignored */
380  	   SCIP_Bool*            success             /**< buffer to store whether rowprep could be turned into SCIP_ROW without loss, or NULL if not of interest */
381  	   );
382  	
383  	/** scales a rowprep by given factor (after some rounding)
384  	 *
385  	 * @return Exponent of actually applied scaling factor, if written as \f$2^x\f$.
386  	 */
387  	SCIP_EXPORT
388  	int SCIPscaleRowprep(
389  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be scaled */
390  	   SCIP_Real             factor              /**< suggested scale factor */
391  	   );
392  	
393  	/** generates a SCIP_ROW from a rowprep, setting its origin to given constraint handler */
394  	SCIP_EXPORT
395  	SCIP_RETCODE SCIPgetRowprepRowConshdlr(
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_CONSHDLR*        conshdlr            /**< constraint handler */
400  	   );
401  	
402  	/** generates a SCIP_ROW from a rowprep, setting its origin to given constraint */
403  	SCIP_EXPORT
404  	SCIP_RETCODE SCIPgetRowprepRowCons(
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_CONS*            cons                /**< constraint */
409  	   );
410  	
411  	/** generates a SCIP_ROW from a rowprep, setting its origin to given separator */
412  	SCIP_EXPORT
413  	SCIP_RETCODE SCIPgetRowprepRowSepa(
414  	   SCIP*                 scip,               /**< SCIP data structure */
415  	   SCIP_ROW**            row,                /**< buffer to store pointer to new row */
416  	   SCIP_ROWPREP*         rowprep,            /**< rowprep to be turned into a row */
417  	   SCIP_SEPA*            sepa                /**< separator */
418  	   );
419  	
420  	/** @} */
421  	
422  	#ifdef __cplusplus
423  	}
424  	#endif
425  	
426  	#endif /* __SCIP_PUB_MISC_ROWPREP_H__ */
427