A threshold search based memetic algorithm for the disjunctively constrained knapsack problem

• URL: http://arxiv.org/abs/2101.04753v1
• Date: Tue, 12 Jan 2021 21:07:33 GMT
• Title: A threshold search based memetic algorithm for the disjunctively constrained knapsack problem
• Authors: Zequn Wei and Jin-Kao Hao
• Abstract summary: The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack. We present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions.
• Score: 21.803219880299764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while satisfying the knapsack capacity. DCKP has numerous applications and is however computationally challenging (NP-hard). In this work, we present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on two sets of 6340 benchmark instances in the literature demonstrate that the proposed algorithm is highly competitive compared to the state-of-the-art methods. In particular, we report 24 and 354 improved best-known results (new lower bounds) for Set I (100 instances) and for Set II (6240 instances), respectively. We analyze the key algorithmic components and shed lights on their roles for the performance of the algorithm. The code of our algorithm will be made publicly available.

Related papers

• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We first introduce the Combinatorial Successive Asign algorithm, which is the first algorithm that can identify the best action even when the size of the action class is exponentially large. We show that the upper bound of the probability of error of the CSA algorithm matches a lower bound up to a logarithmic factor in the exponent. We experimentally compare the algorithms with previous methods and show that our algorithm performs better.
  arXiv  Detail & Related papers  (2023-10-24T09:47:32Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• An algorithm for clustering with confidence-based must-link and cannot-link constraints [0.0]
  We introduce the PCCC (Pairwise-Confidence-Constraints-Clustering) algorithm. The PCCC algorithm iteratively assigns objects to clusters while accounting for the information provided on the pairs of objects. Unlike existing algorithms, our algorithm scales to large-scale instances with up to 60,000 objects, 100 clusters, and millions of cannot-link constraints.
  arXiv  Detail & Related papers  (2022-12-29T19:21:33Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  This is a sample problem in which we search for the optimal stratification from the set of all possible stratifications of basic strata. evaluating the cost of each solution is expensive. We compare the above multi-stage combination of algorithms with three recent algorithms and report the solution costs, evaluation times and training times.
  arXiv  Detail & Related papers  (2021-08-18T08:41:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• 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)
• Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem [26.209597575181775]
  We deal with the Budgeted Maximum Coverage Problem (BMCP) BMCP is closely related to the Set-Union Knapsack Problem (SUKP) We propose a probability learning based tabu search (PLTS) algorithm for addressing this NP-hard problem.
  arXiv  Detail & Related papers  (2020-07-12T12:11:59Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. We provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. We also propose the first algorithm for linear bandits in the the fixed budget setting.
  arXiv  Detail & Related papers  (2020-06-21T00:56:33Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.