[Scip] Could a global cut be discarded ?

[achterberg@zib.de]

Hi Nikolaj,

[This might be of interest to all SCIP users, so I send it to the list as
well. The mail includes a detailed description of what the global cut pool
is used for and some comments about separating cuts at local nodes.]


> For instance, when you say
> _________________________
> "This is the reason why you should also add globally valid cuts to the cut
> pool
>  (at least if separating them is a non-trivial
>  effort), such that they are added automatically to other nodes in the
>  search tree if they are violated."
> _________________________
>
> I guess that this is done with SCIPaddPoolCut(). But even by using this, I
> see that the separator is still generating the same cut long after the
> first time it was discovered. Is this normal behavior and am I right using
> SCIPaddPoolCut() ?

This is normal. See below.


> When you say
> _________________________
> "But even if they are in the cut pool,
>  it could be that your separator finds them again in the same separation
>  round as the cut pool adds them. But this does no harm because identical
>  cuts are discarded by cut filtering."
> _________________________
>
> I've indeed seen that the same cut is not duplicated. Now, what I
> understand is that SCIP decides to remove or add global cuts from time to
> time (when they are no longer violated?). One cut was removed two times
> and added (and discovered) three times. The global cuts are held in the
> global cut pool but not necessarily used. Is this correct?

Correct. See below.


> If my assumption if right, do you think there is a way to keep efficienly
> the cuts discovered by the separator? These cuts are difficult to find
> (some tests on Gomory-Hu trees for huge graphs) and there can be hundreds
> of them. They are globaly valid and once I have one, I would like to use
> it in every LP.

This exactly the task of the global cut pool, see below.


> Is there a way to reintroduce the already discovered cuts if they are
> violated in the current LP without having to discover/test them again?
> Actually, I would like to keep them all in the LPs, so I could parse the
> global cut pool and reintroduce all the cuts that have been removed from
> the LP. Is this possible and advisable?

Here comes the long answer to all of your questions above:

The cut separation loop in SCIP looks as follows:
1. Solve LP.
2. Separate global cut pool.
3. Call sepa methods of constraint handlers with sepaprio >= 0.
4. Call separator plugins.
5. Call sepa methods of constraint handlers with sepaprio < 0.
6. Filter collected cuts.
7. Add cuts that survived the filtering to the LP.
8. Goto 1.

All cut separator methods, including the separation from the global pool,
have an associated separation frequency. For example, if the frequency is
set to 5, the method is called only for nodes that are in depth 0, 5, 10,
15, ... of the search tree. In the default settings, SCIP is a
cut-and-branch algorithm. That means, all frequencies are set to 0, which
is a special value that indicates that the separator should only be
applied at the root node. In particular, this is also true for the global
cut pool.

Now you may ask why a separation frequency of 0 makes any sense for the
global cut pool. The answer is that SCIP can remove cuts again from the LP
(if they are marked as "removable"). The cut pool ensures that a cut that
was added, then removed because it was no longer tight, gets added back
into the LP if it becomes violated again within the cut separation loop of
the current node (i.e., the root node in default settings).


Now back to your questions:

As far as I can see, you are essentially facing two issues:

1. The global cut pool is not separated at local nodes, because the
"separating/poolfreq" parameter is still on its default value 0. You
should just set it to 1 (or any appropriate positive value) in order to
make sure that your cuts from one local node are also used in other local
nodes.

2. Even if the global cut pool added one of your "old" cuts to the
intermediate cut storage (from which the cuts are added to the LP after
cut filtering), you will find the same cut again in your separator and
basically waste the time to find an already known cut. In order to avoid
this, my suggestion is to separate your cuts in a "delayed" fashion. This
means, when your cut separator is called (which is always after the global
cut pool has already been scanned), and there are already cuts in the
separation storage, then you just do nothing and wait for the next round.
If you want to do this manually, you can call SCIPgetNCuts() to get the
current number of cuts stored in the separation storage. If this is
positive, just set *result = SCIP_DELAYED and do nothing. The SCIP_DELAYED
status tells SCIP that even though your separator did not find any cuts it
should be called again (even on the same solution) if nobody else found a
cut or all cuts have been discarded in the filtering step.
The same thing can be done automatically by setting the SEPA_DELAY flag to
TRUE in the creation of the separator plugin. For constraint handlers,
this flag is called CONSHDLR_DELAYSEPA, see the sepa_xxx.c and cons_xxx.c
templates. If the plugin has this flag, than SCIP only calls it if none of
the higher priority plugins have found a cut for the current solution.
If you want to have a finer control on when to separate cuts and when to
delay your separator, you need to use the manual way described above. But
I think you should be fine with the automatic way, at least if your
separation procedure is so expensive that you really want to only call it
if nobody else has found a cut.



I hope this solves most of your issues. If not, feel free to ask again.


Best,

Tobias