4 Presentations

• 
  11:00 AM - 11:25 AM

  Solving the Clique Partitioning Problem as a Maximally Diverse Grouping Problem

  • Jack Brimberg, presenter, GERAD, The Royal Military College of Canada
  • Nenad Mladenovic, Mathematical Institute SANU
  • Dragan Urosevic, Mathematical Institute SANU

  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.

• 
  11:25 AM - 11:50 AM

  A New Variant of the Assignment Problem: Application, NP-Hardness and Algorithms

  • Anand Kulkarni, presenter, University of Windsor
  • Fazle Baki, University of Windsor
  • Ben Chaouch, University of Windsor

  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.

• 
  11:50 AM - 12:15 PM

  Finding Totally Independent Spanning Trees with Integer Programming

  • Alexandre Cunha, presenter, Universidade Federal de Minas Gerais

  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.

• 
  12:15 PM - 12:40 PM

  A Multi-Coloring Problem with Constrained Color Class Sizes

  • Simon Thevenin, presenter, University of Geneva
  • Nicolas Zufferey, University of Geneva
  • Jean-Yves Potvin, Université de Montréal

  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.