Comments (12)
svigerske
commented on June 9, 2024
1
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).
from scip.
matbesancon
commented on June 9, 2024
Hi,
to complete what @svigerske said, it would help to have the printed problem from SCIP: scipopt/PySCIPOpt#583 (comment)
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
from scip.
matbesancon
commented on June 9, 2024
@rileyjmurray if this can help, do you have a file format in another format that you can dump from CVX?
from scip.
SteveDiamond
commented on June 9, 2024
I've uploaded the .cip file for the above CVXPY formulation. (Renamed to .txt so github allows the attachment.)
cvxpy_socp_3.txt
from scip.
matbesancon
commented on June 9, 2024
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?
from scip.
rileyjmurray
commented on June 9, 2024
@matbesancon can you post the solver output here?
from scip.
matbesancon
commented on June 9, 2024
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>
from scip.
matbesancon
commented on June 9, 2024
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 %
from scip.
SteveDiamond
commented on June 9, 2024
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)
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
from scip.
svigerske
commented on June 9, 2024
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
from scip.
rileyjmurray
commented on June 9, 2024
@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.
from scip.
svigerske
commented on June 9, 2024
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.
from scip.
Related Issues (20)
- Assertion failed with minimal quadratic model HOT 1
- Assertion failed at the end of a solve HOT 3
- Data race in interrupt.c HOT 4
- ImportError: libscip.so.8.0: cannot open shared object file: No such file or directory HOT 1
- Suboptimal MIP solution reported as optimal HOT 2
- Can you build binary package for a more recent liunx distribution? HOT 3
- SegFault after compiling HOT 5
- Coloring application Branching Rule contradictory code HOT 7
- 2 tests fail HOT 1
- lot of tests from viprchk and «ctest -R MIPEX» failed on «exact-rational» branch HOT 9
- RFE: dynamic line length HOT 6
- question: how not to use nlpi_ipopt which depend on proprietray libhsl.so? HOT 3
- Interesting paper HOT 1
- `RelWithDebInfo` build is still asserting. HOT 4
- question: compiled with GMP=on, how to ensure GMP is used with CVXPY? HOT 3
- Difference in the objective value of a MIP in version 8.1.0 HOT 3
- What are the uses of nauty in SCIP? HOT 4
- System.AccessViolationException when trying to delete a restriction after LPError HOT 1
- Highs interface, option values function call deprecated
- Adding constraint improves objective. HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from scip.