Laboratoire de Génie Informatique et d’Automatique de l’Artois


Network-flow pseudo-polynomial models

The 12 February 2013 at 14:00 Seminars room of the LGI2A, FSA, Béthune
Rita MACEDO Post-doctoral researcher Université du Minho, Portuga

Integer programming problems are a special case of the broader area of optimization or mathematical programming. From the computational complexity theory, we known that many of these problems are NP-hard, which means that they are easy to state but very hard to solve, even becoming intractable for instances that are not very small. The applicability of these problems in both theoretical issues and practical real-world situations is widespread, but despite all the recent advances in mathematical programming theory and computer technology, these problems remain very difficult to solve exactly. In this presentation, we address two of these problems, the cutting stock problem and the vehicle routing problem. Both problems have been studied for several decades by researchers and practitioners of the Operations Research field. Their interest and contribution to real-world applications in business, industry and several kinds of organizations are irrefutable. We describe new integer programming models, and a generalized algorithmic framework based on network-flow pseudo-polynomial models which has proved to be efficient when compared to other exact approaches in the literature.