3 présentations

• 
  13h00 - 13h22

  Accelerated Local Search Heuristics for the Quadratic Assignment Problem with In-Memory Computing Hardware

  • Haesol Im, prés., 1QBit
  • Chan Woo Yang, 1QBit
  • Moslem Noori, 1QBit
  • Elisabetta Valiante, 1QBit
  • Arne Heittmann, Peter Grunberg Institute, Forschungszentrum Juelich
  • Thomas Van Vaerenbergh, Hewlett Packard Labs
  • Dmitri Strukov, University of California, Santa Barbara
  • Ignacio Rozada, 1QBit

  In-memory computing (IMC) devices, such as memristor-based analog Ising machines, offer significant speedups and efficiency gains over traditional CPU-based solvers, particularly for solving combinatorial optimization problems. However, they face challenges with constrained problems like the quadratic assignment problem (QAP), where mapping to binary formulations like quadratic unconstrained binary optimization introduces overhead and limits parallelism.
  In this work, we present a novel local search heuristic designed for IMC hardware to tackle the QAP. Our approach enables massive parallelism that allows for computing of the full neighbourhoods simultaneously to make update decisions. We ensure binary solutions remain feasible by selecting local moves that lead to neighbouring feasible solutions, leveraging feasible-space search heuristics and a problem’s underlying structure. We demonstrate the effectiveness of our approach for both digital and analog-compatible CPU implementations by comparing it with state-of-the-art heuristics for solving the QAP.

• 
  13h22 - 13h44

  An Analytic Centre Approach to Inverse Mixed Integer Optimization

  • Göksu Ece Okur, prés., University of Waterloo
  • Samir Elhedhli, University of Waterloo

  We propose an innovative solution approach for inverse mixed integer optimization that is inspired by interior-point methods. Since mixed integer solutions are typically interior, we utilize weighted analytic center concepts from interior-point methods and provide structural results and models that can efficiently solve large problems. We first demonstrate that the optimality of a given solution can be characterized by identifying a linear programming solution that is optimal with respect to a cost vector. We then quantify the optimality gap and minimize it to render the observed solution near-optimal. Computational testing demonstrates the efficiency of the proposed approach in finding good solutions in quick computational times.

• 
  13h44 - 14h06

  Serial and Parallel Two-Column Probing for Mixed-Integer Programming

  • Yongzheng Dai, prés., The Ohio State University

  Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branchand-cut solvers. Such fixing is typically performed one variable at a time— this paper develops instead a two-column probing scheme that instead f ixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings; computational experiments demonstrate its promise.