SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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-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 presol_milp.cpp
26 * @brief MILP presolver
27 * @author Leona Gottwald
28 *
29 * Calls the presolve library and communicates (multi-)aggregations, fixings, and bound
30 * changes to SCIP by utilizing the postsolve information. Constraint changes can currently
31 * only be communicated by deleting all constraints and adding new ones.
32 *
33 * @todo add infrastructure to SCIP for handling parallel columns
34 * @todo better communication of constraint changes by adding more information to the postsolve structure
35 * @todo allow to pass additional external locks to the presolve library that are considered when doing reductions
36 *
37 */
38
39/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
40
41#include "scip/presol_milp.h"
42
43#ifndef SCIP_WITH_PAPILO
44
45/** creates the MILP presolver and includes it in SCIP */
47 SCIP* scip /**< SCIP data structure */
48 )
49{
50 assert(scip != NULL);
51 return SCIP_OKAY;
52}
53
54#else
55
56/* disable some warnings that come up in header files of PAPILOs dependencies */
57#ifdef __GNUC__
58#pragma GCC diagnostic ignored "-Wshadow"
59#pragma GCC diagnostic ignored "-Wctor-dtor-privacy"
60#pragma GCC diagnostic ignored "-Wredundant-decls"
61
62/* disable false warning, !3076, https://gcc.gnu.org/bugzilla/show_bug.cgi?id=106199 */
63#if __GNUC__ == 12 && __GNUC__MINOR__ <= 2
64#pragma GCC diagnostic ignored "-Wstringop-overflow"
65#endif
66#endif
67
68#include <assert.h>
69#include "scip/cons_linear.h"
70#include "scip/pub_matrix.h"
71#include "scip/pub_presol.h"
72#include "scip/pub_var.h"
73#include "scip/pub_cons.h"
74#include "scip/pub_message.h"
75#include "scip/scip_general.h"
76#include "scip/scip_presol.h"
77#include "scip/scip_var.h"
78#include "scip/scip_mem.h"
79#include "scip/scip_prob.h"
80#include "scip/scip_param.h"
81#include "scip/scip_cons.h"
82#include "scip/scip_numerics.h"
83#include "scip/scip_timing.h"
84#include "scip/scip_message.h"
86#include "papilo/core/Presolve.hpp"
87#include "papilo/core/ProblemBuilder.hpp"
88#include "papilo/Config.hpp"
89
90#define PRESOL_NAME "milp"
91#define PRESOL_DESC "MILP specific presolving methods"
92#define PRESOL_PRIORITY 9999999 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */
93#define PRESOL_MAXROUNDS -1 /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
94#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
95
96/* default parameter values */
97#define DEFAULT_THREADS 1 /**< maximum number of threads presolving may use (0: automatic) */
98#define DEFAULT_MAXFILLINPERSUBST 3 /**< maximal possible fillin for substitutions to be considered */
99#define DEFAULT_MAXSHIFTPERROW 10 /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
100#define DEFAULT_DETECTLINDEP 0 /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
101#define DEFAULT_MAXBADGESIZE_SEQ 15000 /**< the max badge size in Probing if PaPILO is executed in sequential mode */
102#define DEFAULT_MAXBADGESIZE_PAR -1 /**< the max badge size in Probing if PaPILO is executed in parallel mode */
103#define DEFAULT_INTERNAL_MAXROUNDS -1 /**< internal max rounds in PaPILO (-1: no limit, 0: model cleanup) */
104#define DEFAULT_RANDOMSEED 0 /**< the random seed used for randomization of tie breaking */
105#define DEFAULT_MODIFYCONSFAC 0.8 /**< modify SCIP constraints when the number of nonzeros or rows is at most this
106 * factor times the number of nonzeros or rows before presolving */
107#define DEFAULT_MARKOWITZTOLERANCE 0.01 /**< the markowitz tolerance used for substitutions */
108#define DEFAULT_VERBOSITY 0
109#define DEFAULT_HUGEBOUND 1e8 /**< absolute bound value that is considered too huge for activitity based calculations */
110#define DEFAULT_ENABLEPARALLELROWS TRUE /**< should the parallel rows presolver be enabled within the presolve library? */
111#define DEFAULT_ENABLEDOMCOL TRUE /**< should the dominated column presolver be enabled within the presolve library? */
112#define DEFAULT_ENABLEDUALINFER TRUE /**< should the dualinfer presolver be enabled within the presolve library? */
113#define DEFAULT_ENABLEMULTIAGGR TRUE /**< should the multi-aggregation presolver be enabled within the presolve library? */
114#define DEFAULT_ENABLEPROBING TRUE /**< should the probing presolver be enabled within the presolve library? */
115#define DEFAULT_ENABLESPARSIFY FALSE /**< should the sparsify presolver be enabled within the presolve library? */
116#define DEFAULT_FILENAME_PROBLEM "-" /**< default filename to store the instance before presolving */
117
118/*
119 * Data structures
120 */
121
122/** presolver data */
123struct SCIP_PresolData
124{
125 int lastncols; /**< the number of columns from the last call */
126 int lastnrows; /**< the number of rows from the last call */
127 int threads; /**< maximum number of threads presolving may use (0: automatic) */
128 int maxfillinpersubstitution; /**< maximal possible fillin for substitutions to be considered */
129 int maxbadgesizeseq; /**< the max badge size in Probing if PaPILO is called in sequential mode */
130 int maxbadgesizepar; /**< the max badge size in Probing if PaPILO is called in parallel mode */
131 int internalmaxrounds; /**< internal max rounds in PaPILO (-1: no limit, 0: model cleanup) */
132 int maxshiftperrow; /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
133 int detectlineardependency; /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
134 int randomseed; /**< the random seed used for randomization of tie breaking */
135 int verbosity;
136
137 SCIP_Bool enablesparsify; /**< should the sparsify presolver be enabled within the presolve library? */
138 SCIP_Bool enabledomcol; /**< should the dominated column presolver be enabled within the presolve library? */
139 SCIP_Bool enableprobing; /**< should the probing presolver be enabled within the presolve library? */
140 SCIP_Bool enabledualinfer; /**< should the dualinfer presolver be enabled within the presolve library? */
141 SCIP_Bool enablemultiaggr; /**< should the multi-aggregation presolver be enabled within the presolve library? */
142 SCIP_Bool enableparallelrows; /**< should the parallel rows presolver be enabled within the presolve library? */
143 SCIP_Real modifyconsfac; /**< modify SCIP constraints when the number of nonzeros or rows is at most this
144 * factor times the number of nonzeros or rows before presolving */
145 SCIP_Real markowitztolerance; /**< the markowitz tolerance used for substitutions */
146 SCIP_Real hugebound; /**< absolute bound value that is considered too huge for activitity based calculations */
147
148 char* filename = NULL; /**< filename to store the instance before presolving */
149};
150
151using namespace papilo;
152
153/*
154 * Local methods
155 */
156
157/** builds the presolvelib problem datastructure from the matrix */
158static
159Problem<SCIP_Real> buildProblem(
160 SCIP* scip, /**< SCIP data structure */
161 SCIP_MATRIX* matrix /**< initialized SCIP_MATRIX data structure */
162 )
163{
164 ProblemBuilder<SCIP_Real> builder;
165
166 /* build problem from matrix */
167 int nnz = SCIPmatrixGetNNonzs(matrix);
168 int ncols = SCIPmatrixGetNColumns(matrix);
169 int nrows = SCIPmatrixGetNRows(matrix);
170 builder.reserve(nnz, nrows, ncols);
171
172 /* set up columns */
173 builder.setNumCols(ncols);
174 for(int i = 0; i != ncols; ++i)
175 {
176 SCIP_VAR* var = SCIPmatrixGetVar(matrix, i);
177 SCIP_Real lb = SCIPvarGetLbGlobal(var);
178 SCIP_Real ub = SCIPvarGetUbGlobal(var);
179 builder.setColLb(i, lb);
180 builder.setColUb(i, ub);
181 builder.setColLbInf(i, SCIPisInfinity(scip, -lb));
182 builder.setColUbInf(i, SCIPisInfinity(scip, ub));
183#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
185 builder.setColImplInt(i, TRUE);
186 else
187 builder.setColIntegral(i, SCIPvarIsIntegral(var));
188#else
189 builder.setColIntegral(i, SCIPvarIsIntegral(var));
190#endif
191 builder.setObj(i, SCIPvarGetObj(var));
192 }
193
194 /* set up rows */
195 builder.setNumRows(nrows);
196 for(int i = 0; i != nrows; ++i)
197 {
198 int* rowcols = SCIPmatrixGetRowIdxPtr(matrix, i);
199 SCIP_Real* rowvals = SCIPmatrixGetRowValPtr(matrix, i);
200 int rowlen = SCIPmatrixGetRowNNonzs(matrix, i);
201 builder.addRowEntries(i, rowlen, rowcols, rowvals);
202
203 SCIP_Real lhs = SCIPmatrixGetRowLhs(matrix, i);
204 SCIP_Real rhs = SCIPmatrixGetRowRhs(matrix, i);
205 builder.setRowLhs(i, lhs);
206 builder.setRowRhs(i, rhs);
207 builder.setRowLhsInf(i, SCIPisInfinity(scip, -lhs));
208 builder.setRowRhsInf(i, SCIPisInfinity(scip, rhs));
209 }
210
211 /* init objective offset - the value itself is irrelevant */
212 builder.setObjOffset(0);
213
214 return builder.build();
215}
216
217/*
218 * Callback methods of presolver
219 */
220
221/** copy method for constraint handler plugins (called when SCIP copies plugins) */
222static
223SCIP_DECL_PRESOLCOPY(presolCopyMILP)
224{ /*lint --e{715}*/
226
227 return SCIP_OKAY;
228}
229
230/** destructor of presolver to free user data (called when SCIP is exiting) */
231static
232SCIP_DECL_PRESOLFREE(presolFreeMILP)
233{ /*lint --e{715}*/
234 SCIP_PRESOLDATA* data = SCIPpresolGetData(presol);
235 assert(data != NULL);
236
237 SCIPpresolSetData(presol, NULL);
239 return SCIP_OKAY;
240}
241
242/** initialization method of presolver (called after problem was transformed) */
243static
244SCIP_DECL_PRESOLINIT(presolInitMILP)
245{ /*lint --e{715}*/
246 SCIP_PRESOLDATA* data = SCIPpresolGetData(presol);
247 assert(data != NULL);
248
249 data->lastncols = -1;
250 data->lastnrows = -1;
251
252 return SCIP_OKAY;
253}
254
255/** execution method of presolver */
256static
257SCIP_DECL_PRESOLEXEC(presolExecMILP)
258{ /*lint --e{715}*/
259 SCIP_MATRIX* matrix;
260 SCIP_PRESOLDATA* data;
261 SCIP_Bool initialized;
262 SCIP_Bool complete;
263 SCIP_Bool infeasible;
264 SCIP_Real timelimit;
265
267
268 data = SCIPpresolGetData(presol);
269
270 int nvars = SCIPgetNVars(scip);
271 int nconss = SCIPgetNConss(scip);
272
273 /* run only if the problem size reduced by some amount since the last call or if it is the first call */
274 if( data->lastncols != -1 && data->lastnrows != -1 &&
275 nvars > data->lastncols * 0.85 &&
276 nconss > data->lastnrows * 0.85 )
277 return SCIP_OKAY;
278
279 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
280 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
281
282 /* if infeasibility was detected during matrix creation, return here */
283 if( infeasible )
284 {
285 if( initialized )
286 SCIPmatrixFree(scip, &matrix);
287
289 return SCIP_OKAY;
290 }
291
292 /* we only work on pure MIPs, also disable to try building the matrix again if it failed once */
293 if( !initialized || !complete )
294 {
295 data->lastncols = 0;
296 data->lastnrows = 0;
297
298 if( initialized )
299 SCIPmatrixFree(scip, &matrix);
300
301 return SCIP_OKAY;
302 }
303
304 /* only allow communication of constraint modifications by deleting all constraints when some already have been upgraded */
305 SCIP_CONSHDLR* linconshdlr = SCIPfindConshdlr(scip, "linear");
306 assert(linconshdlr != NULL);
307 bool allowconsmodification = (SCIPconshdlrGetNCheckConss(linconshdlr) == SCIPmatrixGetNRows(matrix));
308
309 Problem<SCIP_Real> problem = buildProblem(scip, matrix);
310 Presolve<SCIP_Real> presolve;
311
312 /* store current numbers of aggregations, fixings, and changed bounds for statistics */
313 int oldnaggrvars = *naggrvars;
314 int oldnfixedvars = *nfixedvars;
315 int oldnchgbds = *nchgbds;
316
317 /* important so that SCIP does not throw an error, e.g. when an integer variable is substituted
318 * into a knapsack constraint */
319 presolve.getPresolveOptions().substitutebinarieswithints = false;
320
321 /* currently these changes cannot be communicated to SCIP correctly since a constraint needs
322 * to be modified in the cases where slackvariables are removed from constraints but for the
323 * presolve library those look like normal substitution on the postsolve stack */
324 presolve.getPresolveOptions().removeslackvars = false;
325
326 /* communicate the SCIP parameters to the presolve library */
327 presolve.getPresolveOptions().maxfillinpersubstitution = data->maxfillinpersubstitution;
328 presolve.getPresolveOptions().markowitz_tolerance = data->markowitztolerance;
329 presolve.getPresolveOptions().maxshiftperrow = data->maxshiftperrow;
330 presolve.getPresolveOptions().hugeval = data->hugebound;
331
332 /* removal of linear dependent equations has only an effect when constraint modifications are communicated */
333 presolve.getPresolveOptions().detectlindep = allowconsmodification ? data->detectlineardependency : 0;
334
335 /* communicate the random seed */
336 presolve.getPresolveOptions().randomseed = SCIPinitializeRandomSeed(scip, (unsigned int)data->randomseed);
337
338#ifdef PAPILO_TBB
339 /* set number of threads to be used for presolve */
340 presolve.getPresolveOptions().threads = data->threads;
341#else
342 if (data->threads != DEFAULT_THREADS)
344 "PaPILO can utilize only multiple threads if it is build with TBB.\n");
345 presolve.getPresolveOptions().threads = 1;
346#endif
347
348#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 3)
349 presolve.getPresolveOptions().maxrounds = data->internalmaxrounds;
350#endif
351
352 /* disable dual reductions that are not permitted */
353 if( !complete )
354 presolve.getPresolveOptions().dualreds = 0;
355 else if( SCIPallowStrongDualReds(scip) )
356 presolve.getPresolveOptions().dualreds = 2;
357 else if( SCIPallowWeakDualReds(scip) )
358 presolve.getPresolveOptions().dualreds = 1;
359 else
360 presolve.getPresolveOptions().dualreds = 0;
361
362 /* set up the presolvers that shall participate */
363 using uptr = std::unique_ptr<PresolveMethod<SCIP_Real>>;
364
365 /* fast presolvers*/
366 presolve.addPresolveMethod( uptr( new SingletonCols<SCIP_Real>() ) );
367 presolve.addPresolveMethod( uptr( new CoefficientStrengthening<SCIP_Real>() ) );
368 presolve.addPresolveMethod( uptr( new ConstraintPropagation<SCIP_Real>() ) );
369
370 /* medium presolver */
371 presolve.addPresolveMethod( uptr( new SimpleProbing<SCIP_Real>() ) );
372 if( data->enableparallelrows )
373 presolve.addPresolveMethod( uptr( new ParallelRowDetection<SCIP_Real>() ) );
374 /* todo: parallel cols cannot be handled by SCIP currently
375 * addPresolveMethod( uptr( new ParallelColDetection<SCIP_Real>() ) ); */
376 presolve.addPresolveMethod( uptr( new SingletonStuffing<SCIP_Real>() ) );
377#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
378 DualFix<SCIP_Real> *dualfix = new DualFix<SCIP_Real>();
379 dualfix->set_fix_to_infinity_allowed(false);
380 presolve.addPresolveMethod( uptr( dualfix ) );
381#else
382 presolve.addPresolveMethod( uptr( new DualFix<SCIP_Real>() ) );
383#endif
384 presolve.addPresolveMethod( uptr( new FixContinuous<SCIP_Real>() ) );
385 presolve.addPresolveMethod( uptr( new SimplifyInequalities<SCIP_Real>() ) );
386 presolve.addPresolveMethod( uptr( new SimpleSubstitution<SCIP_Real>() ) );
387
388 /* exhaustive presolvers*/
389 presolve.addPresolveMethod( uptr( new ImplIntDetection<SCIP_Real>() ) );
390 if( data->enabledualinfer )
391 presolve.addPresolveMethod( uptr( new DualInfer<SCIP_Real>() ) );
392 if( data->enableprobing )
393 {
394#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
395 Probing<SCIP_Real> *probing = new Probing<SCIP_Real>();
396 if( presolve.getPresolveOptions().runs_sequential() )
397 {
398 probing->set_max_badge_size( data->maxbadgesizeseq );
399 }
400 else
401 {
402 probing->set_max_badge_size( data->maxbadgesizepar );
403 }
404 presolve.addPresolveMethod( uptr( probing ) );
405
406#else
407 presolve.addPresolveMethod( uptr( new Probing<SCIP_Real>() ) );
408 if( data->maxbadgesizeseq != DEFAULT_MAXBADGESIZE_SEQ )
410 " The parameter 'presolving/milp/maxbadgesizeseq' can only be used with PaPILO 2.1.0 or later versions.\n");
411
412 if( data->maxbadgesizepar != DEFAULT_MAXBADGESIZE_PAR )
414 " The parameter 'presolving/milp/maxbadgesizepar' can only be used with PaPILO 2.1.0 or later versions.\n");
415
416#endif
417 }
418 if( data->enabledomcol )
419 presolve.addPresolveMethod( uptr( new DominatedCols<SCIP_Real>() ) );
420 if( data->enablemultiaggr )
421 presolve.addPresolveMethod( uptr( new Substitution<SCIP_Real>() ) );
422 if( data->enablesparsify )
423 presolve.addPresolveMethod( uptr( new Sparsify<SCIP_Real>() ) );
424
425 /* set tolerances */
426 presolve.getPresolveOptions().feastol = SCIPfeastol(scip);
427 presolve.getPresolveOptions().epsilon = SCIPepsilon(scip);
428
429 /* adjust output settings of presolve library */
430#ifdef SCIP_PRESOLLIB_ENABLE_OUTPUT
431 problem.setName(SCIPgetProbName(scip));
432#else
433 presolve.setVerbosityLevel((VerbosityLevel) data->verbosity);
434#endif
435
436 /* communicate the time limit */
437 SCIP_CALL( SCIPgetRealParam(scip, "limits/time", &timelimit) );
438 if( !SCIPisInfinity(scip, timelimit) )
439 presolve.getPresolveOptions().tlim = timelimit - SCIPgetSolvingTime(scip);
440
441 if( 0 != strncmp(data->filename, DEFAULT_FILENAME_PROBLEM, strlen(DEFAULT_FILENAME_PROBLEM)) )
442 {
444 " writing transformed problem to %s (only enforced constraints)\n", data->filename);
445 SCIP_CALL(SCIPwriteTransProblem(scip, data->filename, NULL, FALSE));
446 }
447
448 /* call the presolving */
450 " (%.1fs) running MILP presolver\n", SCIPgetSolvingTime(scip));
451 int oldnnz = problem.getConstraintMatrix().getNnz();
452
453 /*call presolving without storing information for dual postsolve*/
454#if (PAPILO_VERSION_MAJOR >= 2)
455 PresolveResult<SCIP_Real> res = presolve.apply(problem, false);
456#else
457 PresolveResult<SCIP_Real> res = presolve.apply(problem);
458#endif
459 data->lastncols = problem.getNCols();
460 data->lastnrows = problem.getNRows();
461
462 /* evaluate the result */
463 switch(res.status)
464 {
465 case PresolveStatus::kInfeasible:
468 " (%.1fs) MILP presolver detected infeasibility\n",
470 SCIPmatrixFree(scip, &matrix);
471 return SCIP_OKAY;
472 case PresolveStatus::kUnbndOrInfeas:
473 case PresolveStatus::kUnbounded:
476 " (%.1fs) MILP presolver detected unboundedness\n",
478 SCIPmatrixFree(scip, &matrix);
479 return SCIP_OKAY;
480 case PresolveStatus::kUnchanged:
482 data->lastncols = nvars;
483 data->lastnrows = nconss;
485 " (%.1fs) MILP presolver found nothing\n",
487 SCIPmatrixFree(scip, &matrix);
488 return SCIP_OKAY;
489 case PresolveStatus::kReduced:
490 data->lastncols = problem.getNCols();
491 data->lastnrows = problem.getNRows();
493 }
494
495 /* result indicated success, now populate the changes into the SCIP structures */
496
497 /* tighten bounds of variables that are still present after presolving */
498 VariableDomains<SCIP_Real>& varDomains = problem.getVariableDomains();
499 for( int i = 0; i != problem.getNCols(); ++i )
500 {
501 assert( ! varDomains.flags[i].test(ColFlag::kInactive) );
502 SCIP_VAR* var = SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[i]);
503 if( !varDomains.flags[i].test(ColFlag::kLbInf) )
504 {
505 SCIP_Bool infeas;
506 SCIP_Bool tightened;
507 SCIP_CALL( SCIPtightenVarLb(scip, var, varDomains.lower_bounds[i], TRUE, &infeas, &tightened) );
508
509 if( tightened )
510 *nchgbds += 1;
511
512 if( infeas )
513 {
515 break;
516 }
517 }
518
519 if( !varDomains.flags[i].test(ColFlag::kUbInf) )
520 {
521 SCIP_Bool infeas;
522 SCIP_Bool tightened;
523 SCIP_CALL( SCIPtightenVarUb(scip, var, varDomains.upper_bounds[i], TRUE, &infeas, &tightened) );
524
525 if( tightened )
526 *nchgbds += 1;
527
528 if( infeas )
529 {
531 break;
532 }
533 }
534 }
535
536 if( *result == SCIP_CUTOFF )
537 {
539 " (%.1fs) MILP presolver detected infeasibility\n",
541 SCIPmatrixFree(scip, &matrix);
542 return SCIP_OKAY;
543 }
544
545 /* transfer variable fixings and aggregations */
546 std::vector<SCIP_VAR*> tmpvars;
547 std::vector<SCIP_Real> tmpvals;
548
549 /* if the size of the problem decreased by a sufficient factor, create all constraints from scratch if allowed */
550 int newnnz = problem.getConstraintMatrix().getNnz();
551 bool constraintsReplaced = false;
552 if( newnnz == 0 || (allowconsmodification &&
553 (problem.getNCols() <= data->modifyconsfac * SCIPmatrixGetNColumns(matrix) ||
554 problem.getNRows() <= data->modifyconsfac * SCIPmatrixGetNRows(matrix) ||
555 newnnz <= data->modifyconsfac * oldnnz)) )
556 {
557 int oldnrows = SCIPmatrixGetNRows(matrix);
558 int newnrows = problem.getNRows();
559
560 constraintsReplaced = true;
561
562 /* capture constraints that are still present in the problem after presolve */
563 for( int i = 0; i < newnrows; ++i )
564 {
565 SCIP_CONS* c = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
567 }
568
569 /* delete all constraints */
570 *ndelconss += oldnrows;
571 *naddconss += newnrows;
572
573 for( int i = 0; i < oldnrows; ++i )
574 {
576 }
577
578 /* now loop over rows of presolved problem and create them as new linear constraints,
579 * then release the old constraint after its name was passed to the new constraint */
580 const Vec<RowFlags>& rflags = problem.getRowFlags();
581 const auto& consmatrix = problem.getConstraintMatrix();
582 for( int i = 0; i < newnrows; ++i )
583 {
584 auto rowvec = consmatrix.getRowCoefficients(i);
585 const int* rowcols = rowvec.getIndices();
586 /* SCIPcreateConsBasicLinear() requires a non const pointer */
587 SCIP_Real* rowvals = const_cast<SCIP_Real*>(rowvec.getValues());
588 int rowlen = rowvec.getLength();
589
590 /* retrieve SCIP compatible left and right hand sides */
591 SCIP_Real lhs = rflags[i].test(RowFlag::kLhsInf) ? - SCIPinfinity(scip) : consmatrix.getLeftHandSides()[i];
592 SCIP_Real rhs = rflags[i].test(RowFlag::kRhsInf) ? SCIPinfinity(scip) : consmatrix.getRightHandSides()[i];
593
594 /* create variable array matching the value array */
595 tmpvars.clear();
596 tmpvars.reserve(rowlen);
597 for( int j = 0; j < rowlen; ++j )
598 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[rowcols[j]]));
599
600 /* create and add new constraint with name of old constraint */
601 SCIP_CONS* oldcons = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
602 SCIP_CONS* cons;
603 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, SCIPconsGetName(oldcons), rowlen, tmpvars.data(), rowvals, lhs, rhs) );
604 SCIP_CALL( SCIPaddCons(scip, cons) );
605
606 /* release old and new constraint */
607 SCIP_CALL( SCIPreleaseCons(scip, &oldcons) );
608 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
609 }
610 }
611
612 /* PaPILO's aggregations are valid regarding the constraints as they were presolved by PaPILO.
613 * If coefficients were changed, but constraints in SCIP are not replaced by those from PaPILO,
614 * then it can not be guaranteed that the bounds of multiaggregated variables will be enforced,
615 * i.e., will be implied by the constraints in SCIP (see also #3704).
616 * Only for variable aggregations, SCIP will ensure this by tightening the bounds on the aggregation
617 * variable as part of SCIPaggregateVars(). For multiaggregations, we will only accept those
618 * where we can be sure with a simple check that the bounds on the aggregated variable are implied.
619 */
620 bool checkmultaggr =
621#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 3)
622 presolve.getStatistics().single_matrix_coefficient_changes > 0
623#else
624 presolve.getStatistics().ncoefchgs > 0
625#endif
626 && !constraintsReplaced;
627
628 /* loop over res.postsolve and add all fixed variables and aggregations to scip */
629 for( std::size_t i = 0; i != res.postsolve.types.size(); ++i )
630 {
631 ReductionType type = res.postsolve.types[i];
632 int first = res.postsolve.start[i];
633 int last = res.postsolve.start[i + 1];
634
635 switch( type )
636 {
637 case ReductionType::kFixedCol:
638 {
639 SCIP_Bool infeas;
640 SCIP_Bool fixed;
641 int col = res.postsolve.indices[first];
642
643 SCIP_VAR* var = SCIPmatrixGetVar(matrix, col);
644
645 SCIP_Real value = res.postsolve.values[first];
646
647 SCIP_CALL( SCIPfixVar(scip, var, value, &infeas, &fixed) );
648 *nfixedvars += 1;
649
650 assert(!infeas);
651 /* SCIP has different rules for aggregating variables than PaPILO: therefore the variable PaPILO
652 * tries to fix now may have been aggregated by SCIP before. Additionally, after aggregation SCIP
653 * sometimes performs bound tightening resulting in possible fixings. These cases need to be excluded. */
656 break;
657 }
658/*
659 * Dual-postsolving in PaPILO required introducing a postsolve-type for substitution with additional information.
660 * Further, the different Substitution-postsolving types store the required postsolving data differently (in different order) in the postsolving stack.
661 * Therefore, we need to distinguish how to parse the required data (rowLength, col, side, startRowCoefficients, lastRowCoefficients) from the postsolving stack.
662 * If these values are accessed, the procedure is the same for both.
663 */
664#if (PAPILO_VERSION_MAJOR >= 2)
665 case ReductionType::kSubstitutedColWithDual:
666#endif
667 case ReductionType::kSubstitutedCol:
668 {
669 int col = 0;
670 SCIP_Real side = 0;
671
672 int rowlen = 0;
673 int startRowCoefficients = 0;
674 int lastRowCoefficients = 0;
675
676 if( type == ReductionType::kSubstitutedCol )
677 {
678 rowlen = last - first - 1;
679 col = res.postsolve.indices[first];
680 side = res.postsolve.values[first];
681
682 startRowCoefficients = first + 1;
683 lastRowCoefficients = last;
684 }
685#if (PAPILO_VERSION_MAJOR >= 2)
686 if( type == ReductionType::kSubstitutedColWithDual )
687 {
688 rowlen = (int) res.postsolve.values[first];
689 col = res.postsolve.indices[first + 3 + rowlen];
690 side = res.postsolve.values[first + 1];
691
692 startRowCoefficients = first + 3;
693 lastRowCoefficients = first + 3 + rowlen;
694
695 assert(side == res.postsolve.values[first + 2]);
696 assert(res.postsolve.indices[first + 1] == 0);
697 assert(res.postsolve.indices[first + 2] == 0);
698 }
699 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
700#else
701 assert( type == ReductionType::kSubstitutedCol );
702#endif
703 SCIP_Bool infeas;
704 SCIP_Bool aggregated;
705 SCIP_Bool redundant = FALSE;
706 SCIP_Real constant = 0.0;
707 if( rowlen == 2 )
708 {
709 SCIP_Real updatedSide;
710 SCIP_VAR* varx = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients]);
711 SCIP_VAR* vary = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients + 1]);
712 SCIP_Real scalarx = res.postsolve.values[startRowCoefficients];
713 SCIP_Real scalary = res.postsolve.values[startRowCoefficients + 1];
714
715 SCIP_CALL( SCIPgetProbvarSum(scip, &varx, &scalarx, &constant) );
717
718 SCIP_CALL( SCIPgetProbvarSum(scip, &vary, &scalary, &constant) );
720
721 updatedSide = side - constant;
722
723 SCIP_CALL( SCIPaggregateVars(scip, varx, vary, scalarx, scalary, updatedSide, &infeas, &redundant, &aggregated) );
724 }
725 else
726 {
727 SCIP_Real colCoef = 0.0;
728 SCIP_Real updatedSide;
729 SCIP_Bool checklbimplied;
730 SCIP_Bool checkubimplied;
731 SCIP_Real impliedlb;
732 SCIP_Real impliedub;
733 int j;
734
735 for( j = startRowCoefficients; j < lastRowCoefficients; ++j )
736 {
737 if( res.postsolve.indices[j] == col )
738 {
739 colCoef = res.postsolve.values[j];
740 break;
741 }
742 }
743
744 tmpvars.clear();
745 tmpvals.clear();
746 tmpvars.reserve(rowlen);
747 tmpvals.reserve(rowlen);
748
749 assert(colCoef != 0.0);
750 SCIP_VAR* aggrvar = SCIPmatrixGetVar(matrix, col);
751
752 SCIP_CALL( SCIPgetProbvarSum(scip, &aggrvar, &colCoef, &constant) );
754
755 updatedSide = side - constant;
756
757 /* we need to check whether lb/ub on aggrvar is implied by bounds of other variables in multiaggregation
758 * if checkmultaggr is TRUE and the lb/ub is finite
759 * it should be sufficient to ensure global bounds on aggrvar (and as we are in presolve, local=global anyway)
760 */
761 checklbimplied = checkmultaggr && !SCIPisInfinity(scip, -SCIPvarGetLbGlobal(aggrvar));
762 checkubimplied = checkmultaggr && !SCIPisInfinity(scip, SCIPvarGetUbGlobal(aggrvar));
763 impliedlb = impliedub = updatedSide / colCoef;
764
765 for( j = startRowCoefficients; j < lastRowCoefficients; ++j )
766 {
767 SCIP_Real coef;
768 SCIP_VAR* var;
769
770 if( res.postsolve.indices[j] == col )
771 continue;
772
773 coef = - res.postsolve.values[j] / colCoef;
774 var = SCIPmatrixGetVar(matrix, res.postsolve.indices[j]);
775
776 if( checklbimplied )
777 {
778 if( coef > 0.0 )
779 {
780 /* if impliedlb will be -infinity, then we can give up: we cannot use this mutiaggregation */
782 break;
783 else
784 impliedlb += coef * SCIPvarGetLbLocal(var);
785 }
786 else
787 {
789 break;
790 else
791 impliedlb += coef * SCIPvarGetUbLocal(var);
792 }
793 }
794
795 if( checkubimplied )
796 {
797 if( coef > 0.0 )
798 {
800 break;
801 else
802 impliedub += coef * SCIPvarGetUbLocal(var);
803 }
804 else
805 {
807 break;
808 else
809 impliedub += coef * SCIPvarGetLbLocal(var);
810 }
811 }
812
813 tmpvals.push_back(coef);
814 tmpvars.push_back(var);
815 }
816
817 /* if implied bounds are not sufficient to ensure bounds on aggrvar, then we cannot use the multiaggregation */
818 if( j < lastRowCoefficients )
819 break;
820
821 if( checklbimplied && SCIPisGT(scip, SCIPvarGetLbGlobal(aggrvar), impliedlb) )
822 break;
823
824 if( checkubimplied && SCIPisLT(scip, SCIPvarGetUbGlobal(aggrvar), impliedub) )
825 break;
826
827 SCIP_CALL( SCIPmultiaggregateVar(scip, aggrvar, tmpvars.size(),
828 tmpvars.data(), tmpvals.data(), updatedSide / colCoef, &infeas, &aggregated) );
829 }
830
831 if( aggregated )
832 *naggrvars += 1;
833 else if( constraintsReplaced && !redundant )
834 {
835 /* if the constraints where replaced, we need to add the failed substitution as an equality to SCIP */
836 tmpvars.clear();
837 tmpvals.clear();
838 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
839 {
840 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
841 tmpvals.push_back(res.postsolve.values[j]);
842 }
843
844 SCIP_CONS* cons;
845 String name = fmt::format("{}_failed_aggregation_equality", SCIPvarGetName(SCIPmatrixGetVar(matrix, col)));
846 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name.c_str(),
847 tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
848 SCIP_CALL( SCIPaddCons(scip, cons) );
849 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
850 *naddconss += 1;
851 }
852
853 if( infeas )
854 {
856 break;
857 }
858
859 break;
860 }
861 case ReductionType::kParallelCol:
862 return SCIP_INVALIDRESULT;
863#if (PAPILO_VERSION_MAJOR <= 1 && PAPILO_VERSION_MINOR==0)
864#else
865 case ReductionType::kFixedInfCol: {
866 /* todo: currently SCIP can not handle this kind of reduction (see issue #3391) */
867 assert(false);
868 if(!constraintsReplaced)
869 continue;
870 SCIP_Bool infeas;
871 SCIP_Bool fixed;
872 SCIP_Real value = SCIPinfinity(scip);
873
874 int column = res.postsolve.indices[first];
875 bool is_negative_infinity = res.postsolve.values[first] < 0;
876 SCIP_VAR* column_variable = SCIPmatrixGetVar(matrix, column);
877
878 if( is_negative_infinity )
879 {
880 value = -SCIPinfinity(scip);
881 }
882
883 SCIP_CALL( SCIPfixVar(scip, column_variable, value, &infeas, &fixed) );
884 *nfixedvars += 1;
885
886 assert(!infeas);
887 assert(fixed);
888 break;
889 }
890#endif
891#if (PAPILO_VERSION_MAJOR >= 2)
892 case ReductionType::kVarBoundChange :
893 case ReductionType::kRedundantRow :
894 case ReductionType::kRowBoundChange :
895 case ReductionType::kReasonForRowBoundChangeForcedByRow :
896 case ReductionType::kRowBoundChangeForcedByRow :
897 case ReductionType::kSaveRow :
898 case ReductionType::kReducedBoundsCost :
899 case ReductionType::kColumnDualValue :
900 case ReductionType::kRowDualValue :
901 case ReductionType::kCoefficientChange :
902 // dual ReductionTypes should be only calculated for dual reductions and should not appear for MIP
903 SCIPerrorMessage("PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
904 SCIPABORT(); /*lint --e{527}*/
905 break;
906#endif
907 default:
908 SCIPdebugMsg(scip, "PaPILO returned unknown data type: \n" );
909 continue;
910 }
911 }
912
913 /* finish with a final verb message and return */
915 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
916 SCIPgetSolvingTime(scip), presolve.getStatistics().nrounds, *naggrvars - oldnaggrvars,
917 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds);
918
919 /* free the matrix */
920 assert(initialized);
921 SCIPmatrixFree(scip, &matrix);
922
923 return SCIP_OKAY;
924}
925
926
927/*
928 * presolver specific interface methods
929 */
930
931/** creates the xyz presolver and includes it in SCIP */
933 SCIP* scip /**< SCIP data structure */
934 )
935{
936 SCIP_PRESOLDATA* presoldata;
937 SCIP_PRESOL* presol;
938
939#if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
940 String name = fmt::format("PaPILO {}.{}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH, PAPILO_VERSION_TWEAK);
941#else
942 String name = fmt::format("PaPILO {}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH);
943#endif
944
945#if defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
946 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: {}]", PAPILO_GITHASH);
947#elif !defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
948 String desc("parallel presolve for integer and linear optimization (github.com/scipopt/papilo)");
949#elif defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
950 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: {}]", PAPILO_GITHASH);
951#elif !defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
952 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB)");
953#endif
954
955 /* add external code info for the presolve library */
956 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, name.c_str(), desc.c_str()) );
957
958 /* create MILP presolver data */
959 presoldata = NULL;
960 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
961 BMSclearMemory(presoldata);
962
963 presol = NULL;
964
965 /* include presolver */
967 presolExecMILP,
968 presoldata) );
969
970 assert(presol != NULL);
971
972 /* set non fundamental callbacks via setter functions */
973 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyMILP) );
974 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeMILP) );
975 SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitMILP) );
976
977 /* add MILP presolver parameters */
979 "presolving/" PRESOL_NAME "/threads",
980 "maximum number of threads presolving may use (0: automatic)",
981 &presoldata->threads, FALSE, DEFAULT_THREADS, 0, INT_MAX, NULL, NULL) );
982
984 "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
985 "maximal possible fillin for substitutions to be considered",
986 &presoldata->maxfillinpersubstitution, FALSE, DEFAULT_MAXFILLINPERSUBST, INT_MIN, INT_MAX, NULL, NULL) );
987
989 "presolving/" PRESOL_NAME "/maxshiftperrow",
990 "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
991 &presoldata->maxshiftperrow, TRUE, DEFAULT_MAXSHIFTPERROW, 0, INT_MAX, NULL, NULL) );
992
994 "presolving/" PRESOL_NAME "/randomseed",
995 "the random seed used for randomization of tie breaking",
996 &presoldata->randomseed, FALSE, DEFAULT_RANDOMSEED, INT_MIN, INT_MAX, NULL, NULL) );
997
998 if( DependentRows<double>::Enabled )
999 {
1001 "presolving/" PRESOL_NAME "/detectlineardependency",
1002 "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
1003 &presoldata->detectlineardependency, TRUE, DEFAULT_DETECTLINDEP, 0, 2, NULL, NULL) );
1004 }
1005 else
1006 presoldata->detectlineardependency = 0;
1007
1009 "presolving/" PRESOL_NAME "/modifyconsfac",
1010 "modify SCIP constraints when the number of nonzeros or rows is at most this factor "
1011 "times the number of nonzeros or rows before presolving",
1012 &presoldata->modifyconsfac, FALSE, DEFAULT_MODIFYCONSFAC, 0.0, 1.0, NULL, NULL) );
1013
1015 "presolving/" PRESOL_NAME "/markowitztolerance",
1016 "the markowitz tolerance used for substitutions",
1017 &presoldata->markowitztolerance, FALSE, DEFAULT_MARKOWITZTOLERANCE, 0.0, 1.0, NULL, NULL) );
1018
1020 "presolving/" PRESOL_NAME "/hugebound",
1021 "absolute bound value that is considered too huge for activitity based calculations",
1022 &presoldata->hugebound, FALSE, DEFAULT_HUGEBOUND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1023
1024#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
1025 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/maxbadgesizeseq",
1026 "maximal badge size in Probing in PaPILO if PaPILO is executed in sequential mode",
1027 &presoldata->maxbadgesizeseq, FALSE, DEFAULT_MAXBADGESIZE_SEQ, -1, INT_MAX, NULL, NULL));
1028
1029 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/maxbadgesizepar",
1030 "maximal badge size in Probing in PaPILO if PaPILO is executed in parallel mode",
1031 &presoldata->maxbadgesizepar, FALSE, DEFAULT_MAXBADGESIZE_PAR, -1, INT_MAX, NULL, NULL));
1032#else
1033 presoldata->maxbadgesizeseq = DEFAULT_MAXBADGESIZE_SEQ;
1034 presoldata->maxbadgesizepar = DEFAULT_MAXBADGESIZE_PAR;
1035#endif
1036
1037#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 3)
1038 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/internalmaxrounds",
1039 "internal maxrounds for each milp presolving (-1: no limit, 0: model cleanup)",
1040 &presoldata->internalmaxrounds, TRUE, DEFAULT_INTERNAL_MAXROUNDS, -1, INT_MAX, NULL, NULL));
1041#else
1042 presoldata->internalmaxrounds = DEFAULT_INTERNAL_MAXROUNDS;
1043#endif
1044
1046 "presolving/" PRESOL_NAME "/enableparallelrows",
1047 "should the parallel rows presolver be enabled within the presolve library?",
1048 &presoldata->enableparallelrows, TRUE, DEFAULT_ENABLEPARALLELROWS, NULL, NULL) );
1049
1051 "presolving/" PRESOL_NAME "/enabledomcol",
1052 "should the dominated column presolver be enabled within the presolve library?",
1053 &presoldata->enabledomcol, TRUE, DEFAULT_ENABLEDOMCOL, NULL, NULL) );
1054
1056 "presolving/" PRESOL_NAME "/enabledualinfer",
1057 "should the dualinfer presolver be enabled within the presolve library?",
1058 &presoldata->enabledualinfer, TRUE, DEFAULT_ENABLEDUALINFER, NULL, NULL) );
1059
1061 "presolving/" PRESOL_NAME "/enablemultiaggr",
1062 "should the multi-aggregation presolver be enabled within the presolve library?",
1063 &presoldata->enablemultiaggr, TRUE, DEFAULT_ENABLEMULTIAGGR, NULL, NULL) );
1064
1066 "presolving/" PRESOL_NAME "/enableprobing",
1067 "should the probing presolver be enabled within the presolve library?",
1068 &presoldata->enableprobing, TRUE, DEFAULT_ENABLEPROBING, NULL, NULL) );
1069
1071 "presolving/" PRESOL_NAME "/enablesparsify",
1072 "should the sparsify presolver be enabled within the presolve library?",
1073 &presoldata->enablesparsify, TRUE, DEFAULT_ENABLESPARSIFY, NULL, NULL) );
1074
1075 SCIP_CALL( SCIPaddStringParam(scip, "presolving/" PRESOL_NAME "/probfilename",
1076 "filename to store the problem before MILP presolving starts (only enforced constraints)",
1077 &presoldata->filename, TRUE, DEFAULT_FILENAME_PROBLEM, NULL, NULL) );
1078
1079 SCIP_CALL(SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/verbosity",
1080 "verbosity level of PaPILO (0: quiet, 1: errors, 2: warnings, 3: normal, 4: detailed)",
1081 &presoldata->verbosity, FALSE, DEFAULT_VERBOSITY, 0, 4, NULL, NULL));
1082
1083 return SCIP_OKAY;
1084}
1085
1086#endif
Constraint handler for linear constraints in their most general form, .
#define NULL
Definition def.h:267
#define SCIP_REAL_MAX
Definition def.h:174
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define SCIPABORT()
Definition def.h:346
#define SCIP_CALL(x)
Definition def.h:374
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)
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1067
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2843
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3042
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition scip_prob.c:648
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
#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 SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:194
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 SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
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
SCIP_RETCODE SCIPincludePresolMILP(SCIP *scip)
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4656
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8214
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1174
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1139
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition presol.c:522
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition presol.c:512
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
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)
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5202
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
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:8400
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17926
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5319
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17584
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition scip_var.c:1793
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
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:8534
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:17610
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8275
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition scip_var.c:8655
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:8628
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
return SCIP_OKAY
int c
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition matrix.c:1778
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1708
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1742
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1684
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1754
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:454
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition matrix.c:1604
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1860
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition matrix.c:1072
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1660
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1696
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition matrix.c:1732
#define BMSclearMemory(ptr)
Definition memory.h:129
#define PRESOL_NAME
#define PRESOL_PRIORITY
#define PRESOL_MAXROUNDS
#define PRESOL_TIMING
#define PRESOL_DESC
MILP presolver that calls the presolve library on the constraint matrix.
public methods for managing constraints
public methods for matrix
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public methods for presolvers
public methods for problem variables
#define DEFAULT_RANDOMSEED
public methods for constraint handler plugins and constraints
general public methods
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for random numbers
static SCIP_RETCODE presolve(SCIP *scip, SCIP_Bool *unbounded, SCIP_Bool *infeasible, SCIP_Bool *vanished)
public methods for timing
public methods for SCIP variables
@ SCIP_VERBLEVEL_HIGH
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
struct SCIP_PresolData SCIP_PRESOLDATA
Definition type_presol.h:51
#define SCIP_DECL_PRESOLFREE(x)
Definition type_presol.h:68
#define SCIP_DECL_PRESOLINIT(x)
Definition type_presol.h:76
#define SCIP_DECL_PRESOLEXEC(x)
@ SCIP_DIDNOTRUN
Definition type_result.h:42
@ SCIP_CUTOFF
Definition type_result.h:48
@ SCIP_DIDNOTFIND
Definition type_result.h:44
@ SCIP_UNBOUNDED
Definition type_result.h:47
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_INVALIDRESULT
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_IMPLINT
Definition type_var.h:64
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54
@ SCIP_VARSTATUS_NEGATED
Definition type_var.h:55
@ SCIP_VARSTATUS_AGGREGATED
Definition type_var.h:53