[SCIP] Fwd: Adding an efficacious cut is not increasing the bound
Naga Venkata Chaitanya Gudapati - nagavenkata.gudapati@studio.unibo.it
nagavenkata.gudapati at studio.unibo.it
Tue Mar 17 12:39:57 CET 2020
Thanks for the reply. I think the issue is, since I am doing branch cut and price, after adding the cut, some more columns are getting added and hence the lower bound is reduced again.
I think I have to figure out how to not add columns once I add cuts. But I think I should ask that as a separate question.
Thanks for your help.
________________________________________
From: Scip <scip-bounces at zib.de> on behalf of Leona Gottwald <gottwald at zib.de>
Sent: Thursday, March 12, 2020 6:29 AM
To: scip at zib.de
Subject: [SCIP] Fwd: Adding an efficacious cut is not increasing the bound
This should have gone to the list
-------- Forwarded Message --------
Subject: Re: [SCIP] Adding an efficacious cut is not increasing the bound
Date: Thu, 12 Mar 2020 11:28:11 +0100
From: Leona Gottwald <gottwald at zib.de><mailto:gottwald at zib.de>
To: Naga Venkata Chaitanya Gudapati - nagavenkata.gudapati at studio.unibo.it<mailto:nagavenkata.gudapati at studio.unibo.it> <nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it>
Hi Naga,
a cut that is added with SCIPaddRow() does not necessarily end up in in
the LP. SCIP does select a subset of cuts to be added to the LP
heuristically. If your cut is globally valid, then you could add it to
the cutpool (with SCIPaddPoolCut()). The cutpool will consider the cut
in several separation rounds if it is violated and not just in the one
it was found. If you want to force your cut going to the LP, then you
could use SCIPaddRow but set the third parameter "forcecut" to TRUE
instead of FALSE.
Best,
Leona
On 3/12/20 9:31 AM, Naga Venkata Chaitanya Gudapati -
nagavenkata.gudapati at studio.unibo.it<mailto:nagavenkata.gudapati at studio.unibo.it> wrote:
Hello Diego,
Thanks for the reply. But when I add the cut by hand, the dual bound definitely increases ( the problem is formulated in such a way that the bound should increase). I also noticed in the last line of the log that:
best solution is not feasible in original problem
I assume that means the cut is added but somehow the optimal solution is not getting updated?
________________________________________
From: Diego Delle Donne <diegodd at gmail.com><mailto:diegodd at gmail.com>
Sent: Thursday, March 12, 2020 4:14 AM
To: Naga Venkata Chaitanya Gudapati - nagavenkata.gudapati at studio.unibo.it<mailto:nagavenkata.gudapati at studio.unibo.it>
Cc: scip at zib.de<mailto:scip at zib.de>
Subject: Re: [SCIP] Adding an efficacious cut is not increasing the bound
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<mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it> (<nagavenkata.gudapati at studio.unibo.it<mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it><mailto: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<mailto:scip-bounces at zib.de><mailto:scip-bounces at zib.de><mailto:scip-bounces at zib.de>> on behalf of Naga Venkata Chaitanya Gudapati - nagavenkata.gudapati at studio.unibo.it<mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it> <nagavenkata.gudapati at studio.unibo.it<mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it><mailto:nagavenkata.gudapati at studio.unibo.it>>
Sent: Wednesday, March 11, 2020 2:48 PM
To: scip at zib.de<mailto:scip at zib.de><mailto:scip at zib.de><mailto: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<mailto:Scip at zib.de><mailto:Scip at zib.de><mailto:Scip at zib.de>
https://listserv.zib.de/mailman/listinfo/scip
_______________________________________________
Scip mailing list
Scip at zib.de<mailto:Scip at zib.de>
https://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list