Files
Verhaeghe_81151000_2015.pdf
Open access - Adobe PDF
- 1.61 MB
Details
- Supervisors
- Faculty
- Degree label
- Abstract
- Constraint programming is a well known way to solve complex problems and especially problems that can be modelled as an aggregation of multiple complex sub-problems. The branch \& bound based solving methods is helped by powerful propagation procedure, helping at the reducing of the domains of the variable at each node of the search tree. The solver OscaR implements different classes for each different types of constraint, each having a specific propagator. The development of an effective OscaR constraint for the sub-problem of the \mincircuit (minimal Hamiltonian tour in a graph) requires effective bounding procedures. Based on mathematical models, two main iterative methods have been analysed. Both rely on Lagrangian relaxation of the mathematical representation of the Travelling Salesman Problem. The first considers the symmetric version of the TSP applied to a symmetric equivalent transformation of the asymmetric graph. The second is based on a transposition of the initial symmetric method to asymmetric concepts directly. The results say that from a strict theoretical point of view, both methods are equivalent and give the same result as the linear relaxation (relaxation unpractical due to a number of constraint growing in a factorial way with respect to the number of vertexes involved). But in practice, due to the instability of the iterative method caused by the step size, the asymmetric based method gives better results for a fixed given number of iterations. Concerning the time of execution of both methods, as the symmetric version is based on a greedy quick optimised algorithm, it takes less time to compute the wanted amount of iteration.