[Scip] Questions regarding a Constraint Handler

[michael.winkler@zib.de]

Hi,

> 1. In the cpp file you don't have the method
SCIPcreateConsSubtourBasic().
> When
> do you need this?. I am not really sure about its purpose. I totally get
the SCIPcreateConsSubtour() method. However, the basic method is not
clear
> for me. You have:
>

The whole idea of the SCIPcreateCons*Basic() is to create constraints
without having to think about values for the (initial, separate, ...)
flags.
So it should be easier for (other) users to create constraints, when they
are not sure how the flags should be set.

>
> 2. About the CONSCHECK method. What I understand about it is the following:
> The only purpose this method is to check if a solution that is produced
by
> any method "outside" the standard BCP (i.e., a heuristic) is feasible.
The
> reason why it does not adds a cut or a constraint is because the fact
that
> the solution that it is being checked is not produced by the LP cycle,
hence, there is no point of adding any cut. Is this correct?
>

Almost. The purpose is to check any given solution which should be checked
as a global valid solution. These solutions can be originated by a
heuristic, by the lp or by ... . There are probably some reasons why this
callback does not allow to add cuts or constraints. Some of them are that
you want to distinguish between the possibility to only check(, which
should be fast algorithm,) or to be able to create a cut/constraint, if
the solution was violated, and that you still want to able to only check
the best solution in the original problem space.

> 3. About the CONSENFOLP. Since it may add a cut or a constraint, is it
possible for the case of the TSP to call sepaSubtour instead of
> findSubtourwithin this method?
>

Yes.

> 4. Also, what is the main difference between adding a global cut pool
and
> adding a constraint for the case of the TSP? If you use  SCIPaddCut(),
you
> add the cut locally to the current node of the B&B tree?. I guess that
if
> you add it to the global cut, they become available for other nodes to use,
> right? This is also the case if you add a constraint instead, right? The
reason I am asking is that the sub-tour elimination constraints are
constraints that actually define the TSP polyhedron. Contrary to simple
valid inequalities that just cut fractional solutions. This constraints
define the feasible integer solutions, so why do you add those as cuts
and
> not as constraints.
>

A constraint is more powerful than a cut, a constraint can be propagated
or separated ..., a cut is only a row in the lp.
Choosing SCIPaddCut() does not decide whether the cut is local or global,
this is done by setting the 3rd last parameter of SCIPcreateEmptyRow*().
You can also add a constraint locally by calling SCIPaddConsLocal()
instead of globally by calling SCIPaddCons(). So all the added cuts here
are globally valid.

> 5. Furthermore, since those are added with   SCIPaddCut() that means
that
> they are added locally. This implies that you may have to add the same
cut
> in a different node of the B&B tree, right? Is it better if you add
those
> as SCIPaddCons()and then  return, SCIP_CONSADDEDinstead?
>

See above.

> 6. SCIP_DECL_CONSHDLRCLONE has the same purpose as
> the SCIP_DECL_CONSHDLRCOPY, right? SCIP_DECL_CONSHDLRCLONE is just for
cpp
> (implements the cloneable property). I guess that for c I should
implement
> COPY instead, right?
>

Yes.

> 7. Could you please elaborate a little bit more the explanation of the
WARNING in CONSDELETE method. I guess that this is only valid if for an
reason you plan to delete the constraint while the BPC is still in
process,
> right? should I be worried is this is not the case?
>

This is a very unlikely case, which you should not really worry about.

> 8. For CONSPROP you have:
>
> The CONSPROP callback is called during the subproblem processing. It should
> propagate the constraints, which means that it should infer reductions
in
> the variables' local bounds from the current local bounds.
>
>
> By the subproblem you mean when a pricer is called? So, I'm guessing
that
> the idea is propagate possible bound changes possibly produced by the
constraint handler inside the pricer's subproblem. I concluded this
because
> for the TSP, since you are not generating variables, you don have to
perform such propagations, right? That is why you return DIDNOTTURN. Do
you
> guys have an example of a case in which you implement this?
>

The meaning of subproblem is more like a current problem in a branch and
bound node. It tries to change mostly local bounds which can be derived
from branching decisions (and other propagations), but could also be used
for new global information, e.g. creating/deleting constraints. It has
nothing to do with pricing but since it is not fundamental, you do not
need to implement the callback method.

Best, Michael