The 22nd edition of the COMEX Belgian Mathematical Optimization Workshop is planned on 20th and 21st of April 2017. It will be held at le Floréal Club, avenue de Villez, 6 in La-Roche-en-Ardennes.
The invited speakers for this edition are Ivana Ljubic (Essec) and Hande Yaman (Bilkent University).
Abstracts:
Speaker: Ivana Ljubic
Title: Recent Developments on Exact Solvers for the (Prize-Collecting) Steiner Tree Problem
Abstract: In this tutorial we study the Steiner tree problem (STP) in graphs and its more general version, known as the asymmetric prize-collecting Steiner tree problem (APCSTP). Several well-known network design problems can be transformed to the APCSTP, including the Steiner tree problem (STP), prize-collecting Steiner tree problem (PCSTP), maximum-weight connected subgraph problem (MWCS), and the node-weighted Steiner tree problem (NWSTP). The 11th DIMACS Challenge in 2014 has been devoted to this class of problems and it has provided new results on the state-of-the-art of existing computational methods, but has also highlighted algorithmic ideas that have not received sufficient attention in the existing literature.
In the first part of this tutorial we will recapitulate some of the most frequently used MIP formulations for the (prize-collecting) STP, and then we will present details of our implementation which won the DIMACS challenge in many categories. Our approach is based on the idea of “thinning out” the usual models for the sake of getting a more agile framework. In particular, our model involves node variables only, which is rather appealing for the “uniform” cases where all edges have the same cost. We will also demonstrate how to build a unified solver on top of the new node-based model and the previous state-of-the-art model (defined in the space of arc and node variables). The solver relies on local branching, initialization heuristics, preprocessing and local search procedures. A filtering mechanism is applied to automatically select the best algorithmic ingredients for each instance individually.
In the second part of the talk we will focus on the more recent developments concerning an exact branch-and-bound solver for the APCSTP. The main component of our framework is a new dual ascent algorithm for the rooted APCSTP, which generalizes Wong’s dual ascent algorithm for the Steiner arborescence problem. The lower bounds and dual information obtained from the algorithm are exploited within powerful bound-based reduction tests and for guiding primal heuristics. The framework is complemented by additional alternative-based reduction tests. Extensive computational results on benchmark instances for the PCSTP, MWCS, and NWSTP indicate the framework’s effectiveness, as most instances from literature are solved to optimality within seconds, including most of the (previously unsolved) largest instances from the recent DIMACS Challenge on Steiner trees.
The latter is an open-source project (available on GitHub) which we hope will help to boost the further development of exact approaches for this challenging class of network design problems.
Speaker: Hande Yaman
Title: Exact Methods for Non-Hamiltonian Routing Problems
Abstract: The classical traveling salesman problem (TSP) seeks a Hamitonian cycle (a cycle that visits every node exactly once) of minimum cost. Even though early routing problems focus on finding Hamiltonian cycles, many routing applications also require the choice of nodes that are to be visited or the number of times a node is visited. In this talk, we present exact methods for three non-Hamiltonian routing problems; namely, the split delivery VRP, the time constrained maximal covering TSP and the VRP with roaming delivery locations. We propose an iterative approach to solve the split delivery VRP where a relaxation is tigthened at each iteration by adding new variables and constraints. For the time constrained maximal covering TSP, we give a new family of facet defining inequalities and use them in a branch-and-cut approach. Finally, we present a branch-and-price algorithm to solve the VRP with roaming delivery locations.
This is joint work with O.E. Karasan, M. Savelsbergh and G. Ozbaygin.
Registration information:
You can already register by sending an email to Julie Vandewalle <[email protected]>.
If you wish to present a 30 minutes contributed talk, please also indicate it with your registration email by giving the title of your talk.
Please also let us know if you have constraints for the meals (e.g. vegetarian).
THE DEADLINE for registration (with or without contribution) is March 20, 2017.
The registration fee is 190 euros. It includes the accomodation in a (shared) double room, and all meals for the two days. A supplement of 15 EUR will be asked for a single rooms. Due to the limited number of rooms available, PhD students are asked to share a room.