We propose a method based on search guidance structures to solve the fixed charge capacitated multicommodity network design problems. In particular, adaptative memories are used to identify meaningful fragments of solutions in order to create a target one. At each iteration, fixed costs and flows on arcs are transferred to nodes that are split consequently into categories. This information is used to update the target solution. With this approach the target solution represents the result of our learning, thus our proposed algorithm iterates by narrowing the search toward the target solution. When no more learning is observed, the target solution is dramatically modified by exploiting additional memory means (i.e. residency based memories) to reach new regions. An adaptive path relinking is then applied as a post-optimization technique to explore the solution space better.

The multicommodity capacitated fixed-charge network design problem (MCND) is a hard combinatorial optimization problem used to model a wide variety of applications in different areas such as transportation, telecommunication, production, etc. Recently, we have developed an efficient cutting-plane procedure which strengthens the usual LP relaxation. This procedure incorporates two families of cutset type inequalities, namely cover inequalities and minimum cardinality inequalities, in addition to new families of inequalities that we have developed for the single-node structure. In order to design an exact algorithm to solve the MCND, we propose a branch-and-cut algorithm (B&C) based on our cutting-plane procedure. In this talk we report on a branching rule, a fathoming rule and on a heuristic used to find a feasible solution. We also report computational results and compare them to those obtained by the B&C of the state-of-the-art CPLEX.

In this paper, we consider mixed-integer programming (MIP) formulations of a generic multi-commodity network flow problem with piecewise linear costs. The formulations we study are based on variable disaggregation techniques, which have been used for a while to derive strong MIP formulations for variants of the fixed-charge network flow problem, a special case of our generic problem.

La présentation porte sur le processus de design de réseau manufacturier et de la planification des ressources pour un manufacturier qui veut proposer une offre hautement personnalisée. Une méthode hybride constituée d’un heuristique et un modèle mathématique sera illustrée à travers d’un cas dans l’industrie du golf avec une emphase sur le niveau de service et les délais de livraison.