Originally posted by: SystemAdmin

[anujiitm2004@gmail.com said:]

Hey folks,

I am trying to solve set-covering problem in branch and price method.  so some of my questions are:

1. Is there any  branching scheme for the set-covering problem?

2. Will Ryan-Foster scheme work for the set-covering problem?

3. Is there any  branching scheme available in CPLEX 11.2 for the set-covering problem?

Your help will be greatly appreciated.

Thanks,
Anuj
IIT MADRAS
INDIA
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[jgregory said:]

There is not an implementation of Ryan-Foster in CPLEX. 

A tactic said to be helpful at times on set covering (partitioning, packing) problems is to set the parameter MIPOrdType to 3, which directs CPLEX to branch based on the ratio, for each variable, of the objective coefficient to the non-zero count in the constraint matrix.

For set covering, if poor-quality solutions are easy to find but nothing close to the eventually-optimal feasible solution is found early in the search, you could additionally try invoking the RINS algorithm with the RINSHeur parameter, although too aggressive a RINS setting (e.g. every node) will cost more time than it saves.
#CPLEXOptimizers
#DecisionOptimization