The Cutting Stock Problem (CSP) is usually solved by branch-and-price where the linear relaxations are solved by Column Generation (CG). The performance of CG is known to be affected by its instability features especially for large size degenerate problems. We propose a stabilized CG algorithm using k-piecewise linear stabilizing terms. A simple procedure is used to compute a good quality initial point. The algorithm is compared to other stabilization techniques on well known CSP instances.

Le problème de tournées de véhicules avec dépôts multiples (PTVDM) est un problème NP-difficile pouvant être résolu de manière exacte par un algorithme de séparation et d'évaluation progressive. La qualité de la solution initiale de l'arbre de branchement peut permettre de raccourcir les temps de calcul du problème à résoudre. Nous présenterons deux méthodes heuristiques qui visent l'obtention d'une solution initiale de grande qualité pour permettre de diminuer les temps de résolution du PTVDM. La première se base sur une affectation tâche-dépôt et la seconde s'appuie sur un principe de "cluster-first, route-second". Des résultats numériques seront présentés.

The shortest path problem with resource constraints consists in finding a path from an origin point to a destination point in an acyclic graph at minimum cost while respecting constraints on the use of resources. The complexity of a dynamic programming type of algorithm increases with the number of resources. A first heuristic currently used to rapidly produce feasible solutions consists in using dominance only on a subset of resources. Nagih and Soumis (2005) propose an improvement of this heuristic through aggregation of resources at each node of the graph by projecting on a vector of smaller dimension and the use of a Lagrangian relaxation algorithm to determine the coefficients of the projection. This talk critically evaluates the method described by Nagih and Soumis by proving that the selection method of the multipliers of the projection at the nodes does not give as good results as the heuristic that it proposes to improve, and that it is sensitive to random parameters. Moreover, we explain why the results obtained are very unstable.