HEC Montréal, Canada, 2  4 mai 2011
Journées de l'optimisation 2011
HEC Montréal, Canada, 2 — 4 mai 2011
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 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.

10h55  11h20
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. 
11h20  11h45
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.

11h45  12h10
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.