Search code examples
scipbranch-and-bound

SCIP using old code


I am kind of new to the SCIP. I want to use SCIP as a branch and price framework. I have coded the problem in C++ already and also have implemented the pricer or column generation as a function. In fact I have implemented the BP algorithm for the root node by linking Cplex.dll to the project and now need to code the branching tree and decided to use SCIP for this purpose. I want to know what is the fastest way I can solve my problem using SCIP and the old codes which I have? Or maybe using GCG is a better and faster way? I have read the GCG documentation but doesn't understand if I should implement the pricer myself again or not? In fact I don't understand the difference between these two (SCIP and GCG). Thanks.


Solution

  • In GCG, you do not need to implement anything yourself. It is a generic solver for branch-and-price. You have to provide the compact formulation, that is, a model which after applying a Dantzig-Wolfe reformulation leads to the master problem you are solving. The reformulation also provides a MIP-formulation of the pricing problem, so GCG can solve this as a sub-MIP for pricing. There is the possibility, however, to plug-in a pricing solver in GCG, to which the pricing MIP to be solved will be passed (with objective function corresponding to the current pricing round). The pricing solver can then solve this problem with any problem-specific algorithm and pass solutions back to GCG.

    In SCIP, on the other hand, you create the master problem you want to solve and implement a pricer which gets dual values from the LP and solves the corresponding pricing problem. This is probably very similar to what you have already.

    Additionally, if you want to do branch-and-price, you need a branching rule. GCG comes with some generic ones, in SCIP you would have to implement one yourself (since the branching decisions must be regarded within your pricing procedure).

    Overall, SCIP is a framework for branch-and-price, i.e., it provides the tree management, LP solving and updates, etc., but you need to implement some things yourself like a reader, the pricer, and the branching rules. GCG is a generic solver, so you can just plug in a compact model, which is reformulated and solved in a generic way. The reformulation is either provided by you via an input file or you can try to let GCG detect an appropriate structure. You do not need to implement anything. It already provides some nice features like primal heuristics that make use of the reformulation, an automatic management of which pricing problem is solved when, and more. On the other hand, the possibilities to extend it further, e.g., by a pricing solver and branching rules are restricted compared to SCIP, since you have to stick to the structure defined by GCG.

    I would say that using SCIP and adding your pricer is probably the easier way and more similar to what you already have (you do not need to formulate the compact model). If you already have an idea on how your branching should work, it should also not be too hard to implement within SCIP.