joint work with Rachida Abounacer, Mohamed Hachimi
We propose an algorithm that has been improved from the classical Clarke and Wright algorithm to solve the Capacitated vehicle routing problem.The main concept of our proposed algorithm is to combine the Clarke and Wright heuristic with Sweep heuristic inspired of transition of probabilities used in Ant Colony algorithm to construct a solution.The objective is to seek a set minimum total cost routes for a fleet of k identical vehicle with capacity D to serve n customers form a depot .Our results shows that our approach provides shorter distances in the majority of well-know instances.
joint work with Borut Lužar, Janez Povh
We present a method for solving stable set problem to optimality that combines techniques from semidefinite optimization and efficient implementation using high-performance computing. We use parallel branch & bound algorithm that applies Lovász theta function and its strengthenings as upper bound to approximate original problem using semidefinite relaxation. Depending on the sparsity of the graph combination of two SDP solvers is used to compute solutions of the obtained relaxations. We will present numerical experience with the proposed algorithm and show scalability and efficiency of it.
joint work with Immanuel Bomze, Lucas Létocart, Francesco Rinaldi, Emiliano Traversi
We propose an algorithm for binary non-convex quadratically constrained quadratic problems. In the extended formulation with the matrix X, product of the original variables, we propose a Dantzig-Wolfe-reformulation-based method with a linear master and a pricing of Max-Cut-type. The domain of this relaxation lies in the cone of Completely Positive matrices. For block-decomposable problems, we present an adaptation of our algorithm which exploits the block structure. We give conditions under which we obtain the same bound as the previous relaxation. We also provide computational results.