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-2026 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 * @author Alexander Hoen
29 *
30 * Calls the presolve library and communicates (multi-)aggregations, fixings, and bound
31 * changes to SCIP by utilizing the postsolve information. Constraint changes can currently
32 * only be communicated by deleting all constraints and adding new ones.
33 *
34 * @todo add infrastructure to SCIP for handling parallel columns
35 * @todo better communication of constraint changes by adding more information to the postsolve structure
36 * @todo allow to pass additional external locks to the presolve library that are considered when doing reductions
37 *
38 */
39
40/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41#include "scip/presol_milp.h"
42
43#ifndef SCIP_WITH_PAPILO
44
45/** creates the MILP presolver and includes it in SCIP */
46SCIP_RETCODE SCIPincludePresolMILP(
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/cons_exactlinear.h"
71#include "scip/pub_matrix.h"
72#include "scip/pub_presol.h"
73#include "scip/pub_var.h"
74#include "scip/pub_cons.h"
75#include "scip/pub_message.h"
76#include "scip/scip_exact.h"
77#include "scip/scip_general.h"
78#include "scip/scip_presol.h"
79#include "scip/scip_var.h"
80#include "scip/scip_mem.h"
81#include "scip/scip_prob.h"
82#include "scip/scip_param.h"
83#include "scip/scip_cons.h"
84#include "scip/scip_numerics.h"
85#include "scip/scip_timing.h"
86#include "scip/scip_message.h"
87#include "scip/scip_randnumgen.h"
88#if defined(SCIP_WITH_EXACTSOLVE)
89#include "scip/struct_rational.h"
90#endif
91#include "scip/rational.h"
92#include "papilo/core/Presolve.hpp"
93#include "papilo/core/ProblemBuilder.hpp"
94#include "papilo/Config.hpp"
95
96/* API since PaPILO 2.3.0 */
97#if !defined(PAPILO_API_VERSION)
98#define PAPILO_APIVERSION 0
99#elif !(PAPILO_API_VERSION + 0)
100#define PAPILO_APIVERSION 1
101#else
102#define PAPILO_APIVERSION PAPILO_API_VERSION
103#endif
104
105#if defined(SCIP_WITH_GMP) && defined(SCIP_WITH_EXACTSOLVE) && !defined(PAPILO_HAVE_GMP)
106#warning SCIP built with GMP and exact solving, but PaPILO without GMP disables exact presolving.
107#endif
108
109#if defined(SCIP_WITH_GMP) && defined(SCIP_WITH_EXACTSOLVE) && defined(PAPILO_HAVE_GMP)
110#define PAPILO_WITH_EXACTPRESOLVE
111#endif
112
113#define PRESOL_NAME "milp"
114#define PRESOL_DESC "MILP specific presolving methods"
115#define PRESOL_PRIORITY 9999999 /**< priority of the presolver (>= 0: before, < 0: after constraint handlers); combined with propagators */
116#define PRESOL_MAXROUNDS (-1) /**< maximal number of presolving rounds the presolver participates in (-1: no limit) */
117#define PRESOL_TIMING SCIP_PRESOLTIMING_MEDIUM /* timing of the presolver (fast, medium, or exhaustive) */
118
119/** general settings for PaPILO */
120#define DEFAULT_THREADS 1 /**< maximum number of threads presolving may use (0: automatic) */
121#define DEFAULT_ABORTFAC_EXHAUSTIVE 0.0008 /**< the abort factor for exhaustive presolving in PAPILO */
122#define DEFAULT_ABORTFAC_MEDIUM 0.0008 /**< the abort factor for medium presolving in PAPILO */
123#define DEFAULT_ABORTFAC_FAST 0.0008 /**< the abort factor for fast presolving in PAPILO */
124#define DEFAULT_DETECTLINDEP 0 /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
125#define DEFAULT_INTERNAL_MAXROUNDS (-1) /**< internal max rounds in PaPILO (-1: no limit, 0: model cleanup) */
126#define DEFAULT_MODIFYCONSFAC 0.8 /**< modify SCIP constraints when the number of nonzeros or rows is at most this
127 * factor times the number of nonzeros or rows before presolving */
128#define DEFAULT_RANDOMSEED 0 /**< the random seed used for randomization of tie breaking */
129
130/** numerics in PaPILO */
131#define DEFAULT_HUGEBOUND 1e8 /**< absolute bound value that is considered too huge for activitity based calculations */
132
133/** presolvers in PaPILO */
134#define DEFAULT_ENABLEDOMCOL TRUE /**< should the dominated column presolver be enabled within the presolve library? */
135#define DEFAULT_ENABLEDUALINFER TRUE /**< should the dualinfer presolver be enabled within the presolve library? */
136#define DEFAULT_ENABLEMULTIAGGR TRUE /**< should the multi-aggregation/substitution presolver be enabled within the presolve library? */
137#define DEFAULT_ENABLEPARALLELROWS TRUE /**< should the parallel rows presolver be enabled within the presolve library? */
138#define DEFAULT_ENABLEPROBING TRUE /**< should the probing presolver be enabled within the presolve library? */
139#define DEFAULT_ENABLESPARSIFY FALSE /**< should the sparsify presolver be enabled within the presolve library? */
140#define DEFAULT_ENABLECLIQUEMERGE FALSE /**< should the clique merging presolver be enabled within the presolve library? */
141#define DEFAULT_ENABLEGF2 FALSE /**< should the GF2 presolver be enabled within the presolve library? */
142
143/** parameters tied to a certain presolve technique in PaPILO */
144#define DEFAULT_MAXBADGESIZE_SEQ 15000 /**< the max badge size in Probing if PaPILO is executed in sequential mode */
145#define DEFAULT_MAXBADGESIZE_PAR (-1) /**< the max badge size in Probing if PaPILO is executed in parallel mode */
146#define DEFAULT_MARKOWITZTOLERANCE 0.01 /**< the markowitz tolerance used for substitutions */
147#define DEFAULT_MAXFILLINPERSUBST 3 /**< maximal possible fillin for substitutions to be considered */
148#define DEFAULT_MAXSHIFTPERROW 10 /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
149#define DEFAULT_MAXEDGESPARALLEL 1000000 /**< maximal amount of edges in the parallel clique merging graph */
150#define DEFAULT_MAXEDGESSEQUENTIAL 100000 /**< maximal amount of edges in the sequential clique merging graph */
151#define DEFAULT_MAXCLIQUESIZE 100 /**< maximal size of clique considered for clique merging */
152#define DEFAULT_MAXGREEDYCALLS 10000 /**< maximal number of greedy max clique calls in a single thread */
153
154/** debug options for PaPILO */
155#define DEFAULT_FILENAME_PROBLEM "-" /**< default filename to store the instance before presolving */
156#define DEFAULT_VERBOSITY 0
157
158
159/*
160 * Data structures
161 */
162
163/** presolver data */
164struct SCIP_PresolMilpData
165{
166 int lastncols; /**< the number of columns from the last call */
167 int lastnrows; /**< the number of rows from the last call */
168 int threads; /**< maximum number of threads presolving may use (0: automatic) */
169 int maxfillinpersubstitution; /**< maximal possible fillin for substitutions to be considered */
170 int maxbadgesizeseq; /**< the max badge size in Probing if PaPILO is called in sequential mode */
171 int maxbadgesizepar; /**< the max badge size in Probing if PaPILO is called in parallel mode */
172 int internalmaxrounds; /**< internal max rounds in PaPILO (-1: no limit, 0: model cleanup) */
173 int maxshiftperrow; /**< maximal amount of nonzeros allowed to be shifted to make space for substitutions */
174 int detectlineardependency; /**< should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always) */
175#if PAPILO_APIVERSION >= 6
176 int maxedgesparallel; /**< maximal amount of edges in the parallel clique merging graph */
177 int maxedgessequential; /**< maximal amount of edges in the sequential clique merging graph */
178 int maxcliquesize; /**< maximal size of clique considered for clique merging */
179 int maxgreedycalls; /**< maximal number of greedy max clique calls in a single thread */
180#endif
181 int randomseed; /**< the random seed used for randomization of tie breaking */
182 int verbosity;
183
184 SCIP_Bool enablesparsify; /**< should the sparsify presolver be enabled within the presolve library? */
185 SCIP_Bool enabledomcol; /**< should the dominated column presolver be enabled within the presolve library? */
186 SCIP_Bool enableprobing; /**< should the probing presolver be enabled within the presolve library? */
187 SCIP_Bool enabledualinfer; /**< should the dualinfer presolver be enabled within the presolve library? */
188 SCIP_Bool enablemultiaggr; /**< should the multi-aggregation presolver be enabled within the presolve library? */
189 SCIP_Bool enableparallelrows; /**< should the parallel rows presolver be enabled within the presolve library? */
190#if PAPILO_APIVERSION >= 6
191 SCIP_Bool enablecliquemerging; /**< should the clique merging presolver be enabled within the presolve library? */
192#endif
193#if PAPILO_APIVERSION >= 13
194 SCIP_Bool enableGF2; /**< should the GF2 presolver be enabled within the presolve library? */
195#endif
196 SCIP_Real modifyconsfac; /**< modify SCIP constraints when the number of nonzeros or rows is at most this
197 * factor times the number of nonzeros or rows before presolving */
198 SCIP_Real markowitztolerance; /**< the markowitz tolerance used for substitutions */
199 SCIP_Real hugebound; /**< absolute bound value that is considered too huge for activitity based calculations */
200 SCIP_Real abortfacexhaustive; /**< abort factor for exhaustive presolving in PAPILO */
201 SCIP_Real abortfacmedium; /**< abort factor for medium presolving in PAPILO */
202 SCIP_Real abortfacfast; /**< abort factor for fast presolving in PAPILO */
203
204 char* filename = NULL; /**< filename to store the instance before presolving */
205};
206typedef struct SCIP_PresolMilpData SCIP_PRESOLMILPDATA;
207
208using namespace papilo;
209
210/*
211 * Local methods
212 */
213
214#if defined(PAPILO_WITH_EXACTPRESOLVE)
215/** casts rational value from PaPILO to SCIP */
216static
217void setRational(
218 SCIP* scip, /**< SCIP data structure */
219 SCIP_RATIONAL* res, /**< pointer to SCIP' rational to set */
220 papilo::Rational papiloval /**< rational value from PaPILO */
221 )
222{
223 assert(scip != NULL);
224 assert(res != NULL);
225
226 res->val = papilo::Rational(papiloval.backend().data());
227 res->isfprepresentable = SCIP_ISFPREPRESENTABLE_UNKNOWN;
228 if( SCIPisInfinity(scip, REALABS(SCIPrationalGetReal(res))) )
229 {
230 res->val > 0 ? SCIPrationalSetInfinity(res) : SCIPrationalSetNegInfinity(res);
231 }
232}
233
234/** builds PaPILO problem from SCIP matrix */
235static
236Problem<papilo::Rational> buildProblemRational(
237 SCIP* scip, /**< SCIP data structure */
238 SCIP_MATRIX* matrix /**< initialized SCIP_MATRIX data structure */
239 )
240{
241 ProblemBuilder<papilo::Rational> builder;
242
243 /* build problem from matrix */
244 int nnz = SCIPmatrixGetNNonzs(matrix);
245 int ncols = SCIPmatrixGetNColumns(matrix);
246 int nrows = SCIPmatrixGetNRows(matrix);
247 builder.reserve(nnz, nrows, ncols);
248
249 /* set up columns */
250 builder.setNumCols(ncols);
251 for( int i = 0; i != ncols; ++i )
252 {
253 SCIP_VAR* var = SCIPmatrixGetVar(matrix, i);
254 SCIP_RATIONAL* lb = SCIPvarGetLbGlobalExact(var);
255 SCIP_RATIONAL* ub = SCIPvarGetUbGlobalExact(var);
256 builder.setColLb(i, lb->val);
257 builder.setColUb(i, ub->val);
258 builder.setColLbInf(i, SCIPrationalIsNegInfinity(lb));
259 builder.setColUbInf(i, SCIPrationalIsInfinity(ub));
260
261 builder.setColIntegral(i, SCIPvarIsIntegral(var));
262 builder.setObj(i, SCIPvarGetObjExact(var)->val);
263 }
264
265 /* set up rows */
266 builder.setNumRows(nrows);
267 for( int i = 0; i != nrows; ++i )
268 {
269 int* rowcols = SCIPmatrixGetRowIdxPtr(matrix, i);
270 SCIP_RATIONAL** rowvalsscip = SCIPmatrixGetRowValPtrExact(matrix, i);
271 Vec<papilo::Rational> rowvals;
272 int rowlen = SCIPmatrixGetRowNNonzs(matrix, i);
273 for( int j = 0; j < rowlen; ++j )
274 rowvals.emplace_back(rowvalsscip[j]->val);
275 builder.addRowEntries(i, rowlen, rowcols, rowvals.data());
276
277 SCIP_RATIONAL* lhs = SCIPmatrixGetRowLhsExact(matrix, i);
278 SCIP_RATIONAL* rhs = SCIPmatrixGetRowRhsExact(matrix, i);
279 builder.setRowLhs(i, lhs->val);
280 builder.setRowRhs(i, rhs->val);
281 builder.setRowLhsInf(i, SCIPrationalIsNegInfinity(lhs));
282 builder.setRowRhsInf(i, SCIPrationalIsInfinity(rhs));
283 }
284
285 builder.setObjOffset(0);
286
287 return builder.build();
288}
289#endif
290
291/** builds PaPILO problem from SCIP matrix */
292static
293Problem<SCIP_Real> buildProblemReal(
294 SCIP* scip, /**< SCIP data structure */
295 SCIP_MATRIX* matrix /**< initialized SCIP_MATRIX data structure */
296 )
297{
298 ProblemBuilder<SCIP_Real> builder;
299
300 /* build problem from matrix */
301 int nnz = SCIPmatrixGetNNonzs(matrix);
302 int ncols = SCIPmatrixGetNColumns(matrix);
303 int nrows = SCIPmatrixGetNRows(matrix);
304 builder.reserve(nnz, nrows, ncols);
305
306 /* set up columns */
307 builder.setNumCols(ncols);
308 for( int i = 0; i != ncols; ++i )
309 {
310 SCIP_VAR* var = SCIPmatrixGetVar(matrix, i);
311 SCIP_Real lb = SCIPvarGetLbGlobal(var);
312 SCIP_Real ub = SCIPvarGetUbGlobal(var);
313 builder.setColLb(i, lb);
314 builder.setColUb(i, ub);
315 builder.setColLbInf(i, SCIPisInfinity(scip, -lb));
316 builder.setColUbInf(i, SCIPisInfinity(scip, ub));
317 builder.setColIntegral(i, SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
318#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
319 builder.setColImplInt(i, SCIPvarIsImpliedIntegral(var));
320#endif
321 builder.setObj(i, SCIPvarGetObj(var));
322 }
323
324 /* set up rows */
325 builder.setNumRows(nrows);
326 for( int i = 0; i != nrows; ++i )
327 {
328 int* rowcols = SCIPmatrixGetRowIdxPtr(matrix, i);
329 SCIP_Real* rowvals = SCIPmatrixGetRowValPtr(matrix, i);
330 int rowlen = SCIPmatrixGetRowNNonzs(matrix, i);
331 builder.addRowEntries(i, rowlen, rowcols, rowvals);
332
333 SCIP_Real lhs = SCIPmatrixGetRowLhs(matrix, i);
334 SCIP_Real rhs = SCIPmatrixGetRowRhs(matrix, i);
335 builder.setRowLhs(i, lhs);
336 builder.setRowRhs(i, rhs);
337 builder.setRowLhsInf(i, SCIPisInfinity(scip, -lhs));
338 builder.setRowRhsInf(i, SCIPisInfinity(scip, rhs));
339 }
340
341 /* init objective offset - the value itself is irrelevant */
342 builder.setObjOffset(0);
343
344#ifdef SCIP_PRESOLLIB_ENABLE_OUTPUT
345 /* show problem name */
346 builder.setProblemName(SCIPgetProbName(scip));
347#endif
348
349 return builder.build();
350}
351
352/** sets up PaPILO's presolve object from the data */
353template <typename T>
354static
355SCIP_RETCODE setupPresolve(
356 SCIP* scip, /**< SCIP data structure */
357 Presolve<T>& presolve, /**< PaPILO's presolve object */
358 SCIP_PRESOLMILPDATA* data, /**< presolver data structure */
359 SCIP_Bool allowconsmodification /**< whether constraint modifications are allowed */
360 )
361{
362 SCIP_Real timelimit;
363
364 /* important so that SCIP does not throw an error, e.g. when an integer variable is substituted
365 * into a knapsack constraint */
366 presolve.getPresolveOptions().substitutebinarieswithints = false;
367
368 /* currently these changes cannot be communicated to SCIP correctly since a constraint needs
369 * to be modified in the cases where slackvariables are removed from constraints but for the
370 * presolve library those look like normal substitution on the postsolve stack */
371 presolve.getPresolveOptions().removeslackvars = false;
372
373 /* communicate the SCIP parameters to the presolve library */
374 presolve.getPresolveOptions().maxfillinpersubstitution = data->maxfillinpersubstitution;
375 presolve.getPresolveOptions().markowitz_tolerance = data->markowitztolerance;
376 presolve.getPresolveOptions().maxshiftperrow = data->maxshiftperrow;
377 presolve.getPresolveOptions().hugeval = data->hugebound;
378
379 /* removal of linear dependent equations has only an effect when constraint modifications are communicated */
380 presolve.getPresolveOptions().detectlindep = allowconsmodification ? data->detectlineardependency : 0;
381
382 /* communicate the random seed */
383 presolve.getPresolveOptions().randomseed = SCIPinitializeRandomSeed(scip, (unsigned int)data->randomseed);
384
385 /* set number of threads to be used for presolve */
386 presolve.getPresolveOptions().threads = data->threads;
387
388#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 3)
389 presolve.getPresolveOptions().maxrounds = data->internalmaxrounds;
390#endif
391
392 /* disable dual reductions that are not permitted */
393 if( SCIPallowStrongDualReds(scip) )
394 presolve.getPresolveOptions().dualreds = 2;
395 else if( SCIPallowWeakDualReds(scip) )
396 presolve.getPresolveOptions().dualreds = 1;
397 else
398 presolve.getPresolveOptions().dualreds = 0;
399
400 /* set up the presolvers that shall participate */
401 using uptr = std::unique_ptr<PresolveMethod<T>>;
402
403 /* fast presolvers*/
404 presolve.addPresolveMethod( uptr( new SingletonCols<T>() ) );
405 presolve.addPresolveMethod( uptr( new CoefficientStrengthening<T>() ) );
406 presolve.addPresolveMethod( uptr( new ConstraintPropagation<T>() ) );
407
408 /* medium presolver */
409 presolve.addPresolveMethod( uptr( new SimpleProbing<T>() ) );
410 if( data->enableparallelrows )
411 presolve.addPresolveMethod( uptr( new ParallelRowDetection<T>() ) );
412 /* todo: parallel cols cannot be handled by SCIP currently
413 * addPresolveMethod( uptr( new ParallelColDetection<SCIP_Real>() ) ); */
414 presolve.addPresolveMethod( uptr( new SingletonStuffing<T>() ) );
415#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
416 DualFix<T> *dualfix = new DualFix<T>();
417 dualfix->set_fix_to_infinity_allowed(false);
418 presolve.addPresolveMethod( uptr( dualfix ) );
419#else
420 presolve.addPresolveMethod( uptr( new DualFix<T>() ) );
421#endif
422 presolve.addPresolveMethod( uptr( new FixContinuous<T>() ) );
423 presolve.addPresolveMethod( uptr( new SimplifyInequalities<T>() ) );
424 presolve.addPresolveMethod( uptr( new SimpleSubstitution<T>() ) );
425#if PAPILO_APIVERSION >= 6
426 if( data->enablecliquemerging )
427 {
428 CliqueMerging<T>* cliquemerging = new CliqueMerging<T>();
429 cliquemerging->setParameters( data->maxedgesparallel, data->maxedgessequential,
430 data->maxcliquesize, data->maxgreedycalls );
431 presolve.addPresolveMethod( uptr( cliquemerging ) );
432 }
433#endif
434#if PAPILO_APIVERSION >= 13
435 if( data->enableGF2 )
436 presolve.addPresolveMethod( uptr( new GF2<T>() ) );
437#endif
438
439 /* exhaustive presolvers*/
440 presolve.addPresolveMethod( uptr( new ImplIntDetection<T>() ) );
441 if( data->enabledualinfer )
442 presolve.addPresolveMethod( uptr( new DualInfer<T>() ) );
443 if( data->enableprobing )
444 {
445#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
446 Probing<T> *probing = new Probing<T>();
447 if( presolve.getPresolveOptions().runs_sequential() )
448 {
449 probing->set_max_badge_size( data->maxbadgesizeseq );
450 }
451 else
452 {
453 probing->set_max_badge_size( data->maxbadgesizepar );
454 }
455#if PAPILO_APIVERSION >= 12
456 // TODO: enable this after performance test. On MIPLIB this brought 3% on instances with cliques.
457 probing->set_numcliquefails(0);
458#endif
459 presolve.addPresolveMethod( uptr( probing ) );
460#else
461 presolve.addPresolveMethod( uptr( new Probing<T>() ) );
462 if( data->maxbadgesizeseq != DEFAULT_MAXBADGESIZE_SEQ )
463 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
464 " The parameter 'presolving/milp/maxbadgesizeseq' can only be used with PaPILO 2.1.0 or later versions.\n");
465
466 if( data->maxbadgesizepar != DEFAULT_MAXBADGESIZE_PAR )
467 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
468 " The parameter 'presolving/milp/maxbadgesizepar' can only be used with PaPILO 2.1.0 or later versions.\n");
469#endif
470 }
471 if( data->enabledomcol )
472 presolve.addPresolveMethod( uptr( new DominatedCols<T>() ) );
473 if( data->enablemultiaggr )
474 presolve.addPresolveMethod( uptr( new Substitution<T>() ) );
475 if( data->enablesparsify )
476 presolve.addPresolveMethod( uptr( new Sparsify<T>() ) );
477
478 /* set numerical tolerances */
479#if PAPILO_APIVERSION >= 3
480 presolve.getPresolveOptions().useabsfeas = false;
481#endif
482 if( SCIPisExact(scip) )
483 {
484 presolve.getPresolveOptions().epsilon = 0.0;
485 presolve.getPresolveOptions().feastol = 0.0;
486 }
487 else
488 {
489 presolve.getPresolveOptions().epsilon = SCIPepsilon(scip);
490 presolve.getPresolveOptions().feastol = SCIPfeastol(scip);
491 }
492
493#ifndef SCIP_PRESOLLIB_ENABLE_OUTPUT
494 /* adjust output settings of presolve library */
495 presolve.setVerbosityLevel((VerbosityLevel) data->verbosity);
496#endif
497
498#if PAPILO_APIVERSION >= 2
499 presolve.getPresolveOptions().abortfac = data->abortfacexhaustive;
500 presolve.getPresolveOptions().abortfacmedium = data->abortfacmedium;
501 presolve.getPresolveOptions().abortfacfast = data->abortfacfast;
502#endif
503
504 /* communicate the time limit */
505 SCIPgetRealParam(scip, "limits/time", &timelimit);
506 if( !SCIPisInfinity(scip, timelimit) )
507 presolve.getPresolveOptions().tlim = timelimit - SCIPgetSolvingTime(scip);
508
509 return SCIP_OKAY;
510}
511
512
513#if defined(PAPILO_WITH_EXACTPRESOLVE)
514/** calls PaPILO presolving in rational arithmetic*/
515static
516SCIP_RETCODE performRationalPresolving(
517 SCIP* scip, /**< SCIP data structure */
518 SCIP_MATRIX* matrix, /**< initialized SCIP_MATRIX data structure */
519 SCIP_PRESOLMILPDATA* data, /**< plugin specific presol data */
520 SCIP_Bool initialized, /**< was the matrix initialized */
521 int* nfixedvars, /**< store number of fixed variables */
522 int* naggrvars, /**< store number of aggregated variables */
523 int* nchgvartypes, /**< store number of changed variable types */
524 int* nchgbds, /**< store number of changed bounds */
525 int* naddholes, /**< store number of added holes */
526 int* ndelconss, /**< store the number of deleted cons */
527 int* naddconss, /**< store the number of added cons */
528 int* nupgdconss, /**< store the number of upgraded cons */
529 int* nchgcoefs, /**< store the number of changed coefficients */
530 int* nchgsides, /**< store the number of changed sides */
531 SCIP_RESULT* result /**< result pointer */
532 )
533{
534 int nvars = SCIPgetNVars(scip);
535 int nconss = SCIPgetNConss(scip);
536
537 SCIP_CONSHDLR* linconshdlr = SCIPfindConshdlr(scip, "exactlinear");
538 assert(linconshdlr != NULL);
539 bool allowconsmodification = (SCIPconshdlrGetNCheckConss(linconshdlr) == SCIPmatrixGetNRows(matrix));
540
541 /* store current numbers of aggregations, fixings, and changed bounds for statistics */
542 int oldnaggrvars = *naggrvars;
543 int oldnfixedvars = *nfixedvars;
544 int oldnchgbds = *nchgbds;
545
546 Problem<papilo::Rational> problem = buildProblemRational(scip, matrix);
547 Presolve<papilo::Rational> presolve;
548 setupPresolve(scip, presolve, data, allowconsmodification);
549
550 /* call presolving (without storing information for dual postsolve) */
551 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
552 " (%.1fs) running MILP presolver%s\n", SCIPgetSolvingTime(scip),
553 presolve.getPresolveOptions().threads == 1 ? "" : " on multiple threads");
554
555 int oldnnz = problem.getConstraintMatrix().getNnz();
556
557#if (PAPILO_VERSION_MAJOR >= 2)
558 PresolveResult<papilo::Rational> res = presolve.apply(problem, false);
559#else
560 PresolveResult<papilo::Rational> res = presolve.apply(problem);
561#endif
562 data->lastncols = problem.getNCols();
563 data->lastnrows = problem.getNRows();
564
565 /* evaluate the result */
566 switch( res.status )
567 {
568 case PresolveStatus::kInfeasible:
569 *result = SCIP_CUTOFF;
570 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
571 " (%.1fs) MILP presolver detected infeasibility\n",
572 SCIPgetSolvingTime(scip));
573 SCIPmatrixFree(scip, &matrix);
574 return SCIP_OKAY;
575 case PresolveStatus::kUnbndOrInfeas:
576 case PresolveStatus::kUnbounded:
577 *result = SCIP_UNBOUNDED;
578 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
579 " (%.1fs) MILP presolver detected unboundedness\n",
580 SCIPgetSolvingTime(scip));
581 SCIPmatrixFree(scip, &matrix);
582 return SCIP_OKAY;
583 case PresolveStatus::kUnchanged:
584 *result = SCIP_DIDNOTFIND;
585 data->lastncols = nvars;
586 data->lastnrows = nconss;
587 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
588 " (%.1fs) MILP presolver found nothing\n",
589 SCIPgetSolvingTime(scip));
590 SCIPmatrixFree(scip, &matrix);
591 return SCIP_OKAY;
592 case PresolveStatus::kReduced:
593 data->lastncols = problem.getNCols();
594 data->lastnrows = problem.getNRows();
595 *result = SCIP_SUCCESS;
596 }
597
598 /* result indicated success, now populate the changes into the SCIP structures */
599 Vec<SCIP_VAR*> tmpvars;
600 Vec<SCIP_Real> tmpvalsreal;
601
602 /* if the number of nonzeros decreased by a sufficient factor, rather create all constraints from scratch */
603 int newnnz = problem.getConstraintMatrix().getNnz();
604 bool constraintsReplaced = false;
605 if( newnnz == 0 || (allowconsmodification &&
606 (problem.getNRows() <= data->modifyconsfac * data->lastnrows ||
607 newnnz <= data->modifyconsfac * oldnnz)) )
608 {
609 int oldnrows = SCIPmatrixGetNRows(matrix);
610 int newnrows = problem.getNRows();
611
612 constraintsReplaced = true;
613
614 /* capture constraints that are still present in the problem after presolve */
615 for( int i = 0; i < newnrows; ++i )
616 {
617 SCIP_CONS* c = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
618 SCIP_CALL( SCIPcaptureCons(scip, c) );
619 }
620
621 /* delete all constraints */
622 *ndelconss += oldnrows;
623 *naddconss += newnrows;
624
625 for( int i = 0; i < oldnrows; ++i )
626 {
627 SCIP_CALL( SCIPdelCons(scip, SCIPmatrixGetCons(matrix, i)) );
628 }
629
630 /* now loop over rows of presolved problem and create them as new linear constraints,
631 * then release the old constraint after its name was passed to the new constraint
632 */
633 const Vec<RowFlags>& rflags = problem.getRowFlags();
634 const auto& consmatrix = problem.getConstraintMatrix();
635 for( int i = 0; i < newnrows; ++i )
636 {
637 auto rowvec = consmatrix.getRowCoefficients(i);
638 const int* rowcols = rowvec.getIndices();
639 /* SCIPcreateConsBasicLinear() requires a non const pointer */
640 papilo::Rational* rowvals = const_cast<papilo::Rational*>(rowvec.getValues());
641 int rowlen = rowvec.getLength();
642
643 /* retrieve SCIP compatible left and right hand sides */
644 papilo::Rational lhs = rflags[i].test(RowFlag::kLhsInf) ? - SCIPinfinity(scip) : consmatrix.getLeftHandSides()[i];
645 papilo::Rational rhs = rflags[i].test(RowFlag::kRhsInf) ? SCIPinfinity(scip) : consmatrix.getRightHandSides()[i];
646
647 /* create variable array matching the value array */
648 tmpvars.clear();
649 tmpvars.reserve(rowlen);
650 for( int j = 0; j < rowlen; ++j )
651 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[rowcols[j]]));
652
653 /* create and add new constraint with name of old constraint */
654 SCIP_CONS* oldcons = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
655 SCIP_CONS* cons;
656 SCIP_RATIONAL** tmpvals;
657 SCIP_RATIONAL* tmplhs;
658 SCIP_RATIONAL* tmprhs;
659
660 SCIP_CALL( SCIPrationalCreateBufferArray(SCIPbuffer(scip), &tmpvals, rowlen) );
661 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmprhs) );
662 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmplhs) );
663
664 for( int j = 0; j < rowlen; j++ )
665 setRational(scip, tmpvals[j], rowvals[j]);
666
667 setRational(scip, tmprhs, rhs);
668 setRational(scip, tmplhs, lhs);
669 if( rflags[i].test(RowFlag::kLhsInf) )
670 SCIPrationalSetNegInfinity(tmplhs);
671 if( rflags[i].test(RowFlag::kRhsInf) )
672 SCIPrationalSetInfinity(tmprhs);
673
674 SCIP_CALL( SCIPcreateConsBasicExactLinear(scip, &cons, SCIPconsGetName(oldcons), rowlen, tmpvars.data(), tmpvals, tmplhs, tmprhs) );
675 SCIP_CALL( SCIPaddCons(scip, cons) );
676
677 /* release old and new constraint */
678 SCIP_CALL( SCIPreleaseCons(scip, &oldcons) );
679 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
680
681 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmprhs);
682 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmplhs);
683 SCIPrationalFreeBufferArray(SCIPbuffer(scip), &tmpvals, rowlen);
684 }
685 }
686
687 /* loop over res.postsolve and add all fixed variables and aggregations to scip */
688 for( std::size_t i = 0; i != res.postsolve.types.size(); ++i )
689 {
690 ReductionType type =
691 res.postsolve.types[i];
692 int first = res.postsolve.start[i];
693 int last = res.postsolve.start[i + 1];
694
695 switch( type )
696 {
697 case ReductionType::kFixedCol:
698 {
699 SCIP_RATIONAL* tmpval;
700 SCIP_Bool infeas;
701 SCIP_Bool fixed;
702 int col = res.postsolve.indices[first];
703
704 SCIP_VAR* var = SCIPmatrixGetVar(matrix, col);
705
706 papilo::Rational value = res.postsolve.values[first];
707
708 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmpval) );
709 setRational(scip, tmpval, value);
710
711 SCIPrationalDebugMessage("Papilo fix var %s to %q \n", SCIPvarGetName(var), tmpval);
712
713 /* SCIP has different rules for aggregation than PaPILO
714 * As a result, SCIP might have aggregated and replaced the variable that PaPILO now wants to fix
715 */
716 if( SCIPvarGetStatusExact(var) == SCIP_VARSTATUS_AGGREGATED )
717 {
718 SCIP_RATIONAL* aggregatedScalar;
719 SCIP_RATIONAL* aggregatedConst;
720
721 aggregatedScalar = SCIPvarGetAggrScalarExact(var);
722 aggregatedConst = SCIPvarGetAggrConstantExact(var);
723
724 /* fix aggregation variable y in x = a*y + c, instead of fixing x directly */
725 assert( SCIPrationalIsZero(SCIPvarGetObjExact(var)) );
726 assert( !SCIPrationalIsZero(aggregatedScalar));
727 if( SCIPrationalIsAbsInfinity(tmpval) )
728 SCIPrationalMultReal(tmpval, tmpval, SCIPrationalIsNegative(aggregatedScalar) ? -1 : 1);
729 else
730 {
731 SCIPrationalDiff(tmpval, tmpval, aggregatedConst);
732 SCIPrationalDiv(tmpval, tmpval, aggregatedScalar);
733 }
734 var = SCIPvarGetAggrVar(var);
735 }
736
737 /* SCIP might also have fixed the variable during aggregation */
738 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED )
739 break;
740
741 SCIP_CALL( SCIPfixVarExact(scip, var, tmpval, &infeas, &fixed) );
742
743 *nfixedvars += 1;
744
745 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmpval);
746
747 assert(!infeas);
748 assert(fixed || SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED ||
749 SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED);
750 break;
751 }
752 /*
753 * Dual-postsolving in PaPILO required introducing a postsolve-type for substitution with additional information.
754 * Further, the different Substitution-postsolving types store the required postsolving data differently (in different order) in the postsolving stack.
755 * Therefore, we need to distinguish how to parse the required data (rowLength, col, side, startRowCoefficients, lastRowCoefficients) from the postsolving stack.
756 * If these values are accessed, the procedure is the same for both.
757 */
758#if (PAPILO_VERSION_MAJOR >= 2)
759 case ReductionType::kSubstitutedColWithDual:
760#endif
761 case ReductionType::kSubstitutedCol:
762 {
763 int col = 0;
764 papilo::Rational side = 0;
765
766 int rowlen = 0;
767 int startRowCoefficients = 0;
768 int lastRowCoefficients = 0;
769
770 if( type == ReductionType::kSubstitutedCol )
771 {
772 rowlen = last - first - 1;
773 col = res.postsolve.indices[first];
774 side = res.postsolve.values[first];
775
776 startRowCoefficients = first + 1;
777 lastRowCoefficients = last;
778 }
779#if (PAPILO_VERSION_MAJOR >= 2)
780 if( type == ReductionType::kSubstitutedColWithDual )
781 {
782 rowlen = (int) res.postsolve.values[first];
783 col = res.postsolve.indices[first + 3 + rowlen];
784 side = res.postsolve.values[first + 1];
785
786 startRowCoefficients = first + 3;
787 lastRowCoefficients = first + 3 + rowlen;
788
789 assert(side == res.postsolve.values[first + 2]);
790 assert(res.postsolve.indices[first + 1] == 0);
791 assert(res.postsolve.indices[first + 2] == 0);
792 }
793 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
794#else
795 assert( type == ReductionType::kSubstitutedCol );
796#endif
797 SCIP_Bool infeas;
798 SCIP_Bool aggregated;
799 SCIP_Bool redundant = FALSE;
800 SCIP_RATIONAL* constant;
801 if( rowlen == 2 )
802 {
803 SCIP_VAR* varx = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients]);
804 SCIP_VAR* vary = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients + 1]);
805 papilo::Rational scalarx = res.postsolve.values[startRowCoefficients];
806 papilo::Rational scalary = res.postsolve.values[startRowCoefficients + 1];
807
808 SCIP_RATIONAL* tmpscalarx;
809 SCIP_RATIONAL* tmpscalary;
810 SCIP_RATIONAL* tmpside;
811 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &constant) );
812 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmpscalarx) );
813 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmpscalary) );
814 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmpside) );
815
816 setRational(scip, tmpscalarx, scalarx);
817 setRational(scip, tmpscalary, scalary);
818
819 SCIP_CALL( SCIPgetProbvarSumExact(scip, &varx, tmpscalarx, constant) );
820 assert(SCIPvarGetStatus(varx) != SCIP_VARSTATUS_MULTAGGR);
821
822 SCIP_CALL( SCIPgetProbvarSumExact(scip, &vary, tmpscalary, constant) );
823 assert(SCIPvarGetStatus(vary) != SCIP_VARSTATUS_MULTAGGR);
824
825 setRational(scip, tmpside, side);
826 SCIPrationalDiff(tmpside, tmpside, constant);
827
828 SCIPrationalDebugMessage("Papilo aggregate vars %s, %s with scalars %q, %q and constant %q \n", SCIPvarGetName(varx), SCIPvarGetName(vary),
829 tmpscalarx, tmpscalary, constant);
830
831 SCIP_CALL( SCIPaggregateVarsExact(scip, varx, vary, tmpscalarx, tmpscalary, tmpside, &infeas, &redundant, &aggregated) );
832
833 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmpside);
834 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmpscalary);
835 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmpscalarx);
836 SCIPrationalFreeBuffer(SCIPbuffer(scip), &constant);
837 }
838 else
839 {
840 SCIP_RATIONAL* colCoef;
841 SCIP_RATIONAL* updatedSide;
842 SCIP_RATIONAL** tmpvals;
843 int c = 0;
844
845 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &constant) );
846 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &colCoef) );
847 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &updatedSide) );
848 SCIP_CALL( SCIPrationalCreateBufferArray(SCIPbuffer(scip), &tmpvals, rowlen) );
849
850 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
851 {
852 if( res.postsolve.indices[j] == col )
853 {
854 setRational(scip, colCoef, res.postsolve.values[j]);
855 break;
856 }
857 }
858
859 tmpvars.clear();
860 tmpvars.reserve(rowlen);
861
862 assert(!SCIPrationalIsZero(colCoef));
863 SCIP_VAR* aggrvar = SCIPmatrixGetVar(matrix, col);
864
865 SCIP_CALL( SCIPgetProbvarSumExact(scip, &aggrvar, colCoef, constant) );
866 assert(SCIPvarGetStatus(aggrvar) != SCIP_VARSTATUS_MULTAGGR);
867
868 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
869 {
870 if( res.postsolve.indices[j] == col )
871 continue;
872
873 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
874 setRational(scip, tmpvals[c], -res.postsolve.values[j] / colCoef->val);
875 c++;
876 }
877 setRational(scip, updatedSide, side);
878 SCIPrationalDiff(updatedSide, updatedSide, constant);
879 SCIPrationalDiv(updatedSide, updatedSide, colCoef);
880
881 SCIPrationalDebugMessage("Papilo multiaggregate var %s, constant %q \n", SCIPvarGetName(aggrvar), updatedSide);
882
883 SCIP_CALL( SCIPmultiaggregateVarExact(scip, aggrvar, tmpvars.size(),
884 tmpvars.data(), tmpvals, updatedSide, &infeas, &aggregated) );
885
886 SCIPrationalFreeBufferArray(SCIPbuffer(scip), &tmpvals, rowlen);
887 SCIPrationalFreeBuffer(SCIPbuffer(scip), &updatedSide);
888 SCIPrationalFreeBuffer(SCIPbuffer(scip), &colCoef);
889 SCIPrationalFreeBuffer(SCIPbuffer(scip), &constant);
890 }
891
892 if( aggregated )
893 *naggrvars += 1;
894 else if( constraintsReplaced && !redundant )
895 {
896 /* if the constraints where replaced, we need to add the failed substitution as an equality to SCIP */
897 SCIP_RATIONAL** tmpvals;
898 SCIP_RATIONAL* tmpside;
899
900 SCIP_CALL( SCIPrationalCreateBufferArray(SCIPbuffer(scip), &tmpvals, rowlen) );
901 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &tmpside) );
902
903 setRational(scip, tmpside, side);
904
905 tmpvars.clear();
906 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
907 {
908 int idx = j - startRowCoefficients;
909 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
910 setRational(scip, tmpvals[idx], res.postsolve.values[j]);
911 }
912
913 SCIP_CONS* cons;
914 String name = fmt::format("{}_failed_aggregation_equality", SCIPvarGetName(SCIPmatrixGetVar(matrix, col)));
915 SCIP_CALL( SCIPcreateConsBasicExactLinear(scip, &cons, name.c_str(),
916 tmpvars.size(), tmpvars.data(), tmpvals, tmpside, tmpside ) );
917
918 SCIPdebugMessage("Papilo adding failed aggregation equality: \n");
919 SCIPdebug(SCIPprintCons(scip, cons, NULL));
920 SCIP_CALL( SCIPaddCons(scip, cons) );
921 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
922 *naddconss += 1;
923
924 SCIPrationalFreeBuffer(SCIPbuffer(scip), &tmpside);
925 SCIPrationalFreeBufferArray(SCIPbuffer(scip), &tmpvals, rowlen);
926 }
927
928 if( infeas )
929 {
930 *result = SCIP_CUTOFF;
931 break;
932 }
933
934 break;
935 }
936 case ReductionType::kParallelCol:
937 return SCIP_INVALIDRESULT;
938#if (PAPILO_VERSION_MAJOR <= 1 && PAPILO_VERSION_MINOR==0)
939#else
940 case ReductionType::kFixedInfCol: {
941 if(!constraintsReplaced)
942 continue;
943 SCIP_Bool infeas;
944 SCIP_Bool fixed;
945 SCIP_RATIONAL* value;
946
947 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &value) );
948 SCIPrationalSetInfinity(value);
949
950 int column = res.postsolve.indices[first];
951 bool is_negative_infinity = res.postsolve.values[first] < 0;
952 SCIP_VAR* column_variable = SCIPmatrixGetVar(matrix, column);
953
954 if( is_negative_infinity )
955 {
956 SCIPrationalSetNegInfinity(value);
957 }
958
959 SCIP_CALL( SCIPfixVarExact(scip, column_variable, value, &infeas, &fixed) );
960 *nfixedvars += 1;
961
962 assert(!infeas);
963 assert(fixed);
964
965 SCIPrationalFreeBuffer(SCIPbuffer(scip), &value);
966
967 break;
968 }
969#endif
970#if (PAPILO_VERSION_MAJOR >= 2)
971 case ReductionType::kVarBoundChange :
972 case ReductionType::kRedundantRow :
973 case ReductionType::kRowBoundChange :
974 case ReductionType::kReasonForRowBoundChangeForcedByRow :
975 case ReductionType::kRowBoundChangeForcedByRow :
976 case ReductionType::kSaveRow :
977 case ReductionType::kReducedBoundsCost :
978 case ReductionType::kColumnDualValue :
979 case ReductionType::kRowDualValue :
980 case ReductionType::kCoefficientChange :
981 /* dual ReductionTypes should be only calculated for dual reductions and should not appear for MIP */
982 SCIPerrorMessage("PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
983 SCIPABORT(); /*lint --e{527}*/
984 break;
985#endif
986 default:
987 SCIPdebugMsg(scip, "PaPILO returned unknown data type: \n" );
988 continue;
989 }
990 }
991
992 /* tighten bounds of variables that are still present after presolving */
993 if( *result != SCIP_CUTOFF )
994 {
995 VariableDomains<papilo::Rational>& varDomains = problem.getVariableDomains();
996 SCIP_RATIONAL* varbound;
997 SCIP_CALL( SCIPrationalCreateBuffer(SCIPbuffer(scip), &varbound) );
998 varbound->isfprepresentable = SCIP_ISFPREPRESENTABLE_UNKNOWN;
999
1000 for( int i = 0; i != problem.getNCols(); ++i )
1001 {
1002 SCIP_VAR* var = SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[i]);
1003 if( !varDomains.flags[i].test(ColFlag::kLbInf) )
1004 {
1005 SCIP_Bool infeas;
1006 SCIP_Bool tightened;
1007
1008 setRational(scip, varbound, varDomains.lower_bounds[i]);
1009
1010 SCIP_CALL( SCIPtightenVarLbExact(scip, var, varbound, &infeas, &tightened) );
1011
1012 if( tightened )
1013 {
1014 *nchgbds += 1;
1015 SCIPrationalDebugMessage("Papilo tightened lb of variable %s \n", SCIPvarGetName(var));
1016 }
1017
1018 if( infeas )
1019 {
1020 *result = SCIP_CUTOFF;
1021 break;
1022 }
1023 }
1024
1025 if( !varDomains.flags[i].test(ColFlag::kUbInf) )
1026 {
1027 SCIP_Bool infeas;
1028 SCIP_Bool tightened;
1029 setRational(scip, varbound, varDomains.upper_bounds[i]);
1030
1031 SCIP_CALL( SCIPtightenVarUbExact(scip, var, varbound, &infeas, &tightened) );
1032
1033 if( tightened )
1034 {
1035 *nchgbds += 1;
1036 SCIPrationalDebugMessage("Papilo tightened ub of variable %s \n", SCIPvarGetName(var));
1037 }
1038
1039 if( infeas )
1040 {
1041 *result = SCIP_CUTOFF;
1042 break;
1043 }
1044 }
1045 }
1046
1047 SCIPrationalFreeBuffer(SCIPbuffer(scip), &varbound);
1048 }
1049
1050 /* finish with a final verb message and return */
1051 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1052 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
1053 SCIPgetSolvingTime(scip), presolve.getStatistics().nrounds, *naggrvars - oldnaggrvars,
1054 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds);
1055
1056 /* free the matrix */
1057 assert(initialized);
1058 SCIPmatrixFree(scip, &matrix);
1059
1060 return SCIP_OKAY;
1061}
1062#endif
1063
1064/** calls PaPILO presolving in floating-point arithmetic */
1065static
1066SCIP_RETCODE performRealPresolving(
1067 SCIP* scip, /**< SCIP data structure */
1068 SCIP_MATRIX* matrix, /**< initialized SCIP_MATRIX data structure */
1069 SCIP_PRESOLMILPDATA* data, /**< plugin specific presol data */
1070 SCIP_Bool initialized, /**< was the matrix initialized */
1071 int* nfixedvars, /**< store number of fixed variables */
1072 int* naggrvars, /**< store number of aggregated variables */
1073 int* nchgvartypes, /**< store number of changed variable types */
1074 int* nchgbds, /**< store number of changed bounds */
1075 int* naddholes, /**< store number of added holes */
1076 int* ndelconss, /**< store the number of deleted cons */
1077 int* naddconss, /**< store the number of added cons */
1078 int* nupgdconss, /**< store the number of upgraded cons */
1079 int* nchgcoefs, /**< store the number of changed coefficients */
1080 int* nchgsides, /**< store the number of changed sides */
1081 SCIP_RESULT* result /**< result pointer */
1082 )
1083{
1084 int nvars = SCIPgetNVars(scip);
1085 int nconss = SCIPgetNConss(scip);
1086
1087 /* only allow communication of constraint modifications by deleting all constraints when some already have been upgraded */
1088 SCIP_CONSHDLR* linconshdlr = SCIPfindConshdlr(scip, "linear");
1089 assert(linconshdlr != NULL);
1090 SCIP_Bool allowconsmodification = (SCIPconshdlrGetNCheckConss(linconshdlr) == SCIPmatrixGetNRows(matrix));
1091
1092 /* store current numbers of aggregations, fixings, and changed bounds for statistics */
1093 int oldnaggrvars = *naggrvars;
1094 int oldnfixedvars = *nfixedvars;
1095 int oldnchgbds = *nchgbds;
1096
1097 /* create presolving objects */
1098 Problem<SCIP_Real> problem = buildProblemReal(scip, matrix);
1099 int oldnnz = problem.getConstraintMatrix().getNnz();
1100 Presolve<SCIP_Real> presolve;
1101 setupPresolve(scip, presolve, data, allowconsmodification);
1102
1103 /* call the presolving */
1104 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1105 " (%.1fs) running MILP presolver%s\n", SCIPgetSolvingTime(scip),
1106 presolve.getPresolveOptions().threads == 1 ? "" : " on multiple threads");
1107
1108 /* call presolving without storing information for dual postsolve */
1109#if (PAPILO_VERSION_MAJOR >= 2)
1110 PresolveResult<SCIP_Real> res = presolve.apply(problem, false);
1111#else
1112 PresolveResult<SCIP_Real> res = presolve.apply(problem);
1113#endif
1114 data->lastncols = problem.getNCols();
1115 data->lastnrows = problem.getNRows();
1116
1117 /* evaluate the result */
1118 switch( res.status )
1119 {
1120 case PresolveStatus::kInfeasible:
1121 *result = SCIP_CUTOFF;
1122 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1123 " (%.1fs) MILP presolver detected infeasibility\n",
1124 SCIPgetSolvingTime(scip));
1125 SCIPmatrixFree(scip, &matrix);
1126 return SCIP_OKAY;
1127 case PresolveStatus::kUnbndOrInfeas:
1128 case PresolveStatus::kUnbounded:
1129 *result = SCIP_UNBOUNDED;
1130 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1131 " (%.1fs) MILP presolver detected unboundedness\n",
1132 SCIPgetSolvingTime(scip));
1133 SCIPmatrixFree(scip, &matrix);
1134 return SCIP_OKAY;
1135 case PresolveStatus::kUnchanged:
1136 *result = SCIP_DIDNOTFIND;
1137 data->lastncols = nvars;
1138 data->lastnrows = nconss;
1139 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1140 " (%.1fs) MILP presolver found nothing\n",
1141 SCIPgetSolvingTime(scip));
1142 SCIPmatrixFree(scip, &matrix);
1143 return SCIP_OKAY;
1144 case PresolveStatus::kReduced:
1145 data->lastncols = problem.getNCols();
1146 data->lastnrows = problem.getNRows();
1147 *result = SCIP_SUCCESS;
1148 }
1149
1150 /* result indicated success, now populate the changes into the SCIP structures */
1151
1152 /* tighten bounds of variables that are still present after presolving */
1153 VariableDomains<SCIP_Real>& varDomains = problem.getVariableDomains();
1154 for( int i = 0; i != problem.getNCols(); ++i )
1155 {
1156 assert( ! varDomains.flags[i].test(ColFlag::kInactive) );
1157 SCIP_VAR* var = SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[i]);
1158 if( !varDomains.flags[i].test(ColFlag::kLbInf) )
1159 {
1160 SCIP_Bool infeas;
1161 SCIP_Bool tightened;
1162 SCIP_CALL( SCIPtightenVarLb(scip, var, varDomains.lower_bounds[i], TRUE, &infeas, &tightened) );
1163
1164 if( tightened )
1165 *nchgbds += 1;
1166
1167 if( infeas )
1168 {
1169 *result = SCIP_CUTOFF;
1170 break;
1171 }
1172 }
1173
1174 if( !varDomains.flags[i].test(ColFlag::kUbInf) )
1175 {
1176 SCIP_Bool infeas;
1177 SCIP_Bool tightened;
1178 SCIP_CALL( SCIPtightenVarUb(scip, var, varDomains.upper_bounds[i], TRUE, &infeas, &tightened) );
1179
1180 if( tightened )
1181 *nchgbds += 1;
1182
1183 if( infeas )
1184 {
1185 *result = SCIP_CUTOFF;
1186 break;
1187 }
1188 }
1189 }
1190
1191 if( *result == SCIP_CUTOFF )
1192 {
1193 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1194 " (%.1fs) MILP presolver detected infeasibility\n",
1195 SCIPgetSolvingTime(scip));
1196 SCIPmatrixFree(scip, &matrix);
1197 return SCIP_OKAY;
1198 }
1199
1200 /* transfer variable fixings and aggregations */
1201 Vec<SCIP_VAR*> tmpvars;
1202 Vec<SCIP_Real> tmpvals;
1203
1204 /* if the size of the problem decreased by a sufficient factor, create all constraints from scratch if allowed */
1205 int newnnz = problem.getConstraintMatrix().getNnz();
1206 bool constraintsReplaced = false;
1207 if( newnnz == 0 || (allowconsmodification &&
1208 (problem.getNCols() <= data->modifyconsfac * SCIPmatrixGetNColumns(matrix) ||
1209 problem.getNRows() <= data->modifyconsfac * SCIPmatrixGetNRows(matrix) ||
1210 newnnz <= data->modifyconsfac * oldnnz)) )
1211 {
1212 int oldnrows = SCIPmatrixGetNRows(matrix);
1213 int newnrows = problem.getNRows();
1214
1215 constraintsReplaced = true;
1216
1217 /* capture constraints that are still present in the problem after presolve */
1218 for( int i = 0; i < newnrows; ++i )
1219 {
1220 SCIP_CONS* c = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
1221 SCIP_CALL( SCIPcaptureCons(scip, c) );
1222 }
1223
1224 /* delete all constraints */
1225 *ndelconss += oldnrows;
1226 *naddconss += newnrows;
1227
1228 for( int i = 0; i < oldnrows; ++i )
1229 {
1230 SCIP_CALL( SCIPdelCons(scip, SCIPmatrixGetCons(matrix, i)) );
1231 }
1232
1233 /* now loop over rows of presolved problem and create them as new linear constraints,
1234 * then release the old constraint after its name was passed to the new constraint */
1235 const Vec<RowFlags>& rflags = problem.getRowFlags();
1236 const auto& consmatrix = problem.getConstraintMatrix();
1237 for( int i = 0; i < newnrows; ++i )
1238 {
1239 auto rowvec = consmatrix.getRowCoefficients(i);
1240 const int* rowcols = rowvec.getIndices();
1241 /* SCIPcreateConsBasicLinear() requires a non const pointer */
1242 SCIP_Real* rowvals = const_cast<SCIP_Real*>(rowvec.getValues());
1243 int rowlen = rowvec.getLength();
1244
1245 /* retrieve SCIP compatible left and right hand sides */
1246 SCIP_Real lhs = rflags[i].test(RowFlag::kLhsInf) ? - SCIPinfinity(scip) : consmatrix.getLeftHandSides()[i];
1247 SCIP_Real rhs = rflags[i].test(RowFlag::kRhsInf) ? SCIPinfinity(scip) : consmatrix.getRightHandSides()[i];
1248
1249 /* create variable array matching the value array */
1250 tmpvars.clear();
1251 tmpvars.reserve(rowlen);
1252 for( int j = 0; j < rowlen; ++j )
1253 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.origcol_mapping[rowcols[j]]));
1254
1255 /* create and add new constraint with name of old constraint */
1256 SCIP_CONS* oldcons = SCIPmatrixGetCons(matrix, res.postsolve.origrow_mapping[i]);
1257 SCIP_CONS* cons;
1258 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, SCIPconsGetName(oldcons), rowlen, tmpvars.data(), rowvals, lhs, rhs) );
1259 SCIP_CALL( SCIPaddCons(scip, cons) );
1260
1261 /* release old and new constraint */
1262 SCIP_CALL( SCIPreleaseCons(scip, &oldcons) );
1263 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1264 }
1265 }
1266
1267 /* PaPILO's aggregations are valid regarding the constraints as they were presolved by PaPILO.
1268 * If coefficients were changed, but constraints in SCIP are not replaced by those from PaPILO,
1269 * then it can not be guaranteed that the bounds of multiaggregated variables will be enforced,
1270 * i.e., will be implied by the constraints in SCIP (see also #3704).
1271 * Only for variable aggregations, SCIP will ensure this by tightening the bounds on the aggregation
1272 * variable as part of SCIPaggregateVars(). For multiaggregations, we will only accept those
1273 * where we can be sure with a simple check that the bounds on the aggregated variable are implied.
1274 */
1275 bool checkmultaggr =
1276#if PAPILO_APIVERSION >= 1
1277 presolve.getStatistics().single_matrix_coefficient_changes > 0
1278#else
1279 presolve.getStatistics().ncoefchgs > 0
1280#endif
1281 && !constraintsReplaced;
1282
1283 /* loop over res.postsolve and add all fixed variables and aggregations to scip */
1284 for( std::size_t i = 0; i != res.postsolve.types.size(); ++i )
1285 {
1286 ReductionType type = res.postsolve.types[i];
1287 int first = res.postsolve.start[i];
1288 int last = res.postsolve.start[i + 1];
1289
1290 switch( type )
1291 {
1292 case ReductionType::kFixedCol:
1293 {
1294 SCIP_Bool infeas;
1295 SCIP_Bool fixed;
1296 int col = res.postsolve.indices[first];
1297
1298 SCIP_VAR* var = SCIPmatrixGetVar(matrix, col);
1299
1300 SCIP_Real value = res.postsolve.values[first];
1301
1302 SCIP_CALL( SCIPfixVar(scip, var, value, &infeas, &fixed) );
1303 *nfixedvars += 1;
1304
1305 assert(!infeas);
1306 /* SCIP has different rules for aggregating variables than PaPILO: therefore the variable PaPILO
1307 * tries to fix now may have been aggregated by SCIP before. Additionally, after aggregation SCIP
1308 * sometimes performs bound tightening resulting in possible fixings. These cases need to be excluded. */
1309 assert(fixed || SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED ||
1310 SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED);
1311 break;
1312 }
1313 /*
1314 * Dual-postsolving in PaPILO required introducing a postsolve-type for substitution with additional information.
1315 * Further, the different Substitution-postsolving types store the required postsolving data differently (in different order) in the postsolving stack.
1316 * Therefore, we need to distinguish how to parse the required data (rowLength, col, side, startRowCoefficients, lastRowCoefficients) from the postsolving stack.
1317 * If these values are accessed, the procedure is the same for both.
1318 */
1319#if (PAPILO_VERSION_MAJOR >= 2)
1320 case ReductionType::kSubstitutedColWithDual:
1321#endif
1322 case ReductionType::kSubstitutedCol:
1323 {
1324 int col = 0;
1325 SCIP_Real side = 0;
1326
1327 int rowlen = 0;
1328 int startRowCoefficients = 0;
1329 int lastRowCoefficients = 0;
1330
1331 if( type == ReductionType::kSubstitutedCol )
1332 {
1333 rowlen = last - first - 1;
1334 col = res.postsolve.indices[first];
1335 side = res.postsolve.values[first];
1336
1337 startRowCoefficients = first + 1;
1338 lastRowCoefficients = last;
1339 }
1340#if (PAPILO_VERSION_MAJOR >= 2)
1341 if( type == ReductionType::kSubstitutedColWithDual )
1342 {
1343 rowlen = (int) res.postsolve.values[first];
1344 col = res.postsolve.indices[first + 3 + rowlen];
1345 side = res.postsolve.values[first + 1];
1346
1347 startRowCoefficients = first + 3;
1348 lastRowCoefficients = first + 3 + rowlen;
1349
1350 assert(side == res.postsolve.values[first + 2]);
1351 assert(res.postsolve.indices[first + 1] == 0);
1352 assert(res.postsolve.indices[first + 2] == 0);
1353 }
1354 assert( type == ReductionType::kSubstitutedCol || type == ReductionType::kSubstitutedColWithDual );
1355#else
1356 assert( type == ReductionType::kSubstitutedCol );
1357#endif
1358 SCIP_Bool infeas;
1359 SCIP_Bool aggregated;
1360 SCIP_Bool redundant = FALSE;
1361 SCIP_Real constant = 0.0;
1362 if( rowlen == 2 )
1363 {
1364 SCIP_Real updatedSide;
1365 SCIP_VAR* varx = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients]);
1366 SCIP_VAR* vary = SCIPmatrixGetVar(matrix, res.postsolve.indices[startRowCoefficients + 1]);
1367 SCIP_Real scalarx = res.postsolve.values[startRowCoefficients];
1368 SCIP_Real scalary = res.postsolve.values[startRowCoefficients + 1];
1369
1370 SCIP_CALL( SCIPgetProbvarSum(scip, &varx, &scalarx, &constant) );
1371 assert(SCIPvarGetStatus(varx) != SCIP_VARSTATUS_MULTAGGR);
1372
1373 SCIP_CALL( SCIPgetProbvarSum(scip, &vary, &scalary, &constant) );
1374 assert(SCIPvarGetStatus(vary) != SCIP_VARSTATUS_MULTAGGR);
1375
1376 /* If PaPILO tries to aggregate fixed variables then it missed some obvious fixings.
1377 * This might happen if another aggregation leads to fixings which are not applied immediately by PaPILO.
1378 * With the latest version of PaPILO, this should not occur.
1379 */
1380 if( SCIPvarGetStatus(varx) == SCIP_VARSTATUS_FIXED && SCIPvarGetStatus(vary) == SCIP_VARSTATUS_FIXED )
1381 {
1382 SCIPdebugMsg(scip, "Aggregation of <%s> and <%s> rejected because they are already fixed.\n",
1383 SCIPvarGetName(varx), SCIPvarGetName(vary));
1384
1385 break;
1386 }
1387
1388 updatedSide = side - constant;
1389
1390 SCIP_CALL( SCIPaggregateVars(scip, varx, vary, scalarx, scalary, updatedSide, &infeas, &redundant, &aggregated) );
1391 }
1392 else
1393 {
1394 SCIP_Real colCoef = 0.0;
1395 SCIP_Real updatedSide;
1396 SCIP_Bool checklbimplied;
1397 SCIP_Bool checkubimplied;
1398 SCIP_Real impliedlb;
1399 SCIP_Real impliedub;
1400 int j;
1401
1402 for( j = startRowCoefficients; j < lastRowCoefficients; ++j )
1403 {
1404 if( res.postsolve.indices[j] == col )
1405 {
1406 colCoef = res.postsolve.values[j];
1407 break;
1408 }
1409 }
1410
1411 tmpvars.clear();
1412 tmpvals.clear();
1413 tmpvars.reserve(rowlen);
1414 tmpvals.reserve(rowlen);
1415
1416 assert(colCoef != 0.0);
1417 SCIP_VAR* aggrvar = SCIPmatrixGetVar(matrix, col);
1418
1419 SCIP_CALL( SCIPgetProbvarSum(scip, &aggrvar, &colCoef, &constant) );
1420 assert(SCIPvarGetStatus(aggrvar) != SCIP_VARSTATUS_MULTAGGR);
1421
1422 /* If PaPILO tries to multi-aggregate a fixed variable, then it missed some obvious fixings.
1423 * This might happen if another aggregation leads to fixings which are not applied immediately by PaPILO.
1424 * With the latest version of PaPILO, this should not occur.
1425 */
1426 if( SCIPvarGetStatus(aggrvar) == SCIP_VARSTATUS_FIXED )
1427 {
1428 SCIPdebugMsg(scip, "Multi-aggregation of <%s> rejected because it is already fixed.\n",
1429 SCIPvarGetName(aggrvar));
1430
1431 break;
1432 }
1433
1434 updatedSide = side - constant;
1435
1436 /* we need to check whether lb/ub on aggrvar is implied by bounds of other variables in multiaggregation
1437 * if checkmultaggr is TRUE and the lb/ub is finite
1438 * it should be sufficient to ensure global bounds on aggrvar (and as we are in presolve, local=global anyway)
1439 */
1440 checklbimplied = checkmultaggr && !SCIPisInfinity(scip, -SCIPvarGetLbGlobal(aggrvar));
1441 checkubimplied = checkmultaggr && !SCIPisInfinity(scip, SCIPvarGetUbGlobal(aggrvar));
1442 impliedlb = impliedub = updatedSide / colCoef;
1443
1444 for( j = startRowCoefficients; j < lastRowCoefficients; ++j )
1445 {
1446 SCIP_Real coef;
1447 SCIP_VAR* var;
1448
1449 if( res.postsolve.indices[j] == col )
1450 continue;
1451
1452 coef = - res.postsolve.values[j] / colCoef;
1453 var = SCIPmatrixGetVar(matrix, res.postsolve.indices[j]);
1454
1455 if( checklbimplied )
1456 {
1457 if( coef > 0.0 )
1458 {
1459 /* if impliedlb will be -infinity, then we can give up: we cannot use this mutiaggregation */
1460 if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
1461 break;
1462 else
1463 impliedlb += coef * SCIPvarGetLbLocal(var);
1464 }
1465 else
1466 {
1467 if( SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
1468 break;
1469 else
1470 impliedlb += coef * SCIPvarGetUbLocal(var);
1471 }
1472 }
1473
1474 if( checkubimplied )
1475 {
1476 if( coef > 0.0 )
1477 {
1478 if( SCIPisInfinity(scip, SCIPvarGetUbLocal(var)) )
1479 break;
1480 else
1481 impliedub += coef * SCIPvarGetUbLocal(var);
1482 }
1483 else
1484 {
1485 if( SCIPisInfinity(scip, -SCIPvarGetLbLocal(var)) )
1486 break;
1487 else
1488 impliedub += coef * SCIPvarGetLbLocal(var);
1489 }
1490 }
1491
1492 tmpvals.push_back(coef);
1493 tmpvars.push_back(var);
1494 }
1495
1496 /* if implied bounds are not sufficient to ensure bounds on aggrvar, then we cannot use the multiaggregation */
1497 if( j < lastRowCoefficients )
1498 break;
1499
1500 if( checklbimplied && SCIPisGT(scip, SCIPvarGetLbGlobal(aggrvar), impliedlb) )
1501 break;
1502
1503 if( checkubimplied && SCIPisLT(scip, SCIPvarGetUbGlobal(aggrvar), impliedub) )
1504 break;
1505
1506 SCIP_CALL( SCIPmultiaggregateVar(scip, aggrvar, tmpvars.size(),
1507 tmpvars.data(), tmpvals.data(), updatedSide / colCoef, &infeas, &aggregated) );
1508 }
1509
1510 if( aggregated )
1511 *naggrvars += 1;
1512 else if( constraintsReplaced && !redundant )
1513 {
1514 /* if the constraints where replaced, we need to add the failed substitution as an equality to SCIP */
1515 tmpvars.clear();
1516 tmpvals.clear();
1517 for( int j = startRowCoefficients; j < lastRowCoefficients; ++j )
1518 {
1519 tmpvars.push_back(SCIPmatrixGetVar(matrix, res.postsolve.indices[j]));
1520 tmpvals.push_back(res.postsolve.values[j]);
1521 }
1522
1523 SCIP_CONS* cons;
1524 String name = fmt::format("{}_failed_aggregation_equality", SCIPvarGetName(SCIPmatrixGetVar(matrix, col)));
1525 SCIP_CALL( SCIPcreateConsBasicLinear(scip, &cons, name.c_str(),
1526 tmpvars.size(), tmpvars.data(), tmpvals.data(), side, side ) );
1527 SCIP_CALL( SCIPaddCons(scip, cons) );
1528 SCIP_CALL( SCIPreleaseCons(scip, &cons) );
1529 *naddconss += 1;
1530 }
1531
1532 if( infeas )
1533 {
1534 *result = SCIP_CUTOFF;
1535 break;
1536 }
1537
1538 break;
1539 }
1540 case ReductionType::kParallelCol:
1541 return SCIP_INVALIDRESULT;
1542#if PAPILO_VERSION_MAJOR > 1 || (PAPILO_VERSION_MAJOR == 1 && PAPILO_VERSION_MINOR >= 1)
1543 case ReductionType::kFixedInfCol: {
1544 /* todo: currently SCIP can not handle this kind of reduction (see issue #3391) */
1545 assert(false);
1546 if(!constraintsReplaced)
1547 continue;
1548 SCIP_Bool infeas;
1549 SCIP_Bool fixed;
1550 SCIP_Real value = SCIPinfinity(scip);
1551
1552 int column = res.postsolve.indices[first];
1553 bool is_negative_infinity = res.postsolve.values[first] < 0;
1554 SCIP_VAR* column_variable = SCIPmatrixGetVar(matrix, column);
1555
1556 if( is_negative_infinity )
1557 {
1558 value = -SCIPinfinity(scip);
1559 }
1560
1561 SCIP_CALL( SCIPfixVar(scip, column_variable, value, &infeas, &fixed) );
1562 *nfixedvars += 1;
1563
1564 assert(!infeas);
1565 assert(fixed);
1566 break;
1567 }
1568#endif
1569#if (PAPILO_VERSION_MAJOR >= 2)
1570 case ReductionType::kVarBoundChange :
1571 case ReductionType::kRedundantRow :
1572 case ReductionType::kRowBoundChange :
1573 case ReductionType::kReasonForRowBoundChangeForcedByRow :
1574 case ReductionType::kRowBoundChangeForcedByRow :
1575 case ReductionType::kSaveRow :
1576 case ReductionType::kReducedBoundsCost :
1577 case ReductionType::kColumnDualValue :
1578 case ReductionType::kRowDualValue :
1579 case ReductionType::kCoefficientChange :
1580 /* dual ReductionTypes should be only calculated for dual reductions and should not appear for MIP */
1581 SCIPerrorMessage("PaPILO: PaPILO should not return dual postsolving reductions in SCIP!!\n");
1582 SCIPABORT(); /*lint --e{527}*/
1583 break;
1584#endif
1585 default:
1586 SCIPdebugMsg(scip, "PaPILO returned unknown data type: \n" );
1587 continue;
1588 }
1589 }
1590
1591 /* finish with a final verb message and return */
1592 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1593 " (%.1fs) MILP presolver (%d rounds): %d aggregations, %d fixings, %d bound changes\n",
1594 SCIPgetSolvingTime(scip), presolve.getStatistics().nrounds, *naggrvars - oldnaggrvars,
1595 *nfixedvars - oldnfixedvars, *nchgbds - oldnchgbds);
1596
1597 /* free the matrix */
1598 assert(initialized);
1599 SCIPmatrixFree(scip, &matrix);
1600
1601 return SCIP_OKAY;
1602}
1603
1604
1605/*
1606 * Callback methods of presolver
1607 */
1608
1609/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1610static
1611SCIP_DECL_PRESOLCOPY(presolCopyMILP)
1612{ /*lint --e{715}*/
1613 SCIP_CALL( SCIPincludePresolMILP(scip) );
1614
1615 return SCIP_OKAY;
1616}
1617
1618/** destructor of presolver to free user data (called when SCIP is exiting) */
1619static
1620SCIP_DECL_PRESOLFREE(presolFreeMILP)
1621{ /*lint --e{715}*/
1622 SCIP_PRESOLMILPDATA* data = reinterpret_cast<SCIP_PRESOLMILPDATA*>(SCIPpresolGetData(presol));
1623 assert(data != NULL);
1624
1625 SCIPpresolSetData(presol, NULL);
1626 SCIPfreeBlockMemory(scip, &data);
1627 return SCIP_OKAY;
1628}
1629
1630/** initialization method of presolver (called after problem was transformed) */
1631static
1632SCIP_DECL_PRESOLINIT(presolInitMILP)
1633{ /*lint --e{715}*/
1634 SCIP_PRESOLMILPDATA* data = reinterpret_cast<SCIP_PRESOLMILPDATA*>(SCIPpresolGetData(presol));
1635 assert(data != NULL);
1636
1637 data->lastncols = -1;
1638 data->lastnrows = -1;
1639
1640 return SCIP_OKAY;
1641}
1642
1643
1644/** execution method of presolver */
1645static
1646SCIP_DECL_PRESOLEXEC(presolExecMILP)
1647{ /*lint --e{715}*/
1648 SCIP_MATRIX* matrix;
1649 SCIP_PRESOLMILPDATA* data;
1650 SCIP_Bool initialized;
1651 SCIP_Bool complete;
1652 SCIP_Bool infeasible;
1653
1654 *result = SCIP_DIDNOTRUN;
1655
1656 data = reinterpret_cast<SCIP_PRESOLMILPDATA*>(SCIPpresolGetData(presol));
1657
1658 int nvars = SCIPgetNVars(scip);
1659 int nconss = SCIPgetNConss(scip);
1660
1661 /* run only if the problem size reduced by some amount since the last call or if it is the first call */
1662 if( data->lastncols != -1 && data->lastnrows != -1 &&
1663 nvars > data->lastncols * 0.85 &&
1664 nconss > data->lastnrows * 0.85 )
1665 return SCIP_OKAY;
1666
1667 SCIP_CALL( SCIPmatrixCreate(scip, &matrix, TRUE, &initialized, &complete, &infeasible,
1668 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
1669
1670 /* if infeasibility was detected during matrix creation, return here */
1671 if( infeasible )
1672 {
1673 if( initialized )
1674 SCIPmatrixFree(scip, &matrix);
1675
1676 *result = SCIP_CUTOFF;
1677 return SCIP_OKAY;
1678 }
1679
1680 /* we only work on pure MIPs, also disable to try building the matrix again if it failed once */
1681 if( !initialized || !complete )
1682 {
1683 data->lastncols = 0;
1684 data->lastnrows = 0;
1685
1686 if( initialized )
1687 SCIPmatrixFree(scip, &matrix);
1688
1689 return SCIP_OKAY;
1690 }
1691
1692 if( 0 != strncmp(data->filename, DEFAULT_FILENAME_PROBLEM, strlen(DEFAULT_FILENAME_PROBLEM)) )
1693 {
1694 SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL,
1695 " writing transformed problem to %s (only enforced constraints)\n", data->filename);
1696 SCIP_CALL( SCIPwriteTransProblem(scip, data->filename, NULL, FALSE) );
1697 }
1698
1699 if( !SCIPisExact(scip) )
1700 return performRealPresolving(scip, matrix, data, initialized, nfixedvars, naggrvars, nchgvartypes, nchgbds,
1701 naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result);
1702#if defined(PAPILO_WITH_EXACTPRESOLVE)
1703 else
1704 return performRationalPresolving(scip, matrix, data, initialized, nfixedvars, naggrvars, nchgvartypes, nchgbds,
1705 naddholes, ndelconss, naddconss, nupgdconss, nchgcoefs, nchgsides, result);
1706#endif
1707
1708 return SCIP_OKAY;
1709}
1710
1711
1712/*
1713 * presolver specific interface methods
1714 */
1715
1716/** creates the MILP presolver and includes it in SCIP */
1717SCIP_RETCODE SCIPincludePresolMILP(
1718 SCIP* scip /**< SCIP data structure */
1719 )
1720{
1721 SCIP_PRESOLMILPDATA* presoldata;
1722 SCIP_PRESOL* presol;
1723
1724#if defined(PAPILO_VERSION_TWEAK) && PAPILO_VERSION_TWEAK != 0
1725 String name = fmt::format("PaPILO {}.{}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH, PAPILO_VERSION_TWEAK);
1726#else
1727 String name = fmt::format("PaPILO {}.{}.{}", PAPILO_VERSION_MAJOR, PAPILO_VERSION_MINOR, PAPILO_VERSION_PATCH);
1728#endif
1729
1730#if defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
1731 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: {}]", PAPILO_GITHASH);
1732#elif !defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
1733 String desc("parallel presolve for integer and linear optimization (github.com/scipopt/papilo)");
1734#elif defined(PAPILO_GITHASH_AVAILABLE) && !defined(PAPILO_TBB)
1735 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: {}]", PAPILO_GITHASH);
1736#elif !defined(PAPILO_GITHASH_AVAILABLE) && defined(PAPILO_TBB)
1737 String desc = fmt::format("parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB)");
1738#endif
1739
1740 /* add external code info for the presolve library */
1741 SCIP_CALL( SCIPincludeExternalCodeInformation(scip, name.c_str(), desc.c_str()) );
1742
1743 /* create MILP presolver data */
1744 presoldata = NULL;
1745 SCIP_CALL( SCIPallocBlockMemory(scip, &presoldata) );
1746 BMSclearMemory(presoldata);
1747
1748 presol = NULL;
1749
1750 /* include presolver */
1751 SCIP_CALL( SCIPincludePresolBasic(scip, &presol, PRESOL_NAME, PRESOL_DESC, PRESOL_PRIORITY, PRESOL_MAXROUNDS, PRESOL_TIMING,
1752 presolExecMILP,
1753 reinterpret_cast<SCIP_PRESOLDATA*>(presoldata)) );
1754
1755 assert(presol != NULL);
1756
1757 /* set non fundamental callbacks via setter functions */
1758 SCIP_CALL( SCIPsetPresolCopy(scip, presol, presolCopyMILP) );
1759 SCIP_CALL( SCIPsetPresolFree(scip, presol, presolFreeMILP) );
1760 SCIP_CALL( SCIPsetPresolInit(scip, presol, presolInitMILP) );
1761
1762#if defined(PAPILO_WITH_EXACTPRESOLVE)
1763 /* mark presolver as exact */
1764 SCIPpresolMarkExact(presol);
1765#endif
1766
1767 /* add MILP presolver parameters */
1768#ifdef PAPILO_TBB
1769 SCIP_CALL( SCIPaddIntParam(scip,
1770 "presolving/" PRESOL_NAME "/threads",
1771 "maximum number of threads presolving may use (0: automatic)",
1772 &presoldata->threads, FALSE, DEFAULT_THREADS, 0, INT_MAX, NULL, NULL) );
1773#else
1774 presoldata->threads = 1;
1775#endif
1776
1777 SCIP_CALL( SCIPaddIntParam(scip,
1778 "presolving/" PRESOL_NAME "/maxfillinpersubstitution",
1779 "maximal possible fillin for substitutions to be considered",
1780 &presoldata->maxfillinpersubstitution, FALSE, DEFAULT_MAXFILLINPERSUBST, INT_MIN, INT_MAX, NULL, NULL) );
1781
1782 SCIP_CALL( SCIPaddIntParam(scip,
1783 "presolving/" PRESOL_NAME "/maxshiftperrow",
1784 "maximal amount of nonzeros allowed to be shifted to make space for substitutions",
1785 &presoldata->maxshiftperrow, TRUE, DEFAULT_MAXSHIFTPERROW, 0, INT_MAX, NULL, NULL) );
1786
1787 SCIP_CALL( SCIPaddIntParam(scip,
1788 "presolving/" PRESOL_NAME "/randomseed",
1789 "the random seed used for randomization of tie breaking",
1790 &presoldata->randomseed, FALSE, DEFAULT_RANDOMSEED, INT_MIN, INT_MAX, NULL, NULL) );
1791
1792 if( DependentRows<double>::Enabled )
1793 {
1794 SCIP_CALL( SCIPaddIntParam(scip,
1795 "presolving/" PRESOL_NAME "/detectlineardependency",
1796 "should linear dependent equations and free columns be removed? (0: never, 1: for LPs, 2: always)",
1797 &presoldata->detectlineardependency, TRUE, DEFAULT_DETECTLINDEP, 0, 2, NULL, NULL) );
1798 }
1799 else
1800 presoldata->detectlineardependency = DEFAULT_DETECTLINDEP;
1801
1802 SCIP_CALL( SCIPaddRealParam(scip,
1803 "presolving/" PRESOL_NAME "/modifyconsfac",
1804 "modify SCIP constraints when the number of nonzeros or rows is at most this factor "
1805 "times the number of nonzeros or rows before presolving",
1806 &presoldata->modifyconsfac, FALSE, DEFAULT_MODIFYCONSFAC, 0.0, 1.0, NULL, NULL) );
1807
1808 SCIP_CALL( SCIPaddRealParam(scip,
1809 "presolving/" PRESOL_NAME "/markowitztolerance",
1810 "the markowitz tolerance used for substitutions",
1811 &presoldata->markowitztolerance, FALSE, DEFAULT_MARKOWITZTOLERANCE, 0.0, 1.0, NULL, NULL) );
1812
1813 SCIP_CALL( SCIPaddRealParam(scip,
1814 "presolving/" PRESOL_NAME "/hugebound",
1815 "absolute bound value that is considered too huge for activity based calculations",
1816 &presoldata->hugebound, FALSE, DEFAULT_HUGEBOUND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
1817
1818#if PAPILO_APIVERSION >= 2
1819 SCIP_CALL( SCIPaddRealParam(scip, "presolving/" PRESOL_NAME "/abortfacexhaustive",
1820 "abort threshold for exhaustive presolving in PAPILO",
1821 &presoldata->abortfacexhaustive, TRUE, DEFAULT_ABORTFAC_EXHAUSTIVE, 0.0, 1.0, NULL, NULL) );
1822 SCIP_CALL( SCIPaddRealParam(scip, "presolving/" PRESOL_NAME "/abortfacmedium",
1823 "abort threshold for medium presolving in PAPILO",
1824 &presoldata->abortfacmedium, TRUE, DEFAULT_ABORTFAC_MEDIUM, 0.0, 1.0, NULL, NULL) );
1825 SCIP_CALL( SCIPaddRealParam(scip, "presolving/" PRESOL_NAME "/abortfacfast",
1826 "abort threshold for fast presolving in PAPILO",
1827 &presoldata->abortfacfast, TRUE, DEFAULT_ABORTFAC_FAST, 0.0, 1.0, NULL, NULL) );
1828#else
1829 presoldata->abortfacexhaustive = DEFAULT_ABORTFAC_EXHAUSTIVE;
1830 presoldata->abortfacmedium = DEFAULT_ABORTFAC_MEDIUM;
1831 presoldata->abortfacfast = DEFAULT_ABORTFAC_FAST;
1832#endif
1833
1834#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 1)
1835 SCIP_CALL( SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/maxbadgesizeseq",
1836 "maximal badge size in Probing in PaPILO if PaPILO is executed in sequential mode",
1837 &presoldata->maxbadgesizeseq, FALSE, DEFAULT_MAXBADGESIZE_SEQ, -1, INT_MAX, NULL, NULL) );
1838
1839 SCIP_CALL( SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/maxbadgesizepar",
1840 "maximal badge size in Probing in PaPILO if PaPILO is executed in parallel mode",
1841 &presoldata->maxbadgesizepar, FALSE, DEFAULT_MAXBADGESIZE_PAR, -1, INT_MAX, NULL, NULL) );
1842#else
1843 presoldata->maxbadgesizeseq = DEFAULT_MAXBADGESIZE_SEQ;
1844 presoldata->maxbadgesizepar = DEFAULT_MAXBADGESIZE_PAR;
1845#endif
1846
1847#if PAPILO_VERSION_MAJOR > 2 || (PAPILO_VERSION_MAJOR == 2 && PAPILO_VERSION_MINOR >= 3)
1848 SCIP_CALL( SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/internalmaxrounds",
1849 "internal maxrounds for each milp presolving (-1: no limit, 0: model cleanup)",
1850 &presoldata->internalmaxrounds, TRUE, DEFAULT_INTERNAL_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
1851#else
1852 presoldata->internalmaxrounds = DEFAULT_INTERNAL_MAXROUNDS;
1853#endif
1854
1855 SCIP_CALL( SCIPaddBoolParam(scip,
1856 "presolving/" PRESOL_NAME "/enableparallelrows",
1857 "should the parallel rows presolver be enabled within the presolve library?",
1858 &presoldata->enableparallelrows, TRUE, DEFAULT_ENABLEPARALLELROWS, NULL, NULL) );
1859
1860 SCIP_CALL( SCIPaddBoolParam(scip,
1861 "presolving/" PRESOL_NAME "/enabledomcol",
1862 "should the dominated column presolver be enabled within the presolve library?",
1863 &presoldata->enabledomcol, TRUE, DEFAULT_ENABLEDOMCOL, NULL, NULL) );
1864
1865 SCIP_CALL( SCIPaddBoolParam(scip,
1866 "presolving/" PRESOL_NAME "/enabledualinfer",
1867 "should the dualinfer presolver be enabled within the presolve library?",
1868 &presoldata->enabledualinfer, TRUE, DEFAULT_ENABLEDUALINFER, NULL, NULL) );
1869
1870 SCIP_CALL( SCIPaddBoolParam(scip,
1871 "presolving/" PRESOL_NAME "/enablemultiaggr",
1872 "should the multi-aggregation presolver be enabled within the presolve library?",
1873 &presoldata->enablemultiaggr, TRUE, DEFAULT_ENABLEMULTIAGGR, NULL, NULL) );
1874
1875 SCIP_CALL( SCIPaddBoolParam(scip,
1876 "presolving/" PRESOL_NAME "/enableprobing",
1877 "should the probing presolver be enabled within the presolve library?",
1878 &presoldata->enableprobing, TRUE, DEFAULT_ENABLEPROBING, NULL, NULL) );
1879
1880 SCIP_CALL( SCIPaddBoolParam(scip,
1881 "presolving/" PRESOL_NAME "/enablesparsify",
1882 "should the sparsify presolver be enabled within the presolve library?",
1883 &presoldata->enablesparsify, TRUE, DEFAULT_ENABLESPARSIFY, NULL, NULL) );
1884
1885 SCIP_CALL( SCIPaddStringParam(scip, "presolving/" PRESOL_NAME "/probfilename",
1886 "filename to store the problem before MILP presolving starts (only enforced constraints)",
1887 &presoldata->filename, TRUE, DEFAULT_FILENAME_PROBLEM, NULL, NULL) );
1888
1889 SCIP_CALL( SCIPaddIntParam(scip, "presolving/" PRESOL_NAME "/verbosity",
1890 "verbosity level of PaPILO (0: quiet, 1: errors, 2: warnings, 3: normal, 4: detailed)",
1891 &presoldata->verbosity, FALSE, DEFAULT_VERBOSITY, 0, 4, NULL, NULL) );
1892#if PAPILO_APIVERSION >= 6
1893 SCIP_CALL( SCIPaddBoolParam(scip,
1894 "presolving/" PRESOL_NAME "/enablecliquemerging",
1895 "should the clique merging presolver be enabled within the presolve library?",
1896 &presoldata->enablecliquemerging, TRUE, DEFAULT_ENABLECLIQUEMERGE, NULL, NULL) );
1897 SCIP_CALL( SCIPaddIntParam(scip,
1898 "presolving/" PRESOL_NAME "/maxedgesparallel",
1899 "maximal amount of edges in the parallel clique merging graph",
1900 &presoldata->maxedgesparallel, FALSE, DEFAULT_MAXEDGESPARALLEL, -1, INT_MAX, NULL, NULL) );
1901 SCIP_CALL( SCIPaddIntParam(scip,
1902 "presolving/" PRESOL_NAME "/maxedgessequential",
1903 "maximal amount of edges in the sequential clique merging graph",
1904 &presoldata->maxedgessequential, FALSE, DEFAULT_MAXEDGESSEQUENTIAL, -1, INT_MAX, NULL, NULL) );
1905 SCIP_CALL( SCIPaddIntParam(scip,
1906 "presolving/" PRESOL_NAME "/maxcliquesize",
1907 "maximal size of clique considered for clique merging",
1908 &presoldata->maxcliquesize, FALSE, DEFAULT_MAXCLIQUESIZE, -1, INT_MAX, NULL, NULL) );
1909 SCIP_CALL( SCIPaddIntParam(scip,
1910 "presolving/" PRESOL_NAME "/maxgreedycalls",
1911 "maximal number of greedy max clique calls in a single thread",
1912 &presoldata->maxgreedycalls, FALSE, DEFAULT_MAXGREEDYCALLS, -1, INT_MAX, NULL, NULL) );
1913#endif
1914#if PAPILO_APIVERSION >= 13
1915 SCIP_CALL( SCIPaddBoolParam(scip,
1916 "presolving/" PRESOL_NAME "/enableGF2",
1917 "should the GF2 presolver be enabled within the presolve library?",
1918 &presoldata->enableGF2, TRUE, DEFAULT_ENABLEGF2, NULL, NULL) );
1919#endif
1920
1921 return SCIP_OKAY;
1922}
1923
1924#endif
cons_exactlinear.h
Constraint handler for linear constraints in their most general form, .
cons_linear.h
Constraint handler for linear constraints in their most general form, .
NULL
#define NULL
Definition def.h:257
SCIP_REAL_MAX
#define SCIP_REAL_MAX
Definition def.h:167
SCIP_Bool
#define SCIP_Bool
Definition def.h:100
SCIP_Real
#define SCIP_Real
Definition def.h:165
TRUE
#define TRUE
Definition def.h:102
FALSE
#define FALSE
Definition def.h:103
SCIPABORT
#define SCIPABORT()
Definition def.h:336
REALABS
#define REALABS(x)
Definition def.h:191
SCIP_CALL
#define SCIP_CALL(x)
Definition def.h:364
SCIPcreateConsBasicLinear
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)
Definition cons_linear.c:17924
SCIPcreateConsBasicExactLinear
SCIP_RETCODE SCIPcreateConsBasicExactLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_RATIONAL **vals, SCIP_RATIONAL *lhs, SCIP_RATIONAL *rhs)
Definition cons_exactlinear.c:6778
SCIPgetProbName
const char * SCIPgetProbName(SCIP *scip)
Definition scip_prob.c:1242
SCIPgetNVars
int SCIPgetNVars(SCIP *scip)
Definition scip_prob.c:2246
SCIPaddCons
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3274
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3420
SCIPgetNConss
int SCIPgetNConss(SCIP *scip)
Definition scip_prob.c:3620
SCIPwriteTransProblem
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
Definition scip_prob.c:789
SCIPverbMessage
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition scip_message.c:225
SCIPdebugMsg
#define SCIPdebugMsg
Definition scip_message.h:78
SCIPaddIntParam
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
SCIPaddStringParam
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
SCIPaddRealParam
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
SCIPgetRealParam
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
Definition scip_param.c:307
SCIPaddBoolParam
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
SCIPincludePresolMILP
SCIP_RETCODE SCIPincludePresolMILP(SCIP *scip)
Definition presol_milp.cpp:46
SCIPconshdlrGetNCheckConss
int SCIPconshdlrGetNCheckConss(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4802
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:940
SCIPprintCons
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition scip_cons.c:2536
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8393
SCIPreleaseCons
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1173
SCIPcaptureCons
SCIP_RETCODE SCIPcaptureCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1138
SCIPisExact
SCIP_Bool SCIPisExact(SCIP *scip)
Definition scip_exact.c:193
SCIPincludeExternalCodeInformation
SCIP_RETCODE SCIPincludeExternalCodeInformation(SCIP *scip, const char *name, const char *description)
Definition scip_general.c:777
SCIPbuffer
BMS_BUFMEM * SCIPbuffer(SCIP *scip)
Definition scip_mem.c:72
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIPsetPresolFree
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
Definition scip_presol.c:164
SCIPpresolMarkExact
void SCIPpresolMarkExact(SCIP_PRESOL *presol)
Definition presol.c:615
SCIPpresolSetData
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
Definition presol.c:538
SCIPpresolGetData
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
Definition presol.c:528
SCIPsetPresolCopy
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
Definition scip_presol.c:148
SCIPincludePresolBasic
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:113
SCIPsetPresolInit
SCIP_RETCODE SCIPsetPresolInit(SCIP *scip, SCIP_PRESOL *presol,)
Definition scip_presol.c:180
SCIPrationalSetInfinity
void SCIPrationalSetInfinity(SCIP_RATIONAL *res)
Definition rational.cpp:619
SCIPrationalGetReal
SCIP_Real SCIPrationalGetReal(SCIP_RATIONAL *rational)
Definition rational.cpp:2084
SCIPrationalDebugMessage
#define SCIPrationalDebugMessage
Definition rational.h:641
SCIPrationalDiv
void SCIPrationalDiv(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition rational.cpp:1133
SCIPrationalIsAbsInfinity
SCIP_Bool SCIPrationalIsAbsInfinity(SCIP_RATIONAL *rational)
Definition rational.cpp:1681
SCIPrationalFreeBuffer
void SCIPrationalFreeBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition rational.cpp:474
SCIPrationalDiff
void SCIPrationalDiff(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_RATIONAL *op2)
Definition rational.cpp:984
SCIPrationalCreateBuffer
SCIP_RETCODE SCIPrationalCreateBuffer(BMS_BUFMEM *bufmem, SCIP_RATIONAL **rational)
Definition rational.cpp:124
SCIPrationalIsZero
SCIP_Bool SCIPrationalIsZero(SCIP_RATIONAL *rational)
Definition rational.cpp:1625
SCIPrationalSetNegInfinity
void SCIPrationalSetNegInfinity(SCIP_RATIONAL *res)
Definition rational.cpp:631
SCIPrationalIsNegative
SCIP_Bool SCIPrationalIsNegative(SCIP_RATIONAL *rational)
Definition rational.cpp:1651
SCIPrationalIsInfinity
SCIP_Bool SCIPrationalIsInfinity(SCIP_RATIONAL *rational)
Definition rational.cpp:1661
SCIPrationalCreateBufferArray
SCIP_RETCODE SCIPrationalCreateBufferArray(BMS_BUFMEM *mem, SCIP_RATIONAL ***rational, int size)
Definition rational.cpp:215
SCIPrationalIsNegInfinity
SCIP_Bool SCIPrationalIsNegInfinity(SCIP_RATIONAL *rational)
Definition rational.cpp:1671
SCIPrationalMultReal
void SCIPrationalMultReal(SCIP_RATIONAL *res, SCIP_RATIONAL *op1, SCIP_Real op2)
Definition rational.cpp:1098
SCIPrationalFreeBufferArray
void SCIPrationalFreeBufferArray(BMS_BUFMEM *mem, SCIP_RATIONAL ***ratbufarray, int size)
Definition rational.cpp:519
SCIPgetSolvingTime
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition scip_timing.c:378
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition scip_numerics.c:501
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:512
SCIPfeastol
SCIP_Real SCIPfeastol(SCIP *scip)
Definition scip_numerics.c:168
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:475
SCIPepsilon
SCIP_Real SCIPepsilon(SCIP *scip)
Definition scip_numerics.c:140
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:449
SCIPtightenVarLb
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:6401
SCIPtightenVarUbExact
SCIP_RETCODE SCIPtightenVarUbExact(SCIP *scip, SCIP_VAR *var, SCIP_RATIONAL *newbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:6768
SCIPvarGetAggrScalarExact
SCIP_RATIONAL * SCIPvarGetAggrScalarExact(SCIP_VAR *var)
Definition var.c:23792
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:23418
SCIPvarIsImpliedIntegral
SCIP_Bool SCIPvarIsImpliedIntegral(SCIP_VAR *var)
Definition var.c:23530
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:24300
SCIPaggregateVarsExact
SCIP_RETCODE SCIPaggregateVarsExact(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_RATIONAL *scalarx, SCIP_RATIONAL *scalary, SCIP_RATIONAL *rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition scip_var.c:10692
SCIPvarGetAggrConstantExact
SCIP_RATIONAL * SCIPvarGetAggrConstantExact(SCIP_VAR *var)
Definition var.c:23815
SCIPaggregateVars
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:10550
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:23932
SCIPtightenVarUb
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:6651
SCIPvarGetType
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:23485
SCIPgetProbvarSum
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition scip_var.c:2499
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:24174
SCIPvarGetStatusExact
SCIP_VARSTATUS SCIPvarGetStatusExact(SCIP_VAR *var)
Definition var.c:23428
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:23299
SCIPmultiaggregateVar
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:10834
SCIPvarIsIntegral
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition var.c:23522
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:24266
SCIPvarGetLbGlobalExact
SCIP_RATIONAL * SCIPvarGetLbGlobalExact(SCIP_VAR *var)
Definition var.c:24162
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:24152
SCIPfixVar
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:10318
SCIPgetProbvarSumExact
SCIP_RETCODE SCIPgetProbvarSumExact(SCIP *scip, SCIP_VAR **var, SCIP_RATIONAL *scalar, SCIP_RATIONAL *constant)
Definition scip_var.c:2538
SCIPvarGetObjExact
SCIP_RATIONAL * SCIPvarGetObjExact(SCIP_VAR *var)
Definition var.c:23942
SCIPallowWeakDualReds
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
Definition scip_var.c:10998
SCIPmultiaggregateVarExact
SCIP_RETCODE SCIPmultiaggregateVarExact(SCIP *scip, SCIP_VAR *var, int naggvars, SCIP_VAR **aggvars, SCIP_RATIONAL **scalars, SCIP_RATIONAL *constant, SCIP_Bool *infeasible, SCIP_Bool *aggregated)
Definition scip_var.c:10879
SCIPtightenVarLbExact
SCIP_RETCODE SCIPtightenVarLbExact(SCIP *scip, SCIP_VAR *var, SCIP_RATIONAL *newbound, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:6518
SCIPallowStrongDualReds
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:10984
SCIPvarGetUbGlobalExact
SCIP_RATIONAL * SCIPvarGetUbGlobalExact(SCIP_VAR *var)
Definition var.c:24184
SCIPfixVarExact
SCIP_RETCODE SCIPfixVarExact(SCIP *scip, SCIP_VAR *var, SCIP_RATIONAL *fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:10420
SCIPvarGetAggrVar
SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
Definition var.c:23768
SCIPinitializeRandomSeed
unsigned int SCIPinitializeRandomSeed(SCIP *scip, unsigned int initialseedvalue)
Definition scip_randnumgen.c:111
result
* result
Definition heur_actconsdiving.c:297
SCIP_OKAY
return SCIP_OKAY
Definition heur_actconsdiving.c:237
c
int c
Definition heur_intdiving.c:223
assert
assert(minobj< SCIPgetCutoffbound(scip))
nvars
int nvars
Definition heur_intshifting.c:711
var
SCIP_VAR * var
Definition heur_objpscostdiving.c:269
i
int i
Definition heur_rootsoldiving.c:216
SCIPmatrixGetNNonzs
int SCIPmatrixGetNNonzs(SCIP_MATRIX *matrix)
Definition matrix.c:2107
SCIPmatrixGetRowLhsExact
SCIP_RATIONAL * SCIPmatrixGetRowLhsExact(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2071
SCIPmatrixGetRowNNonzs
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2013
SCIPmatrixGetRowLhs
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2047
SCIPmatrixGetRowValPtr
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1977
SCIPmatrixGetRowValPtrExact
SCIP_RATIONAL ** SCIPmatrixGetRowValPtrExact(SCIP_MATRIX *matrix, int row)
Definition matrix.c:1989
SCIPmatrixGetRowRhs
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2059
SCIPmatrixCreate
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:703
SCIPmatrixGetNColumns
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
Definition matrix.c:1897
SCIPmatrixGetCons
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2189
SCIPmatrixFree
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
Definition matrix.c:1348
SCIPmatrixGetVar
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
Definition matrix.c:1953
SCIPmatrixGetRowRhsExact
SCIP_RATIONAL * SCIPmatrixGetRowRhsExact(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2083
SCIPmatrixGetRowIdxPtr
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
Definition matrix.c:2001
SCIPmatrixGetNRows
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
Definition matrix.c:2037
BMSclearMemory
#define BMSclearMemory(ptr)
Definition memory.h:129
PRESOL_NAME
#define PRESOL_NAME
Definition presol_boundshift.c:52
PRESOL_PRIORITY
#define PRESOL_PRIORITY
Definition presol_boundshift.c:54
PRESOL_MAXROUNDS
#define PRESOL_MAXROUNDS
Definition presol_boundshift.c:55
PRESOL_TIMING
#define PRESOL_TIMING
Definition presol_boundshift.c:56
PRESOL_DESC
#define PRESOL_DESC
Definition presol_boundshift.c:53
presol_milp.h
MILP presolver that calls the presolve library on the constraint matrix.
pub_cons.h
public methods for managing constraints
pub_matrix.h
public methods for matrix
pub_message.h
public methods for message output
SCIPerrorMessage
#define SCIPerrorMessage
Definition pub_message.h:64
SCIPdebug
#define SCIPdebug(x)
Definition pub_message.h:93
SCIPdebugMessage
#define SCIPdebugMessage
Definition pub_message.h:96
pub_presol.h
public methods for presolvers
pub_var.h
public methods for problem variables
rational.h
wrapper for rational number arithmetic
DEFAULT_RANDOMSEED
#define DEFAULT_RANDOMSEED
Definition reader_scflp.c:116
scip_cons.h
public methods for constraint handler plugins and constraints
scip_exact.h
public methods for exact solving
scip_general.h
general public methods
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_numerics.h
public methods for numerical tolerances
scip_param.h
public methods for SCIP parameter handling
scip_presol.h
public methods for presolving plugins
scip_prob.h
public methods for global and local (sub)problems
scip_randnumgen.h
public methods for random numbers
presolve
static SCIP_RETCODE presolve(SCIP *scip, SCIP_Bool *unbounded, SCIP_Bool *infeasible, SCIP_Bool *vanished)
Definition scip_solve.c:1096
scip_timing.h
public methods for timing
scip_var.h
public methods for SCIP variables
SCIP_Rational::val
scip::Rational val
Definition struct_rational.h:48
SCIP_Rational::isfprepresentable
unsigned int isfprepresentable
Definition struct_rational.h:50
struct_rational.h
definition of wrapper class for rational numbers
SCIP_CONS
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
SCIP_CONSHDLR
struct SCIP_Conshdlr SCIP_CONSHDLR
Definition type_cons.h:62
SCIP_MATRIX
struct SCIP_Matrix SCIP_MATRIX
Definition type_matrix.h:42
SCIP_VERBLEVEL_HIGH
@ SCIP_VERBLEVEL_HIGH
Definition type_message.h:61
SCIP_DECL_PRESOLCOPY
#define SCIP_DECL_PRESOLCOPY(x)
Definition type_presol.h:60
SCIP_PRESOLDATA
struct SCIP_PresolData SCIP_PRESOLDATA
Definition type_presol.h:51
SCIP_DECL_PRESOLFREE
#define SCIP_DECL_PRESOLFREE(x)
Definition type_presol.h:68
SCIP_PRESOL
struct SCIP_Presol SCIP_PRESOL
Definition type_presol.h:50
SCIP_DECL_PRESOLINIT
#define SCIP_DECL_PRESOLINIT(x)
Definition type_presol.h:76
SCIP_DECL_PRESOLEXEC
#define SCIP_DECL_PRESOLEXEC(x)
Definition type_presol.h:167
SCIP_RATIONAL
struct SCIP_Rational SCIP_RATIONAL
Definition type_rational.h:40
SCIP_ISFPREPRESENTABLE_UNKNOWN
@ SCIP_ISFPREPRESENTABLE_UNKNOWN
Definition type_rational.h:48
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition type_result.h:48
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition type_result.h:44
SCIP_UNBOUNDED
@ SCIP_UNBOUNDED
Definition type_result.h:47
SCIP_SUCCESS
@ SCIP_SUCCESS
Definition type_result.h:58
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
SCIP_INVALIDRESULT
@ SCIP_INVALIDRESULT
Definition type_retcode.h:53
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition type_retcode.h:63
SCIP
struct Scip SCIP
Definition type_scip.h:39
SCIP_VAR
struct SCIP_Var SCIP_VAR
Definition type_var.h:166
SCIP_VARTYPE_CONTINUOUS
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
SCIP_VARSTATUS_FIXED
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:54
SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:56
SCIP_VARSTATUS_NEGATED
@ SCIP_VARSTATUS_NEGATED
Definition type_var.h:57
SCIP_VARSTATUS_AGGREGATED
@ SCIP_VARSTATUS_AGGREGATED
Definition type_var.h:55