|
|
Detailed schedule
Click on a link for more details
Show all the abstracts
Thursday 30 January:
Thursday 11:15-12:30 TA-1: COMEX - Optimization 1 Room Vesale 023 - Chair: M. Schyns
Thursday 11:15-12:30 TA-2: Software and Implementation Room Vesale 020 - Chair: M. Mezmaz
Thursday 11:15-12:30 TA-3: COMEX - Smart mobility Room Vesale 025 - Chair: A. Caris
Thursday 11:15-12:30 TA-4: Systems Room Pentagone 0A11 - Chair: P. Kunsch
Thursday 14:00-15:40 TB-1: Data Analysis 1 Room Vesale 023 - Chair: X.Siebert
Thursday 14:00-15:40 TB-2: Multiple Objectives Room Vesale 020 - Chair: Y. de Smet
Thursday 14:00-15:40 TB-3: Logistics Room Vesale 025 - Chair: D. De Wolf
Thursday 14:00-15:40 TB-4: COMEX - Applications to Economy Room Pentagone 0A11 - Chair: W. Brauers
Thursday 14:00-15:40 TB-5: Networks Room Pentagone 0A07 - Chair: B. Fortz
Thursday 16:10-17:25 TC-1: Mixed-integer nonlinear programming Room Vesale 023 - Chair: Y. Crama
Thursday 16:10-17:25 TC-2: Decision Analysis 1 Room Vesale 020 - Chair: S. Eppe
Thursday 16:10-17:25 TC-3: Routing Room Vesale 025 - Chair: K. Sörensen
Thursday 16:10-17:25 TC-4: Graphs Room Pentagone 0A11 - Chair: H. Mélot
- Number of non-equivalent colorings of a graph
Hadrien Mélot (Université de Mons, Departement d'Informatique, Faculté des Sciences) Co-authors: A. Hertz
- Price on symmetrisation and average distance
Romain Absil (UMons)
- Solving the Elementary Longest Path as a Mixed Integer Program
Quoc Trung Bui (Université catholique de Louvain ) Co-authors: Yves Deville, Pham Quang Dung Abstract: The Elementary Longest Path Problem (ELPP) consists of determining the longest path on a given graph such that every node appears at most once. The pro- blem arises in a variety of context, e.g., information retrieval, high-performance printed circuit board design, multi-robot patrolling. This problem is known to be NP-hard.
In the literature, an exact algorithm for the ELPP is proposed in [7], where a Constraint Programming model is described together with intelligent search strategies to solve ELPP to optimality. One can easily show that, by adding some artificial nodes, the ELPP and the Elementary Shortest Path (between two specified nodes) Problem (ESPP) are equivalent. Two distinct mathematical for ESPP have been proposed in [2].
In this work, we propose a branch-and-cut algorithm based on the classi- cal formulation in [2]. First, we show a transformation from the ESPP to the Asymmetric Traveling Salesman Problem (ASTP) and vice versa. Then we adapt the valid inequalities of the ASTP (the Dk inequalities, Tk inequalities, and 2- matching inequalities) for the ESPP. Simple valid inequalities called maximum outflow inequalities for the ESPP are also proposed. We additionally develop- ped a simple and efficient algorithm for the separation of sub-tour elimination constraints. If many inequalities are generated in the separation step and are all added into the model, then the size of the model increases and the computation time for the linear relaxation may become costly. We therefore propose an in- equality filter to only keep the best constraints generated in the separation step. The filter is based on the idea of classes of inequalities and on violation threshold.
In the experimental part of this work, we compare our branch-and-cut algo- rithm with two other existing algoritms, the Constraint Programming algorithm from [7], and the branch-and-cut algorithm from [2], but adapted to ESPP. The computational result shows that our branch-and-cut algorithm is faster than the one adapted from [2] and strongly outperforms the algorithm based on Constraint Programming.
Thursday 16:10-17:25 TC-5: Scheduling Room Pentagone 0A07 - Chair: S. Hanafi
Friday 9:00-10:15 FA-1: Queuing Room Vesale 023 - Chair: S. Wittevrongel
Friday 9:00-10:15 FA-2: Decision Analysis 2 Room Vesale 020 - Chair: R. Bisdorff
Friday 9:00-10:15 FA-3: COMEX - Optimization 2 Room Vesale 025 - Chair: M. Labbé
Friday 9:00-10:15 FA-4: Production Room Pentagone 0A11 - Chair: D. Tuyttens
Friday 14:00-15:40 FB-1: Data Analysis 2 Room Vesale 023 - Chair: P. Fortemps
Friday 14:00-15:40 FB-2: Heuristics Room Vesale 020 - Chair: T. Stützle
Friday 14:00-15:40 FB-3: COMEX - Transportation Room Vesale 025 - Chair: F. Spieksma
Friday 14:00-15:40 FB-4: Health Room Pentagone 0A11 - Chair: G. Vanden Berghe
|
|