HEC Montréal, Canada, 2 - 4 mai 2011

Journées de l'optimisation 2011

HEC Montréal, Canada, 2 — 4 mai 2011

Horaire Auteurs Mon horaire

MA5 Optimisation combinatoire / Combinatorial Optimization

2 mai 2011 10h30 – 12h10

Salle: Demers Beaulne

Présidée par Raf Jans

4 présentations

  • 10h30 - 10h55

    New models for and numerical tests of the Hamiltonian p-median problem

    • Stefan Gollowitzer, prés., University of Vienna
    • Dilson Lucas Pereira, Universidade Federal de Minas Gerais
    • Adam Wojciechowski, Chalmers University of Technology

    The Hamiltonian p-median problem (HpMP) was introduced by Branco and Coelho (EJOR, 1990). It is closely related to two well-known problems, namely the Travelling Salesman problem (TSP) and the Vehicle Routing problem (VRP). The HpMP is to find exactly p node-disjoint cycles of minimum edge cost, such that each node of the graph is contained in exactly one cycle. We present three new models for the HpMP problem which differ with regard to the constraints that enforce a maximum number of cycles. We demonstrate that one of the models (SEC) is dominated by another model (PCON) with regard to the LP relaxation. Further, we introduce a class of symmetry breaking constraints. We present results regarding the quality of the lower bounds provided by the respective LP relaxations for two of the models, and provide computational results that demonstrate the computational efficiency.

  • 10h55 - 11h20

    An Exact Method with Variable Fixing for solving the Generalized Assignment Problem

    • Marius Posta, prés., Université de Montréal
    • Jacques Ferland, Université de Montreal
    • Philippe Michelon, Université d'Avignon

    Our algorithm solves the generalized assignment problem exactly by reformulating it into a sequence of decision problems.
    We solve these using a lagrangian branch-and-bound improved with variable-fixing rules which rely on lagrangian relative costs. We compute these efficiently with an existing but little-known dynamic programming algorithm.

  • 11h20 - 11h45

    Enhanced Circuit Models for the (Time-Dependent) ATSP

    • Teresa Godinho, Instituto Politécnico de Beja
    • Luis Gouveia, prés., University of Lisbon
    • Pierre Pesneau, Université de Bordeaux

    In this presentation we present a new formulation for the Time-Dependent Travelling Salesman problem. The main feature of this formulation is that it uses, for each node, a n-circuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit. The results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested, gaps that are close to zero.

  • 11h45 - 12h10

    Efficient Symmetry-Breaking Formulations for the Job Grouping Problem

    • Raf Jans, prés., HEC Montréal
    • Jacques Desrosiers, GERAD, HEC Montréal

    The Job Grouping Problem consists of assigning a set of jobs, each with a specific set of tool requirements, to machines with a limited tool capacity in order to minimize the number of machines needed. We propose and test several MIP formulations that break the symmetry between the identical machines.