Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem

• URL: http://arxiv.org/abs/2405.18772v1
• Date: Wed, 29 May 2024 05:22:31 GMT
• Title: Evolving Reliable Differentiating Constraints for the Chance-constrained Maximum Coverage Problem
• Authors: Saba Sadeghi Ahouei, Jacob de Nobel, Aneta Neumann, Thomas Bäck, Frank Neumann,
• Abstract summary: We study the classical maximum coverage problem in graphs with chance constraints. Our goal is to evolve reliable chance constraint settings for a given graph where the performance of algorithms differs significantly. We develop an evolutionary algorithm that provides sets of chance constraints that differentiate the performance of two search algorithms with high confidence.
• Score: 8.98161858972433
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Chance-constrained problems involve stochastic components in the constraints which can be violated with a small probability. We investigate the impact of different types of chance constraints on the performance of iterative search algorithms and study the classical maximum coverage problem in graphs with chance constraints. Our goal is to evolve reliable chance constraint settings for a given graph where the performance of algorithms differs significantly not just in expectation but with high confidence. This allows to better learn and understand how different types of algorithms can deal with different types of constraint settings and supports automatic algorithm selection. We develop an evolutionary algorithm that provides sets of chance constraints that differentiate the performance of two stochastic search algorithms with high confidence. We initially use traditional approximation ratio as the fitness function of (1+1)~EA to evolve instances, which shows inadequacy to generate reliable instances. To address this issue, we introduce a new measure to calculate the performance difference for two algorithms, which considers variances of performance ratios. Our experiments show that our approach is highly successful in solving the instability issue of the performance ratios and leads to evolving reliable sets of chance constraints with significantly different performance for various types of algorithms.

Related papers

• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
  This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem. Inspired by the success of point-based methods developed for discounted problems, we study their extensions to MRPP. We present a novel algorithm that leverages the strengths of these techniques for efficient exploration of the belief space.
  arXiv  Detail & Related papers  (2024-06-05T02:33:50Z)
• Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selection [25.29451529910051]
  We propose the first provable guarantee for algorithm selection based on algorithm features. We analyze the benefits and costs associated with algorithm features and investigate how the generalization error is affected by different factors.
  arXiv  Detail & Related papers  (2024-05-18T17:38:25Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Provably Efficient Learning in Partially Observable Contextual Bandit [4.910658441596583]
  We show how causal bounds can be applied to improving classical bandit algorithms. This research has the potential to enhance the performance of contextual bandit agents in real-world applications.
  arXiv  Detail & Related papers  (2023-08-07T13:24:50Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  We exploit between first-order algorithms for constrained optimization and non-smooth systems to design a new class of accelerated first-order algorithms. An important property of these algorithms is that constraints are expressed in terms of velocities instead of sparse variables.
  arXiv  Detail & Related papers  (2023-02-01T08:50:48Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  Chemotherapy treatment for cancer is a complex optimisation problem with a large number of interacting variables and constraints. We show that the more sophisticated algorithm would yield better performance on a complex problem like this. We hypothesise that this is caused by the more sophisticated algorithm being impeded by the large number of interactions in the problem.
  arXiv  Detail & Related papers  (2022-05-17T15:28:46Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  Various algorithms for reinforcement learning (RL) exhibit dramatic variation in their convergence rates as a function of problem structure. This research provides guarantees that explain textitex post the performance differences observed. A natural next step is to convert these theoretical guarantees into guidelines that are useful in practice.
  arXiv  Detail & Related papers  (2022-01-21T04:25:35Z)
• Generating Instances with Performance Differences for More Than Just Two Algorithms [2.061388741385401]
  We propose fitness-functions to evolve instances that show large performance differences for more than just two algorithms simultaneously. As a proof-of-principle, we evolve instances of the multi-component Traveling Thief Problem(TTP) for three incomplete TTP-solvers.
  arXiv  Detail & Related papers  (2021-04-29T11:48:41Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  We study the fundamental online $k$-server problem in a learning-augmented setting. We show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff.
  arXiv  Detail & Related papers  (2021-03-02T11:04:33Z)
• Heuristic Strategies for Solving Complex Interacting Stockpile Blending Problem with Chance Constraints [14.352521012951865]
  In this paper, we consider the uncertainty in material grades and introduce chance constraints that are used to ensure the constraints with high confidence. To address the stockpile blending problem with chance constraints, we propose a differential evolution algorithm combining two repair operators.
  arXiv  Detail & Related papers  (2021-02-10T07:56:18Z)
• Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
  We give efficient differentially private algorithms for basic clustering problems. Our results imply an improved algorithm for the Sample and Aggregate privacy framework. One of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
  arXiv  Detail & Related papers  (2020-08-18T16:22:06Z)

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.