Scippy

SCIP

Solving Constraint Integer Programs

presol_milp.cpp
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-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 presol_milp.cpp
17  * @brief MILP presolver
18  * @author Leona Gottwald
19  *
20  * Calls the presolve library and communicates (multi-)aggregations, fixings, and bound
21  * changes to SCIP by utilizing the postsolve information. Constraint changes can currently
22  * only be communicated by deleting all constraints and adding new ones.
23  *
24  * @todo add infrastructure to SCIP for handling parallel columns
25  * @todo better communication of constraint changes by adding more information to the postsolve structure
26  * @todo allow to pass additional external locks to the presolve library that are considered when doing reductions
27  *
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include "scip/presol_milp.h"
33 
34 #ifndef SCIP_WITH_PAPILO
35 
36 /** creates the MILP presolver and includes it in SCIP */
38  SCIP* scip /**< SCIP data structure */
39  )
40 {
41  assert(scip != NULL);
42  return SCIP_OKAY;
43 }
44 
45 #else
46 
47 #include <assert.h>
48 #include "scip/cons_linear.h"
49 #include "scip/pub_matrix.h"
50 #include "scip/pub_presol.h"
51 #include "scip/pub_var.h"
52 #include "scip/pub_cons.h"
53 #include "scip/pub_message.h"
54 #include "scip/scip_general.h"
55 #include "scip/scip_presol.h"
56 #include "scip/scip_var.h"
57 #include "scip/scip_mem.h"
58 #include "scip/scip_prob.h"
59 #include "scip/scip_param.h"
60 #include "scip/scip_cons.h"
61 #include "scip/scip_numerics.h"
62 #include "scip/scip_timing.h"
63 #include "scip/scip_message.h"
64 #include "scip/scip_randnumgen.h"
65 #include "papilo/core/Presolve.hpp"
66 #include "papilo/core/ProblemBuilder.hpp"
67 #include "papilo/Config.hpp"
68 
69 #define PRESOL_NAME "milp"
70 #define PRESOL_DESC "MILP specific presolving methods"
71 #define PRESOL_PRIORITY 9999999 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */
72 #define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
73 #define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
74 
75 /* default parameter values */
76 #define DEFAULT_THREADS 1 /**< maximum number of threads presolving may use (0: automatic) */
77 #define DEFAULT_MAXFILLINPERSUBST 3 /**< maximal possible fillin for substitutions to be considered */
78 #define DEFAULT_MAXSHIFTPERROW 10 /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
79 #define DEFAULT_DETECTLINDEP 0 /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
80 #define DEFAULT_RANDOMSEED 0 /**< the random seed used for randomization of tie breaking */
81 #define DEFAULT_MODIFYCONSFAC 0.8 /**< modify SCIP constraints when the number of nonzeros or rows is at most this
82  * factor times the number of nonzeros or rows before presolving */
83 #define DEFAULT_MARKOWITZTOLERANCE 0.01 /**< the markowitz tolerance used for substitutions */
84 #define DEFAULT_HUGEBOUND 1e8 /**< absolute bound value that is considered too huge for activitity based calculations */
85 #define DEFAULT_ENABLEPARALLELROWS TRUE /**< should the parallel rows presolver be enabled within the presolve library? */
86 #define DEFAULT_ENABLEDOMCOL TRUE /**< should the dominated column presolver be enabled within the presolve library? */
87 #define DEFAULT_ENABLEDUALINFER TRUE /**< should the dualinfer presolver be enabled within the presolve library? */
88 #define DEFAULT_ENABLEMULTIAGGR TRUE /**< should the multi-aggregation presolver be enabled within the presolve library? */
89 #define DEFAULT_ENABLEPROBING TRUE /**< should the probing presolver be enabled within the presolve library? */
90 #define DEFAULT_ENABLESPARSIFY FALSE /**< should the sparsify presolver be enabled within the presolve library? */
91 
92 /*
93  * Data structures
94  */
95 
96 /** presolver data */
97 struct SCIP_PresolData
98 {
99  int lastncols; /**< the number of columns from the last call */
100  int lastnrows; /**< the number of rows from the last call */
101  int threads; /**< maximum number of threads presolving may use (0: automatic) */
102  int maxfillinpersubstitution; /**< maximal possible fillin for substitutions to be considered */
103  int maxshiftperrow; /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
104  int detectlineardependency; /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
105  int randomseed; /**< the random seed used for randomization of tie breaking */
106  SCIP_Bool enablesparsify; /**< should the sparsify presolver be enabled within the presolve library? */
107  SCIP_Bool enabledomcol; /**< should the dominated column presolver be enabled within the presolve library? */
108  SCIP_Bool enableprobing; /**< should the probing presolver be enabled within the presolve library? */
109  SCIP_Bool enabledualinfer; /**< should the dualinfer presolver be enabled within the presolve library? */
110  SCIP_Bool enablemultiaggr; /**< should the multi-aggregation presolver be enabled within the presolve library? */
111  SCIP_Bool enableparallelrows; /**< should the parallel rows presolver be enabled within the presolve library? */
112  SCIP_Real modifyconsfac; /**< modify SCIP constraints when the number of nonzeros or rows is at most this
113  * factor times the number of nonzeros or rows before presolving */
114  SCIP_Real markowitztolerance; /**< the markowitz tolerance used for substitutions */
115  SCIP_Real hugebound; /**< absolute bound value that is considered too huge for activitity based calculations */
116 };
117 
118 using namespace papilo;
119 
120 /*
121  * Local methods
122  */
123 
124 /** builds the presolvelib problem datastructure from the matrix */
125 static
126 Problem<SCIP_Real> buildProblem(
127  SCIP* scip, /**< SCIP data structure */
128  SCIP_MATRIX* matrix /**< initialized SCIP_MATRIX data structure */
129  )
130 {
131  ProblemBuilder<SCIP_Real> builder;
132 
133  /* build problem from matrix */
134  int nnz = SCIPmatrixGetNNonzs(matrix);
135  int ncols = SCIPmatrixGetNColumns(matrix);
136  int nrows = SCIPmatrixGetNRows(matrix);
137  builder.reserve(nnz, nrows, ncols);
138 
139  /* set up columns */
140  builder.setNumCols(ncols);
141  for(int i = 0; i != ncols; ++i)
142  {
143  SCIP_VAR* var = SCIPmatrixGetVar(matrix, i);
144  SCIP_Real lb = SCIPvarGetLbGlobal(var);
145  SCIP_Real ub = SCIPvarGetUbGlobal(var);
146  builder.setColLb(i, lb);
147  builder.setColUb(i, ub);
148  builder.setColLbInf(i, SCIPisInfinity(scip, -lb));
149  builder.setColUbInf(i, SCIPisInfinity(scip, ub));
150 
151  builder.setColIntegral(i, SCIPvarIsIntegral(var));
152  builder.setObj(i, SCIPvarGetObj(var));
153  }
154 
155  /* set up rows */
156  builder.setNumRows(nrows);
157  for(int i = 0; i != nrows; ++i)
158  {
159  int* rowcols = SCIPmatrixGetRowIdxPtr(matrix, i);
160  SCIP_Real* rowvals = SCIPmatrixGetRowValPtr(matrix, i);
161  int rowlen = SCIPmatrixGetRowNNonzs(matrix, i);
162  builder.addRowEntries(i, rowlen, rowcols, rowvals);
163 
164  SCIP_Real lhs = SCIPmatrixGetRowLhs(matrix, i);
165  SCIP_Real rhs = SCIPmatrixGetRowRhs(matrix, i);
166  builder.setRowLhs(i, lhs);
167  builder.setRowRhs(i, rhs);
168  builder.setRowLhsInf(i, SCIPisInfinity(scip, -lhs));
169  builder.setRowRhsInf(i, SCIPisInfinity(scip, rhs));
170  }
171 
172  return builder.build();
173 }
174 
175 /*
176  * Callback methods of presolver
177  */
178 
179 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
180 static
181 SCIP_DECL_PRESOLCOPY(presolCopyMILP)
182 { /*lint --e{715}*/
184 
185  return SCIP_OKAY;
186 }
187 
188 /** destructor of presolver to free user data (called when SCIP is exiting) */
189 static
190 SCIP_DECL_PRESOLFREE(presolFreeMILP)
191 { /*lint --e{715}*/
192  SCIP_PRESOLDATA* data = SCIPpresolGetData(presol);
193  assert(data != NULL);
194 
195  SCIPpresolSetData(presol, NULL);
196  SCIPfreeBlockMemory(scip, &data);
197  return SCIP_OKAY;
198 }
199 
200 /** initialization method of presolver (called after problem was transformed) */
201 static
202 SCIP_DECL_PRESOLINIT(presolInitMILP)
203 { /*lint --e{715}*/
204  SCIP_PRESOLDATA* data = SCIPpresolGetData(presol);
205  assert(data != NULL);
206 
207  data->lastncols = -1;
208  data->lastnrows = -1;
209 
210  return SCIP_OKAY;
211 }
212 
213 /** execution method of presolver */
214 static
215 SCIP_DECL_PRESOLEXEC(presolExecMILP)
216 { /*lint --e{715}*/
217  SCIP_MATRIX* matrix;
218  SCIP_PRESOLDATA* data;
219  SCIP_Bool initialized;
220  SCIP_Bool complete;
221  SCIP_Bool infeasible;
222  SCIP_Real timelimit;
223 
224  *result = SCIP_DIDNOTRUN;
225 
226  data = SCIPpresolGetData(presol);
227 
228  int nvars = SCIPgetNVars(scip);
229  int nconss = SCIPgetNConss(scip);
230 
231  /* run only if the problem size reduced by some amount since the last call or if it is the first call */
232  if( data->lastncols != -1 && data->lastnrows != -1 &&
233  nvars > data->lastncols * 0.85 &&
234  nconss > data->lastnrows * 0.85 )
235  return SCIP_OKAY;
236 
237  SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
238  naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
239 
240  /* if infeasibility was detected during matrix creation, return here */
241  if( infeasible )
242  {
243  if( initialized )
244  SCIPmatrixFree(scip, &matrix);
245 
246  *result = SCIP_CUTOFF;
247  return SCIP_OKAY;
248  }
249 
250  /* we only work on pure MIPs, also disable to try building the matrix again if it failed once */
251  if( !initialized || !complete )
252  {
253  data->lastncols = 0;
254  data->lastnrows = 0;
255 
256  if( initialized )
257  SCIPmatrixFree(scip, &matrix);
258 
259  return SCIP_OKAY;
260  }
261 
262  /* only allow communication of constraint modifications by deleting all constraints when they have not been upgraded yet */
263  SCIP_CONSHDLR* linconshdlr = SCIPfindConshdlr(scip, "linear");
264  assert(linconshdlr != NULL);
265  bool allowconsmodification = (SCIPconshdlrGetNCheckConss(linconshdlr) == SCIPmatrixGetNRows(matrix));
266 
267  Problem<SCIP_Real> problem = buildProblem(scip, matrix);
268  Presolve<SCIP_Real> presolve;
269 
270  /* store current numbers of aggregations, fixings, and changed bounds for statistics */
271  int oldnaggrvars = *naggrvars;
272  int oldnfixedvars = *nfixedvars;
273  int oldnchgbds = *nchgbds;
274 
275  /* important so that SCIP does not throw an error, e.g. when an integer variable is substituted
276  * into a knapsack constraint */
277  presolve.getPresolveOptions().substitutebinarieswithints = false;
278 
279  /* currently these changes cannot be communicated to SCIP correctly since a constraint needs
280  * to be modified in the cases where slackvariables are removed from constraints but for the
281  * presolve library those look like normal substitution on the postsolve stack */
282  presolve.getPresolveOptions().removeslackvars = false;
283 
284  /* communicate the SCIP parameters to the presolve libary */
285  presolve.getPresolveOptions().maxfillinpersubstitution = data->maxfillinpersubstitution;
286  presolve.getPresolveOptions().markowitz_tolerance = data->markowitztolerance;
287  presolve.getPresolveOptions().maxshiftperrow = data->maxshiftperrow;
288  presolve.getPresolveOptions().hugeval = data->hugebound;
289 
290  /* removal of linear dependent equations has only an effect when constraint modifications are communicated */
291  presolve.getPresolveOptions().detectlindep = allowconsmodification ? data->detectlineardependency : 0;
292 
293  /* communicate the random seed */
294  presolve.getPresolveOptions().randomseed = SCIPinitializeRandomSeed(scip, (unsigned int)data->randomseed);
295 
296  /* set number of threads to be used for presolve */
297  presolve.getPresolveOptions().threads = data->threads;
298 
299  /* disable dual reductions that are not permitted */
300  if( !complete )
301  presolve.getPresolveOptions().dualreds = 0;
302  else if( SCIPallowStrongDualReds(scip) )
303  presolve.getPresolveOptions().dualreds = 2;
304  else if( SCIPallowWeakDualReds(scip) )
305  presolve.getPresolveOptions().dualreds = 1;
306  else
307  presolve.getPresolveOptions().dualreds = 0;
308 
309  /* set up the presolvers that shall participate */
310  using uptr = std::unique_ptr<PresolveMethod<SCIP_Real>>;
311 
312  presolve.addPresolveMethod( uptr( new CoefficientStrengthening<SCIP_Real>() ) );
313  presolve.addPresolveMethod( uptr( new SimpleProbing<SCIP_Real>() ) );
314  presolve.addPresolveMethod( uptr( new ConstraintPropagation<SCIP_Real>() ) );
315  presolve.addPresolveMethod( uptr( new ImplIntDetection<SCIP_Real>() ) );
316  presolve.addPresolveMethod( uptr( new FixContinuous<SCIP_Real>() ) );
317 
318  if( data->enableparallelrows )
319  presolve.addPresolveMethod( uptr( new ParallelRowDetection<SCIP_Real>() ) );
320 
321  presolve.addPresolveMethod( uptr( new SimpleSubstitution<SCIP_Real>() ) );
322  presolve.addPresolveMethod( uptr( new SimplifyInequalities<SCIP_Real>() ) );
323  presolve.addPresolveMethod( uptr( new SingletonCols<SCIP_Real>() ) );
324  presolve.addPresolveMethod( uptr( new DualFix<SCIP_Real>() ) );
325 
326  if( data->enablemultiaggr )
327  presolve.addPresolveMethod( uptr( new Substitution<SCIP_Real>() ) );
328 
329  if( data->enableprobing )
330  presolve.addPresolveMethod( uptr( new Probing<SCIP_Real>() ) );
331 
332  if( data->enablesparsify )
333  presolve.addPresolveMethod( uptr( new Sparsify<SCIP_Real>() ) );
334 
335  if( data->enabledualinfer )
336  presolve.addPresolveMethod( uptr( new DualInfer<SCIP_Real>() ) );
337 
338  presolve.addPresolveMethod( uptr( new SingletonStuffing<SCIP_Real>() ) );
339 
340  if( data->enabledomcol )
341  presolve.addPresolveMethod( uptr( new DominatedCols<SCIP_Real>() ) );
342 
343  /* todo: parallel cols cannot be handled by SCIP currently
344  * addPresolveMethod( uptr( new ParallelColDetection<SCIP_Real>() ) ); */
345 
346  /* set tolerances */
347  presolve.getPresolveOptions().feastol = SCIPfeastol(scip);
348  presolve.getPresolveOptions().epsilon = SCIPepsilon(scip);
349 
350  /* adjust output settings of presolve libary */
351 #ifdef SCIP_PRESOLLIB_ENABLE_OUTPUT
352  problem.setName(SCIPgetProbName(scip));
353 #else
354  presolve.setVerbosityLevel(VerbosityLevel::kQuiet);
355 #endif
356 
357  /* communicate the time limit */
358  SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
359  if( !SCIPisInfinity(scip, timelimit) )
360  presolve.getPresolveOptions().tlim = timelimit - SCIPgetSolvingTime(scip);
361 
362  /* call the presolving */
364  " (%.1fs) running MILP presolver\n", SCIPgetSolvingTime(scip));
365  int oldnnz = problem.getConstraintMatrix().getNnz();
366  PresolveResult<SCIP_Real> res = presolve.apply(problem);
367  data->lastncols = problem.getNCols();
368  data->lastnrows = problem.getNRows();
369 
370  /* evaluate the result */
371  switch(res.status)
372  {
373  case PresolveStatus::kInfeasible:
374  *result = SCIP_CUTOFF;
376  " (%.1fs) MILP presolver detected infeasibility\n",
377  SCIPgetSolvingTime(scip));
378  SCIPmatrixFree(scip, &matrix);
379  return SCIP_OKAY;
380  case PresolveStatus::kUnbndOrInfeas:
381  case PresolveStatus::kUnbounded:
382  *result = SCIP_UNBOUNDED;
384  " (%.1fs) MILP presolver detected unboundedness\n",
385  SCIPgetSolvingTime(scip));
386  SCIPmatrixFree(scip, &matrix);
387  return SCIP_OKAY;
388  case PresolveStatus::kUnchanged:
389  *result = SCIP_DIDNOTFIND;
390  data->lastncols = nvars;
391  data->lastnrows = nconss;
393  " (%.1fs) MILP presolver found nothing\n",
394  SCIPgetSolvingTime(scip));
395  SCIPmatrixFree(scip, &matrix);
396  return SCIP_OKAY;
397  case PresolveStatus::kReduced:
398  data->lastncols = problem.getNCols();
399  data->lastnrows = problem.getNRows();
400  *result = SCIP_SUCCESS;
401  }
402 
403  /* result indicated success, now populate the changes into the SCIP structures */
404  std::vector<SCIP_VAR*> tmpvars;
405  std::vector<SCIP_Real> tmpvals;
406 
407  /* if the number of nonzeros decreased by a sufficient factor, rather create all constraints from scratch */
408  int newnnz = problem.getConstraintMatrix().getNnz();
409  bool constraintsReplaced = false;
410  if( newnnz == 0 || (allowconsmodification &&
411  (problem.getNRows() <= data->modifyconsfac * data->lastnrows ||
412  newnnz <= data->modifyconsfac * oldnnz)) )
413  {
414  int oldnrows = SCIPmatrixGetNRows(matrix);
415  int newnrows = problem.getNRows();
416 
417  constraintsReplaced = true;
418 
419  /* capture constraints that are still present in the problem after presolve */
420  for( int i = 0; i < newnrows; ++i )
421  {
422  SCIP_CONS* c = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
423  SCIP_CALL( SCIPcaptureCons(scip, c) );
424  }
425 
426  /* delete all constraints */
427  *ndelconss += oldnrows;
428  *naddconss += newnrows;
429 
430  for( int i = 0; i < oldnrows; ++i )
431  {
432  SCIP_CALL( SCIPdelCons(scip, SCIPmatrixGetCons(matrix, i)) );
433  }
434 
435  /* now loop over rows of presolved problem and create them as new linear constraints,
436  * then release the old constraint after its name was passed to the new constraint */
437  const Vec<RowFlags>& rflags = problem.getRowFlags();
438  const auto& consmatrix = problem.getConstraintMatrix();
439  for( int i = 0; i < newnrows; ++i )
440  {
441  auto rowvec = consmatrix.getRowCoefficients(i);
442  const int* rowcols = rowvec.getIndices();
443  /* SCIPcreateConsBasicLinear() requires a non const pointer */
444  SCIP_Real* rowvals = const_cast<SCIP_Real*>(rowvec.getValues());
445  int rowlen = rowvec.getLength();
446 
447  /* retrieve SCIP compatible left and right hand sides */
448  SCIP_Real lhs = rflags[i].test(RowFlag::kLhsInf) ? - SCIPinfinity(scip) : consmatrix.getLeftHandSides()[i];
449  SCIP_Real rhs = rflags[i].test(RowFlag::kRhsInf) ? SCIPinfinity(scip) : consmatrix.getRightHandSides()[i];
450 
451  /* create variable array matching the value array */
452  tmpvars.clear();
453  tmpvars.reserve(rowlen);
454  for( int j = 0; j < rowlen; ++j )
455  tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[rowcols[j]]));
456 
457  /* create and add new constraint with name of old constraint */
458  SCIP_CONS* oldcons = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
459  SCIP_CONS* cons;
460  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, SCIPconsGetName(oldcons), rowlen, tmpvars.data(), rowvals, lhs, rhs) );
461  SCIP_CALL( SCIPaddCons(scip, cons) );
462 
463  /* release old and new constraint */
464  SCIP_CALL( SCIPreleaseCons(scip, &oldcons) );
465  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
466  }
467  }
468 
469  /* loop over res.postsolve and add all fixed variables and aggregations to scip */
470  for( std::size_t i = 0; i != res.postsolve.types.size(); ++i )
471  {
472  ReductionType type = res.postsolve.types[i];
473  int first = res.postsolve.start[i];
474  int last = res.postsolve.start[i + 1];
475 
476  switch( type )
477  {
478  case ReductionType::kFixedCol:
479  {
480  SCIP_Bool infeas;
481  SCIP_Bool fixed;
482  int col = res.postsolve.indices[first];
483 
484  SCIP_VAR* colvar = SCIPmatrixGetVar(matrix, col);
485 
486  SCIP_Real value = res.postsolve.values[first];
487 
488  SCIP_CALL( SCIPfixVar(scip, colvar, value, &infeas, &fixed) );
489  *nfixedvars += 1;
490 
491  assert(!infeas);
492  assert(fixed);
493  break;
494  }
495  case ReductionType::kSubstitutedCol:
496  {
497  int col = res.postsolve.indices[first];
498  SCIP_Real side = res.postsolve.values[first];
499 
500  int rowlen = last - first - 1;
501  SCIP_Bool infeas;
502  SCIP_Bool aggregated;
503  SCIP_Bool redundant = FALSE;
504  SCIP_Real constant = 0.0;
505  if( rowlen == 2 )
506  {
507  SCIP_VAR* varx = SCIPmatrixGetVar(matrix, res.postsolve.indices[first + 1]);
508  SCIP_VAR* vary = SCIPmatrixGetVar(matrix, res.postsolve.indices[first + 2]);
509  SCIP_Real scalarx = res.postsolve.values[first + 1];
510  SCIP_Real scalary = res.postsolve.values[first + 2];
511 
512  SCIP_CALL( SCIPgetProbvarSum(scip, &varx, &scalarx, &constant) );
513  assert(SCIPvarGetStatus(varx) != SCIP_VARSTATUS_MULTAGGR);
514 
515  SCIP_CALL( SCIPgetProbvarSum(scip, &vary, &scalary, &constant) );
516  assert(SCIPvarGetStatus(vary) != SCIP_VARSTATUS_MULTAGGR);
517 
518  side -= constant;
519 
520  SCIP_CALL( SCIPaggregateVars(scip, varx, vary, scalarx, scalary, side, &infeas, &redundant, &aggregated) );
521  }
522  else
523  {
524  SCIP_Real colCoef = 0.0;
525 
526  for( int j = first + 1; j < last; ++j )
527  {
528  if( res.postsolve.indices[j] == col )
529  {
530  colCoef = res.postsolve.values[j];
531  break;
532  }
533  }
534 
535  tmpvars.clear();
536  tmpvals.clear();
537  tmpvars.reserve(rowlen);
538  tmpvals.reserve(rowlen);
539 
540  assert(colCoef != 0.0);
541  SCIP_VAR* aggrvar = SCIPmatrixGetVar(matrix, col);
542 
543  SCIP_CALL( SCIPgetProbvarSum(scip, &aggrvar, &colCoef, &constant) );
544  assert(SCIPvarGetStatus(aggrvar) != SCIP_VARSTATUS_MULTAGGR);
545 
546  side -= constant;
547 
548  for( int j = first + 1; j < last; ++j )
549  {
550  if( res.postsolve.indices[j] == col )
551  continue;
552 
553  tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
554  tmpvals.push_back(- res.postsolve.values[j] / colCoef);
555  }
556 
557  SCIP_CALL( SCIPmultiaggregateVar(scip, aggrvar, tmpvars.size(),
558  tmpvars.data(), tmpvals.data(), side / colCoef, &infeas, &aggregated) );
559  }
560 
561  if( aggregated )
562  *naggrvars += 1;
563  else if( constraintsReplaced && !redundant )
564  {
565  /* if the constraints where replaced, we need to add the failed substitution as an equality to SCIP */
566  tmpvars.clear();
567  tmpvals.clear();
568  for( int j = first + 1; j < last; ++j )
569  {
570  tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
571  tmpvals.push_back(res.postsolve.values[j]);
572  }
573 
574  SCIP_CONS* cons;
575  String name = fmt::format("{}_failed_aggregation_equality", SCIPvarGetName(SCIPmatrixGetVar(matrix, col)));
576  SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name.c_str(),
577  tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
578  SCIP_CALL( SCIPaddCons(scip, cons) );
579  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
580  *naddconss += 1;
581  }
582 
583  if( infeas )
584  {
585  *result = SCIP_CUTOFF;
586  break;
587  }
588 
589  break;
590  }
591  case ReductionType::kParallelCol:
592  return SCIP_INVALIDRESULT;
593  default:
594  continue;
595  }
596  }
597 
598  /* tighten bounds of variables that are still present after presolving */
599  if( *result != SCIP_CUTOFF )
600  {
601  VariableDomains<SCIP_Real>& varDomains = problem.getVariableDomains();
602  for( int i = 0; i != problem.getNCols(); ++i )
603  {
604  SCIP_VAR* var = SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[i]);
605  if( !varDomains.flags[i].test(ColFlag::kLbInf) )
606  {
607  SCIP_Bool infeas;
608  SCIP_Bool tightened;
609  SCIP_CALL( SCIPtightenVarLb(scip, var, varDomains.lower_bounds[i], TRUE, &infeas, &tightened) );
610 
611  if( tightened )
612  *nchgbds += 1;
613 
614  if( infeas )
615  {
616  *result = SCIP_CUTOFF;
617  break;
618  }
619  }
620 
621  if( !varDomains.flags[i].test(ColFlag::kUbInf) )
622  {
623  SCIP_Bool infeas;
624  SCIP_Bool tightened;
625  SCIP_CALL( SCIPtightenVarUb(scip, var, varDomains.upper_bounds[i], TRUE, &infeas, &tightened) );
626 
627  if( tightened )
628  *nchgbds += 1;
629 
630  if( infeas )
631  {
632  *result = SCIP_CUTOFF;
633  break;
634  }
635  }
636  }
637  }
638 
639  /* finish with a final verb message and return */
641  " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
642  SCIPgetSolvingTime(scip), presolve.getStatistics().nrounds, *naggrvars - oldnaggrvars,
643  *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds);
644 
645  /* free the matrix */
646  assert(initialized);
647  SCIPmatrixFree(scip, &matrix);
648 
649  return SCIP_OKAY;
650 }
651 
652 
653 /*
654  * presolver specific interface methods
655  */
656 
657 /** creates the xyz presolver and includes it in SCIP */
659  SCIP* scip /**< SCIP data structure */
660  )
661 {
662  SCIP_PRESOLDATA* presoldata;
663  SCIP_PRESOL* presol;
664 
665 #if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
666  String name = fmt::format("PaPILO {}.{}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH, PAPILO_VERSION_TWEAK);
667 #else
668  String name = fmt::format("PaPILO {}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH);
669 #endif
670 
671 #ifdef PAPILO_GITHASH_AVAILABLE
672  String desc = fmt::format("parallel presolve for integer and linear optimization [GitHash: {}]", PAPILO_GITHASH);
673 #else
674  String desc("parallel presolve for integer and linear optimization");
675 #endif
676 
677  /* add external code info for the presolve library */
678  SCIP_CALL( SCIPincludeExternalCodeInformation(scip, name.c_str(), desc.c_str()) );
679 
680  /* create MILP presolver data */
681  presoldata = NULL;
682  SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
683 
684  presol = NULL;
685 
686  /* include presolver */
688  presolExecMILP,
689  presoldata) );
690 
691  assert(presol != NULL);
692 
693  /* set non fundamental callbacks via setter functions */
694  SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyMILP) );
695  SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeMILP) );
696  SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitMILP) );
697 
698  /* add MILP presolver parameters */
700  "presolving/" PRESOL_NAME "/threads",
701  "maximum number of threads presolving may use (0: automatic)",
702  &presoldata->threads, FALSE, DEFAULT_THREADS, 0, INT_MAX, NULL, NULL) );
703 
705  "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
706  "maximal possible fillin for substitutions to be considered",
707  &presoldata->maxfillinpersubstitution, FALSE, DEFAULT_MAXFILLINPERSUBST, INT_MIN, INT_MAX, NULL, NULL) );
708 
710  "presolving/" PRESOL_NAME "/maxshiftperrow",
711  "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
712  &presoldata->maxshiftperrow, TRUE, DEFAULT_MAXSHIFTPERROW, 0, INT_MAX, NULL, NULL) );
713 
715  "presolving/" PRESOL_NAME "/randomseed",
716  "the random seed used for randomization of tie breaking",
717  &presoldata->randomseed, FALSE, DEFAULT_RANDOMSEED, INT_MIN, INT_MAX, NULL, NULL) );
718 
719  if( DependentRows<double>::Enabled )
720  {
722  "presolving/" PRESOL_NAME "/detectlineardependency",
723  "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
724  &presoldata->detectlineardependency, TRUE, DEFAULT_DETECTLINDEP, 0, 2, NULL, NULL) );
725  }
726  else
727  presoldata->detectlineardependency = 0;
728 
730  "presolving/" PRESOL_NAME "/modifyconsfac",
731  "modify SCIP constraints when the number of nonzeros or rows is at most this factor "
732  "times the number of nonzeros or rows before presolving",
733  &presoldata->modifyconsfac, FALSE, DEFAULT_MODIFYCONSFAC, 0.0, 1.0, NULL, NULL) );
734 
736  "presolving/" PRESOL_NAME "/markowitztolerance",
737  "the markowitz tolerance used for substitutions",
738  &presoldata->markowitztolerance, FALSE, DEFAULT_MARKOWITZTOLERANCE, 0.0, 1.0, NULL, NULL) );
739 
741  "presolving/" PRESOL_NAME "/hugebound",
742  "absolute bound value that is considered too huge for activitity based calculations",
743  &presoldata->hugebound, FALSE, DEFAULT_HUGEBOUND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
744 
746  "presolving/" PRESOL_NAME "/enableparallelrows",
747  "should the parallel rows presolver be enabled within the presolve library?",
748  &presoldata->enableparallelrows, TRUE, DEFAULT_ENABLEPARALLELROWS, NULL, NULL) );
749 
751  "presolving/" PRESOL_NAME "/enabledomcol",
752  "should the dominated column presolver be enabled within the presolve library?",
753  &presoldata->enabledomcol, TRUE, DEFAULT_ENABLEDOMCOL, NULL, NULL) );
754 
756  "presolving/" PRESOL_NAME "/enabledualinfer",
757  "should the dualinfer presolver be enabled within the presolve library?",
758  &presoldata->enabledualinfer, TRUE, DEFAULT_ENABLEDUALINFER, NULL, NULL) );
759 
761  "presolving/" PRESOL_NAME "/enablemultiaggr",
762  "should the multi-aggregation presolver be enabled within the presolve library?",
763  &presoldata->enablemultiaggr, TRUE, DEFAULT_ENABLEMULTIAGGR, NULL, NULL) );
764 
766  "presolving/" PRESOL_NAME "/enableprobing",
767  "should the probing presolver be enabled within the presolve library?",
768  &presoldata->enableprobing, TRUE, DEFAULT_ENABLEPROBING, NULL, NULL) );
769 
771  "presolving/" PRESOL_NAME "/enablesparsify",
772  "should the sparsify presolver be enabled within the presolve library?",
773  &presoldata->enablesparsify, TRUE, DEFAULT_ENABLESPARSIFY, NULL, NULL) );
774 
775  return SCIP_OKAY;
776 }
777 
778 #endif
SCIP_Real SCIPfeastol(SCIP *scip)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4602
SCIP_Real SCIPepsilon(SCIP *scip)
struct SCIP_PresolData SCIP_PRESOLDATA
Definition: type_presol.h:42
#define PRESOL_NAME
MILP presolver that calls the presolve library on the constraint matrix.
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition: matrix.c:1620
#define PRESOL_MAXROUNDS
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:877
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition: matrix.c:1692
public methods for SCIP parameter handling
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5177
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition: scip_var.c:8617
public methods for memory management
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1820
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5294
public methods for timing
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition: matrix.c:1032
int SCIPgetNConss(SCIP *scip)
Definition: scip_prob.c:3036
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1986
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:360
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:216
#define FALSE
Definition: def.h:73
#define SCIP_DECL_PRESOLCOPY(x)
Definition: type_presol.h:51
public methods for presolving plugins
#define DEFAULT_RANDOMSEED
Definition: reader_scflp.c:107
SCIP_EXPORT SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17515
#define PRESOL_PRIORITY
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
public methods for problem variables
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:48
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:95
SCIP_EXPORT SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:78
public methods for SCIP variables
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
public methods for numerical tolerances
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1668
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2837
#define PRESOL_TIMING
#define SCIP_DECL_PRESOLEXEC(x)
Definition: type_presol.h:158
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1702
public methods for managing constraints
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
SCIP_EXPORT const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17017
SCIP_EXPORT SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17208
#define SCIP_DECL_PRESOLFREE(x)
Definition: type_presol.h:59
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition: presol.c:503
SCIP_RETCODE SCIPmultiaggregateVar(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_Real *scalars, SCIP_Real constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition: scip_var.c:8509
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1656
static SCIP_RETCODE presolve(SCIP *scip, SCIP_Bool *unbounded, SCIP_Bool *infeasible, SCIP_Bool *vanished)
Definition: scip_solve.c:1248
#define NULL
Definition: lpi_spx1.cpp:155
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition: scip_general.c:697
#define SCIP_CALL(x)
Definition: def.h:370
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
Definition: matrix.c:445
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1644
SCIP_RETCODE SCIPincludePresolMILP(SCIP *scip)
Definition: presol_milp.cpp:37
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLCOPY((*presolcopy)))
Definition: scip_presol.c:130
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1075
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition: presol.c:513
public methods for constraint handler plugins and constraints
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition: scip_param.c:298
#define PRESOL_DESC
SCIP_Real SCIPinfinity(SCIP *scip)
#define SCIP_Bool
Definition: def.h:70
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1065
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLINIT((*presolinit)))
Definition: scip_presol.c:162
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
#define SCIP_DECL_PRESOLINIT(x)
Definition: type_presol.h:67
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8250
Constraint handler for linear constraints in their most general form, .
public methods for matrix
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:130
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol, SCIP_DECL_PRESOLFREE((*presolfree)))
Definition: scip_presol.c:146
#define SCIP_REAL_MAX
Definition: def.h:164
public methods for presolvers
general public methods
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition: matrix.c:1714
public methods for random numbers
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
public methods for message output
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:74
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8077
union SCIP_Var::@14 data
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
Definition: scip_presol.c:95
public methods for message handling
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1791
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition: matrix.c:1738
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2764
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8590
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1110
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8375
public methods for global and local (sub)problems
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition: matrix.c:1564