[SCIP] Adding an efficacious cut is not increasing the bound

Wed Mar 11 19:48:21 CET 2020

Hello Everyone,

I have implemented a constraint handler that would add a cut when it detects a cycle in the underlying graph (similar to subtour elimination). It seems to add an efficacious cut but somehow the bound  is not increasing. 

I have the log below. I am also attaching it as a text file ( I numbered each line for readability sake)

As one can see in the log, from line 32 to 35, the separation procedure adds a cut and it is reflected in the cons column as the number of constraints has changed from 48 (line 31) to 49 (line 37) and similarly the number of cuts in the cuts columns has increased from 0 (line 31) to 1  (line 37). It seems like the constraint handler is adding an efficacious cut but nothing is changing when it comes to the dual bound (which should increase).

I did check by adding the cut manually (I wrote a .lp file with the constraint handler disabled and added a row by hand) and it does change the dual bound to 2.000 (the optimal solution after the cut is added).

I was wondering if I have to do something else after the SCIPaddRow procedure in the SepaXYZ function.

LOG:

   1)  LP Solver <SoPlex 4.0.2>: barrier convergence tolerance cannot be set -- tolerance of SCIP and LP solver may differ
   2)  LP Solver <SoPlex 4.0.2>: fastmip setting not available -- SCIP parameter has no effect
   3)  LP Solver <SoPlex 4.0.2>: number of threads settings not available -- SCIP parameter has no effect
   4)  transformed problem has 18 variables (0 bin, 0 int, 0 impl, 18 cont) and 49 constraints
   5)       48 constraints of type <linear>
   6)        1 constraints of type <NDSR>
   7)  
   8)  original problem has more than 57 active (6.46259%) nonzeros and more than 57 (6.46259%) check nonzeros
   9)  
  10)  presolving:
  11)  (round 1, fast)       12 del vars, 0 del conss, 0 add conss, 0 chg bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 0 clqs
  12)  clique table cleanup detected 0 bound changes
  13)  
  14)  presolved problem has more than 21 active (7.14286%) nonzeros and more than 21 (7.14286%) check nonzeros
  15)  
  16)  presolving (2 rounds: 2 fast, 1 medium, 1 exhaustive):
  17)   12 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
  18)   0 implications, 0 cliques
  19)  presolved problem has 6 variables (0 bin, 0 int, 0 impl, 6 cont) and 49 constraints
  20)       48 constraints of type <linear>
  21)        1 constraints of type <NDSR>
  22)  Presolving Time: 0.00
  23)  
  24)  cycle found!
  25)  cycle found!
  26)   time | node  | left  |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr|  dualbound   | primalbound  |  gap   
  27)    0.0s|     1 |     0 |     7 |     - | 682k|   0 |   0 |   8 |  49 |   8 |  48 |   0 |   0 |   0 |      --      |      --      |    Inf 
  28)  cycle found!
  29)    0.0s|     1 |     0 |     9 |     - | 686k|   0 |   0 |   9 |  49 |   9 |  48 |   0 |   0 |   0 |      --      |      --      |    Inf 
  30)  cycle found!
  31)    0.0s|     1 |     0 |     9 |     - | 686k|   0 |   0 |   9 |  49 |   9 |  48 |   0 |   0 |   0 | 1.500000e+00 |      --      |    Inf 
  32)  entering sepaNDSR
  33)    The cut is Efficacious 
  34)    Added cut is feasible
  35)  exiting sepaNDSR 
  36)  cycle found!
  37)    0.0s|     1 |     0 |    12 |     - | 688k|   0 |   0 |  12 |  49 |  12 |  49 |   1 |   0 |   0 | 1.500000e+00 |      --      |    Inf 
  38)  cycle found!
  39)    0.0s|     1 |     0 |    12 |     - | 688k|   0 |   0 |  12 |  49 |  12 |  49 |   1 |   0 |   0 | 1.500000e+00 |      --      |    Inf 
  40)  entering sepaNDSR
  41)    The cut is not Efficacious 
  42)  exiting sepaNDSR 
  43)   No cycle found!
  44)  L 0.0s|     1 |     0 |    12 |     - | 690k|   0 |   0 |  12 |  49 |  12 |  49 |   1 |   0 |   0 | 1.500000e+00 | 3.000000e+00 | 100.00%
  45)    0.0s|     1 |     0 |    12 |     - | 690k|   0 |   0 |  12 |  49 |  12 |  49 |   1 |   0 |   0 | 1.500000e+00 | 3.000000e+00 | 100.00%
  46)  entering sepaNDSR
  47)    The cut is not Efficacious 
  48)  exiting sepaNDSR 
  49)  * 0.0s|     1 |     0 |    12 |     - | 690k|   0 |   0 |  12 |  49 |  12 |  49 |   1 |   0 |   0 | 1.500000e+00 | 1.500000e+00 |   0.00%
  50)  
  51)  SCIP Status        : problem is solved [optimal solution found]
  52)  Solving Time (sec) : 0.02
  53)  Solving Nodes      : 1
  54)  Primal Bound       : +1.50000000000000e+00 (2 solutions)
  55)  Dual Bound         : +1.50000000000000e+00
  56)  Gap                : 0.00 %
  57)  cycle found!
  58)    [NDSR] <Three_OR_NDSR_cut>: violation: graph has a 3_OR cycle
  59)  best solution is not feasible in original problem

Please let me know if any further information is needed.

Best,
Nag

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: SCIP_solveLog_numered.txt
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200311/03cba9f0/attachment.txt>