1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file cuts.h
17 * @ingroup PUBLICCOREAPI
18 * @brief methods for the aggregation rows
19 * @author Jakob Witzig
20 * @author Leona Gottwald
21 *
22 */
23
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25
26 #ifndef __SCIP_CUTS_H__
27 #define __SCIP_CUTS_H__
28
29 #include "scip/def.h"
30 #include "scip/struct_cuts.h"
31 #include "scip/type_cuts.h"
32 #include "scip/type_lp.h"
33 #include "scip/type_misc.h"
34 #include "scip/type_retcode.h"
35 #include "scip/type_scip.h"
36 #include "scip/type_sol.h"
37 #include "scip/type_var.h"
38
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42
43 /**@addtogroup PublicCutMethods
44 *
45 * @{
46 */
47
48 /** perform activity based coefficient tigthening on the given cut; returns TRUE if the cut was detected
49 * to be redundant due to acitvity bounds
50 */
51 SCIP_EXPORT
52 SCIP_Bool SCIPcutsTightenCoefficients(
53 SCIP* scip, /**< SCIP data structure */
54 SCIP_Bool cutislocal, /**< is the cut local? */
55 SCIP_Real* cutcoefs, /**< array of the non-zero coefficients in the cut */
56 SCIP_Real* cutrhs, /**< the right hand side of the cut */
57 int* cutinds, /**< array of the problem indices of variables with a non-zero coefficient in the cut */
58 int* cutnnz, /**< the number of non-zeros in the cut */
59 int* nchgcoefs /**< number of changed coefficients */
60 );
61
62 /** create an empty the aggregation row */
63 SCIP_EXPORT
64 SCIP_RETCODE SCIPaggrRowCreate(
65 SCIP* scip, /**< SCIP data structure */
66 SCIP_AGGRROW** aggrrow /**< pointer to return the aggregation row */
67 );
68
69 /** free a the aggregation row */
70 SCIP_EXPORT
71 void SCIPaggrRowFree(
72 SCIP* scip, /**< SCIP data structure */
73 SCIP_AGGRROW** aggrrow /**< pointer to the aggregation row that should be freed */
74 );
75
76 /** output aggregation row to file stream */
77 SCIP_EXPORT
78 void SCIPaggrRowPrint(
79 SCIP* scip, /**< SCIP data structure */
80 SCIP_AGGRROW* aggrrow, /**< pointer to return aggregation row */
81 FILE* file /**< output file (or NULL for standard output) */
82 );
83
84 /** copy the aggregation row */
85 SCIP_EXPORT
86 SCIP_RETCODE SCIPaggrRowCopy(
87 SCIP* scip, /**< SCIP data structure */
88 SCIP_AGGRROW** aggrrow, /**< pointer to return the aggregation row */
89 SCIP_AGGRROW* source /**< source the aggregation row */
90 );
91
92 /** add weighted row to the aggregation row */
93 SCIP_EXPORT
94 SCIP_RETCODE SCIPaggrRowAddRow(
95 SCIP* scip, /**< SCIP data structure */
96 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
97 SCIP_ROW* row, /**< row to add to the aggregation row */
98 SCIP_Real weight, /**< scale for adding given row to the aggregation row */
99 int sidetype /**< specify row side type (-1 = lhs, 0 = automatic, 1 = rhs) */
100 );
101
102 /** Removes a given variable @p var from position @p pos the aggregation row and updates the right-hand side according
103 * to sign of the coefficient, i.e., rhs -= coef * bound, where bound = lb if coef >= 0 and bound = ub, otherwise.
104 *
105 * @note: The choice of global or local bounds depend on the validity (global or local) of the aggregation row.
106 *
107 * @note: The list of non-zero indices will be updated by swapping the last non-zero index to @p pos.
108 */
109 SCIP_EXPORT
110 void SCIPaggrRowCancelVarWithBound(
111 SCIP* scip, /**< SCIP data structure */
112 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
113 SCIP_VAR* var, /**< variable that should be removed */
114 int pos, /**< position of the variable in the aggregation row */
115 SCIP_Bool* valid /**< pointer to return whether the aggregation row is still valid */
116 );
117
118 /** add the objective function with right-hand side @p rhs and scaled by @p scale to the aggregation row */
119 SCIP_EXPORT
120 SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(
121 SCIP* scip, /**< SCIP data structure */
122 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
123 SCIP_Real rhs, /**< right-hand side of the artificial row */
124 SCIP_Real scale /**< scalar */
125 );
126
127 /** add weighted constraint to the aggregation row */
128 SCIP_EXPORT
129 SCIP_RETCODE SCIPaggrRowAddCustomCons(
130 SCIP* scip, /**< SCIP data structure */
131 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
132 int* inds, /**< variable problem indices in constraint to add to the aggregation row */
133 SCIP_Real* vals, /**< values of constraint to add to the aggregation row */
134 int len, /**< length of constraint to add to the aggregation row */
135 SCIP_Real rhs, /**< right hand side of constraint to add to the aggregation row */
136 SCIP_Real weight, /**< (positive) scale for adding given constraint to the aggregation row */
137 int rank, /**< rank to use for given constraint */
138 SCIP_Bool local /**< is constraint only valid locally */
139 );
140
141 /** calculates the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
142 *
143 * @return the efficacy norm of the given aggregation row, which depends on the "separating/efficacynorm" parameter
144 */
145 SCIP_EXPORT
146 SCIP_Real SCIPaggrRowCalcEfficacyNorm(
147 SCIP* scip, /**< SCIP data structure */
148 SCIP_AGGRROW* aggrrow /**< the aggregation row */
149 );
150
151 /** clear all entries in the aggregation row but do not free the internal memory */
152 SCIP_EXPORT
153 void SCIPaggrRowClear(
154 SCIP_AGGRROW* aggrrow /**< the aggregation row */
155 );
156
157 /** aggregate rows using the given weights; the current content of the aggregation
158 * row, \p aggrrow, gets overwritten
159 */
160 SCIP_EXPORT
161 SCIP_RETCODE SCIPaggrRowSumRows(
162 SCIP* scip, /**< SCIP data structure */
163 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
164 SCIP_Real* weights, /**< row weights in row summation */
165 int* rowinds, /**< array to store indices of non-zero entries of the weights array, or NULL */
166 int nrowinds, /**< number of non-zero entries in weights array, -1 if rowinds is NULL */
167 SCIP_Bool sidetypebasis, /**< choose sidetypes of row (lhs/rhs) based on basis information? */
168 SCIP_Bool allowlocal, /**< should local rows be used? */
169 int negslack, /**< should negative slack variables be used? (0: no, 1: only for integral rows, 2: yes) */
170 int maxaggrlen, /**< maximal number of non-zeros in the aggregation row */
171 SCIP_Bool* valid /**< is the aggregation valid */
172 );
173
174 /** removes all (close enough to) zero entries in the aggregation row */
175 SCIP_EXPORT
176 void SCIPaggrRowRemoveZeros(
177 SCIP* scip, /**< SCIP datastructure */
178 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
179 SCIP_Bool useglbbounds, /**< consider global bound although the cut is local? */
180 SCIP_Bool* valid /**< pointer to return whether the aggregation row is still valid */
181 );
182
183 /** get array with lp positions of aggregated rows */
184 SCIP_EXPORT
185 int* SCIPaggrRowGetRowInds(
186 SCIP_AGGRROW* aggrrow /**< the aggregation row */
187 );
188
189 /** get array with weights of aggregated rows */
190 SCIP_EXPORT
191 SCIP_Real* SCIPaggrRowGetRowWeights(
192 SCIP_AGGRROW* aggrrow /**< the aggregation row */
193 );
194
195 /** checks whether a given row has been added to the aggregation row */
196 SCIP_EXPORT
197 SCIP_Bool SCIPaggrRowHasRowBeenAdded(
198 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
199 SCIP_ROW* row /**< row for which it is checked whether it has been added to the aggregation */
200 );
201
202 /** gets the min and max absolute value of the weights used to aggregate the rows;
203 * must not be called for empty aggregation rows
204 */
205 SCIP_EXPORT
206 void SCIPaggrRowGetAbsWeightRange(
207 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
208 SCIP_Real* minabsrowweight, /**< pointer to store smallest absolute value of weights used for aggregating rows */
209 SCIP_Real* maxabsrowweight /**< pointer to store largest absolute value of weights used for aggregating rows */
210 );
211
212 /** gets the array of corresponding variable problem indices for each non-zero in the aggregation row */
213 SCIP_EXPORT
214 int* SCIPaggrRowGetInds(
215 SCIP_AGGRROW* aggrrow
216 );
217
218 /** gets the number of non-zeros in the aggregation row */
219 SCIP_EXPORT
220 int SCIPaggrRowGetNNz(
221 SCIP_AGGRROW* aggrrow /**< the aggregation row */
222 );
223
224 /** gets the non-zero value for the given non-zero index */
225 static INLINE
SCIPaggrRowGetValue(SCIP_AGGRROW * aggrrow,int i)226 SCIP_Real SCIPaggrRowGetValue(
227 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
228 int i /**< non-zero index; must be between 0 and SCIPaggrRowGetNNz(aggrrow) - 1 */
229 )
230 {
231 SCIP_Real QUAD(val);
232
233 QUAD_ARRAY_LOAD(val, aggrrow->vals, aggrrow->inds[i]);
234
235 return QUAD_TO_DBL(val);
236 }
237
238 /** gets the non-zero value for the given problem index of a variable */
239 static INLINE
SCIPaggrRowGetProbvarValue(SCIP_AGGRROW * aggrrow,int probindex)240 SCIP_Real SCIPaggrRowGetProbvarValue(
241 SCIP_AGGRROW* aggrrow, /**< the aggregation row */
242 int probindex /**< problem index of variable; must be between 0 and SCIPgetNVars(scip) - 1 */
243 )
244 {
245 SCIP_Real QUAD(val);
246
247 QUAD_ARRAY_LOAD(val, aggrrow->vals, probindex);
248
249 return QUAD_TO_DBL(val);
250 }
251
252 /** gets the rank of the aggregation row */
253 SCIP_EXPORT
254 int SCIPaggrRowGetRank(
255 SCIP_AGGRROW* aggrrow /**< the aggregation row */
256 );
257
258 /** checks if the aggregation row is only valid locally */
259 SCIP_EXPORT
260 SCIP_Bool SCIPaggrRowIsLocal(
261 SCIP_AGGRROW* aggrrow /**< the aggregation row */
262 );
263
264 /** gets the right hand side of the aggregation row */
265 SCIP_EXPORT
266 SCIP_Real SCIPaggrRowGetRhs(
267 SCIP_AGGRROW* aggrrow /**< the aggregation row */
268 );
269
270 /** gets the number of row aggregations */
271 SCIP_EXPORT
272 int SCIPaggrRowGetNRows(
273 SCIP_AGGRROW* aggrrow /**< aggregation row */
274 );
275
276 /** perform a cut selection algorithm for the given array of cuts; the array is partitioned
277 * so that the selected cuts come first and the remaining ones are at the end of the array
278 */
279 SCIP_EXPORT
280 SCIP_RETCODE SCIPselectCuts(
281 SCIP* scip, /**< SCIP data structure */
282 SCIP_ROW** cuts, /**< array with cuts to perform selection algorithm */
283 SCIP_RANDNUMGEN* randnumgen, /**< random number generator for tie-breaking, or NULL */
284 SCIP_Real goodscorefac, /**< factor of best score among the given cuts to consider a cut good
285 * and filter with less strict settings of the maximum parallelism */
286 SCIP_Real badscorefac, /**< factor of best score among the given cuts to consider a cut bad
287 * and discard it regardless of its parallelism to other cuts */
288 SCIP_Real goodmaxparall, /**< maximum parallelism for good cuts */
289 SCIP_Real maxparall, /**< maximum parallelism for non-good cuts */
290 SCIP_Real dircutoffdistweight,/**< weight of directed cutoff distance in score calculation */
291 SCIP_Real efficacyweight, /**< weight of efficacy (shortest cutoff distance) in score calculation */
292 SCIP_Real objparalweight, /**< weight of objective parallelism in score calculation */
293 SCIP_Real intsupportweight, /**< weight of integral support in score calculation */
294 int ncuts, /**< number of cuts in given array */
295 int nforcedcuts, /**< number of forced cuts at start of given array */
296 int maxselectedcuts, /**< maximal number of cuts to select */
297 int* nselectedcuts /**< pointer to return number of selected cuts */
298 );
299
300 /** calculates an MIR cut out of the weighted sum of LP rows given by an aggregation row; the
301 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
302 * participate in an MIR cut.
303 *
304 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
305 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
306 *
307 * @pre This method can be called if @p scip is in one of the following stages:
308 * - \ref SCIP_STAGE_SOLVING
309 *
310 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
311 */
312 SCIP_EXPORT
313 SCIP_RETCODE SCIPcalcMIR(
314 SCIP* scip, /**< SCIP data structure */
315 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
316 SCIP_Bool postprocess, /**< apply a post-processing step to the resulting cut? */
317 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
318 SCIP_Bool usevbds, /**< should variable bounds be used in bound transformation? */
319 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
320 SCIP_Bool fixintegralrhs, /**< should complementation tried to be adjusted such that rhs gets fractional? */
321 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
322 * -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound;
323 * NULL for using closest bound for all variables */
324 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
325 * NULL for using closest bound for all variables */
326 SCIP_Real minfrac, /**< minimal fractionality of rhs to produce MIR cut for */
327 SCIP_Real maxfrac, /**< maximal fractionality of rhs to produce MIR cut for */
328 SCIP_Real scale, /**< additional scaling factor multiplied to the aggrrow; must be positive */
329 SCIP_AGGRROW* aggrrow, /**< the aggregation row to compute an MIR cut for */
330 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut */
331 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut */
332 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
333 int* cutnnz, /**< pointer to store the number of non-zeros in the cut */
334 SCIP_Real* cutefficacy, /**< pointer to store the efficacy of the cut, or NULL */
335 int* cutrank, /**< pointer to return rank of generated cut */
336 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
337 SCIP_Bool* success /**< pointer to store whether the returned coefficients are a valid MIR cut */
338 );
339
340 /** calculates an MIR cut out of the weighted sum of LP rows given by an aggregation row; the
341 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
342 * participate in an MIR cut. The function uses a cut generation heuristic which tries different scaling
343 * factors and complementations of the variables to improve the cut's efficacy.
344 * For further details we refer to:
345 *
346 * Marchand, H., & Wolsey, L. A. (2001). Aggregation and mixed integer rounding to solve MIPs.
347 * Operations research, 49(3), 363-371.
348 *
349 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
350 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
351 *
352 * @pre This method can be called if @p scip is in one of the following stages:
353 * - \ref SCIP_STAGE_SOLVING
354 *
355 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
356 */
357 SCIP_EXPORT
358 SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(
359 SCIP* scip, /**< SCIP data structure */
360 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
361 SCIP_Bool postprocess, /**< apply a post-processing step to the resulting cut? */
362 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
363 SCIP_Bool usevbds, /**< should variable bounds be used in bound transformation? */
364 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
365 int maxtestdelta, /**< maximum number of deltas to test */
366 int* boundsfortrans, /**< bounds that should be used for transformed variables: vlb_idx/vub_idx,
367 * -1 for global lb/ub, -2 for local lb/ub, or -3 for using closest bound;
368 * NULL for using closest bound for all variables */
369 SCIP_BOUNDTYPE* boundtypesfortrans, /**< type of bounds that should be used for transformed variables;
370 * NULL for using closest bound for all variables */
371 SCIP_Real minfrac, /**< minimal fractionality of rhs to produce MIR cut for */
372 SCIP_Real maxfrac, /**< maximal fractionality of rhs to produce MIR cut for */
373 SCIP_AGGRROW* aggrrow, /**< the aggregation row to compute MIR cut for */
374 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut */
375 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut */
376 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
377 int* cutnnz, /**< pointer to store the number of non-zeros in the cut */
378 SCIP_Real* cutefficacy, /**< pointer to store efficacy of best cut; only cuts that are strictly better than the value of
379 * this efficacy on input to this function are returned */
380 int* cutrank, /**< pointer to return rank of generated cut */
381 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
382 SCIP_Bool* success /**< pointer to store whether a valid and efficacious cut was returned */
383 );
384
385 /** calculates a lifted simple generalized flow cover cut out of the weighted sum of LP rows given by an aggregation row; the
386 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
387 * participate in an MIR cut.
388 * For further details we refer to:
389 *
390 * Gu, Z., Nemhauser, G. L., & Savelsbergh, M. W. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs.
391 * Mathematical Programming, 85(3), 439-467.
392 *
393 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
394 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
395 *
396 * @pre This method can be called if @p scip is in one of the following stages:
397 * - \ref SCIP_STAGE_SOLVING
398 *
399 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
400 */
401 SCIP_EXPORT
402 SCIP_RETCODE SCIPcalcFlowCover(
403 SCIP* scip, /**< SCIP data structure */
404 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
405 SCIP_Bool postprocess, /**< apply a post-processing step to the resulting cut? */
406 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
407 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
408 SCIP_AGGRROW* aggrrow, /**< the aggregation row to compute flow cover cut for */
409 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut */
410 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut */
411 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
412 int* cutnnz, /**< pointer to store the number of non-zeros in the cut */
413 SCIP_Real* cutefficacy, /**< pointer to store the efficacy of the cut, or NULL */
414 int* cutrank, /**< pointer to return rank of generated cut */
415 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
416 SCIP_Bool* success /**< pointer to store whether a valid cut was returned */
417 );
418
419 /** calculates a strong CG cut out of the weighted sum of LP rows given by an aggregation row; the
420 * aggregation row must not contain non-zero weights for modifiable rows, because these rows cannot
421 * participate in a strongcg cut
422 *
423 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
424 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
425 *
426 * @pre This method can be called if @p scip is in one of the following stages:
427 * - \ref SCIP_STAGE_SOLVING
428 *
429 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
430 */
431 SCIP_EXPORT
432 SCIP_RETCODE SCIPcalcStrongCG(
433 SCIP* scip, /**< SCIP data structure */
434 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
435 SCIP_Bool postprocess, /**< apply a post-processing step to the resulting cut? */
436 SCIP_Real boundswitch, /**< fraction of domain up to which lower bound is used in transformation */
437 SCIP_Bool usevbds, /**< should variable bounds be used in bound transformation? */
438 SCIP_Bool allowlocal, /**< should local information allowed to be used, resulting in a local cut? */
439 SCIP_Real minfrac, /**< minimal fractionality of rhs to produce strong CG cut for */
440 SCIP_Real maxfrac, /**< maximal fractionality of rhs to produce strong CG cut for */
441 SCIP_Real scale, /**< additional scaling factor multiplied to all rows */
442 SCIP_AGGRROW* aggrrow, /**< the aggregation row to compute a strong CG cut for */
443 SCIP_Real* cutcoefs, /**< array to store the non-zero coefficients in the cut */
444 SCIP_Real* cutrhs, /**< pointer to store the right hand side of the cut */
445 int* cutinds, /**< array to store the problem indices of variables with a non-zero coefficient in the cut */
446 int* cutnnz, /**< pointer to store the number of non-zeros in the cut */
447 SCIP_Real* cutefficacy, /**< pointer to store the efficacy of the cut, or NULL */
448 int* cutrank, /**< pointer to return rank of generated cut */
449 SCIP_Bool* cutislocal, /**< pointer to store whether the generated cut is only valid locally */
450 SCIP_Bool* success /**< pointer to store whether a valid cut was returned */
451 );
452
453 /** @} */
454
455 #ifdef __cplusplus
456 }
457 #endif
458
459 #endif
460