4 Presentations

• 
  10:30 AM - 10:55 AM

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

  • Stefan Gollowitzer, presenter, 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.

• 
  10:55 AM - 11:20 AM

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

  • Marius Posta, presenter, 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.

• 
  11:20 AM - 11:45 AM

  Enhanced Circuit Models for the (Time-Dependent) ATSP

  • Teresa Godinho, Instituto Politécnico de Beja
  • Luis Gouveia, presenter, 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.

• 
  11:45 AM - 12:10 PM

  Efficient Symmetry-Breaking Formulations for the Job Grouping Problem

  • Raf Jans, presenter, 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.