[SCIP] Adding an efficacious cut is not increasing the bound
Diego Delle Donne
diegodd at gmail.com
Thu Mar 12 09:14:06 CET 2020
Hi Naga,
I don't know if this would help but have in mind that adding a cut does not
always have to improve the dual bound. You may have multiple solutions with
the same objective value and your cut is probably cutting just one (or some
but not all) of them.
I'd suggest to check whether the new optimal solution (found after the cut)
satisfies the cut or not. If it satisfies the cut (and have the same
objective value), then you are in the case of multiple optimal solutions
(which is the most common case in CO problems I'd say).
Good luck
Diego
El jue., 12 mar. 2020 a las 8:48, Naga Venkata Chaitanya Gudapati -
nagavenkata.gudapati at studio.unibo.it (<nagavenkata.gudapati at studio.unibo.it>)
escribió:
> I should have added the code for adding the cut. Apologies for that.
>
> SCIP_CALL( SCIPflushRowExtensions(scip, row) );
> // add cut
> if( SCIPisCutEfficacious(scip, sol, row) )
> {
> std::cout << "The cut is Efficacious " << "\n";
> SCIP_Bool infeasible;
> SCIP_CALL( SCIPaddRow(scip, row, false, &infeasible) );
> if ( infeasible )
> {
> *result = SCIP_CUTOFF;
> std::cout << "Added cut is infeasible" << "\n";
> }
> else
> {
> std::cout << "Added cut is feasible" << "\n";
> *result = SCIP_SEPARATED;
>
> }
>
> }
> else
> {
> std::cout << "The cut is not Efficacious " << "\n";
> }
>
> ________________________________________
> From: Scip <scip-bounces at zib.de> on behalf of Naga Venkata Chaitanya
> Gudapati - nagavenkata.gudapati at studio.unibo.it <
> nagavenkata.gudapati at studio.unibo.it>
> Sent: Wednesday, March 11, 2020 2:48 PM
> To: scip at zib.de
> Subject: [SCIP] Adding an efficacious cut is not increasing the bound
>
> 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
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20200312/742198b1/attachment.html>
More information about the Scip
mailing list