[SCIP] SCIP checking "worse" solutions

[Marc Pfetsch]

Hi Alexander,

you are looking for the parameter "misc/improvingsols".

However, in your case, it could still be that the primal solution that 
you found is not optimal, so you need to possible produce a better 
solution. And there are heuristics in SCIP (like heur_crossover) that 
produce better solutions by combining worse solutions. The less primal 
solutions you produce the less successful they will be. But of course 
the behavior depends on the particular instance.

Best

Marc

On 11/05/2022 00:07, Alex Meiburg wrote:
> Hi all,
> 
> I have a problem with all binary variables, easy feasibility, and I just 
> care about finding the optimal solution. There are exponentially many 
> linear constraints, so I've implemented a custom constraint handler, and 
> a heuristic. The goal of the heuristic is to provide one pretty-good 
> solution, hoping it will cut off large portions of the tree. I also set 
> the emphasis to SCIP_PARAMEMPHASIS_OPTIMALITY.
> 
> Indeed, the heuristic is good, and it pretty quickly has (say) primal 
> and dual bounds of 2577 and 2573, respectively, in a particular 
> minimization problem. But then after this point I still get several 
> hundred calls to CONSCHECK in my constraint handler, checking the 
> feasibility of other solutions with objective values over 2600. These 
> points are all feasible, they don't lead to any improvement (even though 
> they are feasible), and they end up taking a long time in all the 
> CONSCHECK calls I have to process.
> 
> It would seem that SCIP should know that it can eliminate these 
> solutions, as they seem "terminal"(?) -- even though they are feasible, 
> they don't lead to any further searching -- and they are worse than the 
> current primal solution. Is there a setting in SCIP to change this 
> behavior, or is this a result of my constraint handler not giving 
> sufficient information to SCIP (that's keeping it from concluding useful 
> things?)
> 
> Some extra information:
>   -My constraint handler doesn't have actual associated constraints, 
> it's just a "global" thing the way that I'm using it. I don't know if 
> this harms performance, it just seemed easier to implement this way.
>   -SCIP is solving the problem completely at the first node; all these 
> feasible solutions are at the first node.
>   -My CONSCHECK isn't providing information on constraint violation. I 
> do have code to add global cuts (or rows, or new linear constraints) in 
> CONSCHECK. I'm not sure if I'm supposed to do this or not. Either way, 
> adding cuts in or not doesn't seem to really affect the performance.
> 
> Thanks for any information.
> Best,
> Alexander Meiburg
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip