SCIP 8 incorrectly reports a second-order cone program as infeasible.

[rileyjmurray]

Hi all. Several months ago I opened an issue on the PySCIPOpt repo containing an example where PySCIPOpt 4.2 (running SCIP 8) incorrectly claimed that a small SOCP was infeasible. Since the issue has seen no activity over there and it probably belongs here, I'm posting just to make sure the SCIP devs are aware.

The relevant issue is: https://github.com/scipopt/PySCIPOpt/issues/583.

Ping @BrannonKing, since he might be interested in this getting resolved.

[matbesancon]

Hi, to complete what @svigerske said, it would help to have the printed problem from SCIP: https://github.com/scipopt/PySCIPOpt/issues/583#issuecomment-1226108545 The function to do this would be:

SCIP_RETCODE SCIPwriteOrigProblem(SCIP *    scip,
        const char *    filename,
        const char *    extension,
        SCIP_Bool   genericnames 
    )

https://www.scipopt.org/doc/html/group__GlobalProblemMethods.php#ga2f6d67a1ccef7a6363e6d6a56523c0d0

you can write to a .cip file. Let us know if anything is missing

[matbesancon]

@rileyjmurray if this can help, do you have a file format in another format that you can dump from CVX?

[SteveDiamond]

I've uploaded the .cip file for the above CVXPY formulation. (Renamed to .txt so github allows the attachment.) cvxpy_socp_3.txt

[matbesancon]

hi, thanks for the CIP file, I ran it with both SCIP 8.0.0 and 8.0.1 and both found an optimal solution (same value).

Not sure whether there is a setting or dependency that could cause that in CVX?

[rileyjmurray]

@matbesancon can you post the solver output here?

[matbesancon]

with 8.0.1

SCIP version 8.0.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: Soplex 6.0.1] [GitHash: c84ee4283e]
Copyright (C) 2002-2022 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

External libraries: 
  Readline 7.0         GNU library for command line editing (gnu.org/s/readline)
  Soplex 6.0.1         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 8b86b300]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.1.2            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  PaPILO 2.1.0         parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: 9363218]
  bliss 0.77           Computing Graph Automorphism Groups by T. Junttila and P. Kaski (www.tcs.hut.fi/Software/bliss/)
  Ipopt 3.14.4         Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)

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

SCIP> read test.cip 

read problem <test.cip>
============

original problem has 11 variables (0 bin, 0 int, 0 impl, 11 cont) and 12 constraints
SCIP> optimize

presolving:
(round 1, fast)       7 del vars, 7 del conss, 0 add conss, 14 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast)       7 del vars, 7 del conss, 0 add conss, 16 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present
presolving (3 rounds: 3 fast, 1 medium, 1 exhaustive):
 7 deleted vars, 7 deleted constraints, 0 added constraints, 16 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 4 variables (0 bin, 0 int, 0 impl, 4 cont) and 5 constraints
      2 constraints of type <linear>
      3 constraints of type <nonlinear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
t 0.0s|     1 |     0 |     0 |     - | trivial|   0 |   4 |   5 |   0 |   0 |  0 |   0 |   0 |-2.111111e+00 | 0.000000e+00 |    Inf | unknown
  0.0s|     1 |     0 |     8 |     - |   832k |   0 |  11 |   5 |  14 |   0 |  0 |   0 |   0 |-1.958623e+00 | 0.000000e+00 |    Inf | unknown
L 0.0s|     1 |     0 |     8 |     - |  subnlp|   0 |  11 |   5 |  14 |   0 |  0 |   0 |   0 |-1.958623e+00 |-1.932105e+00 |   1.37%| unknown
  0.0s|     1 |     0 |    11 |     - |   832k |   0 |  11 |   5 |  16 |   2 |  1 |   0 |   0 |-1.932285e+00 |-1.932105e+00 |   0.01%| unknown
  0.0s|     1 |     0 |    11 |     - |   832k |   0 |  11 |   5 |  14 |   2 |  1 |   0 |   0 |-1.932285e+00 |-1.932105e+00 |   0.01%| unknown
  0.0s|     1 |     0 |    13 |     - |   832k |   0 |  11 |   5 |  16 |   4 |  2 |   0 |   0 |-1.932105e+00 |-1.932105e+00 |   0.00%| unknown
  0.0s|     1 |     0 |    13 |     - |   832k |   0 |  11 |   5 |  16 |   4 |  2 |   0 |   0 |-1.932105e+00 |-1.932105e+00 |   0.00%| unknown

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

SCIP> 

[matbesancon]

8.0.0:

SCIP version 8.0.0 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 6.0.0] [GitHash: a740f0891e]
Copyright (C) 2002-2021 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)

External libraries: 
  Readline 7.0         GNU library for command line editing (gnu.org/s/readline)
  SoPlex 6.0.0         Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 71a5873d]
  CppAD 20180000.0     Algorithmic Differentiation of C++ algorithms developed by B. Bell (github.com/coin-or/CppAD)
  ZLIB 1.2.11          General purpose compression library by J. Gailly and M. Adler (zlib.net)
  GMP 6.1.2            GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
  PaPILO 2.1.0.1       parallel presolve for integer and linear optimization (github.com/scipopt/papilo) [GitHash: ab4ea5c]
  bliss 0.73p          Computing Graph Automorphism Groups by T. Junttila and P. Kaski (www.tcs.hut.fi/Software/bliss/)
  Ipopt 3.14.4         Interior Point Optimizer developed by A. Waechter et.al. (github.com/coin-or/Ipopt)

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

SCIP> read test.cip 

read problem <test.cip>
============

original problem has 11 variables (0 bin, 0 int, 0 impl, 11 cont) and 12 constraints
SCIP> optimize

presolving:
(round 1, fast)       7 del vars, 7 del conss, 0 add conss, 14 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast)       7 del vars, 7 del conss, 0 add conss, 16 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
   (0.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (0.0s) no symmetry present
presolving (3 rounds: 3 fast, 1 medium, 1 exhaustive):
 7 deleted vars, 7 deleted constraints, 0 added constraints, 16 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 4 variables (0 bin, 0 int, 0 impl, 4 cont) and 5 constraints
      2 constraints of type <linear>
      3 constraints of type <nonlinear>
Presolving Time: 0.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
t 0.0s|     1 |     0 |     0 |     - | trivial|   0 |   4 |   5 |   0 |   0 |  0 |   0 |   0 |-2.111111e+00 | 0.000000e+00 |    Inf | unknown
  0.0s|     1 |     0 |     8 |     - |   832k |   0 |  11 |   5 |  14 |   0 |  0 |   0 |   0 |-1.958623e+00 | 0.000000e+00 |    Inf | unknown
L 0.0s|     1 |     0 |     8 |     - |  subnlp|   0 |  11 |   5 |  14 |   0 |  0 |   0 |   0 |-1.958623e+00 |-1.932105e+00 |   1.37%| unknown
  0.0s|     1 |     0 |    11 |     - |   832k |   0 |  11 |   5 |  16 |   2 |  1 |   0 |   0 |-1.932285e+00 |-1.932105e+00 |   0.01%| unknown
  0.0s|     1 |     0 |    11 |     - |   832k |   0 |  11 |   5 |  14 |   2 |  1 |   0 |   0 |-1.932285e+00 |-1.932105e+00 |   0.01%| unknown
  0.0s|     1 |     0 |    13 |     - |   832k |   0 |  11 |   5 |  16 |   4 |  2 |   0 |   0 |-1.932105e+00 |-1.932105e+00 |   0.00%| unknown
  0.0s|     1 |     0 |    13 |     - |   832k |   0 |  11 |   5 |  16 |   4 |  2 |   0 |   0 |-1.932105e+00 |-1.932105e+00 |   0.00%| unknown

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

[SteveDiamond]

Thanks @matbesancon for the quick response! We have identified some issues on our side and are moving towards a new CVXPY - SCIP interface. I'm finding new issues though with the attached problem, generated by the following CVXPY code

import numpy as np
import cvxpy as cp

x = np.arange(100)
y = 5 * x**2 - 3 * x + 4
v = cp.Variable(integer=True)
problem = cp.Problem(cp.Minimize(cp.sum_squares(y - v)), [v >= 3, v <= 4])
problem.solve(solver=cp.SCIP, verbose=True)
print(v.value)

test.txt

It's very strange because I get the correct answer when I set the dimension of x to be <= 30 or so, but infeasible for larger dimensions. Definitely possible that this is a problem on our side but wanted to highlight the issue here. I'm using pyscipopt 4.2, SCIP 8.0.1, and the cvxpy branch https://github.com/cvxpy/cvxpy/tree/feature/scip4

[svigerske]

Looks like some numerical issue with variables getting large. If I let v (x_1) be continuous, SCIP claims to find a feasible point with v=4 and objective value around 1e10, but it actually violates the SOC constraint. This is due to variable aggregations, e.g., soc_t_103 = 97424 - 2 x_1, which changes the constraint during presolve.

We could have a closer look, but this doesn't look like as if it is caused by issues in interfaces.

CC @KBestuzheva

[rileyjmurray]

@svigerske I think the numerics of that problem are indeed very bad, and probably not worth investigating. But I would like to follow up on the problem that led me to file this issue:

It's true that we have been able to change CVXPY so that SCIP 8 solves the desired problems. But this required non-obvious changes to the solver settings we passed to pyscipopt. Specifically, we previously had the following lines by default in pyscipopt:

        model.setPresolve(SCIP_PARAMSETTING.OFF)
        model.setHeuristics(SCIP_PARAMSETTING.OFF)
        model.disablePropagation()

It seems that these settings can lead to incorrect behavior on our test problems with SOC constraints. This is surprising since we need these settings in order to correctly recover dual variables when solving LPs. For now our plan for now is to remove these calls to model settings for all problems except continuous LPs. But the SCIP devs may want to look into why presolve and/or heuristics seem to be necessary for problems with SOC constraints.

[svigerske]

These settings shouldn't lead to wrong behavior, but they disable a lot of features in SCIP which are useful for performance.

It doesn't make much sense to me to use SCIP as a solver for LPs (use an LP solver for that), but if you have to, and if you need a dual solution as well, then it is indeed best to change these settings only if solving LPs (in which case they may sometimes improve performance, too).

[svigerske]

I tried again with test.txt, but couldn't get a feasible solution if not relaxing integrality. The same when using Mosek instead of SCIP. So I agree it's not worth to continue investigating this at the moment.

The original issue seems to have been fixed on the CVXPY side.