Journées de l'optimisation 2018
HEC Montréal, Québec, Canada, 7 — 9 mai 2018
WB10 Exact methods for combinatorial optimization
9 mai 2018 15h30 – 17h10
Salle: Sony (48)
Présidée par Claudio Contardo
4 présentations

15h30  15h55
Benders decomposition for treeofhubs location problems
In this talk, we study the TreeofHub Location Problems. First, we present relevant literature review and motivation for the problem. We present a mathematical formulation and a Benders Decomposition to solve the problem. In the second part of the talk we study the hopconstrained THLP. We reformulate the problem and present a Benders decomposition to solve the hopconstrained version of the problem. We discuss optimalityfeasibility cuts and their relation to other valid inequalities for both variations of THLP. We present experimental results assessing the performance of the proposed solution methodologies. Finally, we draw conclusions and talk about possible future research.

15h55  16h20
Binary search for partitioning graphs using kconnected subgraphs
We study the problem of partitioning a weighted graph G = (V, E, w) into p subgraphs, each of which must be kconnected. The weight of a cluster is the minimum weight of a kconnected subgraph, and the objective is to find the partition that minimizes the maximum such weight. We solve this problem using a binary search algorithm, for which the subproblems are solved by means of branchandprice. Preliminary results will be provided

16h20  16h45
A new branchpriceandcut algorithm for the pickup and delivery problem with time windows
The pickup and delivery problem with time windows aims at finding routes to satisfy a set of requests. We investigate the impact of disregarding precedence and paring relations within the routes to obtain less restrictive dominance rules in column generation algorithms. Multicommodity paths are then generated to reinforce route feasibility.

16h45  17h10
Solving the optimum communication spanning tree problem
This talk presents an exact algorithm based on Benders decomposition to solve the optimum communication spanning tree problem. It integrates a strong reformulation, combinatorial bounds, intree heuristics, fast separation algorithms, and a tailored branching rule. Computational experiments show solution time savings of up to two orders of magnitude compared to stateoftheart exact algorithms.