[Cbc] How to iteratively cutting the current optimal solution

[Pierre.Lebodic at lri.fr]

Hello,

I've tried driver4b on my test instances. It is a labeled oriented
subgraph isomorphism problem, with a minimization of label distances
between matching edges and nodes. Originally, every variable is binary,
but the formulation is so that most of them can be relaxed into continuous
(ub=1) variables without affecting the feasible set. This is done in my
MPS files. This can be restored, at a small computational price.

The results of my tests are:
-driver4b, as far as my tests show, ends with a segfault while producing
feasible solutions.

-If multiple solutions are generated, there's no monotonicity, and it
seems like there is no control over the quality of the solutions
generated, despite the cutoff. For my application, monotonicity is not
mandatory, but we would like to enforce an interval in which solutions
every feasible solution is found. To define the interval, we use either
the optimal value if found or the integrality gap. There are currently
three kind of cuts implemented to cut the current solution. Two of them
can cut more than one feasible solution at a time. For our application, it
is mandatory that each time we apply such a cut, the other feasible
solutions that we cut are necessarily worse (or say not better by more
than 5%) than the one we just found. This is why up until now, we have
been searching for feasible solutions starting from the best ones.

-I would have liked to compare your approach with my implementation via
the symphony callbacks. However, the single solution resolution is 10
times slower on cbc2.3 than on symphony 5.1, with no tuning. It beats
symphony 5.2 though, which I'm trying out at the moment. From what I can
tell, the recent advances that have been implemented on both solvers do
not benefit my class of instances. Feasibility pump for instance
drastically slows the research. My first impressions on driver4b is that
once the first solution found, subsequent solutions are found faster than
with symphony, which starts all over again, so this is promising.

Here is a link to a series of 80 test instances:
http://www.lri.fr/~lebodicp/wp-content/uploads/subgraph_isomorphism_mps_instances.tar.gz

Let us see what happens for instance 40:
We ask symphony for the 5 best solutions (with smallest possible cut).
Their values are 3.437, 3.532, 3.550, 3.552, 3.580. This is the desired
solutions set for this example. Of course if we find other feasible
solutions with at no additional cost it is also fine.
We ask driver4b to search for solutions.
With cut type #1 and rhs initialized at -1 . Values are 4.40433, 4.38777,
4.28425, 3.43735, 3.68324, 3.53232, then segfault.
With cut type #2, values are 4.40433, 4.38777, 4.28425, 4.20635, 4.10759,
4.06212, 3.8775, 4.1021, 4.12286, segfault.
With cut type #1 and feasibility pump disabled: 4.28425, 3.43735, 3.68324,
3.53232, segfault.
With cut type #2 and feasibility pump disabled: 4.28425, 4.20635, 4.06212,
4.07036, 4.06867, 4.1021, 4.10759, 4.39617, 3.97043, 4.05624, segfault.


Also the output indicates that too many variables are set to 1, but this
might just be a small bug linked to the fact that some variables are
[0,1]. For this problem, the solution always contains 7 {0,1} variables
set to 1, and 16 [0,1] variables set to 1.

Thanks for your time.

Pierre