SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
sepa_aggregation.c
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-2024 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 sepa_aggregation.c
26 * @ingroup DEFPLUGINS_SEPA
27 * @brief flow cover and complemented mixed integer rounding cuts separator (Marchand's version)
28 * @author Leona Gottwald
29 * @author Kati Wolter
30 * @author Tobias Achterberg
31 *
32 * For an overview see:
33 *
34 * Marchand, H., & Wolsey, L. A. (2001).@n
35 * Aggregation and mixed integer rounding to solve MIPs.@n
36 * Operations research, 49(3), 363-371.
37 *
38 * Some remarks:
39 * - In general, continuous variables are less prefered than integer variables, since their cut
40 * coefficient is worse.
41 * - We seek for aggregations that project out continuous variables that are far away from their bound,
42 * since if it is at its bound then it doesn't contribute to the violation
43 * - These aggregations are also useful for the flowcover separation, so after building an aggregation
44 * we try to generate a MIR cut and a flowcover cut.
45 * - We only keep the best cut.
46 */
47
48/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49
51#include "scip/cuts.h"
52#include "scip/pub_lp.h"
53#include "scip/pub_message.h"
54#include "scip/pub_misc.h"
55#include "scip/pub_misc_sort.h"
56#include "scip/pub_sepa.h"
57#include "scip/pub_var.h"
58#include "scip/scip_branch.h"
59#include "scip/scip_cut.h"
60#include "scip/scip_general.h"
61#include "scip/scip_lp.h"
62#include "scip/scip_mem.h"
63#include "scip/scip_message.h"
64#include "scip/scip_numerics.h"
65#include "scip/scip_param.h"
66#include "scip/scip_prob.h"
67#include "scip/scip_sepa.h"
68#include "scip/scip_sol.h"
70#include "scip/scip_tree.h"
71#include "scip/scip_var.h"
73#include <string.h>
74
75
76#define SEPA_NAME "aggregation"
77#define SEPA_DESC "aggregation heuristic for complemented mixed integer rounding cuts and flowcover cuts"
78#define SEPA_PRIORITY -3000
79#define SEPA_FREQ 10
80#define SEPA_MAXBOUNDDIST 1.0
81#define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
82#define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
83
84#define DEFAULT_MAXROUNDS -1 /**< maximal number of cmir separation rounds per node (-1: unlimited) */
85#define DEFAULT_MAXROUNDSROOT -1 /**< maximal number of cmir separation rounds in the root node (-1: unlimited) */
86#define DEFAULT_MAXTRIES 200 /**< maximal number of rows to start aggregation with per separation round
87 * (-1: unlimited) */
88#define DEFAULT_MAXTRIESROOT -1 /**< maximal number of rows to start aggregation with per round in the root node
89 * (-1: unlimited) */
90#define DEFAULT_MAXFAILS 20 /**< maximal number of consecutive unsuccessful aggregation tries (-1: unlimited) */
91#define DEFAULT_MAXFAILSROOT 100 /**< maximal number of consecutive unsuccessful aggregation tries in the root node
92 * (-1: unlimited) */
93#define DEFAULT_MAXAGGRS 3 /**< maximal number of aggregations for each row per separation round */
94#define DEFAULT_MAXAGGRSROOT 6 /**< maximal number of aggregations for each row per round in the root node */
95#define DEFAULT_MAXSEPACUTS 100 /**< maximal number of cmir cuts separated per separation round */
96#define DEFAULT_MAXSEPACUTSROOT 500 /**< maximal number of cmir cuts separated per separation round in root node */
97#define DEFAULT_MAXSLACK 0.0 /**< maximal slack of rows to be used in aggregation */
98#define DEFAULT_MAXSLACKROOT 0.1 /**< maximal slack of rows to be used in aggregation in the root node */
99#define DEFAULT_DENSITYSCORE 1e-4 /**< weight of row density in the aggregation scoring of the rows */
100#define DEFAULT_SLACKSCORE 1e-3 /**< weight of slack in the aggregation scoring of the rows */
101#define DEFAULT_MAXAGGDENSITY 0.20 /**< maximal density of aggregated row */
102#define DEFAULT_MAXROWDENSITY 0.05 /**< maximal density of row to be used in aggregation */
103#define DEFAULT_DENSITYOFFSET 100 /**< additional number of variables allowed in row on top of density */
104#define DEFAULT_MAXROWFAC 1e+4 /**< maximal row aggregation factor */
105#define DEFAULT_MAXTESTDELTA -1 /**< maximal number of different deltas to try (-1: unlimited) */
106#define DEFAULT_AGGRTOL 1e-2 /**< aggregation heuristic: we try to delete continuous variables from the current
107 * aggregation, whose distance to its tightest bound is >= L - DEFAULT_AGGRTOL,
108 * where L is the largest of the distances between a continuous variable's value
109 * and its tightest bound in the current aggregation */
110#define DEFAULT_TRYNEGSCALING TRUE /**< should negative values also be tested in scaling? */
111#define DEFAULT_FIXINTEGRALRHS TRUE /**< should an additional variable be complemented if f0 = 0? */
112#define DEFAULT_DYNAMICCUTS TRUE /**< should generated cuts be removed from the LP if they are no longer tight? */
113
114#define BOUNDSWITCH 0.5
115#define POSTPROCESS TRUE
116#define USEVBDS TRUE
117#define MINFRAC 0.05
118#define MAXFRAC 0.999
119#define MAKECONTINTEGRAL FALSE
120#define IMPLINTSARECONT
121
122
123/*
124 * Data structures
125 */
126
127/** separator data */
128struct SCIP_SepaData
129{
130 SCIP_Real maxslack; /**< maximal slack of rows to be used in aggregation */
131 SCIP_Real maxslackroot; /**< maximal slack of rows to be used in aggregation in the root node */
132 SCIP_Real densityscore; /**< weight of row density in the aggregation scoring of the rows */
133 SCIP_Real slackscore; /**< weight of slack in the aggregation scoring of the rows */
134 SCIP_Real maxaggdensity; /**< maximal density of aggregated row */
135 SCIP_Real maxrowdensity; /**< maximal density of row to be used in aggregation */
136 SCIP_Real maxrowfac; /**< maximal row aggregation factor */
137 SCIP_Real aggrtol; /**< tolerance for bound distance used in aggregation heuristic */
138 int maxrounds; /**< maximal number of cmir separation rounds per node (-1: unlimited) */
139 int maxroundsroot; /**< maximal number of cmir separation rounds in the root node (-1: unlimited) */
140 int maxtries; /**< maximal number of rows to start aggregation with per separation round
141 * (-1: unlimited) */
142 int maxtriesroot; /**< maximal number of rows to start aggregation with per round in the root node
143 * (-1: unlimited) */
144 int maxfails; /**< maximal number of consecutive unsuccessful aggregation tries
145 * (-1: unlimited) */
146 int maxfailsroot; /**< maximal number of consecutive unsuccessful aggregation tries in the root
147 * node (-1: unlimited) */
148 int maxaggrs; /**< maximal number of aggregations for each row per separation round */
149 int maxaggrsroot; /**< maximal number of aggregations for each row per round in the root node */
150 int maxsepacuts; /**< maximal number of cmir cuts separated per separation round */
151 int maxsepacutsroot; /**< maximal number of cmir cuts separated per separation round in root node */
152 int densityoffset; /**< additional number of variables allowed in row on top of density */
153 int maxtestdelta; /**< maximal number of different deltas to try (-1: unlimited) */
154 SCIP_Bool trynegscaling; /**< should negative values also be tested in scaling? */
155 SCIP_Bool fixintegralrhs; /**< should an additional variable be complemented if f0 = 0? */
156 SCIP_Bool dynamiccuts; /**< should generated cuts be removed from the LP if they are no longer tight? */
157 SCIP_Bool sepflowcover; /**< whether flowcover cuts should be separated in the current call */
158 SCIP_Bool sepknapsackcover; /**< whether knapsack cover cuts should be separated in the current call */
159 SCIP_Bool sepcmir; /**< whether cMIR cuts should be separated in the current call */
160 SCIP_SEPA* cmir; /**< separator for adding cmir cuts */
161 SCIP_SEPA* flowcover; /**< separator for adding flowcover cuts */
162 SCIP_SEPA* knapsackcover; /**< separator for adding knapsack cover cuts */
163};
164
165/** data used for aggregation of row */
166typedef
167struct AggregationData {
168 SCIP_Real* bounddist; /**< bound distance of continuous variables */
169 int* bounddistinds; /**< problem indices of the continUous variables corresponding to the bounddistance value */
170 int nbounddistvars; /**< number of continuous variables that are not at their bounds */
171 SCIP_ROW** aggrrows; /**< array of rows suitable for substitution of continuous variable */
172 SCIP_Real* aggrrowscoef; /**< coefficient of continuous variable in row that is suitable for substitution of that variable */
173 int aggrrowssize; /**< size of aggrrows array */
174 int naggrrows; /**< occupied positions in aggrrows array */
175 int* aggrrowsstart; /**< array with start positions of suitable rows for substitution for each
176 * continuous variable with non-zero bound distance */
177 int* ngoodaggrrows; /**< array with number of rows suitable for substitution that only contain
178 * one continuous variable that is not at it's bound */
179 int* nbadvarsinrow; /**< number of continuous variables that are not at their bounds for each row */
180 SCIP_AGGRROW* aggrrow; /**< store aggregation row here so that it can be reused */
182
183/*
184 * Local methods
185 */
186
187/** adds given cut to LP if violated */
188static
190 SCIP* scip, /**< SCIP data structure */
191 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
192 SCIP_SEPA* sepa, /**< separator */
193 SCIP_Bool makeintegral, /**< should cut be scaled to integral coefficients if possible? */
194 SCIP_Real* cutcoefs, /**< coefficients of active variables in cut */
195 int* cutinds, /**< problem indices of variables in cut */
196 int cutnnz, /**< number of non-zeros in cut */
197 SCIP_Real cutrhs, /**< right hand side of cut */
198 SCIP_Real cutefficacy, /**< efficacy of cut */
199 SCIP_Bool cutislocal, /**< is the cut only locally valid? */
200 SCIP_Bool cutremovable, /**< should the cut be removed from the LP due to aging or cleanup? */
201 int cutrank, /**< rank of the cut */
202 const char* cutclassname, /**< name of cut class to use for row names */
203 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
204 int* ncuts, /**< pointer to count the number of added cuts */
205 SCIP_ROW** thecut /**< pointer to return cut if it was added */
206 )
207{
208 assert(scip != NULL);
209 assert(cutcoefs != NULL);
210 assert(cutoff != NULL);
211 assert(ncuts != NULL);
212
213 *cutoff = FALSE;
214
215 if( cutnnz > 0 && SCIPisEfficacious(scip, cutefficacy) )
216 {
217 SCIP_VAR** vars;
218 int i;
219 SCIP_ROW* cut;
220 char cutname[SCIP_MAXSTRLEN];
221 SCIP_Bool success;
222
223 /* get active problem variables */
225
226 /* create cut name */
227 (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "%s%" SCIP_LONGINT_FORMAT "_%d", cutclassname, SCIPgetNLPs(scip), *ncuts);
228
229tryagain:
230 SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, cutremovable) );
231
233
234 for( i = 0; i < cutnnz; ++i )
235 {
236 SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[i]], cutcoefs[i]) );
237 }
238
239 /* set cut rank */
240 SCIProwChgRank(cut, cutrank);
241
242 SCIPdebugMsg(scip, " -> found potential %s cut <%s>: rhs=%f, eff=%f\n", cutclassname, cutname, cutrhs, cutefficacy);
244
245 /* if requested, try to scale the cut to integral values but only if the scaling is small; otherwise keep the fractional cut */
246 if( makeintegral && SCIPgetRowNumIntCols(scip, cut) == SCIProwGetNNonz(cut) )
247 {
249 1000LL, 1000.0, MAKECONTINTEGRAL, &success) );
250
252 {
253 /* release the row */
254 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
255
256 /* the scaling destroyed the cut, so try to add it again, but this time do not scale it */
257 makeintegral = FALSE;
258 goto tryagain;
259 }
260 }
261 else
262 {
263 success = FALSE;
264 }
265
266 if( success && !SCIPisCutEfficacious(scip, sol, cut) )
267 {
268 SCIPdebugMsg(scip, " -> %s cut <%s> no longer efficacious: rhs=%f, eff=%f\n", cutclassname, cutname, cutrhs, cutefficacy);
270
271 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
272
273 /* the cut is not efficacious anymore due to the scaling, so do not add it */
274 return SCIP_OKAY;
275 }
276
277 SCIPdebugMsg(scip, " -> found %s cut <%s>: rhs=%f, eff=%f, rank=%d, min=%f, max=%f (range=%g)\n",
278 cutclassname, cutname, cutrhs, cutefficacy, SCIProwGetRank(cut),
282
284
285 if( SCIPisCutNew(scip, cut) )
286 {
287 (*ncuts)++;
288
289 if( !cutislocal )
290 {
292 }
293 else
294 {
296 }
297
298 *thecut = cut;
299 }
300 else
301 {
302 /* release the row */
303 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
304 }
305 }
306
307 return SCIP_OKAY;
308}
309
310/** setup data for aggregating rows */
311static
313 SCIP* scip, /**< SCIP data structure */
314 SCIP_SOL* sol, /**< solution to separate, NULL for LP solution */
315 SCIP_Bool allowlocal, /**< should local cuts be allowed */
316 AGGREGATIONDATA* aggrdata /**< pointer to aggregation data to setup */
317 )
318{
319 SCIP_VAR** vars;
320 int nvars;
321 int nbinvars;
322 int nintvars;
323 int ncontvars;
324 int firstcontvar;
325 int nimplvars;
326 SCIP_ROW** rows;
327 int nrows;
328 int i;
329
330 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) );
331 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
332
333 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->bounddist, ncontvars + nimplvars) );
334 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->bounddistinds, ncontvars + nimplvars) );
335 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->ngoodaggrrows, ncontvars + nimplvars) );
336 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->aggrrowsstart, ncontvars + nimplvars + 1) );
337 SCIP_CALL( SCIPallocBufferArray(scip, &aggrdata->nbadvarsinrow, nrows) );
338 SCIP_CALL( SCIPaggrRowCreate(scip, &aggrdata->aggrrow) );
339 assert( aggrdata->aggrrow != NULL );
340 BMSclearMemoryArray(aggrdata->nbadvarsinrow, nrows);
341
342 aggrdata->nbounddistvars = 0;
343 aggrdata->aggrrows = NULL;
344 aggrdata->aggrrowscoef = NULL;
345 aggrdata->aggrrowssize = 0;
346 aggrdata->naggrrows = 0;
347
348 firstcontvar = nvars - ncontvars;
349
350 for( i = nbinvars + nintvars; i < nvars; ++i )
351 {
352 SCIP_Real bounddist;
353 SCIP_Real primsol;
354 SCIP_Real distlb;
355 SCIP_Real distub;
356 SCIP_Real bestlb;
357 SCIP_Real bestub;
358 SCIP_Real bestvlb;
359 SCIP_Real bestvub;
360 int bestvlbidx;
361 int bestvubidx;
362
363 /* compute the bound distance of the variable */
364 if( allowlocal )
365 {
366 bestlb = SCIPvarGetLbLocal(vars[i]);
367 bestub = SCIPvarGetUbLocal(vars[i]);
368 }
369 else
370 {
371 bestlb = SCIPvarGetLbGlobal(vars[i]);
372 bestub = SCIPvarGetUbGlobal(vars[i]);
373 }
374
375 SCIP_CALL( SCIPgetVarClosestVlb(scip, vars[i], sol, &bestvlb, &bestvlbidx) );
376 SCIP_CALL( SCIPgetVarClosestVub(scip, vars[i], sol, &bestvub, &bestvubidx) );
377 if( bestvlbidx >= 0 )
378 bestlb = MAX(bestlb, bestvlb);
379 if( bestvubidx >= 0 )
380 bestub = MIN(bestub, bestvub);
381
383 distlb = primsol - bestlb;
384 distub = bestub - primsol;
385
386 bounddist = MIN(distlb, distub);
387 bounddist = MAX(bounddist, 0.0);
388
389 /* prefer continuous variables over implicit integers to be aggregated out */
390 if( i < firstcontvar )
391 bounddist *= 0.1;
392
393 /* when variable is not at its bound, we want to project it out, so add it to the aggregation data */
394 if( !SCIPisZero(scip, bounddist) )
395 {
396 int k = aggrdata->nbounddistvars++;
397
398 aggrdata->bounddist[k] = bounddist;
399 aggrdata->bounddistinds[k] = i;
400 aggrdata->aggrrowsstart[k] = aggrdata->naggrrows;
401
402 /* the current variable is a bad variable (continuous, not at its bound): increase the number of bad variable
403 * count on each row this variables appears in; also each of these rows can be used to project the variable out
404 * so store them.
405 */
406 if( SCIPvarIsInLP(vars[i]) )
407 {
408 SCIP_COL* col = SCIPvarGetCol(vars[i]);
409 SCIP_ROW** colrows = SCIPcolGetRows(col);
410 SCIP_Real* colrowvals = SCIPcolGetVals(col);
411 int ncolnonzeros = SCIPcolGetNLPNonz(col);
412 int aggrrowsminsize = aggrdata->naggrrows + ncolnonzeros;
413
414 if( aggrrowsminsize > aggrdata->aggrrowssize )
415 {
416 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrdata->aggrrows, aggrrowsminsize) );
417 SCIP_CALL( SCIPreallocBufferArray(scip, &aggrdata->aggrrowscoef, aggrrowsminsize) );
418 aggrdata->aggrrowssize = aggrrowsminsize;
419 }
420 assert(aggrdata->aggrrows != NULL || aggrdata->aggrrowssize == 0);
421 assert(aggrdata->aggrrowscoef != NULL || aggrdata->aggrrowssize == 0);
422 assert(aggrdata->aggrrowssize > 0 || ncolnonzeros == 0);
423
424 for( k = 0; k < ncolnonzeros; ++k )
425 {
426 /* ignore modifiable rows and local rows if those are not permitted */
427 if( SCIProwIsModifiable(colrows[k]) || (!allowlocal && SCIProwIsLocal(colrows[k])) )
428 continue;
429
430 ++aggrdata->nbadvarsinrow[SCIProwGetLPPos(colrows[k])];
431 assert(aggrdata->aggrrows != NULL); /* for lint */
432 assert(aggrdata->aggrrowscoef != NULL);
433 /* coverity[var_deref_op] */
434 aggrdata->aggrrows[aggrdata->naggrrows] = colrows[k];
435 aggrdata->aggrrowscoef[aggrdata->naggrrows] = colrowvals[k];
436 ++aggrdata->naggrrows;
437 }
438 }
439 }
440 }
441
442 /* add sentinel entry at the end */
443 aggrdata->aggrrowsstart[aggrdata->nbounddistvars] = aggrdata->naggrrows;
444
445 /* for each continous variable that is not at its bounds check if there is a
446 * row where it is the only such variable ("good" rows). In the array with the rows that are
447 * suitable for substituting this variable move the good rows to the beginning
448 * and store the number of good rows for each of the variables.
449 * If a variable has at least one good row, then it is a "better" variable and we make
450 * the value of the bounddistance for this variable negative, to mark it.
451 * Note that better variables are continous variables that are not at their bounds
452 * and can be projected out without introducing bad variables (by using a good row).
453 */
454 {
455 int beg;
456
457 beg = aggrdata->aggrrowsstart[0];
458 for( i = 0; i < aggrdata->nbounddistvars; ++i )
459 {
460 int k;
461 int ngoodrows;
462 int end;
463
464 end = aggrdata->aggrrowsstart[i + 1];
465 ngoodrows = 0;
466 for( k = beg; k < end; ++k )
467 {
468 /* coverity[var_deref_op] */
469 int lppos = SCIProwGetLPPos(aggrdata->aggrrows[k]);
470
471 if( aggrdata->nbadvarsinrow[lppos] == 1 &&
472 SCIPisEQ(scip, SCIProwGetLhs(aggrdata->aggrrows[k]), SCIProwGetRhs(aggrdata->aggrrows[k])) )
473 {
474 int nextgoodrowpos = beg + ngoodrows;
475 if( k > nextgoodrowpos )
476 {
477 SCIPswapPointers((void**) (&aggrdata->aggrrows[k]), (void**) (&aggrdata->aggrrows[nextgoodrowpos]));
478 SCIPswapReals(&aggrdata->aggrrowscoef[k], &aggrdata->aggrrowscoef[nextgoodrowpos]);
479 }
480 ++ngoodrows;
481 }
482 }
483 if( ngoodrows > 0 )
484 {
485 aggrdata->bounddist[i] = -aggrdata->bounddist[i];
486 }
487 aggrdata->ngoodaggrrows[i] = ngoodrows;
488 beg = end;
489 }
490 }
491
492 return SCIP_OKAY;
493}
494
495/** free resources held in aggregation data */
496static
498 SCIP* scip, /**< SCIP datastructure */
499 AGGREGATIONDATA* aggrdata /**< pointer to ggregation data */
500 )
501{
502 SCIPaggrRowFree(scip, &aggrdata->aggrrow);
510}
511
512/** retrieves the candidate rows for canceling out the given variable, also returns the number of "good" rows which are the
513 * rows stored at the first ngoodrows positions. A row is good if its continuous variables are all at their bounds, except
514 * maybe the given continuous variable (in probvaridx)
515 */
516static
518 AGGREGATIONDATA* aggrdata, /**< pointer to ggregation data */
519 int probvaridx, /**< problem index of variables to retrieve candidates for */
520 SCIP_ROW*** rows, /**< pointer to store array to candidate rows */
521 SCIP_Real** rowvarcoefs, /**< pointer to store array of coefficients of given variable in the corresponding rows */
522 int* nrows, /**< pointer to return number of rows in returned arrays */
523 int* ngoodrows /**< pointer to return number of "good" rows in the returned arrays */
524 )
525{
526 int aggrdataidx;
527
528 if( !SCIPsortedvecFindInt(aggrdata->bounddistinds, probvaridx, aggrdata->nbounddistvars, &aggrdataidx) )
529 return FALSE;
530
531 *rows = aggrdata->aggrrows + aggrdata->aggrrowsstart[aggrdataidx];
532 *nrows = aggrdata->aggrrowsstart[aggrdataidx + 1] - aggrdata->aggrrowsstart[aggrdataidx];
533 *rowvarcoefs = aggrdata->aggrrowscoef + aggrdata->aggrrowsstart[aggrdataidx];
534 *ngoodrows = aggrdata->ngoodaggrrows[aggrdataidx];
535
536 return TRUE;
537}
538
539/** find the bound distance value in the aggregation data struct for the given variable problem index */
540static
542 AGGREGATIONDATA* aggrdata, /**< SCIP datastructure */
543 int probvaridx /**< problem index of variables to retrieve candidates for */
544 )
545{
546 int aggrdataidx;
547
548 if( !SCIPsortedvecFindInt(aggrdata->bounddistinds, probvaridx, aggrdata->nbounddistvars, &aggrdataidx) )
549 return 0.0;
550
551 return aggrdata->bounddist[aggrdataidx];
552}
553
554/** Aggregates the next row suitable for cancelling out an active continuous variable.
555 *
556 * Equality rows that contain no other active continuous variables are preffered and apart from that
557 * the scores for the rows are used to determine which row is aggregated next
558 */
559static
561 SCIP* scip, /**< SCIP data structure */
562 SCIP_SEPADATA* sepadata, /**< separator data */
563 SCIP_Real* rowlhsscores, /**< aggregation scores for left hand sides of row */
564 SCIP_Real* rowrhsscores, /**< aggregation scores for right hand sides of row */
565 AGGREGATIONDATA* aggrdata, /**< aggregation data */
566 SCIP_AGGRROW* aggrrow, /**< current aggregation row */
567 int* naggrs, /**< pointer to increase counter if real aggregation took place */
568 SCIP_Bool* success /**< pointer to return whether another row was added to the aggregation row */
569 )
570{
571 int i;
572 int firstcontvar;
573 int* badvarinds;
574 SCIP_Real* badvarbddist;
575 int nbadvars;
576 SCIP_Real minbddist;
577 SCIP_ROW* bestrow;
578 SCIP_Real bestrowscore;
579 SCIP_Real aggrfac;
580 int bestrowside;
581 int ncontvars;
582 int nnz = SCIPaggrRowGetNNz(aggrrow);
583 int* inds = SCIPaggrRowGetInds(aggrrow);
584
585 assert( success != NULL );
586 *success = FALSE;
587
588 firstcontvar = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip);
590 assert( firstcontvar + ncontvars == SCIPgetNVars(scip) );
591
592 SCIP_CALL( SCIPallocBufferArray(scip, &badvarinds, MIN(ncontvars, nnz)) );
593 SCIP_CALL( SCIPallocBufferArray(scip, &badvarbddist, MIN(ncontvars, nnz)) );
594
595 nbadvars = 0;
596
597 for( i = 0; i < nnz; ++i )
598 {
599 SCIP_Real bounddist;
600
601 /* only consider continuous variables */
602 if( inds[i] < firstcontvar )
603 continue;
604
605 bounddist = aggrdataGetBoundDist(aggrdata, inds[i]);
606
607 if( bounddist == 0.0 )
608 continue;
609
610 badvarinds[nbadvars] = inds[i];
611 badvarbddist[nbadvars] = bounddist;
612 ++nbadvars;
613 }
614
615 if( nbadvars == 0 )
616 goto TERMINATE;
617
618 SCIPsortDownRealInt(badvarbddist, badvarinds, nbadvars);
619
620 aggrfac = 0.0;
621 bestrowscore = 0.0;
622 bestrowside = 0;
623 minbddist = 0.0;
624 bestrow = NULL;
625
626 /* because the "good" bad variables have a negative bound distance, they are at the end */
627 for( i = nbadvars - 1; i >= 0; --i )
628 {
629 int probvaridx;
630 SCIP_ROW** candrows;
631 SCIP_Real* candrowcoefs;
632 int nrows;
633 int ngoodrows;
634 int k;
635
636 /* if the bound distance is not negative, there are no more good variables so stop */
637 if( badvarbddist[i] > 0.0 )
638 break;
639
640 /* if no best row was found yet, this variable has the currently best bound distance */
641 if( aggrfac == 0.0 )
642 minbddist = -badvarbddist[i] * (1.0 - sepadata->aggrtol);
643
644 /* if the bound distance of the current variable is smaller than the minimum bound distance stop looping */
645 if( -badvarbddist[i] < minbddist )
646 break;
647
648 probvaridx = badvarinds[i];
649
650 if( !getRowAggregationCandidates(aggrdata, probvaridx, &candrows, &candrowcoefs, &nrows, &ngoodrows) )
651 return SCIP_ERROR;
652
653 assert(ngoodrows > 0); /* bounddistance was negative for this variable, so it should have good rows */
654 assert(ngoodrows <= nrows);
655
656 for( k = 0; k < ngoodrows; ++k )
657 {
658 SCIP_Real rowaggrfac;
659 SCIP_Real rowscore;
660 int lppos;
661
662 /* do not add rows twice */
663 if( SCIPaggrRowHasRowBeenAdded(aggrrow, candrows[k]) )
664 continue;
665
666 rowaggrfac = - SCIPaggrRowGetProbvarValue(aggrrow, probvaridx) / candrowcoefs[k];
667
668 /* if factor is too extreme skip this row */
669 if( SCIPisFeasZero(scip, rowaggrfac) || REALABS(rowaggrfac) > sepadata->maxrowfac )
670 continue;
671
672 lppos = SCIProwGetLPPos(candrows[k]);
673
674 /* row could be used and good rows are equalities, so ignore sidetype */
675 rowscore = MAX(rowlhsscores[lppos], rowrhsscores[lppos]);
676
677 /* if this rows score is better than the currently best score, remember it */
678 if( aggrfac == 0.0 || rowscore > bestrowscore )
679 {
680 bestrow = candrows[k];
681 aggrfac = rowaggrfac;
682 bestrowscore = rowscore;
683 bestrowside = 0;
684 }
685 }
686 }
687
688 /* found a row among the good rows, so aggregate it and stop */
689 if( aggrfac != 0.0 )
690 {
691 ++(*naggrs);
692 SCIP_CALL( SCIPaggrRowAddRow(scip, aggrrow, bestrow, aggrfac, bestrowside) );
693 SCIPaggrRowRemoveZeros(scip, aggrrow, FALSE, success);
694 goto TERMINATE;
695 }
696
697 for( i = 0; i < nbadvars; ++i )
698 {
699 int probvaridx;
700 SCIP_ROW** candrows;
701 SCIP_Real* candrowcoefs;
702 int nrows;
703 int ngoodrows;
704 int k;
705
706 /* if the bound distance is negative, there are no more variables to be tested, so stop */
707 if( badvarbddist[i] < 0.0 )
708 break;
709
710 /* if no best row was found yet, this variable has the currently best bound distance */
711 if( aggrfac == 0.0 )
712 minbddist = badvarbddist[i] * (1.0 - sepadata->aggrtol);
713
714 /* if the bound distance of the current variable is smaller than the minimum bound distance stop looping */
715 if( badvarbddist[i] < minbddist )
716 break;
717
718 probvaridx = badvarinds[i];
719
720 if( !getRowAggregationCandidates(aggrdata, probvaridx, &candrows, &candrowcoefs, &nrows, &ngoodrows) )
721 return SCIP_ERROR;
722
723 /* bounddistance was positive for this variable, so it should not have good rows */
724 assert(ngoodrows == 0);
725
726 for( k = 0; k < nrows; ++k )
727 {
728 SCIP_Real rowaggrfac;
729 SCIP_Real rowscore;
730 int rowside;
731 int lppos;
732
733 /* do not add rows twice */
734 if( SCIPaggrRowHasRowBeenAdded(aggrrow, candrows[k]) )
735 continue;
736
737 rowaggrfac = - SCIPaggrRowGetProbvarValue(aggrrow, probvaridx) / candrowcoefs[k];
738
739 /* if factor is too extreme skip this row */
740 if( SCIPisFeasZero(scip, rowaggrfac) || REALABS(rowaggrfac) > sepadata->maxrowfac )
741 continue;
742
743 /* row could be used, decide which side */
744 lppos = SCIProwGetLPPos(candrows[k]);
745
746 /* either both or none of the rowscores are 0.0 so use the one which gives a positive slack */
747 if( (rowaggrfac < 0.0 && !SCIPisInfinity(scip, -SCIProwGetLhs(candrows[k]))) || SCIPisInfinity(scip, SCIProwGetRhs(candrows[k])) )
748 {
749 rowscore = rowlhsscores[lppos];
750 rowside = -1;
751 }
752 else
753 {
754 rowscore = rowrhsscores[lppos];
755 rowside = 1;
756 }
757
758 /* if this rows score is better than the currently best score, remember it */
759 if( aggrfac == 0.0 || SCIPisGT(scip, rowscore, bestrowscore) ||
760 (SCIPisEQ(scip, rowscore, bestrowscore) && aggrdata->nbadvarsinrow[lppos] < aggrdata->nbadvarsinrow[SCIProwGetLPPos(bestrow)]) )
761 {
762 bestrow = candrows[k];
763 aggrfac = rowaggrfac;
764 bestrowscore = rowscore;
765 bestrowside = rowside;
766 }
767 }
768 }
769
770 /* found a row so aggregate it */
771 if( aggrfac != 0.0 )
772 {
773 ++(*naggrs);
774 SCIP_CALL( SCIPaggrRowAddRow(scip, aggrrow, bestrow, aggrfac, bestrowside) );
775 SCIPaggrRowRemoveZeros(scip, aggrrow, FALSE, success);
776 }
777
778TERMINATE:
779 SCIPfreeBufferArray(scip, &badvarbddist);
780 SCIPfreeBufferArray(scip, &badvarinds);
781
782 return SCIP_OKAY;
783}
784
785/** aggregates different single mixed integer constraints by taking linear combinations of the rows of the LP */
786static
788 SCIP* scip, /**< SCIP data structure */
789 AGGREGATIONDATA* aggrdata, /**< pointer to aggregation data */
790 SCIP_SEPA* sepa, /**< separator */
791 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
792 SCIP_Bool allowlocal, /**< should local cuts be allowed */
793 SCIP_Real* rowlhsscores, /**< aggregation scores for left hand sides of row */
794 SCIP_Real* rowrhsscores, /**< aggregation scores for right hand sides of row */
795 int startrow, /**< index of row to start aggregation; -1 for using the objective cutoff constraint */
796 int maxaggrs, /**< maximal number of aggregations */
797 SCIP_Bool* wastried, /**< pointer to store whether the given startrow was actually tried */
798 SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
799 int* cutinds, /**< buffer array to store temporarily cut */
800 SCIP_Real* cutcoefs, /**< buffer array to store temporarily cut */
801 SCIP_Bool negate, /**< should the start row be multiplied by -1 */
802 int* ncuts /**< pointer to count the number of generated cuts */
803 )
804{
806 SCIP_ROW** rows;
807
808 SCIP_Real startweight;
809 SCIP_Real startrowact;
810 int maxaggrnonzs;
811 int naggrs;
812 int nrows;
813 int maxtestdelta;
814
815 assert(scip != NULL);
816 assert(aggrdata != NULL);
817 assert(aggrdata->aggrrow != NULL);
818 assert(sepa != NULL);
819 assert(rowlhsscores != NULL);
820 assert(rowrhsscores != NULL);
821 assert(wastried != NULL);
822 assert(cutoff != NULL);
823 assert(ncuts != NULL);
824
826 assert(sepadata != NULL);
827
828 *cutoff = FALSE;
829 *wastried = FALSE;
830
831 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
832 assert(nrows == 0 || rows != NULL);
833
834 maxtestdelta = sepadata->maxtestdelta == -1 ? INT_MAX : sepadata->maxtestdelta;
835
836 /* calculate maximal number of non-zeros in aggregated row */
837 maxaggrnonzs = (int)(sepadata->maxaggdensity * SCIPgetNLPCols(scip)) + sepadata->densityoffset;
838
839 /* add start row to the initially empty aggregation row (aggrrow) */
840 if( startrow < 0 )
841 {
842 SCIP_Real rhs;
843
844 /* if the objective is integral we round the right hand side of the cutoff constraint.
845 * Therefore the constraint may not be valid for the problem but it is valid for the set
846 * of all improving solutions. We refrain from adding an epsilon cutoff for the case
847 * of a non-integral objective function to avoid cutting of any improving solution even
848 * if the improvement is below some epsilon value.
849 */
851 rhs = floor(SCIPgetUpperbound(scip) - 0.5);
852 else
853 rhs = SCIPgetUpperbound(scip);
854
855 SCIP_CALL( SCIPaggrRowAddObjectiveFunction(scip, aggrdata->aggrrow, rhs, 1.0) );
856
857 if( SCIPaggrRowGetNNz(aggrdata->aggrrow) == 0 )
858 {
859 SCIPaggrRowClear(aggrdata->aggrrow);
860 return SCIP_OKAY;
861 }
862 }
863 else
864 {
865 assert(0 <= startrow && startrow < nrows);
866
867 SCIPdebugMsg(scip, "start c-MIR aggregation with row <%s> (%d/%d)\n", SCIProwGetName(rows[startrow]), startrow, nrows);
868
869 startrowact = SCIPgetRowSolActivity(scip, rows[startrow], sol);
870
871 if( startrowact <= 0.5 * SCIProwGetLhs(rows[startrow]) + 0.5 * SCIProwGetRhs(rows[startrow]) )
872 startweight = -1.0;
873 else
874 startweight = 1.0;
875
876 SCIP_CALL( SCIPaggrRowAddRow(scip, aggrdata->aggrrow, rows[startrow], negate ? -startweight : startweight, 0) ); /*lint !e644*/
877 }
878
879 /* try to generate cut from the current aggregated row; add cut if found, otherwise add another row to aggrrow
880 * in order to get rid of a continuous variable
881 */
882 naggrs = 0;
883 while( naggrs <= maxaggrs )
884 {
885 int cutrank = 0;
886 int cutnnz = 0;
887 SCIP_Bool aggrsuccess;
888 SCIP_Bool cmirsuccess;
889 SCIP_Bool cmircutislocal = FALSE;
890 SCIP_Bool flowcoversuccess;
891 SCIP_Real flowcoverefficacy;
892 SCIP_Bool flowcovercutislocal = FALSE;
893 SCIP_Bool knapsackcoversuccess;
894 SCIP_Real knapsackcoverefficacy;
895 SCIP_Bool knapsackcovercutislocal = FALSE;
896 SCIP_ROW* cut = NULL;
897 SCIP_Real cutrhs = SCIP_INVALID;
898 SCIP_Real cutefficacy;
899
900 *wastried = TRUE;
901
902 /* Step 1:
903 * try to generate a MIR cut out of the current aggregated row
904 */
905
906 flowcoverefficacy = -SCIPinfinity(scip);
907
908 if( sepadata->sepflowcover )
909 {
910 SCIP_CALL( SCIPcalcFlowCover(scip, sol, POSTPROCESS, BOUNDSWITCH, allowlocal, aggrdata->aggrrow, /*lint !e644*/
911 cutcoefs, &cutrhs, cutinds, &cutnnz, &flowcoverefficacy, &cutrank, &flowcovercutislocal, &flowcoversuccess) );
912 }
913 else
914 {
915 flowcoversuccess = FALSE;
916 }
917
918 /* initialize the knapsack cover cut efficacy variable with the flowcover efficacy so that
919 * only knapsack cover cuts better than that efficacy are returned.
920 */
921 knapsackcoverefficacy = flowcoverefficacy;
922
923 if( sepadata->sepknapsackcover )
924 {
925 SCIP_CALL( SCIPcalcKnapsackCover(scip, sol, allowlocal, aggrdata->aggrrow, /*lint !e644*/
926 cutcoefs, &cutrhs, cutinds, &cutnnz, &knapsackcoverefficacy, &cutrank, &knapsackcovercutislocal, &knapsackcoversuccess) );
927 }
928 else
929 {
930 knapsackcoversuccess = FALSE;
931 }
932
933 /* initialize the cutefficacy variable with the knapsackcoverefficacy, so that only CMIR cuts
934 * that have a higher efficacy than that of a flowcover or knapsack cover cut possibly
935 * found in the call above are returned since the previous cut is overwritten in that case.
936 */
937 cutefficacy = knapsackcoverefficacy;
938
939 if( sepadata->sepcmir )
940 {
942 aggrdata->aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cmircutislocal, &cmirsuccess) );
943 }
944 else
945 {
946 cmirsuccess = FALSE;
947 }
948
949 if( cmirsuccess )
950 {
951 /* cppcheck-suppress uninitvar */
952 SCIP_CALL( addCut(scip, sol, sepadata->cmir, FALSE, cutcoefs, cutinds, cutnnz, cutrhs, cutefficacy,
953 cmircutislocal, sepadata->dynamiccuts, cutrank, startrow < 0 ? "objcmir" : "cmir", cutoff, ncuts, &cut) ); /*lint !e644*/
954 }
955 else if ( knapsackcoversuccess )
956 {
957 /* cppcheck-suppress uninitvar */
958 SCIP_CALL( addCut(scip, sol, sepadata->knapsackcover, FALSE, cutcoefs, cutinds, cutnnz, cutrhs, cutefficacy,
959 knapsackcovercutislocal, sepadata->dynamiccuts, cutrank, startrow < 0 ? "objlci" : "lci", cutoff, ncuts, &cut) ); /*lint !e644*/
960 }
961 else if ( flowcoversuccess )
962 {
963 /* cppcheck-suppress uninitvar */
964 SCIP_CALL( addCut(scip, sol, sepadata->flowcover, FALSE, cutcoefs, cutinds, cutnnz, cutrhs, cutefficacy,
965 flowcovercutislocal, sepadata->dynamiccuts, cutrank, startrow < 0 ? "objflowcover" : "flowcover", cutoff, ncuts, &cut) ); /*lint !e644*/
966 }
967
968 if ( *cutoff )
969 {
970 if( cut != NULL )
971 {
972 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
973 }
974 break;
975 }
976
977 /* if the cut was successfully added, decrease the score of the rows used in the aggregation and clean the aggregation
978 * row (and call this function again with a different start row for aggregation)
979 */
980 if( cut != NULL )
981 {
982 int* rowinds;
983 int i;
984
985 rowinds = SCIPaggrRowGetRowInds(aggrdata->aggrrow);
986 nrows = SCIPaggrRowGetNRows(aggrdata->aggrrow);
987
988 /* decrease row score of used rows slightly */
989 for( i = 0; i < nrows; ++i )
990 {
991 SCIP_Real fac = 1.0 - 0.999 * SCIProwGetParallelism(rows[rowinds[i]], cut, 'e');
992
993 rowlhsscores[rowinds[i]] *= fac;
994 rowrhsscores[rowinds[i]] *= fac;
995 }
996
997 SCIP_CALL( SCIPreleaseRow(scip, &cut) );
998
999 SCIPdebugMsg(scip, " -> abort aggregation: cut found\n");
1000 break;
1001 }
1002
1003 /* Step 2:
1004 * aggregate an additional row in order to remove a continuous variable
1005 */
1006
1007 /* abort, if we reached the maximal number of aggregations */
1008 if( naggrs == maxaggrs )
1009 {
1010 SCIPdebugMsg(scip, " -> abort aggregation: maximal number of aggregations reached\n");
1011 break;
1012 }
1013
1014 SCIP_CALL( aggregateNextRow(scip, sepadata, rowlhsscores, rowrhsscores, aggrdata, aggrdata->aggrrow,
1015 &naggrs, &aggrsuccess) );
1016
1017 /* no suitable aggregation was found or number of non-zeros is now too large so abort */
1018 if( ! aggrsuccess || SCIPaggrRowGetNNz(aggrdata->aggrrow) > maxaggrnonzs || SCIPaggrRowGetNNz(aggrdata->aggrrow) == 0 )
1019 {
1020 break;
1021 }
1022
1023 SCIPdebugMsg(scip, " -> current aggregation has %d/%d nonzeros and consists of %d/%d rows\n",
1024 SCIPaggrRowGetNNz(aggrdata->aggrrow), maxaggrnonzs, naggrs, maxaggrs);
1025 }
1026
1027 SCIPaggrRowClear(aggrdata->aggrrow);
1028
1029 return SCIP_OKAY;
1030}
1031
1032/** gives an estimate of how much the activity of this row is affected by fractionality in the current solution */
1033static
1035 SCIP_ROW* row, /**< the LP row */
1036 SCIP_Real* fractionalities /**< array of fractionalities for each variable */
1037 )
1038{
1039 int nlpnonz;
1040 int i;
1041 SCIP_COL** cols;
1042 SCIP_Real* vals;
1043 SCIP_Real fracsum = 0.0;
1044
1045 cols = SCIProwGetCols(row);
1046 vals = SCIProwGetVals(row);
1047 nlpnonz = SCIProwGetNLPNonz(row);
1048
1049 for( i = 0; i < nlpnonz; ++i )
1050 {
1051 SCIP_VAR* var = SCIPcolGetVar(cols[i]);
1052 fracsum += REALABS(vals[i] * fractionalities[SCIPvarGetProbindex(var)]);
1053 }
1054
1055 return fracsum;
1056}
1057
1058/** searches for and adds c-MIR cuts that separate the given primal solution */
1059static
1061 SCIP* scip, /**< SCIP data structure */
1062 SCIP_SEPA* sepa, /**< the c-MIR separator */
1063 SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
1064 SCIP_Bool allowlocal, /**< should local cuts be allowed */
1065 int depth, /**< current depth */
1066 SCIP_RESULT* result /**< pointer to store the result */
1067 )
1068{
1069 AGGREGATIONDATA aggrdata;
1071 SCIP_VAR** vars;
1072 SCIP_Real* varsolvals;
1073 SCIP_Real* bestcontlbs;
1074 SCIP_Real* bestcontubs;
1075 SCIP_Real* fractionalities;
1076 SCIP_ROW** rows;
1077 SCIP_Real* rowlhsscores;
1078 SCIP_Real* rowrhsscores;
1079 SCIP_Real* rowscores;
1080 int* roworder;
1081 SCIP_Real maxslack;
1082 SCIP_Bool cutoff = FALSE;
1083 SCIP_Bool wastried;
1084 int nvars;
1085 int nintvars;
1086 int ncontvars;
1087 int nrows;
1088 int nnonzrows;
1089 int ntries;
1090 int nfails;
1091 int ncalls;
1092 int maxtries;
1093 int maxfails;
1094 int maxaggrs;
1095 int maxsepacuts;
1096 int ncuts;
1097 int r;
1098 int v;
1099 int oldncuts;
1100
1101 int* cutinds;
1102 SCIP_Real* cutcoefs;
1103
1104 assert(result != NULL);
1106
1107 sepadata = SCIPsepaGetData(sepa);
1108 assert(sepadata != NULL);
1109
1111
1112 /* only call the cmir cut separator a given number of times at each node */
1113 if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
1114 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
1115 return SCIP_OKAY;
1116
1117 /* check which cuts should be separated */
1118 {
1119 int cmirfreq;
1120 int flowcoverfreq;
1121 int knapsackcoverfreq;
1122
1123 cmirfreq = SCIPsepaGetFreq(sepadata->cmir);
1124 flowcoverfreq = SCIPsepaGetFreq(sepadata->flowcover);
1125 knapsackcoverfreq = SCIPsepaGetFreq(sepadata->knapsackcover);
1126
1127 sepadata->sepcmir = cmirfreq > 0 ? (depth % cmirfreq) == 0 : cmirfreq == depth;
1128 sepadata->sepflowcover = flowcoverfreq > 0 ? (depth % flowcoverfreq) == 0 : flowcoverfreq == depth;
1129 sepadata->sepknapsackcover = knapsackcoverfreq > 0 ? (depth % knapsackcoverfreq) == 0 : knapsackcoverfreq == depth;
1130 }
1131
1132 if( ! sepadata->sepcmir && ! sepadata->sepflowcover && ! sepadata->sepknapsackcover )
1133 return SCIP_OKAY;
1134
1135 /* get all rows and number of columns */
1136 SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
1137 assert(nrows == 0 || rows != NULL);
1138
1139 /* nothing to do, if LP is empty */
1140 if( nrows == 0 )
1141 return SCIP_OKAY;
1142
1143 /* check whether SCIP was stopped in the meantime */
1144 if( SCIPisStopped(scip) )
1145 return SCIP_OKAY;
1146
1147 /* get active problem variables */
1150 ncontvars = SCIPgetNContVars(scip);
1151#ifdef IMPLINTSARECONT
1152 ncontvars += SCIPgetNImplVars(scip); /* also aggregate out implicit integers */
1153#endif
1154 nintvars = nvars - ncontvars;
1155 assert(nvars == 0 || vars != NULL);
1156
1157 /* nothing to do, if problem has no variables */
1158 if( nvars == 0 )
1159 return SCIP_OKAY;
1160
1161 SCIPdebugMsg(scip, "separating c-MIR cuts\n");
1162
1164
1165 /* get data structure */
1166 SCIP_CALL( SCIPallocBufferArray(scip, &rowlhsscores, nrows) );
1167 SCIP_CALL( SCIPallocBufferArray(scip, &rowrhsscores, nrows) );
1168 SCIP_CALL( SCIPallocBufferArray(scip, &roworder, nrows) );
1169 SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
1170 SCIP_CALL( SCIPallocBufferArray(scip, &bestcontlbs, ncontvars) );
1171 SCIP_CALL( SCIPallocBufferArray(scip, &bestcontubs, ncontvars) );
1172 SCIP_CALL( SCIPallocBufferArray(scip, &fractionalities, nvars) );
1174 SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
1175 SCIP_CALL( SCIPallocBufferArray(scip, &rowscores, nrows) );
1176
1177 /* get the solution values for all active variables */
1178 SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, varsolvals) );
1179
1180 /* calculate the fractionality of the integer variables in the current solution */
1181 for( v = 0; v < nintvars; ++v )
1182 {
1183 fractionalities[v] = SCIPfeasFrac(scip, varsolvals[v]);
1184 fractionalities[v] = MIN(fractionalities[v], 1.0 - fractionalities[v]);
1185 }
1186
1187 /* calculate the fractionality of the continuous variables in the current solution;
1188 * The fractionality of a continuous variable x is defined to be a * f_y,
1189 * if there is a variable bound x <= a * y + c where f_y is the fractionality of y
1190 * and in the current solution the variable bound has no slack.
1191 */
1192 for( ; v < nvars; ++v )
1193 {
1194 SCIP_VAR** vlbvars;
1195 SCIP_VAR** vubvars;
1196 SCIP_Real* vlbcoefs;
1197 SCIP_Real* vubcoefs;
1198 SCIP_Real closestvlb;
1199 SCIP_Real closestvub;
1200 int closestvlbidx;
1201 int closestvubidx;
1202
1203 SCIP_CALL( SCIPgetVarClosestVlb(scip, vars[v], sol, &closestvlb, &closestvlbidx) );
1204 SCIP_CALL( SCIPgetVarClosestVub(scip, vars[v], sol, &closestvub, &closestvubidx) );
1205
1206 vlbvars = SCIPvarGetVlbVars(vars[v]);
1207 vubvars = SCIPvarGetVubVars(vars[v]);
1208 vlbcoefs = SCIPvarGetVlbCoefs(vars[v]);
1209 vubcoefs = SCIPvarGetVubCoefs(vars[v]);
1210
1211 fractionalities[v] = 0.0;
1212 if( closestvlbidx != -1 && SCIPisEQ(scip, varsolvals[v], closestvlb) )
1213 {
1214 int vlbvarprobidx = SCIPvarGetProbindex(vlbvars[closestvlbidx]);
1215 SCIP_Real frac = SCIPfeasFrac(scip, varsolvals[vlbvarprobidx]);
1216
1217 if( frac < 0.0 )
1218 frac = 0.0;
1219 assert(frac >= 0.0 && frac < 1.0);
1220 frac = MIN(frac, 1.0 - frac) * vlbcoefs[closestvlbidx];
1221 fractionalities[v] += frac;
1222 }
1223
1224 if( closestvubidx != -1 && SCIPisEQ(scip, varsolvals[v], closestvub) )
1225 {
1226 int vubvarprobidx = SCIPvarGetProbindex(vubvars[closestvubidx]);
1227 SCIP_Real frac = SCIPfeasFrac(scip, varsolvals[vubvarprobidx]);
1228
1229 if( frac < 0.0 )
1230 frac = 0.0;
1231 assert(frac >= 0.0 && frac < 1.0);
1232 frac = MIN(frac, 1.0 - frac) * vubcoefs[closestvubidx];
1233 fractionalities[v] += frac;
1234 }
1235 }
1236
1237 /* get the maximal number of cuts allowed in a separation round */
1238 if( depth == 0 )
1239 {
1240 maxtries = sepadata->maxtriesroot;
1241 maxfails = sepadata->maxfailsroot;
1242 maxaggrs = sepadata->maxaggrsroot;
1243 maxsepacuts = sepadata->maxsepacutsroot;
1244 maxslack = sepadata->maxslackroot;
1245 }
1246 else
1247 {
1248 maxtries = sepadata->maxtries;
1249 maxfails = sepadata->maxfails;
1250 maxaggrs = sepadata->maxaggrs;
1251 maxsepacuts = sepadata->maxsepacuts;
1252 maxslack = sepadata->maxslack;
1253 }
1254
1255 /* calculate aggregation scores for both sides of all rows, and sort rows by decreasing maximal score
1256 * TODO: document score definition */
1257
1258 /* count the number of non-zero rows and zero rows. these values are used for the sorting of the rowscores.
1259 * only the non-zero rows need to be sorted. */
1260 nnonzrows = 0;
1261 for( r = 0; r < nrows; r++ )
1262 {
1263 int nnonz;
1264
1265 assert(SCIProwGetLPPos(rows[r]) == r);
1266
1267 nnonz = SCIProwGetNLPNonz(rows[r]);
1268 if( nnonz == 0 || SCIProwIsModifiable(rows[r]) || (!allowlocal && SCIProwIsLocal(rows[r])) )
1269 {
1270 /* ignore empty rows, modifiable rows, and local rows if they are not allowed */
1271 rowlhsscores[r] = 0.0;
1272 rowrhsscores[r] = 0.0;
1273 }
1274 else
1275 {
1276 SCIP_Real activity;
1277 SCIP_Real lhs;
1278 SCIP_Real rhs;
1279 SCIP_Real dualsol;
1280 SCIP_Real dualscore;
1281 SCIP_Real rowdensity;
1282 SCIP_Real rownorm;
1283 SCIP_Real slack;
1284 SCIP_Real fracact;
1285 SCIP_Real fracscore;
1286 SCIP_Real objnorm;
1287
1288 objnorm = SCIPgetObjNorm(scip);
1289 objnorm = MAX(objnorm, 1.0);
1290
1291 fracact = getRowFracActivity(rows[r], fractionalities);
1292 dualsol = (sol == NULL ? SCIProwGetDualsol(rows[r]) : 1.0);
1293 activity = SCIPgetRowSolActivity(scip, rows[r], sol);
1294 lhs = SCIProwGetLhs(rows[r]);
1295 rhs = SCIProwGetRhs(rows[r]);
1296 rownorm = SCIProwGetNorm(rows[r]);
1297 rownorm = MAX(rownorm, 0.1);
1298 rowdensity = (SCIP_Real)(nnonz - sepadata->densityoffset)/(SCIP_Real)nvars;
1299 assert(SCIPisPositive(scip, rownorm));
1300 fracscore = fracact / rownorm;
1301
1302 slack = (activity - lhs)/rownorm;
1303 dualscore = MAX(fracscore * dualsol/objnorm, 0.0001);
1304 if( !SCIPisInfinity(scip, -lhs) && SCIPisLE(scip, slack, maxslack)
1305 && rowdensity <= sepadata->maxrowdensity
1306 && rowdensity <= sepadata->maxaggdensity ) /*lint !e774*/
1307 {
1308 rowlhsscores[r] = dualscore + sepadata->densityscore * (1.0-rowdensity) + sepadata->slackscore * MAX(1.0 - slack, 0.0);
1309 assert(rowlhsscores[r] > 0.0);
1310 }
1311 else
1312 rowlhsscores[r] = 0.0;
1313
1314 slack = (rhs - activity)/rownorm;
1315 dualscore = MAX(-fracscore * dualsol/objnorm, 0.0001);
1316 if( !SCIPisInfinity(scip, rhs) && SCIPisLE(scip, slack, maxslack)
1317 && rowdensity <= sepadata->maxrowdensity
1318 && rowdensity <= sepadata->maxaggdensity ) /*lint !e774*/
1319 {
1320 rowrhsscores[r] = dualscore + sepadata->densityscore * (1.0-rowdensity) + sepadata->slackscore * MAX(1.0 - slack, 0.0);
1321 assert(rowrhsscores[r] > 0.0);
1322 }
1323 else
1324 rowrhsscores[r] = 0.0;
1325
1326 /* for the row order only use the fractionality score since it best indicates how likely it is to find a cut */
1327 if( fracscore != 0.0 )
1328 {
1329 roworder[nnonzrows] = r;
1330 rowscores[nnonzrows] = fracscore;
1331 ++nnonzrows;
1332 }
1333 }
1334
1335 SCIPdebugMsg(scip, " -> row %d <%s>: lhsscore=%g rhsscore=%g maxscore=%g\n", r, SCIProwGetName(rows[r]),
1336 rowlhsscores[r], rowrhsscores[r], rowscores[r]);
1337 }
1338 assert(nnonzrows <= nrows);
1339
1340 SCIPsortDownRealInt(rowscores, roworder, nnonzrows);
1341 SCIPfreeBufferArray(scip, &rowscores);
1342
1343 /* calculate the data required for performing the row aggregation */
1344 SCIP_CALL( setupAggregationData(scip, sol, allowlocal, &aggrdata) );
1345
1346 ncuts = 0;
1347 if( maxtries < 0 )
1348 maxtries = INT_MAX;
1349 if( maxfails < 0 )
1350 maxfails = INT_MAX;
1351 else if( depth == 0 && 2 * SCIPgetNSepaRounds(scip) < maxfails )
1352 maxfails += maxfails - 2 * SCIPgetNSepaRounds(scip); /* allow up to double as many fails in early separounds of root node */
1353
1354 /* start aggregation heuristic for each row in the LP and generate resulting cuts */
1355 ntries = 0;
1356 nfails = 0;
1357
1359 {
1360 /* try separating the objective function with the cutoff bound */
1361 SCIP_CALL( aggregation(scip, &aggrdata, sepa, sol, allowlocal, rowlhsscores, rowrhsscores,
1362 -1, 2 * maxaggrs, &wastried, &cutoff, cutinds, cutcoefs, FALSE, &ncuts) );
1363
1364 if( cutoff )
1365 goto TERMINATE;
1366 }
1367
1368 for( r = 0; r < nnonzrows && ntries < maxtries && ncuts < maxsepacuts && !SCIPisStopped(scip); r++ )
1369 {
1370 oldncuts = ncuts;
1371 SCIP_CALL( aggregation(scip, &aggrdata, sepa, sol, allowlocal, rowlhsscores, rowrhsscores,
1372 roworder[r], maxaggrs, &wastried, &cutoff, cutinds, cutcoefs, FALSE, &ncuts) );
1373
1374 /* if trynegscaling is true we start the aggregation heuristic again for this row, but multiply it by -1 first.
1375 * This is done by calling the aggregation function with the parameter negate equal to TRUE
1376 */
1377 if( sepadata->trynegscaling && !cutoff )
1378 {
1379 SCIP_CALL( aggregation(scip, &aggrdata, sepa, sol, allowlocal, rowlhsscores, rowrhsscores,
1380 roworder[r], maxaggrs, &wastried, &cutoff, cutinds, cutcoefs, TRUE, &ncuts) );
1381 }
1382
1383 if ( cutoff )
1384 break;
1385
1386 if( !wastried )
1387 {
1388 continue;
1389 }
1390 ntries++;
1391
1392 if( ncuts == oldncuts )
1393 {
1394 nfails++;
1395 if( nfails >= maxfails )
1396 {
1397 break;
1398 }
1399 }
1400 else
1401 {
1402 nfails = 0;
1403 }
1404 }
1405 TERMINATE:
1406 /* free data structure */
1407 destroyAggregationData(scip, &aggrdata);
1408 SCIPfreeBufferArray(scip, &cutcoefs);
1409 SCIPfreeBufferArray(scip, &cutinds);
1410 SCIPfreeBufferArray(scip, &fractionalities);
1411 SCIPfreeBufferArray(scip, &bestcontubs);
1412 SCIPfreeBufferArray(scip, &bestcontlbs);
1413 SCIPfreeBufferArray(scip, &varsolvals);
1414 SCIPfreeBufferArray(scip, &roworder);
1415 SCIPfreeBufferArray(scip, &rowrhsscores);
1416 SCIPfreeBufferArray(scip, &rowlhsscores);
1417
1418 if ( cutoff )
1420 else if ( ncuts > 0 )
1422
1423 return SCIP_OKAY;
1424}
1425
1426/*
1427 * Callback methods of separator
1428 */
1429
1430/** copy method for separator plugins (called when SCIP copies plugins) */
1431static
1432SCIP_DECL_SEPACOPY(sepaCopyAggregation)
1433{ /*lint --e{715}*/
1434 assert(scip != NULL);
1435 assert(sepa != NULL);
1436 assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
1437
1438 /* call inclusion method of constraint handler */
1440
1441 return SCIP_OKAY;
1442}
1443
1444/** destructor of separator to free user data (called when SCIP is exiting) */
1445static
1446SCIP_DECL_SEPAFREE(sepaFreeAggregation)
1447{ /*lint --e{715}*/
1449
1450 /* free separator data */
1451 sepadata = SCIPsepaGetData(sepa);
1452 assert(sepadata != NULL);
1453
1455
1456 SCIPsepaSetData(sepa, NULL);
1457
1458 return SCIP_OKAY;
1459}
1460
1461/** LP solution separation method of separator */
1462static
1463SCIP_DECL_SEPAEXECLP(sepaExeclpAggregation)
1464{ /*lint --e{715}*/
1465 assert( result != NULL );
1466
1468
1469 /* only call separator, if we are not close to terminating */
1470 if( SCIPisStopped(scip) )
1471 return SCIP_OKAY;
1472
1473 /* only call separator, if an optimal LP solution is at hand */
1475 return SCIP_OKAY;
1476
1477 /* only call separator, if there are fractional variables */
1478 if( SCIPgetNLPBranchCands(scip) == 0 )
1479 return SCIP_OKAY;
1480
1481 SCIP_CALL( separateCuts(scip, sepa, NULL, allowlocal, depth, result) );
1482
1483 return SCIP_OKAY;
1484}
1485
1486/** arbitrary primal solution separation method of separator */
1487static
1488SCIP_DECL_SEPAEXECSOL(sepaExecsolAggregation)
1489{ /*lint --e{715}*/
1490 assert( result != NULL );
1491
1493
1494 SCIP_CALL( separateCuts(scip, sepa, sol, allowlocal, depth, result) );
1495
1496 return SCIP_OKAY;
1497}
1498
1499/** LP solution separation method of dummy separator */
1500static
1501SCIP_DECL_SEPAEXECLP(sepaExeclpDummy)
1502{ /*lint --e{715}*/
1503 assert( result != NULL );
1504
1506
1507 return SCIP_OKAY;
1508}
1509
1510/** arbitrary primal solution separation method of dummy separator */
1511static
1512SCIP_DECL_SEPAEXECSOL(sepaExecsolDummy)
1513{ /*lint --e{715}*/
1514 assert( result != NULL );
1515
1517
1518 return SCIP_OKAY;
1519}
1520
1521/*
1522 * separator specific interface methods
1523 */
1524
1525/** creates the cmir separator and includes it in SCIP */
1527 SCIP* scip /**< SCIP data structure */
1528 )
1529{
1531 SCIP_SEPA* sepa;
1532
1533 /* create cmir separator data */
1535
1536 /* include dummy separators */
1537 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->flowcover, "flowcover", "separator for flowcover cuts", -100000, SEPA_FREQ, 0.0,
1538 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) );
1539
1540 assert(sepadata->flowcover != NULL);
1541
1542 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->cmir, "cmir", "separator for cmir cuts", -100000, SEPA_FREQ, 0.0,
1543 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) );
1544
1545 assert(sepadata->cmir != NULL);
1546
1547 SCIP_CALL( SCIPincludeSepaBasic(scip, &sepadata->knapsackcover, "knapsackcover", "separator for knapsack cover cuts", -100000, SEPA_FREQ, 0.0,
1548 SEPA_USESSUBSCIP, FALSE, sepaExeclpDummy, sepaExecsolDummy, NULL) );
1549
1550 assert(sepadata->knapsackcover != NULL);
1551
1552 /* include separator */
1555 sepaExeclpAggregation, sepaExecsolAggregation,
1556 sepadata) );
1557
1558 assert(sepa != NULL);
1559
1560 /* set non-NULL pointers to callback methods */
1561 SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyAggregation) );
1562 SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeAggregation) );
1563
1564 /* mark main separator as a parent */
1566
1567 /* set pointer from child separators to main separator */
1568 SCIPsetSepaParentsepa(scip, sepadata->flowcover, sepa);
1569 SCIPsetSepaParentsepa(scip, sepadata->cmir, sepa);
1570 SCIPsetSepaParentsepa(scip, sepadata->knapsackcover, sepa);
1571
1572 /* add cmir separator parameters */
1574 "separating/" SEPA_NAME "/maxrounds",
1575 "maximal number of cmir separation rounds per node (-1: unlimited)",
1576 &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
1578 "separating/" SEPA_NAME "/maxroundsroot",
1579 "maximal number of cmir separation rounds in the root node (-1: unlimited)",
1580 &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
1582 "separating/" SEPA_NAME "/maxtries",
1583 "maximal number of rows to start aggregation with per separation round (-1: unlimited)",
1584 &sepadata->maxtries, TRUE, DEFAULT_MAXTRIES, -1, INT_MAX, NULL, NULL) );
1586 "separating/" SEPA_NAME "/maxtriesroot",
1587 "maximal number of rows to start aggregation with per separation round in the root node (-1: unlimited)",
1588 &sepadata->maxtriesroot, TRUE, DEFAULT_MAXTRIESROOT, -1, INT_MAX, NULL, NULL) );
1590 "separating/" SEPA_NAME "/maxfails",
1591 "maximal number of consecutive unsuccessful aggregation tries (-1: unlimited)",
1592 &sepadata->maxfails, TRUE, DEFAULT_MAXFAILS, -1, INT_MAX, NULL, NULL) );
1594 "separating/" SEPA_NAME "/maxfailsroot",
1595 "maximal number of consecutive unsuccessful aggregation tries in the root node (-1: unlimited)",
1596 &sepadata->maxfailsroot, TRUE, DEFAULT_MAXFAILSROOT, -1, INT_MAX, NULL, NULL) );
1598 "separating/" SEPA_NAME "/maxaggrs",
1599 "maximal number of aggregations for each row per separation round",
1600 &sepadata->maxaggrs, TRUE, DEFAULT_MAXAGGRS, 0, INT_MAX, NULL, NULL) );
1602 "separating/" SEPA_NAME "/maxaggrsroot",
1603 "maximal number of aggregations for each row per separation round in the root node",
1604 &sepadata->maxaggrsroot, TRUE, DEFAULT_MAXAGGRSROOT, 0, INT_MAX, NULL, NULL) );
1606 "separating/" SEPA_NAME "/maxsepacuts",
1607 "maximal number of cmir cuts separated per separation round",
1608 &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
1610 "separating/" SEPA_NAME "/maxsepacutsroot",
1611 "maximal number of cmir cuts separated per separation round in the root node",
1612 &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
1614 "separating/" SEPA_NAME "/maxslack",
1615 "maximal slack of rows to be used in aggregation",
1616 &sepadata->maxslack, TRUE, DEFAULT_MAXSLACK, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1618 "separating/" SEPA_NAME "/maxslackroot",
1619 "maximal slack of rows to be used in aggregation in the root node",
1620 &sepadata->maxslackroot, TRUE, DEFAULT_MAXSLACKROOT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1622 "separating/" SEPA_NAME "/densityscore",
1623 "weight of row density in the aggregation scoring of the rows",
1624 &sepadata->densityscore, TRUE, DEFAULT_DENSITYSCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1626 "separating/" SEPA_NAME "/slackscore",
1627 "weight of slack in the aggregation scoring of the rows",
1628 &sepadata->slackscore, TRUE, DEFAULT_SLACKSCORE, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1630 "separating/" SEPA_NAME "/maxaggdensity",
1631 "maximal density of aggregated row",
1632 &sepadata->maxaggdensity, TRUE, DEFAULT_MAXAGGDENSITY, 0.0, 1.0, NULL, NULL) );
1634 "separating/" SEPA_NAME "/maxrowdensity",
1635 "maximal density of row to be used in aggregation",
1636 &sepadata->maxrowdensity, TRUE, DEFAULT_MAXROWDENSITY, 0.0, 1.0, NULL, NULL) );
1638 "separating/" SEPA_NAME "/densityoffset",
1639 "additional number of variables allowed in row on top of density",
1640 &sepadata->densityoffset, TRUE, DEFAULT_DENSITYOFFSET, 0, INT_MAX, NULL, NULL) );
1642 "separating/" SEPA_NAME "/maxrowfac",
1643 "maximal row aggregation factor",
1644 &sepadata->maxrowfac, TRUE, DEFAULT_MAXROWFAC, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1646 "separating/" SEPA_NAME "/maxtestdelta",
1647 "maximal number of different deltas to try (-1: unlimited)",
1648 &sepadata->maxtestdelta, TRUE, DEFAULT_MAXTESTDELTA, -1, INT_MAX, NULL, NULL) );
1650 "separating/" SEPA_NAME "/aggrtol",
1651 "tolerance for bound distances used to select continuous variable in current aggregated constraint to be eliminated",
1652 &sepadata->aggrtol, TRUE, DEFAULT_AGGRTOL, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1654 "separating/" SEPA_NAME "/trynegscaling",
1655 "should negative values also be tested in scaling?",
1656 &sepadata->trynegscaling, TRUE, DEFAULT_TRYNEGSCALING, NULL, NULL) );
1658 "separating/" SEPA_NAME "/fixintegralrhs",
1659 "should an additional variable be complemented if f0 = 0?",
1660 &sepadata->fixintegralrhs, TRUE, DEFAULT_FIXINTEGRALRHS, NULL, NULL) );
1662 "separating/" SEPA_NAME "/dynamiccuts",
1663 "should generated cuts be removed from the LP if they are no longer tight?",
1664 &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
1665
1666 return SCIP_OKAY;
1667}
methods for the aggregation rows
#define NULL
Definition def.h:267
#define SCIP_MAXSTRLEN
Definition def.h:288
#define SCIP_REAL_MAX
Definition def.h:174
#define SCIP_INVALID
Definition def.h:193
#define MIN(x, y)
Definition def.h:243
#define SCIP_Real
Definition def.h:173
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_LONGINT_FORMAT
Definition def.h:165
#define REALABS(x)
Definition def.h:197
#define SCIP_CALL(x)
Definition def.h:374
SCIP_Bool SCIPisStopped(SCIP *scip)
int SCIPgetNIntVars(SCIP *scip)
Definition scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition scip_prob.c:2127
int SCIPgetNContVars(SCIP *scip)
Definition scip_prob.c:2172
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition scip_prob.c:1866
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
SCIP_Real SCIPgetObjNorm(SCIP *scip)
Definition scip_prob.c:1641
int SCIPgetNBinVars(SCIP *scip)
Definition scip_prob.c:2037
SCIP_Bool SCIPisObjIntegral(SCIP *scip)
Definition scip_prob.c:1562
#define SCIPdebugMsg
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:139
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition misc.c:10396
void SCIPswapReals(SCIP_Real *value1, SCIP_Real *value2)
Definition misc.c:10383
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
Definition lp.c:17042
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
Definition lp.c:17161
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
Definition lp.c:17151
int SCIPcolGetNLPNonz(SCIP_COL *col)
Definition lp.c:17140
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:361
SCIP_Bool SCIPaggrRowHasRowBeenAdded(SCIP_AGGRROW *aggrrow, SCIP_ROW *row)
Definition cuts.c:2526
SCIP_RETCODE SCIPcutGenerationHeuristicCMIR(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool usevbds, SCIP_Bool allowlocal, int maxtestdelta, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real minfrac, SCIP_Real maxfrac, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:4220
SCIP_RETCODE SCIPaggrRowCreate(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1731
SCIP_RETCODE SCIPcalcKnapsackCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:8055
void SCIPaggrRowClear(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2141
SCIP_Bool SCIPisCutNew(SCIP *scip, SCIP_ROW *row)
Definition scip_cut.c:343
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition scip_cut.c:117
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
int SCIPaggrRowGetNRows(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2494
void SCIPaggrRowFree(SCIP *scip, SCIP_AGGRROW **aggrrow)
Definition cuts.c:1763
int * SCIPaggrRowGetInds(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2549
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:250
void SCIPaggrRowRemoveZeros(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Bool useglbbounds, SCIP_Bool *valid)
Definition cuts.c:2479
int SCIPaggrRowGetNNz(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2559
SCIP_RETCODE SCIPaggrRowAddRow(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_ROW *row, SCIP_Real weight, int sidetype)
Definition cuts.c:1867
static INLINE SCIP_Real SCIPaggrRowGetProbvarValue(SCIP_AGGRROW *aggrrow, int probindex)
Definition cuts.h:251
int * SCIPaggrRowGetRowInds(SCIP_AGGRROW *aggrrow)
Definition cuts.c:2504
SCIP_RETCODE SCIPaggrRowAddObjectiveFunction(SCIP *scip, SCIP_AGGRROW *aggrrow, SCIP_Real rhs, SCIP_Real scale)
Definition cuts.c:2012
SCIP_RETCODE SCIPcalcFlowCover(SCIP *scip, SCIP_SOL *sol, SCIP_Bool postprocess, SCIP_Real boundswitch, SCIP_Bool allowlocal, SCIP_AGGRROW *aggrrow, SCIP_Real *cutcoefs, SCIP_Real *cutrhs, int *cutinds, int *cutnnz, SCIP_Real *cutefficacy, int *cutrank, SCIP_Bool *cutislocal, SCIP_Bool *success)
Definition cuts.c:7425
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
Definition scip_lp.c:570
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
Definition scip_lp.c:168
int SCIPgetNLPCols(SCIP *scip)
Definition scip_lp.c:527
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_Real SCIPgetRowMaxCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1922
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition lp.c:17292
SCIP_Real SCIPgetRowMinCoef(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1904
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition lp.c:17411
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1635
SCIP_Real SCIProwGetParallelism(SCIP_ROW *row1, SCIP_ROW *row2, char orthofunc)
Definition lp.c:7724
int SCIProwGetNNonz(SCIP_ROW *row)
Definition lp.c:17213
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
Definition lp.c:17238
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition lp.c:17302
int SCIProwGetNLPNonz(SCIP_ROW *row)
Definition lp.c:17227
SCIP_Real SCIProwGetNorm(SCIP_ROW *row)
Definition lp.c:17268
int SCIProwGetLPPos(SCIP_ROW *row)
Definition lp.c:17501
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1658
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition lp.c:17401
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
Definition scip_lp.c:1844
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition scip_lp.c:2212
const char * SCIProwGetName(SCIP_ROW *row)
Definition lp.c:17351
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition scip_lp.c:1453
int SCIProwGetRank(SCIP_ROW *row)
Definition lp.c:17381
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition lp.c:17534
SCIP_Real SCIProwGetDualsol(SCIP_ROW *row)
Definition lp.c:17312
int SCIPgetRowNumIntCols(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1886
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
Definition lp.c:17248
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition scip_lp.c:2144
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition scip_sepa.c:109
int SCIPsepaGetFreq(SCIP_SEPA *sepa)
Definition sepa.c:787
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:167
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition sepa.c:743
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
Definition sepa.c:880
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition sepa.c:633
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition sepa.c:643
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
Definition scip_sepa.c:151
void SCIPsetSepaIsParentsepa(SCIP *scip, SCIP_SEPA *sepa)
Definition scip_sepa.c:303
void SCIPsetSepaParentsepa(SCIP *scip, SCIP_SEPA *sepa, SCIP_SEPA *parentsepa)
Definition scip_sepa.c:318
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_sol.c:1254
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Real SCIPgetUpperbound(SCIP *scip)
int SCIPgetNSepaRounds(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Real SCIPfeasFrac(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
Definition var.c:17789
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition var.c:18292
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
SCIP_RETCODE SCIPgetVarClosestVub(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvub, int *closestvubidx)
Definition scip_var.c:6631
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition var.c:17768
SCIP_RETCODE SCIPgetVarClosestVlb(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real *closestvlb, int *closestvlbidx)
Definition scip_var.c:6608
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition var.c:18282
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition var.c:18324
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition var.c:18334
SCIP_Bool SCIPvarIsInLP(SCIP_VAR *var)
Definition var.c:17800
SCIP_RETCODE SCIPincludeSepaAggregation(SCIP *scip)
SCIP_Bool SCIPsortedvecFindInt(int *intarray, int val, int len, int *pos)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10877
return SCIP_OKAY
SCIP_Longint ncalls
int depth
SCIP_Bool cutoff
static SCIP_SOL * sol
int r
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
SCIP_Real primsol
SCIP_Real frac
static SCIP_VAR ** vars
int nbinvars
int nintvars
static SCIP_Real negate(SCIP_Real x)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
Definition memory.h:130
public methods for LP management
public methods for message output
#define SCIPdebug(x)
Definition pub_message.h:93
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for branching rule plugins and branching
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for separator plugins
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
#define SEPA_PRIORITY
#define DEFAULT_MAXTRIES
struct AggregationData AGGREGATIONDATA
#define BOUNDSWITCH
#define SEPA_DELAY
#define DEFAULT_SLACKSCORE
#define DEFAULT_MAXAGGRS
#define DEFAULT_MAXFAILS
#define MAXFRAC
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SOL *sol, SCIP_SEPA *sepa, SCIP_Bool makeintegral, SCIP_Real *cutcoefs, int *cutinds, int cutnnz, SCIP_Real cutrhs, SCIP_Real cutefficacy, SCIP_Bool cutislocal, SCIP_Bool cutremovable, int cutrank, const char *cutclassname, SCIP_Bool *cutoff, int *ncuts, SCIP_ROW **thecut)
#define DEFAULT_AGGRTOL
#define DEFAULT_DYNAMICCUTS
static SCIP_Bool getRowAggregationCandidates(AGGREGATIONDATA *aggrdata, int probvaridx, SCIP_ROW ***rows, SCIP_Real **rowvarcoefs, int *nrows, int *ngoodrows)
#define POSTPROCESS
#define SEPA_DESC
static SCIP_Real aggrdataGetBoundDist(AGGREGATIONDATA *aggrdata, int probvaridx)
#define DEFAULT_MAXSLACKROOT
#define MAKECONTINTEGRAL
#define DEFAULT_MAXFAILSROOT
#define DEFAULT_MAXAGGRSROOT
#define DEFAULT_MAXROUNDSROOT
#define SEPA_USESSUBSCIP
#define DEFAULT_MAXSLACK
static SCIP_RETCODE aggregateNextRow(SCIP *scip, SCIP_SEPADATA *sepadata, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, AGGREGATIONDATA *aggrdata, SCIP_AGGRROW *aggrrow, int *naggrs, SCIP_Bool *success)
#define DEFAULT_TRYNEGSCALING
#define DEFAULT_MAXTRIESROOT
#define DEFAULT_MAXROWFAC
#define DEFAULT_MAXSEPACUTSROOT
#define DEFAULT_DENSITYSCORE
#define DEFAULT_DENSITYOFFSET
#define DEFAULT_FIXINTEGRALRHS
static SCIP_RETCODE setupAggregationData(SCIP *scip, SCIP_SOL *sol, SCIP_Bool allowlocal, AGGREGATIONDATA *aggrdata)
#define USEVBDS
#define DEFAULT_MAXTESTDELTA
#define SEPA_MAXBOUNDDIST
#define SEPA_FREQ
#define MINFRAC
#define DEFAULT_MAXSEPACUTS
#define DEFAULT_MAXAGGDENSITY
#define SEPA_NAME
static SCIP_RETCODE aggregation(SCIP *scip, AGGREGATIONDATA *aggrdata, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, SCIP_Real *rowlhsscores, SCIP_Real *rowrhsscores, int startrow, int maxaggrs, SCIP_Bool *wastried, SCIP_Bool *cutoff, int *cutinds, SCIP_Real *cutcoefs, SCIP_Bool negate, int *ncuts)
static SCIP_Real getRowFracActivity(SCIP_ROW *row, SCIP_Real *fractionalities)
#define DEFAULT_MAXROUNDS
static void destroyAggregationData(SCIP *scip, AGGREGATIONDATA *aggrdata)
#define DEFAULT_MAXROWDENSITY
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Bool allowlocal, int depth, SCIP_RESULT *result)
flow cover and complemented mixed integer rounding cuts separator (Marchand's version)
SCIP_AGGRROW * aggrrow
SCIP_Real * bounddist
SCIP_Real * aggrrowscoef
@ SCIP_LPSOLSTAT_OPTIMAL
Definition type_lp.h:43
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_SEPARATED
Definition type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
Definition type_sepa.h:52
#define SCIP_DECL_SEPAEXECSOL(x)
Definition type_sepa.h:166
#define SCIP_DECL_SEPAEXECLP(x)
Definition type_sepa.h:136
#define SCIP_DECL_SEPAFREE(x)
Definition type_sepa.h:69
#define SCIP_DECL_SEPACOPY(x)
Definition type_sepa.h:61