[Scip] branching on constraints

Wed Apr 17 16:30:22 MEST 2013

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/