Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling

• URL: http://arxiv.org/abs/2510.05955v1
• Date: Tue, 07 Oct 2025 14:11:28 GMT
• Title: Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling
• Authors: Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Michael Perk,
• Abstract summary: We consider a class of optimization problems that are fundamental to testing in modern software systems.<n>We are able to solve the largest instances in published benchmark sets to provable optimality.
• Score: 0.8242194776558897
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a class of optimization problems that are fundamental to testing in modern configurable software systems, e.g., in automotive industries. In pairwise interaction sampling, we are given a (potentially very large) configuration space, in which each dimension corresponds to a possible Boolean feature of a software system; valid configurations are the satisfying assignments of a given propositional formula $\varphi$. The objective is to find a minimum-sized family of configurations, such that each pair of features is jointly tested at least once. Due to its relevance in Software Engineering, this problem has been studied extensively for over 20 years. In addition to new theoretical insights (we prove BH-hardness), we provide a broad spectrum of key contributions on the practical side that allow substantial progress for the practical performance. Remarkably, we are able to solve the largest instances we found in published benchmark sets (with about 500000000 feasible interactions) to provable optimality. Previous approaches were not even able to compute feasible solutions.

Related papers

• BONO-Bench: A Comprehensive Test Suite for Bi-objective Numerical Optimization with Traceable Pareto Sets [0.0]
  This paper proposes an extensive problem generation approach for bi-objective numerical optimization problems.<n>It supports configuration of test problem properties, such as the number of decision variables.<n>The general approach underlying our proposed generator is released in the Python package textttbonobench to facilitate reproducible benchmarking.
  arXiv  Detail & Related papers  (2026-01-23T18:42:20Z)
• DynaAct: Large Language Model Reasoning with Dynamic Action Spaces [58.298135359318024]
  We propose a novel framework named textscDynaAct for automatically constructing a compact action space.<n>Our approach significantly improves overall performance, while maintaining efficient inference without introducing substantial latency.
  arXiv  Detail & Related papers  (2025-11-11T09:47:13Z)
• A Constrained Multi-Fidelity Bayesian Optimization Method [2.038050035201515]
  We propose a constrained multi-fidelity Bayesian optimization (CMFBO) method with novel acquisition functions.<n>Specifically, we design efficient acquisition functions that 1) have analytically closed-form expressions; 2) are straightforward to implement; and 3) do not require feasible initial samples.<n>We demonstrate the effectiveness of our algorithms on synthetic test problems using different combinations of acquisition functions.
  arXiv  Detail & Related papers  (2025-10-13T03:45:54Z)
• DaSAThco: Data-Aware SAT Heuristics Combinations Optimization via Large Language Models [2.9789407216680286]
  We introduce DaSAThco, a framework that learns a generalizable mapping from instance features to tailored ensembles.<n>Our framework uses a Large Language Model, guided by systematically defined Problem Archetypes, to generate a diverse portfolio of specialized ensembles and subsequently learns an adaptive selection mechanism to form the final mapping.
  arXiv  Detail & Related papers  (2025-09-16T02:58:50Z)
• How Low Can We Go? Minimizing Interaction Samples for Configurable Systems [2.569213261297365]
  We present a framework for combining near-optimal solutions with provable lower bounds on the required sample size.<n>Our algorithm SampLNS can reliably find samples of smaller size than previous methods in 85% of the cases.<n>This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners.
  arXiv  Detail & Related papers  (2025-01-12T12:02:26Z)
• BEACON: A Bayesian Optimization Strategy for Novelty Search in Expensive Black-Box Systems [1.204357447396532]
  Novelty search (NS) seeks to uncover diverse system behaviors through simulations or experiments.<n>NS methods typically rely on evolutionary strategies and other meta-heuristics that require dense sampling of the input space.<n>We introduce BEACON, a sample-efficient, Bayesian optimization-inspired approach to NS that is tailored for settings where the input-to-behavior relationship is opaque and costly to evaluate.
  arXiv  Detail & Related papers  (2024-06-05T20:23:52Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• BOtied: Multi-objective Bayesian optimization with tied multivariate ranks [33.414682601242006]
  In this paper, we show a natural connection between non-dominated solutions and the extreme quantile of the joint cumulative distribution function. Motivated by this link, we propose the Pareto-compliant CDF indicator and the associated acquisition function, BOtied. Our experiments on a variety of synthetic and real-world problems demonstrate that BOtied outperforms state-of-the-art MOBO acquisition functions.
  arXiv  Detail & Related papers  (2023-06-01T04:50:06Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• Batched Data-Driven Evolutionary Multi-Objective Optimization Based on Manifold Interpolation [6.560512252982714]
  We propose a framework for implementing batched data-driven evolutionary multi-objective optimization. It is so general that any off-the-shelf evolutionary multi-objective optimization algorithms can be applied in a plug-in manner. Our proposed framework is featured with a faster convergence and a stronger resilience to various PF shapes.
  arXiv  Detail & Related papers  (2021-09-12T23:54:26Z)
• USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems [9.015720257837575]
  We consider the regression between spaces, aiming to infer high-quality optimization solutions from samples of input-solution pairs. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework. We obtain highly encouraging experimental results for several classic problems on both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-07-15T17:59:08Z)
• BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration [72.88493072196094]
  We present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a set of input-output examples. We show that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches.
  arXiv  Detail & Related papers  (2020-07-28T17:46:18Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  We investigate how large should a training set be to ensure that a parameter's average metrics performance over the training set is close to its expected, future performance. We show that if this approximation holds under the L-infinity norm, we can provide strong sample complexity bounds. We empirically evaluate our bounds in the context of integer programming, one of the most powerful tools in computer science.
  arXiv  Detail & Related papers  (2020-06-21T15:32:21Z)

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.