[Scip] Questions regarding a Constraint Handler
Gerald Gamrath
gamrath at zib.de
Thu Sep 6 16:56:02 MEST 2012
Hi Jose,
most of the separators in SCIP check whether the rows they want to use
are modifiable and do not use them in this case. That means that if you
marked your Ax+By=b constraints to be modifiable, those should not be
used to create cuts. On the other hand, I'm not sure whether
structure-bases separators, e.g., the clique separator, handle the B&P case.
Therefore, it is probably better to deactivate all default separators,
just to be sure. In order to do this, you have to set the separation
frequencies of the separators or constraint handlers to -1, which you
can do using the method SCIPsetIntParam().
You can easily get a complete list of all parameters changed by setting
the separation emphasis to off, if you start the interactive shell of
SCIP and set the emphasis setting there by typing "set sepa emph off".
All of the parameters listed then should be changed, except for your own
separator.
Best,
Gerald
Am 05.09.2012 05:29, schrieb 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
> <mailto: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
>
>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20120906/55a3e061/attachment.html
More information about the Scip
mailing list