Better Understandings and Configurations in MaxSAT Local Search Solvers via Anytime Performance Analysis

• URL: http://arxiv.org/abs/2403.06568v1
• Date: Mon, 11 Mar 2024 10:10:35 GMT
• Title: Better Understandings and Configurations in MaxSAT Local Search Solvers via Anytime Performance Analysis
• Authors: Furong Ye, Chuan Luo, Shaowei Cai
• Abstract summary: This paper demonstrates that Empirical Cumulative Distribution Functions can be used to compare MaxSAT local search solvers' anytime performance. The assessment reveals distinctions in solvers' performance and displays that the (dis)advantages of solvers adjust along different running times.
• Score: 21.834696252131405
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Though numerous solvers have been proposed for the MaxSAT problem, and the benchmark environment such as MaxSAT Evaluations provides a platform for the comparison of the state-of-the-art solvers, existing assessments were usually evaluated based on the quality, e.g., fitness, of the best-found solutions obtained within a given running time budget. However, concerning solely the final obtained solutions regarding specific time budgets may restrict us from comprehending the behavior of the solvers along the convergence process. This paper demonstrates that Empirical Cumulative Distribution Functions can be used to compare MaxSAT local search solvers' anytime performance across multiple problem instances and various time budgets. The assessment reveals distinctions in solvers' performance and displays that the (dis)advantages of solvers adjust along different running times. This work also exhibits that the quantitative and high variance assessment of anytime performance can guide machines, i.e., automatic configurators, to search for better parameter settings. Our experimental results show that the hyperparameter optimization tool, i.e., SMAC, generally achieves better parameter settings of local search when using the anytime performance as the cost function, compared to using the fitness of the best-found solutions.

Related papers

• 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)
• Controllable Prompt Tuning For Balancing Group Distributional Robustness [53.336515056479705]
  We introduce an optimization scheme to achieve good performance across groups and find a good solution for all without severely sacrificing performance on any of them. We propose Controllable Prompt Tuning (CPT), which couples our approach with prompt-tuning techniques. On spurious correlation benchmarks, our procedures achieve state-of-the-art results across both transformer and non-transformer architectures, as well as unimodal and multimodal data.
  arXiv  Detail & Related papers  (2024-03-05T06:23:55Z)
• Automatic MILP Solver Configuration By Learning Problem Similarities [1.1585113506994469]
  Mixed Linear Programs (MILP) solvers expose numerous configuration parameters to control their internal algorithms. We aim to predict configuration parameters for unseen problem instances that yield lower-cost solutions without the time overhead of searching-and-evaluating configurations. We show that instances that have similar costs using one solver configuration also have similar costs using another solver configuration in the same runtime environment.
  arXiv  Detail & Related papers  (2023-07-02T21:31:47Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• Uncertainty-Aware Search Framework for Multi-Objective Bayesian Optimization [40.40632890861706]
  We consider the problem of multi-objective (MO) blackbox optimization using expensive function evaluations. We propose a novel uncertainty-aware search framework referred to as USeMO to efficiently select the sequence of inputs for evaluation.
  arXiv  Detail & Related papers  (2022-04-12T16:50:48Z)
• 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)
• Fighting the curse of dimensionality: A machine learning approach to finding global optima [77.34726150561087]
  This paper shows how to find global optima in structural optimization problems. By exploiting certain cost functions we either obtain the global at best or obtain superior results at worst when compared to established optimization procedures.
  arXiv  Detail & Related papers  (2021-10-28T09:50:29Z)
• Cost-Efficient Online Hyperparameter Optimization [94.60924644778558]
  We propose an online HPO algorithm that reaches human expert-level performance within a single run of the experiment. Our proposed online HPO algorithm reaches human expert-level performance within a single run of the experiment, while incurring only modest computational overhead compared to regular training.
  arXiv  Detail & Related papers  (2021-01-17T04:55:30Z)
• Identifying Properties of Real-World Optimisation Problems through a Questionnaire [2.805617945875364]
  This work investigates the properties of real-world problems through a questionnaire. It enables the design of future benchmark problems that more closely resemble those found in the real world.
  arXiv  Detail & Related papers  (2020-11-11T05:09:01Z)
• Anytime Behavior of Inexact TSP Solvers and Perspectives for Automated Algorithm Selection [0.0]
  Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard optimization problems. We extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality.
  arXiv  Detail & Related papers  (2020-05-27T11:36:53Z)
• Analysis of the Performance of Algorithm Configurators for Search Heuristics with Global Mutation Operators [0.0]
  ParamRLS can efficiently identify the optimal neighbourhood size to be used by local search. We show that the simple ParamRLS-F can identify the optimal mutation rates even when using cutoff times that are considerably smaller than the expected optimisation time of the best parameter value for both problem classes.
  arXiv  Detail & Related papers  (2020-04-09T12:42:30Z)

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.