Méthodes de décomposition pour l'optimisation discrète

30 pagesMany practical problems are modelled by integer programs. The difficulty of their resolution lies in the characterization of the feasible domain. Face to this difficulty, the researchers directed themselves towards approximations of this domain by decomposing the problem. The decomposition generally results in the relaxation of the integrality conditions on a subset of constraints. Decomposition methods differ from the bound quality and from the resolution methods used like their complexity. We present in this report some of these methods, analyze their strong and weak points and finally, establish a synthesis showing the relation between some methods considered to be different