|
 
|
[PAN13] Hybrid column generation for large-size Covering Integer Programs
Conférence Internationale avec comité de lecture : European Chapter on Combinatorial Optimization, May 2013, pp.34-35, Paris, France,Mots clés: Transportation planning, column generation, CIP approximation heuristic
Résumé:
The Column Generation approach is generally a high-performing approach to solve the linear relaxation of Covering Integer Programs (CIP).
In this communication, we propose a hybrid column generation approach for large-size CIP that runs a greedy heuristic at appropriate iterations of the column generation process to complete subsets of columns accordingly to a given coverage threshold. This heuristic is an extension of the best-known CIP approximation heuristic of Dobson to the case when explicit enumeration of the set of columns is infeasible. This extension uses fractional optimization, namely the Dinkelback's algorithm, for solving combinatorial pricing subproblems.
Numerical results on a real-case transportation planning problem show that the hybrid scheme improves the three main performance criteria of Column Generation: computational time, convergence in terms of number of iterations, and quality of integer solutions found from the last Restricted Master Program. A research paper associated to this talk is to appear in Computers and OR
Equipe:
oc
BibTeX
| @inproceedings { | |||
| PAN13, | |||
| title | = | "{Hybrid column generation for large-size Covering Integer Programs}", | |
| author | = | " A. Plateau and L. ALFANDARI and A. Nagih and J. Sadki ", | |
| booktitle | = | "{European Chapter on Combinatorial Optimization}", | |
| year | = | 2013, | |
| month | = | "May", | |
| pages | = | "34-35", | |
| address | = | "Paris, France", | |
| } | |||
