[Scip] Changing the bounds of a FIXED variable
Gerald Gamrath
gamrath at zib.de
Tue Mar 12 15:11:42 MET 2013
Hi Vivek,
yes, MP should be the master problem.
Why do you need to read in the original problem containing all variables
at first? If a small version of your model has nearly one million
variables, you might easily run out of memory just for reading in larger
problems (that's one of the reasons for using B&P).
I would suggest you do something similar to what is done in the
Binpacking or Coloring example which come with SCIP: You write your own
reader which reads in the data of your problem (e.g., for binpacking,
which items with which sizes do you have) and then create your master
constraints, which are initially empty or you already create some master
variables. Based on that data, you also create the pricing subproblem
and your pricer can store information about the "meaning" of the
variables in the variable data. Best you just have a look at the
examples and the FAQ.
Best,
Gerald
On 12.03.2013 14:17, Vivek Periaraj wrote:
> Hi Gerald,
>
> 1) Ok.
>
> 2) That's correct. You mean to say MP to be Master Problem right? RMP is the Restricted Master Problem to which we add priced columns. Or you mean MP to be the model with the all the feasible solutions we have attained so far and that includes one additional convexity constraint?
>
> A smaller version of my model has about 916,893 binary variables.
>
> 3) Got it. Thanks.
>
> Regards,
> Vivek.
>
> ----- Original Message -----
>
> From: "Gerald Gamrath" <gamrath at zib.de>
> To: "Vivek Periaraj" <vivek.periaraj at gmail.com>
> Cc: scip at zib.de
> Sent: Tuesday, March 12, 2013 4:06:36 PM
> Subject: Re: [Scip] Changing the bounds of a FIXED variable
>
> Hi Vivek,
>
> 1) Yes, that point changed a bit because the automatic deletion of
> priced variables is now implemented (see the current FAQ). However, as I
> mentioned, this is only done for variables which were created at the
> current node and are not contained in any other information like
> solutions. Thus, you still cannot just delete a variable you want to
> remove from the problem, you can instead fix it to 0 (globally or
> locally), which means that it will have no impact anymore. However, you
> cannot revert that, as you could also not revert the deletion of a
> variable, you would just need to generate it again.
>
> 2) I'm still not sure what exactly you are doing. Is the following correct?
>
> a) The original SCIP model you construct contains *all* variables, let's
> say x_i, i=1,...n. You fix most of them to 0, only some of them, say all
> i a subset i \in I, are not fixed and thus form the initial RMP.
> b) In the pricing step, you add some new variables to the RMP, say x_i,
> i \in {1,...,n} \setminus I. This means, each variables you create
> during pricing corresponds to exactly one original variable, and each
> original variable corresponds to exactly one MP variable (either already
> priced into the RMP or implicitly given by the pricer).
> c) Your pricing problem is some optimization problem, so all variables
> in the original problem represent solutions of this optimization problem.
>
> Is this how you do it? If that's the case, how many variables does your
> original problem have?
>
> 3) Concerning your other question: SCIPwill stop the pricing loop when
> your pricer did not add a new variable in one call. This means that when
> your pricer works correctly, the pricing is stopped when the current RMP
> solution is optimal for the MP. You can also stop it earlier by not
> adding a variable in a pricing call, even if there might be some
> improving ones, but you need to set the *result pointer in the REDCOST
> callback to SCIP_DIDNOTRUN in this case, so that SCIP knows that the
> current LP value is no valid dual bound. Pricing is performed at every
> node of the branch-and-bound tree in this way.
>
> Best,
> Gerald
>
> On 12.03.2013 08:54, Vivek Periaraj wrote:
>> Hi Gerald,
>>
>> 1)
>>
>> The following is from the FAQ:
>>
>> <Quote>
>> How can I delete variables?
>>
>> Currently, it is not possible to delete variables during solving. A variable can be removed from the problem by SCIPdelVar(), but it remains in the corresponding constraints. Instead of that, you should either fix the variable to zero by SCIPfixVar(), which fixes the variable globally or use SCIPchgVarUbNode() and SCIPchgVarLBNode(), which change the bounds only for the current subtree
>> </Quote>
>>
>> I am trying to delete the variables before solving.
>>
>> 2)
>>
>> Yes. I try to delete them from the problem and then price them back. I would like to retain the indices of the original problem. This helps me to compute the reduced costs correctly and also in the sub problem that I solve. I use cpx as an LP solver. I use CPLEX to solve the sub-problems so that's why I would like to keep the indices of the original problem intact.
>>
>> No. I don't do any reformulations of the read-in problem into the RMP.
>>
>> Yes. I solve sub-problems using CPLEX. This is my pricing problem.
>>
>> Currently I am doing the following:
>>
>> 1) The model is developed in GAMS. So I translate the original model into LP files and dictionary files. Which are read by the program.
>> 2) The CPLEX data structures (like rmatval/cmatval/etc) of the read-in problem are populated.
>> 3) I solve a LP model to create the initial RMP with correct bounds for a subset of variables and other variables fixed to 0.
>> 4) I create SCIP model - variables and constraints - for all the variables and constraints in the original model. (I added this step because I was not able to get the correct duals if I directly read in an LP file using SCIPreadProb(). So I am now using SCIPcreateVar(), SCIPcreateConsLinear() and SCIPaddCoefsLinear() methods).
>> 5) I fix those variables that are not part of the initial RMP in the newly created SCIP problem object.
>> 6) I activate the pricer. In the pricer, I solve the sub-problem using CPLEX.
>>
>> I have now reached until this point.
>>
>> After your suggestions, I am doing this - I let the fixed variables to be present in the model. I don't try to delete them or change their bounds. As I price new variables, I create new variable pointers and add that variable to the problem object using SCIPcreateVar() and SCIPaddCoefsLinear(). I keep track of this new variable pointers in a array that has the original model's indices. So no issues there. I think this has worked out well so far. Because my LP's are fast and I don't get errors when I use SCIPaddPricedVars(). I guess this would create more variables than necessary, but I would come back to this step at a later point to make it more efficient. This should help me to get the best of B&P framework in SCIP.
>>
>> Another question I had: In the root node relaxation, does SCIP price out as many variables as possible and then stops when no more variables can be priced?
>>
>> Regards,
>> Vivek.
>>
>>
>> ----- Original Message -----
>>
>> From: "Gerald Gamrath" <gamrath at zib.de>
>> To: "Vivek Periaraj" <vivek.periaraj at gmail.com>
>> Cc: scip at zib.de
>> Sent: Tuesday, March 12, 2013 5:06:37 AM
>> Subject: Re: [Scip] Changing the bounds of a FIXED variable
>>
>> Hi Vivek,
>>
>> 1) Which point in the FAQ do you mean? If it suggests to fix variables
>> in the context of branch-and-price, I need to check that this was
>> changed or is clarified in the current FAQ. Anyway, please look into the
>> new FAQ instead of the old one, there were a lot of new points added. I
>> guess you use SCIP 3.0?
>> 2) I'm still not really sure what you are doing. Do I understand you
>> correctly that you read in the complete problem containing all
>> variables, then remove these variables and price them back in
>> dynamically? Or do you do some kind of reformulation in order to
>> transfer the read-in problem into the RMP? If you are able to read in
>> all master problem variables, I doubt that branch-and-price really
>> helps, you should try to solve the complete MIP instead. How do you do
>> the pricing? Do you solve some subproblem or do you just iterate over
>> all possible variables? If you just want to speed up the LP solving, you
>> could set the initial flag of the variables to FALSE, which means that
>> the corresponding columns are not added to the LP at the beginning, but
>> priced in dynamically.
>> Perhaps you can explain a bit more about your application and what
>> exactly you want to do.
>>
>> Best,
>> Gerald
>>
>> On 11.03.2013 17:16, Vivek Periaraj wrote:
>>> Hi Gerald,
>>>
>>> Thanks.
>>>
>>> 1) Make sense. That's why I was unable to change them. I do this for pricing but I think that's a wrong approach.I was trying the approach suggested inhttp://scip.zib.de/doc-2.0.2/html/FAQ.html. I guess that's for earlier version and no longer applicable.
>>> 2) I want to delete variables before solving. The reason is I want to get the mapping of the variables in the RMP to be in sync with the variables in the original problem. So I first create the variables, get the variable pointers for each index for the variables of the original problem. At this point, I would like to delete those variables that are not part of the initial RMP. This way I could ensure the computations of the reduced costs and pricing of new variables to be mapped to the original problem. If I do SCIPdelVar(), it's marked for deletion but the variable data is still present in the problem. Can I achieve the same thing as what CPXdelsetcols() does in CPLEX?
>>>
>>> Regards,
>>> Vivek.
>>>
>>> ----- Original Message -----
>>>
>>> From: "Gerald Gamrath"<gamrath at zib.de>
>>> To: "Vivek Periaraj"<vivek.periaraj at gmail.com>
>>> Cc:scip at zib.de
>>> Sent: Monday, March 11, 2013 9:29:51 PM
>>> Subject: Re: [Scip] Changing the bounds of a FIXED variable
>>>
>>> Dear Vivek,
>>>
>>> 1) If a variable is fixed to some value, both bounds get changed to that
>>> value. Why do you want to change the bounds afterwards? Do you want to
>>> relax them? That is not possible during the solving process (because it
>>> would mean that all the dual bound computed so far, nodes cut off, etc.
>>> might be wrong because they were based on the fixing).
>>> 2) During solving, you also cannot just delete variables, because of
>>> similar reasons and some more (the variable might be part of a solution,
>>> SCIP might have branched on it,...). However, you can mark them to be
>>> deleted automatically during pricing and if they aged out of the LP at
>>> the node where they were created, they will automatically be deleted, if
>>> possible. Please have a look at the FAQ where this is described in more
>>> detail:http://scip.zib.de/doc/html/FAQ.shtml#Q5.11
>>>
>>> Best,
>>> Gerald
>>>
>>> On 11.03.2013 16:47, Vivek Periaraj wrote:
>>>> Hello,
>>>>
>>>> 1) Is there a way to change the bounds of a fixed variable? I fix it using SCIPfixVar() but SCIPchgVarLb() and SCIPchgVarUb() does not allow me to change the bounds.
>>>> 2) How to delete a variable from the problem object. If I do SCIPdelVar(), the variable is marked for deletion but it's not deleted from the problem object.
>>>>
>>>> Regards,
>>>> Vivek
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de
>>>> http://listserv.zib.de/mailman/listinfo/scip
More information about the Scip
mailing list