[SCIP] small gaps
Stefan Vigerske
svigerske at gams.com
Tue Jun 29 10:35:47 CEST 2021
Hi,
maybe try constraints/quadratic/upgrade/bounddisjunction = FALSE.
That disables upgrades of quadratic constraints of the form
(x - a) * (y - b) = 0 with x >= a and y >= b
into bounddisjunction constraints "x <= a or y <= b".
(and something similar for (x - a) * (y - b) >= 0)
The bounddisjunction is more explicit (and should use better branching
points), but the nlp-based primal heuristics don't see these constraints
(which could be the reason why time was spend on multistart, subnlp, and
undercover without finding anything) and the branching on
bounddisjunctions also seems to happen separate from the one on
variables in quadratic constraints (so they are not scored together).
Other things that could have an effect:
- change the branching rule by giving a high priority to mostinf or
inference (the pseudo-costs in the default pscost rule may be bad)
- increase the frequency of obbt so it also runs within the tree (but it
is expensive) or increase the working limits of obbt (obbt generates
genvbounds, which seem to find a lot of domain reductions)
- try enabling the eccuts separator (it needs a special structure in the
quadratic constraints and did not seem to help on average, but for
(almost) every method there are some instances where it shines)
Stefan
On 6/28/21 10:50 PM, Pelda, Johannes wrote:
> Hi there,
>
>
> I face the same problem as described here: On 27.01.20 18:59, Marcus Daniels wrote.
>
>
>
> Finding a gap of 2,67% scip does not evolve the bounds anymore and seems to stuck somewhere from 74 sec. onwards (see also the statistics below):
>
>
>
> 199s|230700 | 39973 |851710 | 3.7 | 143M | 104 | 448 | 498 | 572 | 225k| 1 | 18 | 0 |-2.072734e-01 |-2.018794e-01 | 2.67%| 71.62%
>
> 199s|230800 | 39985 |851953 | 3.7 | 143M | 104 | 448 | 498 | 572 | 225k| 1 | 18 | 0 |-2.072734e-01 |-2.018794e-01 | 2.67%| 71.62%
>
> 199s|230900 | 39997 |852211 | 3.7 | 143M | 104 | 448 | 498 | 572 | 225k| 1 | 18 | 0 |-2.072734e-01 |-2.018794e-01 | 2.67%| 71.62%
>
> 199s|231000 | 40009 |852444 | 3.7 | 143M | 104 | 448 | 498 | 572 | 225k| 1 | 18 | 0 |-2.072734e-01 |-2.018794e-01 | 2.67%| 71.62%
>
>
>
>
> The example is very small and a non-convex MINLP. I tried already Stefan's approach and set the following without success:
>
>
>
>> constraints/quadratic/sepanlpmincont = 0 or
>
>> constraints/quadratic/gaugecuts = TRUE or
>
>> constraints/quadratic/projectedcuts = TRUE or"
>
>
> Any help to improve the solving time I appreciate.
>
> Best regards,
> Johannes
>
>
> STATISTICS:
> SCIP Status : solving was interrupted [time limit reached]
> Total Time : 200.00
> solving : 200.00
> presolving : 0.00 (included in solving)
> reading : 0.00
> copying : 0.00 (9 #copies) (minimal 0.00, maximal 0.00, average 0.00)
> Original Problem :
> Problem name : sim4dhs
> Variables : 833 (0 binary, 0 integer, 0 implicit integer, 833 continuous)
> Constraints : 1157 initial, 1157 maximal
> Objective : minimize, 18 non-zeros (abs.min = 1, abs.max = 1)
> Presolved Problem :
> Problem name : t_sim4dhs
> Variables : 448 (0 binary, 0 integer, 0 implicit integer, 448 continuous)
> Constraints : 502 initial, 503 maximal
> Objective : minimize, 36 non-zeros (abs.min = 1, abs.max = 1)
> Nonzeros : 1486 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
> inttobinary : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
> milp : 0.00 0.00 0 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 9 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 9 54 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 0 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.00 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
> linear : 0.00 0.00 10 110 221 0 462 0 547 0 0 0
> bounddisjunction : 0.00 0.00 8 0 0 0 0 0 270 0 0 0
> quadratic : 0.00 0.00 11 0 0 0 486 0 0 162 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 - - 29 - - - - -
> Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoRelax #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
> benderslp : 0 0 0 0 146624 0 0 2093 0 0 0 0 0 0 0
> integral : 0 0 0 0 146624 0 0 2093 0 0 0 0 0 0 0
> linear : 268+ 271 10 654303 136164 0 0 2089 0 27513 1686248 0 0 0 0
> bounddisjunction : 55 55 0 200862 136164 0 0 2086 0 0 107715 0 0 0 160934
> quadratic : 179 179 270721 626790 146624 0 0 476 0 7 1599829 319558 224443 0 0
> benders : 0 0 0 0 136164 0 0 1 0 0 0 0 0 0 0
> countsols : 0 0 0 0 55697 0 0 1 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
> linear : 8.00 0.00 0.00 6.00 2.00 0.00 0.00 0.00 0.00 0.00
> bounddisjunction : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
> quadratic : 15.00 0.00 9.00 6.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
> 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 : 3 0 0 0
> genvbounds : 192530 0 1 148031
> nlobbt : 0 0 0 0
> obbt : 2 0 0 6
> probing : 0 0 0 0
> pseudoobj : 800580 0 0 8
> redcost : 0 0 0 0
> rootredcost : 3 0 0 9
> 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 : 1.00 0.00 0.00 1.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.00 0.00 0.00 0.00 0.00 0.00
> vbounds : 0.00 0.00 0.00 0.00 0.00 0.00
> 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 262 19 - 0 0.0 0 0.0 18 3.3 0
> bound exceed. LP : 3.00 56250 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 - - 1 0 0.0 - - 18 - -
> applied locally : - - - 0 0 0.0 - - 0 - -
> Separators : ExecTime SetupTime Calls Cutoffs DomReds Cuts Applied Conss
> cut pool : 0.00 0 - - 0 - - (maximal pool size: 0)
> aggregation : 0.00 0.00 0 0 0 0 0 0
> cgmip : 0.00 0.00 0 0 0 0 0 0
> clique : 0.00 0.00 0 0 0 0 0 0
> closecuts : 0.00 0.00 0 0 0 0 0 0
> cmir : 0.00 0.00 0 0 0 0 0 0
> convexproj : 0.00 0.00 0 0 0 0 0 0
> disjunctive : 0.00 0.00 0 0 0 0 0 0
> eccuts : 0.00 0.00 0 0 0 0 0 0
> flowcover : 0.00 0.00 0 0 0 0 0 0
> gauge : 0.00 0.00 0 0 0 0 0 0
> gomory : 0.00 0.00 0 0 0 0 0 0
> impliedbounds : 0.00 0.00 0 0 0 0 0 0
> intobj : 0.00 0.00 0 0 0 0 0 0
> mcf : 0.00 0.00 0 0 0 0 0 0
> oddcycle : 0.00 0.00 0 0 0 0 0 0
> rapidlearning : 0.00 0.00 0 0 0 0 0 0
> strongcg : 0.00 0.00 0 0 0 0 0 0
> zerohalf : 0.00 0.00 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
> 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 : 1.00 0.00 0 55695 0 0 0 0 0 111390
> 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 - - 2 2
> 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 258 0 0
> alns : 0.00 0.00 9 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 268 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
> dualval : 0.00 0.00 0 0 0
> farkasdiving : 0.00 0.00 0 0 0
> feaspump : 0.00 0.00 0 0 0
> fixandinfer : 0.00 0.00 0 0 0
> fracdiving : 0.00 0.00 258 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
> intdiving : 0.00 0.00 0 0 0
> intshifting : 0.00 0.00 0 0 0
> linesearchdiving : 0.00 0.00 255 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 : 26.00 0.00 1 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.00 0.00 0 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 0 0 0
> shiftandpropagate: 0.00 0.00 0 0 0
> shifting : 0.00 0.00 0 0 0
> simplerounding : 0.00 0.00 0 0 0
> subnlp : 13.00 0.00 25 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 1 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 -
> Diving (single) : Calls Nodes LP Iters Backtracks Conflicts MinDepth MaxDepth AvgDepth RoundSols NLeafSols MinSolDpt MaxSolDpt AvgSolDpt
> actconsdiving : 0 - - - - - - - - - - - -
> coefdiving : 0 - - - - - - - - - - - -
> conflictdiving : 268 0 0 0 0 10 52 24.9 0 - - - -
> distributiondivin: 0 - - - - - - - - - - - -
> farkasdiving : 0 - - - - - - - - - - - -
> fracdiving : 258 0 0 0 0 8 52 25.8 0 - - - -
> guideddiving : 0 - - - - - - - - - - - -
> linesearchdiving : 255 0 0 0 0 8 52 25.6 0 - - - -
> pscostdiving : 0 - - - - - - - - - - - -
> veclendiving : 0 - - - - - - - - - - - -
> Diving (adaptive) : Calls Nodes LP Iters Backtracks Conflicts MinDepth MaxDepth AvgDepth RoundSols NLeafSols MinSolDpt MaxSolDpt AvgSolDpt
> actconsdiving : 0 - - - - - - - - - - - -
> coefdiving : 46 0 0 0 0 11 51 24.0 0 - - - -
> conflictdiving : 0 - - - - - - - - - - - -
> distributiondivin: 0 - - - - - - - - - - - -
> farkasdiving : 0 - - - - - - - - - - - -
> fracdiving : 56 0 0 0 0 9 48 24.1 0 - - - -
> guideddiving : 43 0 0 0 0 11 50 26.2 0 - - - -
> linesearchdiving : 59 0 0 0 0 8 50 26.2 0 - - - -
> pscostdiving : 0 - - - - - - - - - - - -
> veclendiving : 54 0 0 0 0 11 52 24.9 0 - - - -
> Neighborhoods : Calls SetupTime SolveTime SolveNodes Sols Best Exp3 EpsGreedy UCB TgtFixRate Opt Inf Node Stal Sol Usr Othr Actv
> zeroobjective : 9 0.00 0.00 0 0 0 0.00000 -1.00000 0.52023 0.900 0 0 0 0 0 0 9 1
> rens : 0 0.00 0.00 0 0 0 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
> rins : 0 0.00 0.00 0 0 0 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
> mutation : 0 0.00 0.00 0 0 0 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
> localbranching : 0 0.00 0.00 0 0 0 0.00000 -1.00000 1.00000 0.900 0 0 0 0 0 0 0 0
> crossover : 0 0.00 0.00 0 0 0 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 -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 -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 -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 : 2.00 3779 12 3.00 6.00 2.00 3775
> dual LP : 80.00 345034 841460 3.55 10518.25 17.00 107774
> lex dual LP : 0.00 0 0 0.00 -
> barrier LP : 0.00 0 0 0.00 - 0.00 0
> resolve instable : 0.00 2 540 270.00 -
> diving/probing LP: 0.00 353 11215 31.77 -
> strong branching : 0.00 0 0 0.00 - - - 0
> (at root node) : - 0 0 0.00 -
> conflict analysis: 0.00 0 0 0.00 -
> NLP : Time Calls
> all NLPs : 0.00 0
> B&B Tree :
> number of runs : 1
> nodes : 231096 (136162 internal, 94934 leaves)
> feasible leaves : 2
> infeas. leaves : 27775
> objective leaves : 67156
> nodes (total) : 231096 (136162 internal, 94934 leaves)
> nodes left : 40018
> max depth : 104
> max depth (total): 104
> backtracks : 39139 (16.9%)
> early backtracks : 0 (0.0%)
> nodes exc. ref. : 0 (0.0%)
> delayed cutoffs : 0
> repropagations : 300 (374 domain reductions, 0 cutoffs)
> avg switch length: 8.70
> switching time : 14.00
> Estim. Tree Size : 464614
> Estimation Tree : 272325 nodes (232307 visited, 136162 internal, 96145 leaves, 40018 open), weight: 0.7703 completed 0.7162
> Estimations : estim value trend resolution smooth
> wbe : 249622 - - - -
> tree-profile : -1 - - - -
> gap : 464614 0.97398 0.00000 128 464352
> tree-weight : 464614 0.77032 0.00000 128 464352
> leaf-frequency : 1889673 0.41387 0.00001 128 1879390
> ssg : 464614 0.31513 -0.00000 128 464352
> open-nodes : 464614 40018.00000 16.56581 128 464352
> Root Node :
> First LP value : -5.61775671324110e-01
> First LP Iters : 367
> First LP Time : 0.00
> Final Dual Bound : -2.34180732949713e-01
> Final Root Iters : 1901
> Root LP Estimate : -2.30185933155962e-01
> Solution :
> Solutions found : 2 (2 improvements)
> First Solution : -1.48600766997846e-01 (in run 1, after 602 nodes, 33.00 seconds, depth 21, found by <relaxation>)
> Gap First Sol. : 53.04 %
> Gap Last Sol. : 7.14 %
> Primal Bound : -2.01879429012952e-01 (in run 1, after 2396 nodes, 42.00 seconds, depth 31, found by <relaxation>)
> Dual Bound : -2.07273362411977e-01
> Gap : 2.67 %
> Integrals : Total Avg%
> primal-dual : 4035.38 20.18
> primal-ref : - - (not evaluated)
> dual-ref : - - (not evaluated)
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
More information about the Scip
mailing list