Presolving renders problem infeasible

[rajgoel]

While debugging my own application, I encountered a problem that appears to be related to SCIP presolving. Presolve appears to render this non-linear problem debug_problem.cip infeasible:

With 3 rounds of presolving

scip -c "read debug_problem.cip set presolving maxrounds 3 optimize quit"

I get

SCIP version 10.0.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 8.0.1] [GitHash: 76a50c97d6]
Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 8.0.1         Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: c69290aa]
  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)
  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.7.0          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 4.0.4        AMPL .nl file reader library (github.com/ampl/mp)
  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)

user parameter file <scip.set> not found - using default parameters


read problem <debug_problem.cip>
============

original problem has 843 variables (740 bin, 41 int, 62 cont) and 1338 constraints
presolving/maxrounds = 3

presolving:
(round 1, fast)       211 del vars, 470 del conss, 8 add conss, 482 chg bounds, 28 chg sides, 0 chg coeffs, 96 upgd conss, 0 impls, 0 clqs, 0 implints
(round 2, fast)       625 del vars, 688 del conss, 8 add conss, 507 chg bounds, 54 chg sides, 0 chg coeffs, 109 upgd conss, 0 impls, 12 clqs, 0 implints
   (0.1s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.1s) symmetry computation finished: 170 generators found (max: 1500, log10 of symmetry group size: 229.17) (symcode time: 0.00)
dynamic symmetry handling statistics:
   orbitopal reduction:       no components
   orbital reduction:          4 components of sizes 83, 63, 11, 3
   lexicographic reduction:  161 permutations with support sizes 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 6
handled 11 out of 11 symmetry components
presolving (3 rounds: 3 fast, 1 medium, 1 exhaustive):
 691 deleted vars, 1155 deleted constraints, 25 added constraints, 716 tightened bounds, 0 added holes, 56 changed sides, 0 changed coefficients
 1 implications, 5 cliques, 8 implied integral variables (0 bin, 0 int, 8 cont)
presolving detected infeasibility
Presolving Time: 0.07

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

Whereas with at most 2 rounds of presolving

scip -c "read debug_problem.cip set presolving maxrounds 2 optimize quit"

I get

SCIP version 10.0.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 8.0.1] [GitHash: 76a50c97d6]
Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 8.0.1         Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: c69290aa]
  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)
  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.7.0          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 4.0.4        AMPL .nl file reader library (github.com/ampl/mp)
  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)

user parameter file <scip.set> not found - using default parameters


read problem <debug_problem.cip>
============

original problem has 843 variables (740 bin, 41 int, 62 cont) and 1338 constraints
presolving/maxrounds = 2

presolving:
(round 1, fast)       211 del vars, 470 del conss, 8 add conss, 482 chg bounds, 28 chg sides, 0 chg coeffs, 96 upgd conss, 0 impls, 0 clqs, 0 implints
   (0.1s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.1s) symmetry computation finished: 26 generators found (max: 1500, log10 of symmetry group size: 150.98) (symcode time: 0.00)
dynamic symmetry handling statistics:
   orbitopal reduction:        5 components: 2x4, 3x3, 2x3, 2x3, 2x5
   orbital reduction:         no components
   lexicographic reduction:   11 permutations with support sizes 10, 10, 10, 10, 10, 4, 10, 4, 4, 10, 4
handled 18 out of 18 symmetry components
presolving (2 rounds: 2 fast, 1 medium, 1 exhaustive):
 798 deleted vars, 835 deleted constraints, 18 added constraints, 520 tightened bounds, 0 added holes, 54 changed sides, 9 changed coefficients
 8 implications, 79 cliques, 2 implied integral variables (0 bin, 0 int, 2 cont)
presolved problem has 150 variables (132 bin, 0 int, 18 cont) and 352 constraints
      6 constraints of type <setppc>
      8 constraints of type <and>
     16 constraints of type <linear>
    322 constraints of type <nonlinear>
transformed objective value is always integral (scale: 1)
Presolving Time: 0.08

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
t 0.1s|     1 |     0 |     0 |     - | trivial|   0 | 150 | 324 |   0 |   0 |  0 |   0 |   0 | 1.000000e-09 | 1.000000e-09 |   0.00%| unknown

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 0.10
Solving Nodes      : 1
Primal Bound       : +1.00000000000000e-09 (1 solutions)
Dual Bound         : +1.00000000000000e-09
Gap                : 0.00 %

I assume presolve should not change the solvability of a problem. Please let me know if I can provide additional information.

I built SCIP 10.01 on Ubuntu 24.04 and

scip -v

gives me

SCIP version 10.0.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 8.0.1] [GitHash: 76a50c97d6]
Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB)

External libraries: 
  Readline 8.2         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 8.0.1         Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: c69290aa]
  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)
  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.7.0          Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
  AMPL/MP 4.0.4        AMPL .nl file reader library (github.com/ampl/mp)
  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)

Compiler: gcc 15.2.0

Build options:
 ARCH=x86_64
 OSTYPE=Linux-6.14.0-37-generic
 COMP=GNU 15.2.0
 BUILD=Release
 CHECKSTAGE=AUTO
 DEBUGSOL=OFF
 EXPRINT=cppad
 SYM=snauty
 GMP=ON
 CONOPT=OFF
 IPOPT=ON
 WORHP=OFF
 LPS=spx
 LPSCHECK=OFF
 LTO=OFF
 NOBLKBUFMEM=OFF
 NOBLKMEM=OFF
 NOBUFMEM=OFF
 THREADSAFE=ON;FORCE
 READLINE=ON
 SANITIZE=OFF
 SHARED=ON
 VERSION=10.0.1
 API_VERSION=156
 ZIMPL=ON
 ZLIB=ON

[svigerske]

I can reproduce. These 1e-6 in many constraints are likely problematic.

[rajgoel]

Was also one of my thoughts. I tried replacing them with 1e-5, but that didnt help.

P.S. My main need is to convert the outcome of expressions like a <= b to boolean. I do this by checking whether b - a <= epsilon or b - a >= 1.1 * epsilon. Let me know if there is a better approch :-)

[svigerske]

If you add something like a + s = b with slack variable s, and indicator constraints z = 1 -> s >= 0, z = 0 -> s <= 0 with a binary variable z, then z=1 means b - a >= 0, so a <= b, and z=0 means b - a <= 0, so b <= a. Changing some 0 to 1e-5 may give a better distinction around a=b.