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

[M. Farham]

Dear SCIP users,

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.

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.

- 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.

- 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.


Thank you in advance for your time and consideration.

M Saleh F
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150825/fe774f86/attachment.html>