[ANP11] Hybridization of column generation and approximation heuristics for large-size Covering Integer Programs

Conférence Internationale avec comité de lecture : MIC 2011 : The IX Metaheuristics International Conference, July 2011, pp.531-533, Udine, Italy,

Auteurs: L. Alfandari , A. Nagih , A. Plateau , J. Sadki

Mots clés: Approximation algorithms, Column generation, Covering integer programming

Résumé: The NP-hard Covering Integer Programming minimization problem models many real-case applications. Covering Integer Programs can appear as basic models in some applications like location problems, but also as master problems resulting from a Dantzig-wolfe decomposition in other applications like transportation problems, cutting stock problems, etc. In this work, we focus on the second category of large-size covering integer programs, for which the column generation method is generally an appropriate solving approach. However, as it provides only a lower bound of the optimal solution, it is often combined with other solving approaches to obtain integer solutions. The main contribution of this work is a hybridization of an approximation heuristic and a classical approach based on column generation. Two real-case transportation and production applications are considered. The goal is not to design the best possible method for each problem but to show the added value of hybridization of given components. Experimental results on the two practical applications show that this combination improves the classical approach on three major criteria : average CPU time, number of iterations and quality of the integer value.

Equipe: oc

Collaboration: , LIPN

BibTeX

@inproceedings {
	ANP11,
	title	=	"{Hybridization of column generation and approximation heuristics for large-size Covering Integer Programs}",
	author	=	" L. ALFANDARI and A. Nagih and A. Plateau and J. Sadki ",
	booktitle	=	"{MIC 2011 : The IX Metaheuristics International Conference}",
	year	=	2011,
	month	=	"July",
	pages	=	"531-533",
	address	=	"Udine, Italy",
}