[Scip] SCIP Bounds converging very slow!

[Paul Theodor Pyl]

Hi all,

we are two Students who are trying to solve clustering problems using
SCIP. We have given an undirected graph consisting of nodes and weighted
edges (the weights are similarity scores and can be negative or
positive). We are using a set of Triangle-Inequalities that are created
in a ConstraintHandler we wrote. The Linear constraints for this
inequalities.
Given 3 variables x1..3 of Type SCIP_VARTYPE_BINARY (the edge weights
are used in the scoring function), we use the folowing inequalities to
guarantee, that either all or none of the edges in a trinagle between
x1..3 are present:

 x1 + x2 - x3 <= 1
 x1 - x2 + x3 <= 1
-x1 + x2 + x3 <= 1

We start without linear constraints and then iteratively add those
triangle-inequalities. Which we only add in the Callback-Function
scip_sepalp. We have implemented the following Callbacks:

-	scip_enfolp
-	scip_check
-	scip_trans

In most of the additional Callback-Functions we only return SCIP_OK and
set *result to SCIP_DIDNOTRUN.

For an Instance of the problem with 40 nodes we compared solution times
from a CPLEX-Implementation with our own SCIP-based program. Our
implementation is always slower, which might be due to inefficient
programming, but we can also see in the output of SCIP, that the primal
and dual-bound change only by minimal amounts in each iteration-step.

So we get differences in the regions of CPLEX solving the instance in
0.05 seconds and our program running for over 8000 seconds. In the
SCIP-Help it is said, that we could implement additional Callbacks to
improove the speed of the program, but since we are using the ConsLinear
Constrainthandler for our triangle-inequalities, which we assume to
already have such advanced features, we are now out of ideas to solve
this problem.

We would be very thankfull for any hints that might help us improve the
performance of our tool.

Thanks in advance,
Marco & Paul