Information about the Workpackages

Extending exact methods to matheuristics
  • 1A) The use of matheuristics can significantly improve the performance of exact methods by finding better primal and dual bounds earlier and thereby closing the optimality gap faster.
  • 1B) Coordination mechanisms from decomposition techniques and exact methods can be used to design matheuristics that find good primal solutions and strong dual bounds faster.
Work package 2: Extending metaheuristics to matheuristics
  • 2A) The use of MP techniques can significantly improve the performance of metaheuristics, mainly by finding very good primal bounds at late stages of the search, but not by improving the search in the early phases.
  • 2B) By solving a dual problem heuristically with a matheuristic, using a separate thread, metaheuristics may be turned into competitive exact methods that scale well in terms of finding primal solutions.
Work package 3: Cooperative search and heterogeneous computing in matheuristics
  • 3A) Cooperative search is a natural and effective strategy for implementing matheuristics.
  • 3B) Parallel and heterogeneous computing combining task and data parallelism, with the modern commodity PC as the main target hardware architecture, can significantly speed up matheuristics, allowing a method to find better solutions and close the optimality gap using less wall clock time.
  • 3C) It is possible to develop self-adaptable matheuristics algorithms that automatically distribute tasks and balance the load on the computational resources at hand, and hence facilitate automatic scaling with future hardware performance enhancements.
Work package 4: Development of explanatory models
  • 4A) Using all experimental results from WP1-WP3, a meta-model can be formulated and used to analyze the relative merit of the different ideas for matheuristics.
  • 4B) The meta-model can be used as a predictive tool for the potential of improvement from specific matheuristic ideas, based on problem properties and current search behavior.