Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem

• URL: http://arxiv.org/abs/2007.05971v1
• Date: Sun, 12 Jul 2020 12:11:59 GMT
• Title: Probability Learning based Tabu Search for the Budgeted Maximum Coverage Problem
• Authors: Liwen Li, Zequn Wei, Jin-Kao Hao and Kun He
• Abstract summary: 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.
• Score: 26.209597575181775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Knapsack problems are classic models that can formulate a wide range of applications. In this work, we deal with the Budgeted Maximum Coverage Problem (BMCP), which is a generalized 0-1 knapsack problem. Given a set of items with nonnegative weights and a set of elements with nonnegative profits, where each item is composed of a subset of elements, BMCP aims to pack a subset of items in a capacity-constrained knapsack such that the total weight of the selected items does not exceed the knapsack capacity, and the total profit of the associated elements is maximized. Note that each element is counted once even if it is covered multiple times. BMCP is closely related to the Set-Union Knapsack Problem (SUKP) that is well studied in recent years. As the counterpart problem of SUKP, however, BMCP was introduced early in 1999 but since then it has been rarely studied, especially there is no practical algorithm proposed. By combining the reinforcement learning technique to the local search procedure, we propose a probability learning based tabu search (PLTS) algorithm for addressing this NP-hard problem. The proposed algorithm iterates through two distinct phases, namely a tabu search phase and a probability learning based perturbation phase. As there is no benchmark instances proposed in the literature, we generate 30 benchmark instances with varied properties. Experimental results demonstrate that our PLTS algorithm significantly outperforms the general CPLEX solver for solving the challenging BMCP in terms of the solution quality.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Chance-Constrained Multiple-Choice Knapsack Problem: Model, Algorithms, and Applications [38.98556852157875]
  We focus on the practical scenario of CCMCKP, where the probability distributions of random weights are unknown but only sample data is available. To solve CCMCKP, we propose a data-driven adaptive local search (DDALS) algorithm.
  arXiv  Detail & Related papers  (2023-06-26T13:35:05Z)
• Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem [18.19836641663039]
  We propose a novel algorithm combining evolutionary computation with the exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. It finds better solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances.
  arXiv  Detail & Related papers  (2022-10-08T05:11:47Z)
• Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights [15.402666674186936]
  We perform runtime analysis of a randomized search algorithm (RSA) and a basic evolutionary algorithm (EA) for the chance-constrained knapsack problem with correlated uniform weights. We show how the weight correlations and the different types of profit profiles influence the runtime behavior of both algorithms in the chance-constrained setting.
  arXiv  Detail & Related papers  (2021-02-10T23:40:01Z)
• A threshold search based memetic algorithm for the disjunctively constrained knapsack problem [21.803219880299764]
  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.
  arXiv  Detail & Related papers  (2021-01-12T21:07:33Z)
• Generalization in portfolio-based algorithm selection [97.74604695303285]
  We provide the first provable guarantees for portfolio-based algorithm selection. We show that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector.
  arXiv  Detail & Related papers  (2020-12-24T16:33:17Z)
• 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)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  This work shows that these hardness barriers do not preclude efficient reinforcement learning for rich and interesting subclasses of Partially Observable Decision Processes (POMDPs) We present a sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs, where the number of observations is larger than the number of latent states and where exploration is essential for learning, thus distinguishing our results from prior works.
  arXiv  Detail & Related papers  (2020-06-22T17:58:54Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  We consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) We establish minimax optimal convergence rates of these algorithms up to poly-log factor gaps. We further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts.
  arXiv  Detail & Related papers  (2020-06-12T05:00:44Z)
• The {0,1}-knapsack problem with qualitative levels [2.0943517417159763]
  A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors.
  arXiv  Detail & Related papers  (2020-02-12T09:00:29Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  We design and analyze CascadeBAI, an algorithm for finding the best set of $K$ items. An upper bound on the time complexity of CascadeBAI is derived by overcoming a crucial analytical challenge. We show, through the derivation of a lower bound on the time complexity, that the performance of CascadeBAI is optimal in some practical regimes.
  arXiv  Detail & Related papers  (2020-01-23T16:47:52Z)

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.