Maialen Murua Etxeberria: ”Advances in Branch – and – Fix methods to solve the Hamiltonian cycle problem in manufacturing optimization”

Zuzendariak_Directores: Roberto Santana Hermida /Diego Jesus Galar Pascual.

2022_03_29, 11:00  Sala Ada Lovelace aretoa.

Abstratc:

The Hamiltonian cycle problem (HCP) consists of of finding a cycle in a given graph that passes through every single vertex exactly once, or determining that this cannot be achieved. Most approaches to solve the problem only work for undirected graphs, or those considered for directed graphs are not fully implemented and not tested for large graphs. One of the approaches to solve the HCP in directed graphs is the Branch-and-Fix (BF) method, an exact method based on linear programming that uses embedding to convert the discrete optimization of the HCP into a continuous one.

One of the limitations of linear programming based methods is that the number of constraints increases with the size of the problem. Another limitation is that they consume time exploring solution spaces that lead to infeasible solutions. To address these limitations two enhancements are applied to the BF: an early subcycle detection step and a graph simplification based on vertices of degree two. We propose a BF collapse algorithm that takes into account some of the limitations of previous HCP algorithms based on linear programming. The BF collapse algorithm is built on the BF and incorporates a number of enhancements developed throughout the dissertation. One important point to consider in the design of the algorithm is the branching rule, as the BF belongs to the family of branching algorithms. This means that the search space is recursively split into smaller spaces. The branching rules proposed in the literature are based on the results obtained from the linear problems, but exploiting more global characteristics of the BF is probably a better option. Hence, a global branching method is proposed and the performance of the method is compared to the methods reported in the literature. In many real-world problems, including manufacturing optimization problems, various criteria should be considered simultaneously, turning optimization problems into multi-objective (MO) optimization problems. Thus, we can find MO variants of well-known optimization problems, such as the TSP. The HCP has a close relationship with the TSP, but, finding cycles in a graph can be difficult depending on the number of vertices and sparsity. Essentially, it is desirable to define the MO HCP and to find an efficient method to solve it. We propose an MO HCP scenario and a heuristic method to solve it by extending the BF.