10h30 - 10h55
New models for and numerical tests of the Hamiltonian p-median problem
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
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
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
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.