Exact solver returns spurious infeasible result with large coefficients

[LegionMammal978]

I've been attempting to use SCIP's exact mode to solve some ILP instances with very large coefficients. However, even with exact/enabled = TRUE, there seems to be some rounding in the objective function that causes issues when the coefficients are more than ~20 digits. As a minimal example, this instance returns SCIP Status: problem is solved [infeasible], even though x = 1 is quite clearly a feasible solution:

$ cat scip.set 
exact/enable = TRUE
$ cat problem.lp 
Minimize
obj: 99999999999999983617 x
Subject To
cond: x >= 1
General
x
End
$ scip -f problem.lp
SCIP version 10.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 7.1.4] [GitHash: ec1ecceb59]
Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 7.1.4         Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 7c53d552]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.3             General purpose compression library by J. Gailly and M. Adler (zlib.net)
  MPFR 4.2.1           GNU Multiple Precision Floating-Point Reliable Library (mpfr.org)
  Boost 1.83.0         Boost C++ Libraries (boost.org)
  TinyCThread 1.2      small portable implementation of the C11 threads API (tinycthread.github.io)
  GMP 6.3.0            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.6.2          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 4.0.0        AMPL .nl file reader library (github.com/ampl/mp)
  PaPILO 2.4.2         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: 4b399c4c]
  Nauty 2.8.8          Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)
  sassy 2.0            Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)

[...]

(See stdout.txt.) I'm not entirely sure if there's some other parameter I have to set to "actually make it exact", or if SCIP is simply the wrong tool for the job here.

[ambros-gleixner]

Thanks for reporting this! Some comments:

• Although SCIP is exact, it has limitations to what input data it can accept which are due to the fact that it follows a hybrid-precision algorithm and maintains a floating-point version of the problem in parallel. The floating-point part can treats numbers beyond 1e20 as infinite. The infinity threshold value can be changed in theory, but currently only at compile time.
• In the trivial problem.lp however, the issue is probably a bug in presolving that has been fixed today. Can you try again with the latest master?
• Generally, I would recommend to rescale your problems before giving them to SCIP. The 20 decimal digits of precision or more are not an issue in itself, but the largest numbers should ideally be below 1e16 in absolute value.
• That being said we should add a warning or even issue an error on such input data.
• Also I recommend you to switch SoPlex to the current master.

[DominikKamp]

Not fixed yet (the report is already on latest master).

[DominikKamp]

Certainly exact SCIP is by default only exact for variables, activities, and objectives within the infinity bounds but in this case it should just provide the correct result without a warning.

[LegionMammal978]

Also I recommend you to switch SoPlex to the current master.

No difference if I switch it to SoPlex 8.0.0 [GitHash: 85549f2c].

Generally, I would recommend to rescale your problems before giving them to SCIP. The 20 decimal digits of precision or more are not an issue in itself, but the largest numbers should ideally be below 1e16 in absolute value.

Yeah, I know this is the standard advice, but it's unfortunately not possible in my case. The actual problem has one huge integer variable (with up to hundreds of digits) and a few hundred boolean variables (all separated by orders of magnitude). The integrality constraint is very important for the huge variable, since a trivial solution will always exist if it is relaxed to a fraction, so there's no way to neglect any of its digits.

In particular, trying to solve this problem with traditional branching will fail miserably. I figured that ILP solvers may have a few more tricks up their sleeve, but it was always a long shot, especially since I've found that ~all of them are optimized for many variables with small coefficients. My other option is to try SAT solvers with bitvector arithmetic, but I've had poor experiences with how slow they are to give unsat results, and with how opaque those results can be. I may just be entirely out of luck here.

[DominikKamp]

Here with scaling just a multiplication by some small factor is meant without changing the variable definitions. In this case it is enough to plug a 0. in front of the objective coefficient. The infinity bound is a fixed absolute value while in principle arbitrarily small coefficients can be handled exactly.

@ambros-gleixner Nevertheless, please check why the empty solution is not accepted in the end of presolving.

[LegionMammal978]

The infinity bound is a fixed absolute value while in principle arbitrarily small coefficients can be handled exactly.

I can shrink the coefficients, but large solution values still cause issues, and I can't shrink those without affecting integrality. To give another minimal example (note that scaling down the objective coefficient further does not help):

$ cat scip.set 
exact/enable = TRUE
lm978@firmament:~/gtms/fast-33-lp$ cat problem.lp 
Minimize
obj: d0
Subject To
cond: 0.00000000000000000001 d0 >= 1
General
d0
End
$ scip -f problem.lp
SCIP version 10.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 8.0.0] [GitHash: ec1ecceb59]
Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 8.0.0         Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 85549f2c]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.3             General purpose compression library by J. Gailly and M. Adler (zlib.net)
  MPFR 4.2.1           GNU Multiple Precision Floating-Point Reliable Library (mpfr.org)
  Boost 1.83.0         Boost C++ Libraries (boost.org)
  TinyCThread 1.2      small portable implementation of the C11 threads API (tinycthread.github.io)
  GMP 6.3.0            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  ZIMPL 3.6.2          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 4.0.0        AMPL .nl file reader library (github.com/ampl/mp)
  PaPILO 2.4.2         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) (built with TBB) [GitHash: 4b399c4c]
  Nauty 2.8.8          Computing Graph Automorphism Groups by Brendan D. McKay (users.cecs.anu.edu.au/~bdm/nauty)
  sassy 2.0            Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)

[...]

SCIP Status        : problem is solved [infeasible]
Solving Time (sec) : 0.00
Solving Nodes      : 0
Primal Bound       : +1.00000000000000e+20 (0 solutions)
Dual Bound         : +1.00000000000000e+20
Gap                : 0.00 %

[...]

stdout.txt

[DominikKamp]

This is expected. If you have a common upper bound on the absolute solution values, try redefining SCIP_DEFAULT_INFINITY in def.h and recompile. Otherwise, if you know that there is a feasible solution in some region, you could offset the variable definitions in advance so that they will not exceed the infinity bound in SCIP.