Incorrect solution from scip when numerics/feastol = 1e-9 #132
Description
For seed.mps.txt, scip produces the wrong answer of 4983.45.. when setting numerics/feastol = 1e-9, while the correct answer should be 4936.16...
I am not sure if this is a duplicate of #126, since for that one, the incorrect answer can be avoided by setting a small feasible tolerance (e.g. numerics/feastol = 1e-9); but for this one, the error only manifests with a small tolerance.
$> scip -f seed.mps -s scip_options.set
SCIP version 10.0.0 [precision: 8 byte] [memory: block] [mode: debug] [LP solver: SoPlex 8.0.0] [GitHash: 376780728d]
Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB)
External libraries:
SoPlex 8.0.0 Linear programming solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: fd60d7e9]
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)
TinyCThread 1.2 small portable implementation of the C11 threads API (tinycthread.github.io)
GMP 6.2.0 GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
AMPL/MP 4.0.0 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)
reading user parameter file <scip_options.set>
read problem <seed.mps>
============
original problem has 5 variables (0 bin, 2 int, 3 cont) and 53 constraints
solve problem
=============
presolving:
(round 1, fast) 0 del vars, 0 del conss, 0 add conss, 1 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
(round 2, fast) 0 del vars, 0 del conss, 0 add conss, 2 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 (symcode time: 0.00)
presolving (3 rounds: 3 fast, 1 medium, 1 exhaustive):
0 deleted vars, 0 deleted constraints, 0 added constraints, 2 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
0 implications, 0 cliques
presolved problem has 5 variables (0 bin, 2 int, 3 cont) and 53 constraints
presolved problem has 0 implied integral variables (0 bin, 0 int, 0 cont)
53 constraints of type <linear>
Presolving Time: 0.01
time | node | left |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr| dualbound | primalbound | gap | compl.
0.0s| 1 | 0 | 14 | - | 856k | 0 | 5 | 54 | 53 | 0 | 0 | 1 | 0 | 4.903790e+03 | -- | Inf | unknown
0.1s| 1 | 0 | 16 | - | 905k | 0 | 5 | 54 | 54 | 1 | 1 | 1 | 0 | 4.930488e+03 | -- | Inf | unknown
0.3s| 1 | 0 | 17 | - | 910k | 0 | 5 | 54 | 54 | 3 | 2 | 1 | 0 | 4.933364e+03 | -- | Inf | unknown
0.3s| 1 | 0 | 18 | - | 910k | 0 | 5 | 54 | 55 | 4 | 3 | 1 | 0 | 4.936166e+03 | -- | Inf | unknown
0.4s| 1 | 0 | 19 | - | 923k | 0 | 5 | 54 | 56 | 5 | 4 | 1 | 0 | 4.936288e+03 | -- | Inf | unknown
0.5s| 1 | 0 | 22 | - | 929k | 0 | 5 | 54 | 57 | 6 | 5 | 1 | 0 | 4.954683e+03 | -- | Inf | unknown
0.6s| 1 | 0 | 24 | - | 954k | 0 | 5 | 54 | 58 | 7 | 6 | 1 | 0 | 4.958691e+03 | -- | Inf | unknown
0.7s| 1 | 0 | 26 | - | 965k | 0 | 5 | 54 | 58 | 9 | 7 | 1 | 0 | 4.979265e+03 | -- | Inf | unknown
0.8s| 1 | 0 | 27 | - | 979k | 0 | 5 | 54 | 59 | 10 | 8 | 1 | 0 | 4.983451e+03 | -- | Inf | unknown
0.8s| 1 | 0 | 27 | - | 979k | 0 | 5 | 52 | 59 | 10 | 9 | 1 | 0 | 4.983451e+03 | -- | Inf | unknown
d 0.8s| 1 | 0 | 27 | - |farkasdi| 0 | 5 | 52 | 59 | 0 | 10 | 1 | 0 | 4.983451e+03 | 4.983451e+03 | 0.00%| unknown
0.8s| 1 | 0 | 27 | - | 979k | 0 | 5 | 52 | 59 | 10 | 10 | 1 | 0 | 4.983451e+03 | 4.983451e+03 | 0.00%| unknown
SCIP Status : problem is solved [optimal solution found]
Solving Time (sec) : 0.79
Solving Nodes : 1
Primal Bound : +4.98345057818728e+03 (1 solutions)
Dual Bound : +4.98345057818728e+03
Gap : 0.00 %
primal solution (original space):
=================================
objective value: 4983.45057818728
x0 -50 (obj:-83.84)
x4 43 (obj:49.74)
x2 -43.6172945702441 (obj:69.1)
x3 -47.6215365486891 (obj:-71.96)
x1 -64.2899977009686 (obj:27.38)
Statistics
==========
SCIP Status : problem is solved [optimal solution found]
Total Time : 0.79
solving : 0.79
presolving : 0.01 (included in solving)
reading : 0.00
copying : 0.00 (0 times copied the problem)
Original Problem :
Problem name : seed
Variables : 5 (0 binary, 2 integer, 3 continuous)
implied integral : 0 (0 binary, 0 integer, 0 continuous)
Constraints : 53 initial, 53 maximal
Objective : minimize, 5 non-zeros (abs.min = 27.38, abs.max = 83.84)
Presolved Problem :
Problem name : t_seed
Variables : 5 (0 binary, 2 integer, 3 continuous)
implied integral : 0 (0 binary, 0 integer, 0 continuous)
Constraints : 53 initial, 54 maximal
Objective : minimize, 5 non-zeros (abs.min = 27.38, abs.max = 83.84)
Nonzeros : 265 constraint, 0 clique table
Presolvers : ExecTime SetupTime Calls FixedVars AggrVars ChgTypes ChgBounds AddHoles DelCons AddCons ChgSides ChgCoefs
boundshift : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
convertinttobin : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
domcol : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
dualagg : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
dualcomp : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
dualinfer : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
dualsparsify : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
gateextraction : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
implics : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
implint : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
inttobinary : 0.00 0.00 3 0 0 0 0 0 0 0 0 0
qpkktref : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
redvub : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
sparsify : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
stuffing : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
trivial : 0.00 0.00 3 0 0 0 0 0 0 0 0 0
tworowbnd : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
dualfix : 0.00 0.00 3 0 0 0 0 0 0 0 0 0
genvbounds : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
probing : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
pseudoobj : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
symmetry : 0.01 0.00 1 0 0 0 0 0 0 0 0 0
vbounds : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
varbound : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
linear : 0.00 0.00 4 0 0 0 2 0 0 0 0 0
benders : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
components : 0.00 0.00 1 0 0 0 0 0 0 0 0 0
root node : - - - 0 - - 10 - - - - -
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoRelax #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
benderslp : 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0
integral : 0 0 0 0 0 0 0 19 0 0 0 0 0 0 0
varbound : 0+ 1 0 11 0 0 0 0 0 0 1 0 0 0 0
exactsol : 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0
linear : 53 53 10 22 0 0 0 17 0 1 7 0 0 0 0
benders : 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
fixedvar : 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
countsols : 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
components : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS EnfoRelax Check ResProp SB-Prop
benderslp : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
integral : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
varbound : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
exactsol : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
linear : 0.01 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
benders : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
fixedvar : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
countsols : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
components : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Propagators : #Propagate #ResProp Cutoffs DomReds
dualfix : 4 0 0 0
genvbounds : 0 0 0 0
nlobbt : 0 0 0 0
obbt : 0 0 0 0
probing : 0 0 0 0
pseudoobj : 15 0 0 0
redcost : 11 0 0 0
rootredcost : 0 0 0 0
symmetry : 0 0 0 0
vbounds : 0 0 0 0
Propagator Timings : TotalTime SetupTime Presolve Propagate ResProp SB-Prop
dualfix : 0.00 0.00 0.00 0.00 0.00 0.00
genvbounds : 0.00 0.00 0.00 0.00 0.00 0.00
nlobbt : 0.00 0.00 0.00 0.00 0.00 0.00
obbt : 0.00 0.00 0.00 0.00 0.00 0.00
probing : 0.00 0.00 0.00 0.00 0.00 0.00
pseudoobj : 0.00 0.00 0.00 0.00 0.00 0.00
redcost : 0.00 0.00 0.00 0.00 0.00 0.00
rootredcost : 0.00 0.00 0.00 0.00 0.00 0.00
symmetry : 0.01 0.00 0.01 0.00 0.00 0.00
vbounds : 0.00 0.00 0.00 0.00 0.00 0.00
Symmetry :
orbitopal red. : 0 reductions applied, 0 cutoffs
orbital reduction: 0 reductions applied, 0 cutoffs
lexicographic red: 0 reductions applied, 0 cutoffs
shadow tree time : 0.00 s
Conflict Analysis : Time Calls Success DomReds Conflicts Literals Reconvs ReconvLits Dualrays Nonzeros LP Iters (pool size: [--,--])
propagation : 0.00 0 0 - 0 0.0 0 0.0 - - -
infeasible LP : 0.00 1 1 - 0 0.0 0 0.0 1 2.0 0
bound exceed. LP : 0.00 0 0 - 0 0.0 0 0.0 0 0.0 0
strong branching : 0.00 0 0 - 0 0.0 0 0.0 - - 0
pseudo solution : 0.00 0 0 - 0 0.0 0 0.0 - - -
applied globally : 0.00 - - 0 0 0.0 - - 1 - -
applied locally : - - - 0 0 0.0 - - 0 - -
Separators : ExecTime SetupTime Calls RootCalls Cutoffs DomReds FoundCuts ViaPoolAdd DirectAdd Applied ViaPoolApp DirectApp Conss
cut pool : 0.00 - 17 17 - - 23 26 - - - - - (maximal pool size: 23)
aggregation : 0.53 0.00 8 8 0 0 5 6 0 3 3 0 0
> cmir : - - - - - - - 6 0 3 3 0 -
> flowcover : - - - - - - - 0 0 0 0 0 -
> knapsackcover : - - - - - - - 0 0 0 0 0 -
cgmip : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
clique : 0.00 0.00 1 1 0 0 0 0 0 0 0 0 0
closecuts : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
convexproj : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
disjunctive : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
eccuts : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
gauge : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
gomory : 0.00 0.00 8 8 0 0 21 19 4 5 3 2 0
> gomorymi : - - - - - - - 13 2 5 3 2 -
> strongcg : - - - - - - - 6 2 0 0 0 -
impliedbounds : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
interminor : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
intobj : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
lagromory : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
mcf : 0.00 0.00 1 1 0 0 0 0 0 0 0 0 0
minor : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
mixing : 0.00 0.00 10 10 0 0 0 0 0 0 0 0 0
multilinear : 0.00 0.00 10 10 0 0 0 0 0 0 0 0 0
oddcycle : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
rapidlearning : 0.00 0.00 0 0 0 0 0 0 0 0 0 0 0
rlt : 0.00 0.00 10 10 0 0 0 0 0 0 0 0 0
zerohalf : 0.00 0.00 8 8 0 0 1 1 0 0 0 0 0
Cutselectors : ExecTime SetupTime Calls RootCalls Selected Forced Filtered RootSelec RootForc RootFilt
hybrid : 0.00 0.00 8 8 6 4 24 6 4 24
ensemble : 0.00 0.00 0 0 0 0 0 0 0 0
dynamic : 0.00 0.00 0 0 0 0 0 0 0 0
Pricers : ExecTime SetupTime Calls Vars
problem variables: 0.00 - 0 0
Branching Rules : ExecTime SetupTime BranchLP BranchExt BranchPS Cutoffs DomReds Cuts Conss Children
allfullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
cloud : 0.00 0.00 0 0 0 0 0 0 0 0
distribution : 0.00 0.00 0 0 0 0 0 0 0 0
fullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
gomory : 0.00 0.00 0 0 0 0 0 0 0 0
inference : 0.00 0.00 0 0 0 0 0 0 0 0
leastinf : 0.00 0.00 0 0 0 0 0 0 0 0
lookahead : 0.00 0.00 0 0 0 0 0 0 0 0
mostinf : 0.00 0.00 0 0 0 0 0 0 0 0
multaggr : 0.00 0.00 0 0 0 0 0 0 0 0
nodereopt : 0.00 0.00 0 0 0 0 0 0 0 0
pscost : 0.00 0.00 0 0 0 0 0 0 0 0
random : 0.00 0.00 0 0 0 0 0 0 0 0
relpscost : 0.00 0.00 0 0 0 0 0 0 0 0
vanillafullstrong: 0.00 0.00 0 0 0 0 0 0 0 0
Primal Heuristics : ExecTime SetupTime Calls Found Best
LP solutions : 0.00 - - 0 0
relax solutions : 0.00 - - 0 0
pseudo solutions : 0.00 - - 0 0
strong branching : 0.00 - - 0 0
actconsdiving : 0.00 0.00 0 0 0
adaptivediving : 0.00 0.00 0 0 0
alns : 0.00 0.00 0 0 0
bound : 0.00 0.00 0 0 0
clique : 0.00 0.00 0 0 0
coefdiving : 0.00 0.00 0 0 0
completesol : 0.00 0.00 0 0 0
conflictdiving : 0.00 0.00 0 0 0
crossover : 0.00 0.00 0 0 0
dins : 0.00 0.00 0 0 0
distributiondivin: 0.00 0.00 0 0 0
dks : 0.00 0.00 0 0 0
dps : 0.00 0.00 0 0 0
dualval : 0.00 0.00 0 0 0
farkasdiving : 0.00 0.00 1 1 1
feaspump : 0.02 0.00 1 0 0
fixandinfer : 0.00 0.00 0 0 0
fracdiving : 0.00 0.00 0 0 0
gins : 0.00 0.00 0 0 0
guideddiving : 0.00 0.00 0 0 0
indicator : 0.00 0.00 0 0 0
indicatordiving : 0.00 0.00 0 0 0
intdiving : 0.00 0.00 0 0 0
intshifting : 0.00 0.00 0 0 0
linesearchdiving : 0.00 0.00 0 0 0
localbranching : 0.00 0.00 0 0 0
locks : 0.00 0.00 0 0 0
lpface : 0.00 0.00 0 0 0
mpec : 0.00 0.00 0 0 0
multistart : 0.00 0.00 0 0 0
mutation : 0.00 0.00 0 0 0
nlpdiving : 0.00 0.00 0 0 0
objpscostdiving : 0.00 0.00 0 0 0
octane : 0.00 0.00 0 0 0
ofins : 0.00 0.00 0 0 0
oneopt : 0.00 0.00 0 0 0
padm : 0.00 0.00 0 0 0
proximity : 0.00 0.00 0 0 0
pscostdiving : 0.00 0.00 0 0 0
randrounding : 0.05 0.00 8 0 0
rens : 0.00 0.00 0 0 0
reoptsols : 0.00 0.00 0 0 0
repair : 0.00 0.00 0 0 0
rins : 0.00 0.00 0 0 0
rootsoldiving : 0.00 0.00 0 0 0
rounding : 0.00 0.00 8 0 0
scheduler : 0.00 0.00 0 0 0
shiftandpropagate: 0.00 0.00 1 0 0
shifting : 0.05 0.00 8 0 0
simplerounding : 0.00 0.00 0 0 0
subnlp : 0.00 0.00 0 0 0
trivial : 0.00 0.00 2 0 0
trivialnegation : 0.00 0.00 0 0 0
trustregion : 0.00 0.00 0 0 0
trysol : 0.00 0.00 0 0 0
twoopt : 0.00 0.00 0 0 0
undercover : 0.00 0.00 0 0 0
vbounds : 0.00 0.00 0 0 0
veclendiving : 0.00 0.00 0 0 0
zeroobj : 0.00 0.00 0 0 0
zirounding : 0.00 0.00 0 0 0
other solutions : - - - 0 -
LNS (Scheduler) : Calls SetupTime SolveTime SolveNodes Sols Best Exp3 Exp3-IX EpsGreedy UCB TgtFixRate Opt Inf Node Stal Sol Usr Othr Actv
rens : 0 0.00 0.00 0 0 0 0.00000 0.20000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 1
rins : 0 0.00 0.00 0 0 0 0.00000 0.20000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 1
mutation : 0 0.00 0.00 0 0 0 0.00000 0.20000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 1
zeroobjective : 0 0.00 0.00 0 0 0 0.00000 0.20000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 1
crossover : 0 0.00 0.00 0 0 0 0.00000 0.20000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 1
localbranching : 0 0.00 0.00 0 0 0 0.00000 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
proximity : 0 0.00 0.00 0 0 0 0.00000 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
dins : 0 0.00 0.00 0 0 0 0.00000 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
trustregion : 0 0.00 0.00 0 0 0 0.00000 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
LP : Time Calls Iterations Iter/call Iter/sec Time-0-It Calls-0-It ItLimit
primal LP : 0.00 0 0 0.00 - 0.00 0
dual LP : 0.00 10 24 2.67 - 0.00 1
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 - 0.00 0
resolve instable : 0.00 0 0 0.00 -
diving/probing LP: 0.02 1 3 3.00 129.33
strong branching : 0.00 0 0 0.00 - - - 0
(at root node) : - 0 0 0.00 -
conflict analysis: 0.00 0 0 0.00 -
B&B Tree :
number of runs : 1
nodes : 1 (0 internal, 1 leaves)
feasible leaves : 0
infeas. leaves : 0
objective leaves : 1
nodes (total) : 1 (0 internal, 1 leaves)
nodes left : 0
max depth : 0
max depth (total): 0
backtracks : 0 (0.0%)
early backtracks : 0 (0.0%)
nodes exc. ref. : 0 (0.0%)
delayed cutoffs : 0
repropagations : 0 (0 domain reductions, 0 cutoffs)
avg switch length: 2.00
switching time : 0.00
Root Node :
First LP value : +4.90378982791530e+03
First LP Iters : 11 (29177.72 Iter/sec)
First LP Time : 0.00
Final Dual Bound : -
Final Root Iters : 24
Root LP Estimate : -
Solution :
Solutions found : 1 (1 improvements)
First Solution : +4.98345057818728e+03 (in run 1, after 1 nodes, 0.78 seconds, depth 1, found by <farkasdiving>)
Gap First Sol. : 0.00 %
Gap Last Sol. : 0.00 %
Primal Bound : +4.98345057818728e+03 (in run 1, after 1 nodes, 0.78 seconds, depth 1, found by <farkasdiving>)
Dual Bound : +4.98345057818728e+03
Gap : 0.00 %
Integrals : Total Avg%
primal-dual : 78.85 99.96
primal-ref : - - (not evaluated)
dual-ref : - - (not evaluated)
Metadata
Metadata
Assignees
Labels
No labels