[Scip] branching on constraints

Alessia Violin aviolin at ulb.ac.be
Fri Apr 19 11:51:04 MEST 2013


Hello Gerald and Ambros,

changing the initial flag makes dual variables changing value, thanks.

But then indeed I am adding the same constraint to different nodes, so I 
will have to change this. I will got through this and see what's 
happening, thanks for the help and all the suggestions.

Alessia




On 04/19/2013 11:15 AM, Gerald Gamrath wrote:
> Hi Alessia,
>
> do you set the initial flag of the linear constraints to TRUE?
>
> Do I understand you correctly that for each original variable x, you
> create one constraint with all master variables that have x = 0, and one
> with all master variables with x = 1? If you branch x to 0, you say that
> the first constraint has a right hand side of 1 and second constraint a
> right hand side of 0? For branching x to 1 the other way around? In
> priciple, this is a valid possibility, but it has two drawbacks:
> 1) This probably consumes a lot of memory, since the constraints with
> master variables with x = 0 are very dense.
> 2) You cannot add the same constraint at different nodes in SCIP, but
> you will branch on the same variable at different nodes, so creating
> each constraint once in advance is not possible, you have to generate
> them when needed.
>
> I always prefer the variant with a dummy constraint which is not added
> to the LP, but just does propagation. It just stores that x has been
> branched to 1 and then iterates over all variables, fixing all master
> variables to 0 which have x != 1. This is essentially the same as the
> constraint, but you don't get so many additional constraints in your
> master, just a lot of variables are fixed to 0 by branching. Please have
> a look at the Binpacking example, the samediff constraint handler does this.
>
> Best,
> Gerald
>
> On 19.04.2013 11:01, Alessia Violin wrote:
>> Hello Gerald,
>>
>> thinking that it would have been easier to update the branching
>> constraints with the new columns founded during the pricing, I created
>> the whole set of possible branching constraint in the main, as a
>> vector of linear constraints for the branch 0 and another for the
>> branch 1, but without adding them to the model (no call of
>> SCIPaddCons). Then in the pricing I am able to add new columns to them
>> every time I found one. In the enfolp call of the constraint handler
>> therefore I check if my solution is integral and if not I add the
>> corresponding constraint to the node with SCIPaddConsNode(). The
>> branching constraint is therefore not created in the constraint
>> handler, but picked up from the vector of linear constraints I created
>> at the beginning. This is what I was refering as "dummy constraints",
>> but maybe I cannot use this strategy?
>> Printing the model after the branching I see the constraint I just
>> added, but as I said then dual variables are zero so the pricing is
>> already optimal and it's not finding new variables to add.
>>
>> best,
>>
>> Alessia
>>
>>
>>
>>
>>
>> On 04/18/2013 05:59 PM, Gerald Gamrath wrote:
>>> Hi Alessia,
>>>
>>>> As you suggested I have dummy constraints for branching, initialized
>>>> fro the beginning but not included in the model, always updated during
>>>> pricing and added to the model of a node when needed.
>>> These dummy constraint are from your own constraint handler? You create
>>> one at each node storing the branching decisions and add to the node
>>> using SCIPaddConsNode()? What do you update during pricing?
>>>
>>>> So in enfolp I create my branches and new nodes are added, along with
>>>> the branching constraints (printing the model I can see them).
>>> These branching constraints are again the dummy constraints or some
>>> linear constraints?
>>>
>>>> But then, in the new node, when it goes back to pricing it doesn't
>>>> find any new column, as dual variables associated to the new
>>>> constraint are null, and therefore it finds that the lp is already
>>>> optimal. So the solution is always the same and it keeps on branching
>>>> onto the same constraint in an infinite loop.
>>> If the branching constraints are you own constraints, they are not part
>>> of the LP and therefore have no dual solution. If they are linear
>>> constraints, they were perhaps not added to the LP. Did you set the
>>> initial flag to TRUE when creating them?
>>>
>>>> I tried to look for dual variables of the transformed constraint, as I
>>>> am doing for all other constrains, but actually it is not finding the
>>>> transformed constraint.
>>>>
>>>> About the consactive, when is it accessing it? I tried but it's never
>>>> going into this function. Indeed, I would like to locally fix some
>>>> variables after the branching decision, should I do if with the method
>>>> SCIPfixVar? but will it be valid only at the current node or globally?
>>> If you add a constraint to a node, the consactive callback is called
>>> whenever the node is entered. You can use this callback to update your
>>> pricing problems, and possibly check whether new variables were added
>>> after you left the node the last time, whoch means that you have to
>>> check and possbily fix these variabes. However, you should not fix
>>> variables within the CONSACTIVE callback, but do that in the CONSPROP
>>> callback. You can do the fixing with SCIPfixVar() than and it will only
>>> be applied locally at the current node.
>>> The samediff Constraint handler in the Binpacking example should give
>>> you a hint about how you can do that.
>>>
>>> Best,
>>> Gerald
>>>
>>>> On 04/17/2013 06:51 PM, Gerald Gamrath wrote:
>>>>> Hi Alessia,
>>>>>
>>>>> it might be that some other constraint handler or branching rule
>>>>> already
>>>>> performed branching. In order to be first, your constraint handler
>>>>> should have a high CONSHDLR_ENFOPRIORITY.
>>>>>
>>>>> You can check the statistics for the number of children created by the
>>>>> plugins. In the interactive shell, you need to type "display
>>>>> statistics", in the API, you call SCIPprintStatistics() after solving.
>>>>> It also might be that the small instance is solved at the root node,
>>>>> e.g., because a good solution is found.
>>>>>
>>>>> The branching has nothing to do with the propagation, for which you
>>>>> changed the timing mask. Branching is never done during the node
>>>>> solving, but just at the end, after column generation is finished.
>>>>> Propagation is a sort of node preprocessing, which tries to tighten
>>>>> the
>>>>> local bounds of variables.
>>>>>
>>>>> For storing your branching decisions, I would suggest you create dummy
>>>>> constraints of your constraint handler which store your branching
>>>>> restrictions. Furthermore, in the CONSACTIVE and CONSDEACTIVE
>>>>> callback,
>>>>> they can update your pricing problem, and they can fix variables to 0
>>>>> locally which do not comply with your branching decision. Please
>>>>> have a
>>>>> look at the Binpacking and the Coloring example, which come with SCIP
>>>>> (see the examples directory).
>>>>>
>>>>> Best,
>>>>> Gerald and Michael
>>>>>
>>>>>
>>>>> On 17.04.2013 16:30, Alessia Violin wrote:
>>>>>> Hello,
>>>>>>
>>>>>> thanks for the explanation.
>>>>>>
>>>>>> I changed needscons to FALSE, but still for a small instance it is
>>>>>> not
>>>>>> entering into the enfolp call of the constraint handler, I don't
>>>>>> understand why. This instance needs branching, as the lp solution is
>>>>>> not integer. I set timinmask parameter to
>>>>>> SCIP_PROPTIMING_AFTERLPNODE,
>>>>>> as I first want to solve the node with column generation and then I
>>>>>> check for integrality and eventually branch, is that correct?
>>>>>>
>>>>>> For bigger instances it is entering, but I didn't managed to make it
>>>>>> working yet. As I need to change the pricing after adding branching
>>>>>> constraint, I would check if a certain constraint has been added to
>>>>>> the current node. For this I found those functions, but I don't
>>>>>> understand very well the difference between them and which one I
>>>>>> should use: SCIPconsIsActive, SCIPconsIsEnabled and SCIPconsIsAdded.
>>>>>>
>>>>>> Best,
>>>>>>
>>>>>> Alessia
>>>>>>
>>>>>>
>>>>>>
>>>>>> On 04/11/2013 06:02 PM, Gerald Gamrath wrote:
>>>>>>> Hi Alessia,
>>>>>>>
>>>>>>> you are right: You need to set needscons to FALSE, because you do
>>>>>>> not
>>>>>>> create constraints of your constraint handler, but the handler
>>>>>>> itself
>>>>>>> needs to check solution candidates.
>>>>>>>
>>>>>>> The integrality constraint handler is just the constraint handler
>>>>>>> that
>>>>>>> ensures that integral and binary variables get integral values.
>>>>>>> Actually, your constraint handler is pretty similar, it just checks
>>>>>>> the
>>>>>>> integrality of the original variables.
>>>>>>>
>>>>>>> Best,
>>>>>>> Gerald
>>>>>>>
>>>>>>> On 11.04.2013 11:36, Alessia Violin wrote:
>>>>>>>> Hello Gerald,
>>>>>>>>
>>>>>>>> thanks for your suggestions. I will have a look at GCG, I didn't
>>>>>>>> know
>>>>>>>> about it! But as my pricing (with stabilization) is already
>>>>>>>> working in
>>>>>>>> SCIP, I will try to continue on this.
>>>>>>>>
>>>>>>>> I added a constraint handler class, define a new object in the main
>>>>>>>> and include it in my scip, do I need to do more to activate it? For
>>>>>>>> the moment the functions of my class are empty, but I tried to put
>>>>>>>> some cout to see if it enters in the functions and in particular in
>>>>>>>> the enfolp, and nothing appears. As parameters for the constraint
>>>>>>>> handler I set
>>>>>>>> sepapriority -100000
>>>>>>>> enfopriority 100000
>>>>>>>> checkpriority -100000
>>>>>>>> sepafreq -1
>>>>>>>> propfreq -1
>>>>>>>> eagerfreq 1
>>>>>>>> maxprerounds 0
>>>>>>>> delaysepa FALSE
>>>>>>>> delayprop FALSE
>>>>>>>> delaypresol FALSE
>>>>>>>> needscons TRUE
>>>>>>>> (maybe the problem is here)
>>>>>>>>
>>>>>>>> What do you mean by integrality constraint handler? do I need to
>>>>>>>> set
>>>>>>>> somewhere that constraints are integer?
>>>>>>>> I am a bit confused...
>>>>>>>>
>>>>>>>> Thanks again,
>>>>>>>>
>>>>>>>> Alessia
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On 04/10/2013 02:46 PM, Gerald Gamrath wrote:
>>>>>>>>> Hi Alessia,
>>>>>>>>>
>>>>>>>>> when you have no integrality restrictions on your variables, but
>>>>>>>>> only on
>>>>>>>>> the sum of your master variables, you should implement a
>>>>>>>>> constraint
>>>>>>>>> handler instead of a branching rule. In the scip_enfolp function,
>>>>>>>>> you
>>>>>>>>> need to check for the integrality of your (implicit) original
>>>>>>>>> variables
>>>>>>>>> and perform branching, if necessary. The enfolp-function is where
>>>>>>>>> the
>>>>>>>>> branching really happens, in particular, the integrality
>>>>>>>>> constraint
>>>>>>>>> handler calls the branching rules within his ENFOLP callback.
>>>>>>>>> Thus,
>>>>>>>>> your
>>>>>>>>> branching rule is not called because no violated integrality
>>>>>>>>> restrictions are identified.
>>>>>>>>>
>>>>>>>>> By the way: did you already have a look at GCG (see
>>>>>>>>> http://www.or.rwth-aachen.de/gcg/), the generic
>>>>>>>>> branch-cut-and-price
>>>>>>>>> solver in the SCIP optimization suite? You only need to read in
>>>>>>>>> the
>>>>>>>>> original formulation (expressed in the x_a^k variables) and
>>>>>>>>> possibly a
>>>>>>>>> structure defining file and GCG will perform a Dantzig-Wolfe
>>>>>>>>> decomposition which will probably end up in the same master
>>>>>>>>> problem
>>>>>>>>> solved by branch-and-price. Within GCG, also the branching on
>>>>>>>>> original
>>>>>>>>> variables as constraints in the master is already implemented. The
>>>>>>>>> pricing problem is solved as a MIP by default, but you might even
>>>>>>>>> add
>>>>>>>>> your own pricing problem solver if you have a better algorithm.
>>>>>>>>>
>>>>>>>>> Best,
>>>>>>>>> Gerald
>>>>>>>>>
>>>>>>>>> On 10.04.2013 12:58, Alessia Violin wrote:
>>>>>>>>>> Dear Ambros,
>>>>>>>>>>
>>>>>>>>>> thanks for your suggestion.
>>>>>>>>>>
>>>>>>>>>> I created a new branchrule class (I am using c++), and in the
>>>>>>>>>> main I
>>>>>>>>>> create a new object of this type and add it with the function
>>>>>>>>>> SCIPincludeObjBranchrule. Then I am looking at the different
>>>>>>>>>> functions
>>>>>>>>>> that are in the class, but it's not very clear to me when it
>>>>>>>>>> enters in
>>>>>>>>>> them during the solving. I saw that in the preprocessing it
>>>>>>>>>> enters
>>>>>>>>>> into
>>>>>>>>>> the scip_initsol. But what about the scip_execlp? It seems to me
>>>>>>>>>> that it
>>>>>>>>>> never enters in it and I suppose it's here I have to add the
>>>>>>>>>> methods
>>>>>>>>>> SCIPcreateChild and SCIPaddConsNode, right?
>>>>>>>>>>
>>>>>>>>>> Then I have another doubt: as in my problem there are no
>>>>>>>>>> integer or
>>>>>>>>>> binary variables, but I want a sum of variables (multiplied by
>>>>>>>>>> parameters) to be binary, how is SCIP dealing with this? Where
>>>>>>>>>> should I
>>>>>>>>>> check for this condition and tell to branch or not?
>>>>>>>>>>
>>>>>>>>>> Sorry for those quite basic questions, it's the first time I
>>>>>>>>>> implement a
>>>>>>>>>> branching rule.
>>>>>>>>>>
>>>>>>>>>> Thanks,
>>>>>>>>>>
>>>>>>>>>> Alessia
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On 04/08/2013 11:50 PM, Ambros Gleixner wrote:
>>>>>>>>>>> Dear Alessia,
>>>>>>>>>>>
>>>>>>>>>>> constraint-based branching is rather straightforward to
>>>>>>>>>>> implement in
>>>>>>>>>>> SCIP.  You have to add a new branching rule that uses the
>>>>>>>>>>> methods
>>>>>>>>>>> SCIPcreateChild() and SCIPaddConsNode() in its branching
>>>>>>>>>>> callbacks.
>>>>>>>>>>>
>>>>>>>>>>> A very good example for this is the Ryan/Foster branching rule
>>>>>>>>>>> that
>>>>>>>>>>> has
>>>>>>>>>>> been implemented in the binpacking example:
>>>>>>>>>>>
>>>>>>>>>>> http://scip.zib.de/doc/examples/Binpacking/index.shtml
>>>>>>>>>>>
>>>>>>>>>>> http://scip.zib.de/doc/examples/Binpacking/branch__ryanfoster_8c_source.shtml
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Hope that helps,
>>>>>>>>>>>
>>>>>>>>>>> Ambros
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Am 08.04.2013 15:47, schrieb Alessia Violin:
>>>>>>>>>>>> Hello,
>>>>>>>>>>>>
>>>>>>>>>>>> solving my problem with branch&price I would like to change the
>>>>>>>>>>>> branching. Now I am branching on binary variables x_a^k = sum_j
>>>>>>>>>>>> l_a^j *
>>>>>>>>>>>> x_a^k,j <= 1, simply defining them as binary in the variable
>>>>>>>>>>>> definition
>>>>>>>>>>>> as they do not occur in the pricing. The variables for the
>>>>>>>>>>>> pricing
>>>>>>>>>>>> are
>>>>>>>>>>>> l_a^j, and x_a^k,j are parameters that I calculate during the
>>>>>>>>>>>> pricing.
>>>>>>>>>>>>
>>>>>>>>>>>> As those x_a^k variables are added only for the branching, I
>>>>>>>>>>>> would
>>>>>>>>>>>> like
>>>>>>>>>>>> to eliminate them and branch directly on constraints sum_a
>>>>>>>>>>>> l_a^j *
>>>>>>>>>>>> x_a^k,j <=1 (they can be 0 or 1).
>>>>>>>>>>>>
>>>>>>>>>>>> Does it exist already in SCIP a branching rule on
>>>>>>>>>>>> constraints? If
>>>>>>>>>>>> not,
>>>>>>>>>>>> shall I do it defining a new branching rule or is there an
>>>>>>>>>>>> easier
>>>>>>>>>>>> way to
>>>>>>>>>>>> do it?
>>>>>>>>>>>>
>>>>>>>>>>>> Thank you in advance for any help and suggestion,
>>>>>>>>>>>>
>>>>>>>>>>>> Alessia
>>>>>>>>>>>>
>>>>>>>>>>> _______________________________________________
>>>>>>>>>>> Scip mailing list
>>>>>>>>>>> Scip at zib.de
>>>>>>>>>>> http://listserv.zib.de/mailman/listinfo/scip

-- 
Alessia Violin
Service Graphes et Optimisation Mathématique (G.O.M.)
Université Libre de Bruxelles
C.P. 210/01
Boulevard du Triomphe
B-1050 BRUXELLES
Tel: 02 650 58 80 - Fax: 02 650 59 70
Email: aviolin at ulb.ac.be
Webpage: http://homepages.ulb.ac.be/~aviolin/



More information about the Scip mailing list