[SCIP] SCIP checking "worse" solutions

[Alex Meiburg]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20220510/675d7ac6/attachment.html>