Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach

• URL: http://arxiv.org/abs/2508.07015v1
• Date: Sat, 09 Aug 2025 15:27:36 GMT
• Title: Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach
• Authors: Hannes Ihalainen, Dieter Vandesande, André Schidler, Jeremias Berg, Bart Bogaerts, Matti Järvisalo,
• Abstract summary: The implicit hitting set (IHS) approach offers a general framework for solving computationally hard optimization problems.<n>We explore alternative algorithmic techniques for hitting set optimization based on different ways of employing pseudo-Boolean (PB) reasoning.<n>We show that exact HS computations instantiated via PB reasoning can be made competitive with a numerically exact IP solver.
• Score: 11.039737232955039
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The implicit hitting set (IHS) approach offers a general framework for solving computationally hard combinatorial optimization problems declaratively. IHS iterates between a decision oracle used for extracting sources of inconsistency and an optimizer for computing so-called hitting sets (HSs) over the accumulated sources of inconsistency. While the decision oracle is language-specific, the optimizers is usually instantiated through integer programming. We explore alternative algorithmic techniques for hitting set optimization based on different ways of employing pseudo-Boolean (PB) reasoning as well as stochastic local search. We extensively evaluate the practical feasibility of the alternatives in particular in the context of pseudo-Boolean (0-1 IP) optimization as one of the most recent instantiations of IHS. Highlighting a trade-off between efficiency and reliability, while a commercial IP solver turns out to remain the most effective way to instantiate HS computations, it can cause correctness issues due to numerical instability; in fact, we show that exact HS computations instantiated via PB reasoning can be made competitive with a numerically exact IP solver. Furthermore, the use of PB reasoning as a basis for HS computations allows for obtaining certificates for the correctness of IHS computations, generally applicable to any IHS instantiation in which reasoning in the declarative language at hand can be captured in the PB-based proof format we employ.

Related papers

• Unlocking Symbol-Level Precoding Efficiency Through Tensor Equivariant Neural Network [84.22115118596741]
  We propose an end-to-end deep learning (DL) framework with low inference complexity for symbol-level precoding.<n>We show that the proposed framework captures substantial performance gains of optimal SLP, while achieving an approximately 80-times speedup over conventional methods.
  arXiv  Detail & Related papers  (2025-10-02T15:15:50Z)
• Variables Ordering Optimization in Boolean Characteristic Set Method Using Simulated Annealing and Machine Learning-based Time Prediction [1.654967376694554]
  This paper introduces a novel framework that integrates machine learning (ML)-based time prediction with simulated annealing (SA)<n>We train an accurate ML predictor ft(X) to estimate solving time for any given variables ordering.<n>Experiments demonstrate that our method substantially outperforms the standard BCS algorithm.
  arXiv  Detail & Related papers  (2025-09-18T09:02:32Z)
• Bayesian Optimization by Kernel Regression and Density-based Exploration [15.763320101917074]
  kernels regression and density-based Exploration (BOKE) algorithm.<n>BOKE uses kernel regression for efficient function approximation, kernel density for exploration, and integrates them into the confidence bound criteria to guide the optimization process.<n>We demonstrate that BOKE not only performs competitively compared to Gaussian process-based methods and several other baseline methods but also exhibits superior computational efficiency.
  arXiv  Detail & Related papers  (2025-02-10T06:16:51Z)
• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  This paper reveals a unified game-theoretic connection between iterative BOND and self-play alignment.<n>We establish a novel framework, WIN rate Dominance (WIND), with a series of efficient algorithms for regularized win rate dominance optimization.
  arXiv  Detail & Related papers  (2024-10-28T04:47:39Z)
• LLaMA-Berry: Pairwise Optimization for O1-like Olympiad-Level Mathematical Reasoning [56.273799410256075]
  The framework combines Monte Carlo Tree Search (MCTS) with iterative Self-Refine to optimize the reasoning path. The framework has been tested on general and advanced benchmarks, showing superior performance in terms of search efficiency and problem-solving capability.
  arXiv  Detail & Related papers  (2024-10-03T18:12:29Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Robust expected improvement for Bayesian optimization [1.8130068086063336]
  We propose a surrogate modeling and active learning technique called robust expected improvement (REI) that ports adversarial methodology into the BO/GP framework. We illustrate and draw comparisons to several competitors on benchmark synthetic exercises and real problems of varying complexity.
  arXiv  Detail & Related papers  (2023-02-16T22:34:28Z)
• Best Arm Identification in Stochastic Bandits: Beyond $\beta-$optimality [31.359578768463752]
  This paper investigates a hitherto unaddressed aspect of best arm identification (BAI) in multi-armed bandits in the fixed-confidence setting. Two key metrics for assessing bandit algorithms are computational efficiency and performance optimality. This paper introduces a framework and an algorithm for BAI that achieves optimal performance with a computationally efficient set of decision rules.
  arXiv  Detail & Related papers  (2023-01-10T05:02:49Z)
• Enhancing Explainability of Hyperparameter Optimization via Bayesian Algorithm Execution [13.037647287689438]
  We study the combination of HPO with interpretable machine learning (IML) methods such as partial dependence plots. We propose a modified HPO method which efficiently searches for optimum global predictive performance. Our method returns more reliable explanations of the underlying black-box without a loss of optimization performance.
  arXiv  Detail & Related papers  (2022-06-11T07:12:04Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  We propose a bilevel optimization method based on Bregman Bregman functions. We also propose an accelerated version of SBiO-BreD method (ASBiO-BreD) by using the variance-reduced technique.
  arXiv  Detail & Related papers  (2021-07-26T16:18:43Z)
• Parallel Scheduling Self-attention Mechanism: Generalization and Optimization [0.76146285961466]
  We propose a general scheduling algorithm, which is derived from the optimum scheduling for small instances solved by a satisfiability checking(SAT) solver. Strategies for further optimization on skipping redundant computations are put forward as well, with which reductions of almost 25% and 50% of the original computations are respectively achieved. The proposed algorithms are applicable regardless of problem sizes, as long as the number of input vectors is divisible to the number of computing units available in the architecture.
  arXiv  Detail & Related papers  (2020-12-02T12:04:16Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.