[SCIP] Adding constraints to the master problem in a branch-and-price algorithm

[Gerald Gamrath]

Dear M Saleh F,

> I am trying to implement a BP algorithm on a VRP. The master problem 
> contains two sets of constraints, say set A and set B. Initially, set 
> B is empty. I solve the SP using the dual values corresponding to sets 
> A and B (B is empty in the beginning) and obtain a column with a 
> negative reduced cost (say x). Then, I add the priced variable to the 
> MP and solve the RMP. If x gets a value in the RMP (i.e. 0 < x <= 1) 
> and has a certain characteristic, I will add a valid inequality for x 
> to the set B (the valid inequality is a set covering constraint called 
> b). At this step, I also want to remove all other columns that do not 
> respect b from the MP. Then, I solve SP using new dual variables to 
> price a new column. This procedure continues until no more columns 
> with negative rc can be generated. At the end the MP contains set A 
> and set B constraints. Set B may be still empty or may have several 
> constraints depending on the procedure explained above.

can you give a few more details on the type of inequalities you are 
generating? You said you will add a valid inequality on x, but x is just 
one variable, with coefficient 0 or 1 in the set covering constraint. Do 
you add a set covering constraint saying that one variable of a specific 
set must be selected, implying that all variables not in that set are 
set to 0? If other variables are forbidden by this, why didn't you need 
to forbid them before? You could just fix all those variables to 0 yourself.


> I am kind of new to SCIP, so I appreciate your help on the following 
> issues.
>
> - The stage in the ObjPricer that I can read the value of the added 
> columns in the last pricing iteration from the solution of the current 
> RMP.
>
I'm not sure I understand what you mean. You can get the value of a 
variable by SCIPgetSolVal(), just give NULL as sol for the current LP 
solution. If you want to do this in the pricer, you should do it in the 
scip_redcost method.

> - Adding a constraint to the current MP (and before the problem is 
> transformed, maybe?) and use the new dual variable in the following 
> run of pricer.
>
The problem is transformed before the solving process starts, so all you 
do is after transformation. If you want to add a constraint related to 
you priced-in variable, I would suggest you do it right when you add the 
variable. Since this variable has negative reduced cost, it will 
probably be nonzero in the next LP solution anyway.

If you don't want to add it right then, you will need to write a 
constraint handler for this, since a pricer's task is to add variable 
and not constraints (this may only be done together with adding the 
priced variable, if needed). This constraint handler should add the set 
B constraints in its sepalp and enfolp callbacks.

> - Checking all columns in the pool and delete those that do not 
> satisfy the new constraint at their upper bound (i.e. 1). Note that if 
> these variables are not deleted, they will be 0 in the final solution. 
> But by deleting them, I prevent the MP from getting too large.
>
Due to internal data structures, it is not allowed to explicitly delete 
variables in SCIP. You may mark them as deletable and SCIP may delete 
them automatically if they are not needed anymore. You can make this 
happen more often by setting lp/cleanupcols(root) to TRUE and decreasing 
the lp/colagelimit.

Best,
Gerald