[Scip] Changing the bounds of a FIXED variable

Tue Mar 12 11:36:36 MET 2013

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 