[Scip] Questions regarding a Constraint Handler

[Jose L Walteros]

Hi Michael,

Thanks for your answers. The code is now working like a charm.

I have a new question, though. I also have a reformulation of my problem
that I want to test. This formulation requires CG to be solved. I am trying
to embed the constraint handler that I created within the BPC.

To describe a bit better my question, let me describe the structure of my
problem first (the reformulation that requires CG).

My problem has the following structure

min c^tx
st

Ax+By>=b
Dx>=h

x,y are binary

where x, is a vector of variables (polynomial in size). This vector is
generated from the problem construction and never changes in terms of the
size (i.e., no other variable x is generated via CG or deleted somewhere in
the code).

On the other hand, vector y is exponential in size, therefore new variables
y are generated via CG.

Furthermore, the set of constraints Dx>=h is also exponential in size and
hence, I had to code the constraint handler to generate those constraints
sequentially in a similar fashion as for the TSP case (even though I am not
breaking cycles the idea is the same). Fortunately, since variables y are
not present in this set of constraints I don't have to worry about their
dual variables when calling the pricer.

Now, the constraint handler that I coded include separation algorithms for
fractional solutions. The problem that I have is that since mi code is
solved via BPC, I require to use (as suggested by you) the line

SCIP_CALL( SCIPsetSeparating(scip, SCIP_PARAMSETTING_OFF, TRUE) );

to avoid adding cuts involving the CG variables (This could mess up the
pricer as those cuts produce a dual and...).

My question is, how can I tell SCIP which separators should be turned off
and which should be used?

If I use the code above, SCIP turns off all separators, including the one
that I created, and of course that is not what I want.

I tried to remove this line and the code works for some of the testing
instances, as for some reason, the other separators are not called during
the execution. However, I am worried that maybe it can happen while solving
other instances.\

Any ideas,

Thanks a lot.

-Jose


On Thu, Aug 30, 2012 at 8:26 AM, <michael.winkler at zib.de> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20120905/672f201a/attachment.html