4 Presentations

• 
  01:00 PM - 01:22 PM

  Hexaly, a new kind of global optimization solver

  • Fred Gardi, presenter, Hexaly

  Hexaly Optimizer is a new kind of global optimization solver. Hexaly APIs unify modeling concepts from mixed-linear programming, nonlinear programming, and constraint programming. Its modeling interface is nonlinear and set-oriented. It also supports user-coded functions, thus enabling black-box optimization and, more particularly, simulation optimization. Under the hood, Hexaly combines various exact and heuristic optimization methods: spatial branch-and-bound, simplex methods, interior-point methods, automatic Dantzig-Wolfe reformulation, column and row generation, propagation methods, local search, population-based methods, and surrogate modeling techniques for black-box optimization. We illustrate these new modeling concepts on the seminal Traveling Salesman Problem (TSP), thus offering natural and compact modeling of the problem and performance on par with Concorde, the renowned TSP solver.

• 
  01:22 PM - 01:44 PM

  Improving Complete Anytime Beam Search for Domain-Independent Dynamic Programming

  • Yuxiao Chen, presenter, University of Toronto
  • J. Christopher Beck, University of Toronto
  • Ryo Kuroiwa, National Institute of Informatics, Japan

  Complete anytime beam search (CABS) is the current state-of-art anytime heuristic search algorithm for solving Domain-Independent Dynamic Programming (DIDP) models of combinatorial optimization problems. CABS iteratively performs beam search with the beam width doubling after each iteration. This behavior results in repeated re-expansion of the same states as each iteration typically revisits the states from previous iterations. We investigate improving CABS in two ways: (1) more intelligent methods of increasing beam width including the extreme option of switching to breadth first heuristic search (BFHS) after a strong primal solution has been found; and (2) hybridizing CABS and BFHS in a multi-threaded search with the communication of primal bounds. Our experiments show that both approaches are able to improve search performance over CABS when provided with the same computational resources.

• 
  01:44 PM - 02:06 PM

  Design and Implementation of the CODD Decision Diagram Solver

  • Laurent Michel, presenter, U. of Connecticut
  • van Hoeve Willem-Jan, Carnegie Mellon University

  This talks highlights the architecture, design and implementation choices at the heart of the CODD solver, a fast combinatorial optimization solver based on decision diagram techonology. CODD strives to achieve a balance between model elegance, conciseness, pragmatism and performance. The presentation will explore key decisions, trade-offs and issues that permeated the design process. The implementation relies on modern C++ and makes extensive use of functional programming ideas. A brief demonstration will outline the experience of a modeler tackling a problem with CODD.

• 
  02:06 PM - 02:28 PM

  Random-Key Optimizers

  • Antonio Chaves, Univ. Fed. of São Paulo
  • Mauricio Resende, presenter, Univ. of Washington

  This study introduces the Random-Key Optimizer (RKO), a flexible stochastic local search framework for combinatorial optimization problems. RKO represents solutions as random-key vectors, which are decoded into feasible solutions using problem-specific decoders. The modular framework integrates multiple metaheuristics, such as simulated annealing, iterated local search, and greedy randomized adaptive search procedures, which can operate independently or collaboratively through an elite solution pool. Implemented in C++, RKO is evaluated on three NP-hard problems: the alpha-neighborhood p-median problem, the tree of hubs location problem, and the node-capacitated graph partitioning problem. Results demonstrate its effectiveness in generating high-quality solutions, showcasing its adaptability and efficiency in tackling diverse optimization problems. This positions RKO as a powerful and versatile tool for addressing complex combinatorial problems.