HEC Montréal, Canada, May 2  4, 2011
2011 Optimization Days
HEC Montréal, Canada, 2 — 4 May 2011
MA5 Optimisation combinatoire / Combinatorial Optimization
May 2, 2011 10:30 AM – 12:10 PM
Location: Demers Beaulne
Chaired by Raf Jans
4 Presentations

10:30 AM  10:55 AM
New models for and numerical tests of the Hamiltonian pmedian problem
The Hamiltonian pmedian problem (HpMP) was introduced by Branco and Coelho (EJOR, 1990). It is closely related to two wellknown problems, namely the Travelling Salesman problem (TSP) and the Vehicle Routing problem (VRP). The HpMP is to find exactly p nodedisjoint 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
Our algorithm solves the generalized assignment problem exactly by reformulating it into a sequence of decision problems.
We solve these using a lagrangian branchandbound improved with variablefixing rules which rely on lagrangian relative costs. We compute these efficiently with an existing but littleknown dynamic programming algorithm. 
11:20 AM  11:45 AM
Enhanced Circuit Models for the (TimeDependent) ATSP
In this presentation we present a new formulation for the TimeDependent Travelling Salesman problem. The main feature of this formulation is that it uses, for each node, a ncircuit 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 SymmetryBreaking Formulations for the Job Grouping Problem
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.