11h00 - 11h25
Solving the Clique Partitioning Problem as a Maximally Diverse Grouping Problem
We show that the Clique Partitioning Problem can be reformulated as the Maximally Diverse Grouping Problem(MDGP). We then modify a skewed general variable neighborhood search heuristic that was first developed to solve the MDGP. As
with the MDGP, the new heuristic achieves a significant improvement over the state of the art.
11h25 - 11h50
A New Variant of the Assignment Problem: Application, NP-Hardness and Algorithms
The paper proposes a new variant of the classical assignment problem which arises in important applications such as health care and inventory management. A proof of its NP-hardness is discussed. Furthermore, an emerging solution technique of Artificial Intelligence and Cohort Intelligence is applied to efficiently solve the problem. The results are compared to solutions obtained by CPLEX.
11h50 - 12h15
Finding Totally Independent Spanning Trees with Integer Programming
Two spanning trees of an undirected graph are totally independent if they are edge disjoint and if the unique paths that connect any pair of vertices in these trees are also node disjoint. Accordingly, K spanning trees are totally independent if they are pairwise totally independent. The problem of finding K totally independent spanning trees (KTIST) or proving that no such trees do exist is NP-Complete. We investigate KTIST and two optimization problems derived from it. One of them consists in
finding the maximum K such that G has K totally independent trees. The other consists of finding K totally independent spanning trees with the minimum possible number of central nodes. We discuss integer programming formulations, valid inequalities and and exact solution approaches, Branch-and-cut and Branch-and-price algorithms, to solve them.
12h15 - 12h40
A Multi-Coloring Problem with Constrained Color Class Sizes
We consider an extension of the graph coloring problem with application in scheduling. Each vertex must be given multiple different colors, and bounds on the size of each color class must be respected. Two different tabu search approaches (relying on different search spaces) are proposed and compared.