[Scip] Pricing runs / adding variables in pricing loop / linear indexing

[Gerald Gamrath]

Dear Jan,

what do you mean exactly with linear indexing (just putting all 
variables into an array? do they need a specific order?)? My feeling 
would be that creating all variables in the beginning should be avoided. 
How do you solve your pricing problem? By iterating over all variables 
or by solving some optimization problem?

In the former case, I would recommend to create all variables in the 
beginning and add them to the constraints, but set their initial flag to 
FALSE, so that they are dynamically priced into the LP. This reduces the 
size of the LP without the need to implement anything (SCIP will just go 
over all variables and check for some with negative reduced costs).

However, if you really want to do branch-and-price, can't you just 
create variables when they should be priced in and add them to your 
local array of variables in that moment. Perhaps even at the place where 
they belong (with some variables in between not yet created)?

But coming to the cause of your problem: SCIP continues pricing if and 
only if a variable was added to the LP. SCIP does not support changing 
the coefficients of existing variables in constraints during the solving 
process (or adding variables already existing in the problem to 
constraints later). Therefore, if you really want/need to keep the 
structure of your code as it already is, I would recommend to not add 
the variables at the beginning when creating them, but only later when 
they should be priced in. Then, it is ok to add them to existing 
contraints at that moment. As you already suspected, you need to 
transform the variable first before adding it to the transformed problem 
(you can use SCIPtransformVar() or SCIPtransformVars() for that).

I don't really get your question about the lower bound. SCIP won't 
continue pricing if no variables were added, because - assuming that no 
coefficients were changed - the LP solution won't change as well. 
Normally when doing branch-and-price, the RMP value should be higher 
than the dualbound and be reduced when adding variables with reduced 
costs. In your case the behavior is different and somehow strange, 
because the variables are already in the LP, but without being in the 
constraints, they might even lead to a better LP solution than your 
complete problem. Why do you want to deactivate some variables or fix 
them to zero/change their bounds?

Best,
Gerald

> Because I need linear indexing, I create (and add*) all variables at
> the beginning. But only the start solution variables are added to the
> set partitioning and knapsack constraints.
>
> In the pricing loop, the reduced cost variables are added to the
> corresponding constraints.
>
> Unfortunately, the pricer stops after one round (because there are no
> variables added). But I know, that there is another variable, which
> should have reduced costs. Is it possible to continue pricing, even if
> the variables are already added to the problem and only the
> coefficients to the constraints are added in the pricing round?
>
>
> I want to compute the lower bound as the lp relaxation of the complete problem.
> If the lower bound is smaller than the dualbound, will the pricing
> continue, even without adding vars?
> Do I have to create another SCIP* problem for this? Is it possible to
> set some variables as initial, or to deactivate them after computation
> of the LP-Relaxation lower bound?
> In my experience, fixing variables to zero or changing the bounds
> leads to messy results in the transformed problem.
>
>
>
> (*) I tried to add the priced variables only in the pricing round, but
> I get an error:
>
> in main():
> - create all vars(f,d)
> - capture all vars
> - add only start solution vars  to the problem / constraints
> - pass vars to pricerdata via SCIPpricerAtfmActivate(...,vars,...)
> In pricer:
> - pricerData->vars = vars;
> - SCIPvarIsDeleted(pricerData->vars(f,d) gives zero
> - SCIP_ERR( SCIPaddVar(scip,pricerData->vars(f,d)), "Error adding SCIP
> variable to problem"); // gives error -9. (SCIPaddPricedVar ->  same
> error)
>
> Does the variable has to be transformed before it can be added to the
> transformed problem?
>
> Best regards
> Jan
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip