Log in

Relevant bibliographies by topics / Knapsack

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'Knapsack'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 June 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Knapsack.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Knapsack"

1

Malitsky, Yuri, Meinolf Sellmann, and Radoslaw Szymanek. "Filtering Bounded Knapsack Constraints in Expected Sublinear Time." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (July 3, 2010): 141–46. http://dx.doi.org/10.1609/aaai.v24i1.7560.

Full text

Abstract:

We present a highly efficient incremental algorithm for propagating bounded knapsack constraints. Our algorithm is based on the sublinear filtering algorithm for binary knapsack constraints by Katriel et al. and achieves similar speed-ups of one to two orders of magnitude when compared with its linear-time counterpart. We also show that the representation of bounded knapsacks as binary knapsacks leads to ineffective filtering behavior. Experiments on standard knapsack benchmarks show that the new algorithm significantly outperforms existing methods for handling bounded knapsack constraints.

APA, Harvard, Vancouver, ISO, and other styles

2

Osipyan, V. O., A. S. Zhuk, E. P. Lukashchik, K. I. Litvinov, and R. Kh Bagdasaryan. "Multiplicative knapsack injectivity as condition of effective unauthorized access protection." Journal of Physics: Conference Series 2131, no. 2 (December 1, 2021): 022084. http://dx.doi.org/10.1088/1742-6596/2131/2/022084.

Full text

Abstract:

Abstract The mathematical modelling of data protection systems based on multiplicative knapsack is considered. In particular, development of cryptographic solution to hierarchic access control problem is represented. Previously in research the authors has formulated the requirements to knapsack in order to apply these to a hierarchic access control problem based on the requirements for similar models. Here in the article the possibility of practical implementation of the construction of such knapsacks is pointed. Based on special mathematical model for multiplicative knapsacks generalized sufficient condition of multiplicative knapsack injectivity is formulated and proved in the article. Known sufficient conditions of multiplicative knapsack injectivity are special cases of authors condition. The mathematical apparatus of additive knapsacks for building multiplicative vector is shown.

APA, Harvard, Vancouver, ISO, and other styles

3

Sur, Giwon, Shun Yuel Ryu, JongWon Kim, and Hyuk Lim. "A Deep Reinforcement Learning-Based Scheme for Solving Multiple Knapsack Problems." Applied Sciences 12, no. 6 (March 17, 2022): 3068. http://dx.doi.org/10.3390/app12063068.

Full text

Abstract:

A knapsack problem is to select a set of items that maximizes the total profit of selected items while keeping the total weight of the selected items no less than the capacity of the knapsack. As a generalized form with multiple knapsacks, the multi-knapsack problem (MKP) is to select a disjointed set of items for each knapsack. To solve MKP, we propose a deep reinforcement learning (DRL) based approach, which takes as input the available capacities of knapsacks, total profits and weights of selected items, and normalized profits and weights of unselected items and determines the next item to be mapped to the knapsack with the largest available capacity. To expedite the learning process, we adopt the Asynchronous Advantage Actor-Critic (A3C) for the policy model. The experimental results indicate that the proposed method outperforms the random and greedy methods and achieves comparable performance to an optimal policy in terms of the profit ratio of the selected items to the total profit sum, particularly when the profits and weights of items have a non-linear relationship such as quadratic forms.

APA, Harvard, Vancouver, ISO, and other styles

4

Devita, Riri Nada, and Aji Prasetya Wibawa. "Teknik-teknik Optimasi Knapsack Problem." Sains, Aplikasi, Komputasi dan Teknologi Informasi 2, no. 1 (April 5, 2020): 35. http://dx.doi.org/10.30872/jsakti.v2i1.3299.

Full text

Abstract:

Optimasi merupakan sebuah teknik yang identik dengan memaksimalkan sumber daya yang terbatas. Salah satunya adalah permasalahan nyata yang memperlukan teknik optimasi adalah cara mengatur barang-barang yang dimuat dalam suatu knapsack (karung/ Tas). Knapsack problem merupakan masalah dimana orang dihadapkan pada persoalan optimasi pemilihan benda yang dapat di tampung ke dalam sebuah knapsack (karung) yang memiliki keterbatasan daya dan ruang tampung. Oleh karena itu, dengan adanya optimasi dalam pemilihan barang yang akan ditampung dalam knapsak tersebut diharapkan dapat menghasilkan efisiensi yang maksimal. Oleh karena itu, paper ini bertujuan untuk mendiskusikan beberapa algoritma optimasi yang sesuai untuk masalah knapsack. Hasil dari studi ini menunjukkan bahwa algoritma Dynamic Programming adalah algoritma yang paling sesuai dalam penyelesaian masalah knapsack karena menghasilkan solusi yang optimum dan waktu running yang tidak lama.

APA, Harvard, Vancouver, ISO, and other styles

5

Sun, Bo, Ali Zeynali, Tongxin Li, Mohammad Hajiesmaili, Adam Wierman, and Danny H. K. Tsang. "Competitive Algorithms for the Online Multiple Knapsack Problem with Application to Electric Vehicle Charging." ACM SIGMETRICS Performance Evaluation Review 49, no. 1 (June 22, 2022): 67–68. http://dx.doi.org/10.1145/3543516.3456271.

Full text

Abstract:

We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, in the full version of this paper, we illustrate the proposed algorithm via trace-based experiments of EV charging.

APA, Harvard, Vancouver, ISO, and other styles

6

Chen, Kai, and Sheldon M. Ross. "STATIC STOCHASTIC KNAPSACK PROBLEMS." Probability in the Engineering and Informational Sciences 29, no. 4 (October 2015): 527–46. http://dx.doi.org/10.1017/s0269964815000170.

Full text

Abstract:

Two stochastic knapsack problem (SKP) models are considered: the static broken knapsack problem (BKP) and the SKP with simple recourse and penalty cost problem. For both models, we assume: the knapsack has a constant capacity; there are n types of items and each type has an infinite supply; a type i item has a deterministic reward vi and a random weight with known distribution Fi. Both models have the same objective to maximize expected total return by finding the optimal combination of items, that is, quantities of items of each type to be put in knapsack. The difference between the two models is: if knapsack is broken when total weights of items put in knapsack exceed the knapsack's capacity, for the static BKP model, all existing rewards would be wiped out, while for the latter model, we could still keep the existing rewards in knapsack but have to pay a fixed penalty plus a variant cost proportional to the overcapacity amount. This paper also discusses the special case when knapsack has an exponentially distributed capacity.

APA, Harvard, Vancouver, ISO, and other styles

7

Rizzi, Romeo, and Luca Nardin. "Polynomial Time Instances for the IKHO Problem." ISRN Electronics 2012 (April 8, 2012): 1–10. http://dx.doi.org/10.5402/2012/859820.

Full text

Abstract:

The Interactive Knapsacks Heuristic Optimization (IKHO) problem is a particular knapsacks model in which, given an array of knapsacks, every insertion in a knapsack affects also the other knapsacks, in terms of weight and profit. The IKHO model was introduced by Isto Aho to model instances of the load clipping problem. The IKHO problem is known to be APX-hard and, motivated by this negative fact, Aho exhibited a few classes of polynomial instances for the IKHO problem. These instances were obtained by limiting the ranges of two structural parameters, c and u, which describe the extent to which an insertion in a knapsack in uences the nearby knapsacks. We identify a new and broad class of instances allowing for a polynomial time algorithm. More precisely, we show that the restriction of IKHO to instances where is bounded by a constant can be solved in polynomial time, using dynamic programming.

APA, Harvard, Vancouver, ISO, and other styles

8

Buayen, Patcharin, and Jeeraporn Werapun. "Efficient 0/1-Multiple-Knapsack Problem Solving by Hybrid DP Transformation and Robust Unbiased Filtering." Algorithms 15, no. 10 (September 30, 2022): 366. http://dx.doi.org/10.3390/a15100366.

Full text

Abstract:

The multiple knapsack problem (0/1-mKP) is a valuable NP-hard problem involved in many science-and-engineering applications. In current research, there exist two main approaches: 1. the exact algorithms for the optimal solutions (i.e., branch-and-bound, dynamic programming (DP), etc.) and 2. the approximate algorithms in polynomial time (i.e., Genetic algorithm, swarm optimization, etc.). In the past, the exact-DP could find the optimal solutions of the 0/1-KP (one knapsack, n objects) in O(nC). For large n and massive C, the unbiased filtering was incorporated with the exact-DP to solve the 0/1-KP in O(n + C′) with 95% optimal solutions. For the complex 0/1-mKP (m knapsacks) in this study, we propose a novel research track with hybrid integration of DP-transformation (DPT), exact-fit (best) knapsack order (m!-to-m2 reduction), and robust unbiased filtering. First, the efficient DPT algorithm is proposed to find the optimal solutions for each knapsack in O([n2,nC]). Next, all knapsacks are fulfilled by the exact-fit (best) knapsack order in O(m2[n2,nC]) over O(m![n2,nC]) while retaining at least 99% optimal solutions as m! orders. Finally, robust unbiased filtering is incorporated to solve the 0/1-mKP in O(m2n). In experiments, our efficient 0/1-mKP reduction confirmed 99% optimal solutions on random and benchmark datasets (n δ 10,000, m δ 100).

APA, Harvard, Vancouver, ISO, and other styles

9

Sun, Bo, Lin Yang, Mohammad Hajiesmaili, Adam Wierman, John C. S. Lui, Don Towsley, and Danny H. K. Tsang. "The Online Knapsack Problem with Departures." Proceedings of the ACM on Measurement and Analysis of Computing Systems 6, no. 3 (December 2022): 1–32. http://dx.doi.org/10.1145/3570618.

Full text

Abstract:

The online knapsack problem is a classic online resource allocation problem in networking and operations research. Its basic version studies how to pack online arriving items of different sizes and values into a capacity-limited knapsack. In this paper, we study a general version that includes item departures, while also considering multiple knapsacks and multi-dimensional item sizes. We design a threshold-based online algorithm and prove that the algorithm can achieve order-optimal competitive ratios. Beyond worst-case performance guarantees, we also aim to achieve near-optimal average performance under typical instances. Towards this goal, we propose a data-driven online algorithm that learns within a policy-class that guarantees a worst-case performance bound. In trace-driven experiments, we show that our data-driven algorithm outperforms other benchmark algorithms in an application of online knapsack to job scheduling for cloud computing.

APA, Harvard, Vancouver, ISO, and other styles

10

Sun, Bo, Lin Yang, Mohammad Hajiesmaili, Adam Wierman, John C. S. Lui, Don Towsley, and Danny H. K. Tsang. "The Online Knapsack Problem with Departures." ACM SIGMETRICS Performance Evaluation Review 51, no. 1 (June 26, 2023): 59–60. http://dx.doi.org/10.1145/3606376.3593576.

Full text

Abstract:

The online knapsack problem is a classic online resource allocation problem in networking and operations research. Its basic version studies how to pack online arriving items of different sizes and values into a capacity-limited knapsack. In this paper, we study a general version that includes item departures, while also considering multiple knapsacks and multi-dimensional item sizes. We design a threshold-based online algorithm and prove that the algorithm can achieve order-optimal competitive ratios. Beyond worst-case optimized algorithms, we also propose a data-driven online algorithm that can achieve near-optimal average performance under typical instances while guaranteeing the worst-case performance.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Knapsack"

1

Yang, Yanchun Bulfin Robert L. "Knapsack problems with setup." Auburn, Ala., 2006. http://repo.lib.auburn.edu/2006%20Summer/Dissertations/YANG_YANCHUN_31.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

SCATAMACCHIA, ROSARIO. "Knapsack Problems with Side Constraints." Doctoral thesis, Politecnico di Torino, 2017. http://hdl.handle.net/11583/2667802.

Full text

Abstract:

The thesis considers a specific class of resource allocation problems in Combinatorial Optimization: the Knapsack Problems. These are paradigmatic NP-hard problems where a set of items with given profits and weights is available. The aim is to select a subset of the items in order to maximize the total profit without exceeding a known knapsack capacity. In the classical 0-1 Knapsack Problem (KP), each item can be picked at most once. The focus of the thesis is on four generalizations of KP involving side constraints beyond the capacity bound. More precisely, we provide solution approaches and insights for the following problems: The Knapsack Problem with Setups; the Collapsing Knapsack Problem; the Penalized Knapsack Problem; the Incremental Knapsack Problem. These problems reveal challenging research topics with many real-life applications. The scientific contributions we provide are both from a theoretical and a practical perspective. On the one hand, we give insights into structural elements and properties of the problems and derive a series of approximation results for some of them. On the other hand, we offer valuable solution approaches for direct applications of practical interest or when the problems considered arise as sub-problems in broader contexts.

APA, Harvard, Vancouver, ISO, and other styles

3

Aslan, Murat. "The Cardinality Constrained Multiple Knapsack Problem." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12610131/index.pdf.

Full text

Abstract:

The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce. In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.

APA, Harvard, Vancouver, ISO, and other styles

4

Suri, Bharath. "Accelerating the knapsack problem on GPUs." Thesis, Linköpings universitet, ESLAB - Laboratoriet för inbyggda system, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-70406.

Full text

Abstract:

The knapsack problem manifests itself in many domains like cryptography, financial domain and bio-informatics. Knapsack problems are often inside optimization loops in system-level design and analysis of embedded systems as well. Given a set of items, each associated with a profit and a weight, the knapsack problem deals with how to choose a subset of items such that the profit is maximized and the total weight of the chosen items is less than the capacity of the knapsack. There exists several variants and extensions of this knapsack problem. In this thesis, we focus on the multiple-choice knapsack problem, where the items are grouped into disjoint classes. However, the multiple-choice knapsack problem is known to be NP-hard. While many different heuristics and approximation schemes have been proposed to solve the problem in polynomial-time, such techniques do not return the optimal solution. A dynamic programming algorithm to solve the problem optimally is known, but has a pseudo-polynomial running time. This leads to high running times of tools in various application domains where knapsack problems must be solved. Many system-level design tools in the embedded systems domain, in particular, would suffer from high running when such a knapsack problem must be solved inside a larger optimization loop. To mitigate the high running times of such algorithms, in this thesis, we propose a GPU-based technique to solve the multiple-choice knapsack problem. We study different approaches to map the dynamic programming algorithm on the GPU and compare their performance in terms of the running times. We employ GPU specific methods to further improve the running times like exploiting the GPU on-chip shared memory. Apart from results on synthetic test-cases, we also demonstrate the applicability of our technique in practice by considering a case-study from system-level design. Towards this, we consider the problem of instruction-set selection for customizable processors.

APA, Harvard, Vancouver, ISO, and other styles

5

Islam, Mohammad Tauhidul, and University of Lethbridge Faculty of Arts and Science. "Approximation algorithms for minimum knapsack problem." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009, 2009. http://hdl.handle.net/10133/1304.

Full text

Abstract:

Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem, with zero-one maximum knapsack in one dimension being the simplest one. In this thesis we study several existing approximation algorithms for the minimization version of the problem and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our experiments show that, the proposed algorithm runs fast and has a good performance ratio in practice. We also conduct extensive experiments on the data provided by Canadian Pacific Logistics Solutions during the MITACS internship program. We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional) minimum knapsack problem and compare its performance with a generalization of a greedy algorithm for minimum knapsack in d dimensions. Our experiments show that the e- approximation scheme exhibits good performance ratio in practice.
x, 85 leaves ; 29 cm

APA, Harvard, Vancouver, ISO, and other styles

6

Kosuch, Stefanie. "Stochastic Optimization Problems with Knapsack Constraint." Paris 11, 2010. http://www.theses.fr/2010PA112154.

Full text

Abstract:

Etant donné un ensemble d'objets, chacun ayant un poids et une valeur. Le problème de sac-à-dos consiste à choisir un sous-ensemble d'objets qui (i) respecte une certaine restriction du poids (la capacité du sac-à-dos) et (ii) dont la valeur totale est maximisée. Dans cette thèse nous étudions quatre problèmes d'optimisation stochastique avec contrainte de sac-à-dos: le problème de sac-à-dos avec recours simple, le problème de sac-à-dos avec contrainte probabiliste, le problème de sac-à-dos avec recours et un problème bi-niveau stochastique avec contrainte de sac-à-dos probabiliste. Les problèmes ont en commun que les poids dans la contrainte de sac-à-dos sont supposés être aléatoires. Nous proposons de résoudre les problèmes du sac-à-dos avec recours simple ou avec contrainte probabiliste en appliquant un algorithme « branch-and-bound ». Des bornes supérieures sont obtenues en résolvant des relaxations continues. Pour ceci, nous appliquons un algorithme de gradient stochastique. Concernant le cas du sac-à-dos avec recours, nous traitons dans un premier temps le problème avec des poids gaussiens et nous proposons des bornes inférieures et supérieures sur sa valeur optimale. Dans un deuxième temps, nous étudions le cas d’une distribution discrète des poids. Nous montrons que (si P n'est pas égal à NP) le problème déterministe équivalent n’admet pas d’algorithme d’approximation avec une garantie de performance égale à une valeur constante. Le problème bi-niveau stochastique avec contrainte de sac-à-dos probabiliste est d’abord reformulé comme un problème bilinéaire. Ce dernier étant difficile à résoudre à l’optimum, nous proposons de résoudre une relaxation avec un nouvel algorithme itératif
Given a set of objects each having a particular weight and value. The knapsack problem consists of choosing among these items a subset such that (i) the total weight of the chosen items does respect a given weight constraint (the capacity of the knapsack) and (ii) the total value of the chosen items is maximized. In this thesis, we study four stochastic optimization problems with knapsack constraint: the simple recourse knapsack problem, the chance-constrained knapsack problem, the two-stage knapsack problem and a bilievel problem with knapsack chance-constraint. All problems have in common that the item weights in the knapsack constraints are assumed to be random. We propose to solve the simple recourse and the chance-constrained knapsack problems using a branch-&-bound algorithm as framework. Upper bounds are obtained by solving relaxed, i. E. Continuous sub-problems. The latter is done by applying a stochastic gradient algorithm. Concerning the two-stage knapsack problem, we treat, in the first instance, the model where the item weights are assumed to be normally distributed and propose upper and lower bounds on the optimal solution value. Then, we study the problem with discretely distributed weights and show that its deterministic equivalent reformulation does not admit a constant factor approximation algorithm unless P=NP. The studied bilevel problem with knapsack chance-constraint is first of all reformulated as a deterministic equivalent bilinear problem. As the latter is generally hard to solve exactly, we propose to solve a relaxation using a novel iterative algorithm

APA, Harvard, Vancouver, ISO, and other styles

7

Kaparis, Konstantinos. "Knapsack problems : inequalities, separation and heuristics." Thesis, Lancaster University, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.525341.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Kulanoot, Araya. "Algorithms for some hard knapsack problems." Thesis, Curtin University, 2000. http://hdl.handle.net/20.500.11937/1101.

Full text

Abstract:

The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The specific problem that arises depends on the number of knapsacks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 0-1Knapsack Problem arises when there is one knapsack and one item of each type.Knapsack Problems have been intensively studied over the past forty years because of their direct application to problems arising in industry (for example, cargo loading, cutting stock, and budget control) and also for their contribution to the solution methods for integer programming problems.Several exact algorithms based on branch and bound and dynamic programming have been proposed to solve the Knapsack Problems. For some types of data instances, very efficient algorithms have been found. However, a number of hard knapsack instances have been identified. For example, subset sum and strongly correlated data types. This has motivated some researchers to develop specialized algorithms for particular hard problems.This thesis considers a number of hard Knapsack Problems with a single constraint. A number of specialized algorithms are developed. Our work focuses on some hard instances of the 0-1Knapsack Problem, the Bounded Knapsack Problem, the Unbounded Knapsack Problem and the Change-Making Problem.Chapter 1 provides the background of the Knapsack Problem including some important Knapsack Problems and standard types of data instances, terminology, and a summary of our work. Chapter 2 gives a review of the applications and the solution methods that have been proposed. The remaining chapters present the details of our specialized algorithms.Chapter 3 proposes algorithms for the hard 0-1Knapsack Problems instances of subset sum, strongly correlated, and inverse strongly correlated. The algorithms for the Bounded Knapsack Problem instances of strongly correlated and subset sum are also presented. Extensive computational results show that our algorithms are able to solve large problems of size up to one million variables in less than 7 seconds.Chapter 4 proposes algorithms for some hard Unbounded Knapsack Problems. Two algorithms one for the Unbounded Strongly Correlated Knapsack Problem (algorithm CKU1) and one for the Unbounded Subset Sum Problem (algorithm CKU2) are presented. Extensive computational results establish that our two algorithms are able to solve large problems with up to one million variables in less than 0.3 second.Finally, Chapter 5 proposes exact algorithms for the Change-Making Problem. The problem is a particular type of single Knapsack Problems. This chapter proposes two exact algorithms: algorithm CKUC for the Unbounded Change-Making Problem (UCMP) and algorithm CKBC for the Bounded Change-Making Problem (BCMP). The algorithms can solve large-sized problems, when the item types are generated in small ranges, in less than 51 milliseconds for UCMP and less than 3.5 seconds for BCMP.

APA, Harvard, Vancouver, ISO, and other styles

9

Kulanoot, Araya. "Algorithms for some hard knapsack problems." Curtin University of Technology, School of Mathematics and Statistics, 2000. http://espace.library.curtin.edu.au:80/R/?func=dbin-jump-full&object_id=11692.

Full text

Abstract:

The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The specific problem that arises depends on the number of knapsacks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 0-1Knapsack Problem arises when there is one knapsack and one item of each type.Knapsack Problems have been intensively studied over the past forty years because of their direct application to problems arising in industry (for example, cargo loading, cutting stock, and budget control) and also for their contribution to the solution methods for integer programming problems.Several exact algorithms based on branch and bound and dynamic programming have been proposed to solve the Knapsack Problems. For some types of data instances, very efficient algorithms have been found. However, a number of hard knapsack instances have been identified. For example, subset sum and strongly correlated data types. This has motivated some researchers to develop specialized algorithms for particular hard problems.This thesis considers a number of hard Knapsack Problems with a single constraint. A number of specialized algorithms are developed. Our work focuses on some hard instances of the 0-1Knapsack Problem, the Bounded Knapsack Problem, the Unbounded Knapsack Problem and the Change-Making Problem.Chapter 1 provides the background of the Knapsack Problem including some important Knapsack Problems and standard types of data instances, terminology, and a summary of our work. Chapter 2 gives a review of the applications and the solution methods that have been proposed. The remaining chapters ++
present the details of our specialized algorithms.Chapter 3 proposes algorithms for the hard 0-1Knapsack Problems instances of subset sum, strongly correlated, and inverse strongly correlated. The algorithms for the Bounded Knapsack Problem instances of strongly correlated and subset sum are also presented. Extensive computational results show that our algorithms are able to solve large problems of size up to one million variables in less than 7 seconds.Chapter 4 proposes algorithms for some hard Unbounded Knapsack Problems. Two algorithms one for the Unbounded Strongly Correlated Knapsack Problem (algorithm CKU1) and one for the Unbounded Subset Sum Problem (algorithm CKU2) are presented. Extensive computational results establish that our two algorithms are able to solve large problems with up to one million variables in less than 0.3 second.Finally, Chapter 5 proposes exact algorithms for the Change-Making Problem. The problem is a particular type of single Knapsack Problems. This chapter proposes two exact algorithms: algorithm CKUC for the Unbounded Change-Making Problem (UCMP) and algorithm CKBC for the Bounded Change-Making Problem (BCMP). The algorithms can solve large-sized problems, when the item types are generated in small ranges, in less than 51 milliseconds for UCMP and less than 3.5 seconds for BCMP.

APA, Harvard, Vancouver, ISO, and other styles

10

Chen, Yuning. "Hybrid Metaheuristics for Quadratic Knapsack Problems Iterated responsive threshold search for the quadratic multiple knapsack problem A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0062.

Full text

Abstract:

Cette thèse considère quatre problèmes d’optimisation combinatoire connus sous le nom de Problèmes de Sac-à-Dos Quadratiques : le problème de sac-à-dos quadratique (QSP), le problème de sac-à-dos multiple quadratique (QMSP), le problème de sac-à-dos multiple quadratique généralisé (GQMSP) et le nouveau problème de sac-à-dos multiple quadratique bi-objectif (BO-QMSP) présenté dans cette thèse. Parmi eux, le QSP est le modèle de base tandis que les trois autres introduisent des contraintes ou des fonctions objectives supplémentaires. Ces problèmes ont de nombreuses applications pratiques. Étant donné qu’ils appartiennent à la famille NP-difficile, il est difficile de les résoudre dans le cas général. Pour cette raison, cette thèse est consacrée à la création d’approches métaheuristiques hybrides efficaces pour résoudre ces quatre problèmes difficiles. Plus précisément, nous développons une approche itérative d’exploration hyperplane pour le QSP, deux algorithmes hybrides ("Iterative responsive threshold search" et "Evolutionary path relinking") pour le QMSP, un algorithme mémétique pour le GQMSP et une approche hybride en deux étapes pour le BO-QMSP. Ces algorithmes partagent certains ingrédients fondamentaux (e.g., les opérateurs de mouvement de base et les heuristiques gloutonnes) qui avec quelques adaptations sont généralement applicables à d’autres problèmes de sac-à-dos quadratiques. Ils possèdent également un certain nombre de conceptions spécifiques aux problèmes étudiés. Tous les algorithmes ont été expérimentalement démontrés être en mesure de rivaliser favorablement avec les méthodes de l’état de l’art
This thesis considers four combinatorial optimization problems known under the name Quadratic Knapsack Problems: the quadratic (single) knapsack problem (QKP), the quadratic multiple knapsack problem (QMKP), the generalized quadratic multiple knapsack problem (GQMKP) and the new bi-objective quadratic multiple knapsack problem (BO-QMKP) introduced in this thesis. Among them, the QKP is the most basic model while the other three generalize upon it by introducing additional constraints or objective functions. These problems have a wide range of practical applications. Given that they belong to the NP-hard family, it is computationally difficult to solve them in the general case. For this reason, this thesis is devoted to developing effective hybrid metaheuristic approaches to tackle these four challenging problems. Specifically, we develop an iterated hyperplane exploration approach for the QKP, two hybrid metaheuristic algorithms (iterated responsive threshold search and evolutionary path relinking) for the QMKP, an effective memetic algorithm for the GQMKP and a hybrid two-stage approach for the BO-QMKP. These algorithms share some fundamental ingredients (e.g., move operators and greedy heuristics) which with small adaptations are generally applicable to other Quadratic Knapsack Problems. They also possess a number of problem-specific designs. All algorithms were experimentally demonstrated to be able to compete favourably with state-of-the-art methods

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "Knapsack"

1

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Stock, Catherine. Sophie's knapsack. New York: Lothrop, Lee & Shepard Books, 1988.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Ulrich, Pferschy, and Pisinger D. (David), eds. Knapsack Problems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Samedi's knapsack. New York: Thomas Dunne Books/St. Martin's Minotaur, 2001.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Stock, Catherine. Sophie's knapsack. New York: Lothrop, Lee & Shepard Books, 1988.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

6

Silvano, Martello, ed. Knapsack, packing and cutting. Toronto: INFOR Journal, 1994.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

7

Silvano, Martello, ed. Knapsack, packing and cutting. Toronto: INFOR Journal, 1994.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

8

Koskinen, Jukka Antero. Knapsack sets for cryptography. Lappeenranta, Finland: Lappeenranta University of Technology, 1994.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

9

My knapsack on my back. Singapore: MRI Publications, 1992.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

10

Sural, H. The bounded knapsack problem with setups. Fontainebleau: INSEAD, 1997.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Book chapters on the topic "Knapsack"

1

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Introduction." In Knapsack Problems, 1–14. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Multiple Knapsack Problems." In Knapsack Problems, 285–316. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "The Multiple-Choice Knapsack Problem." In Knapsack Problems, 317–47. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "The Quadratic Knapsack Problem." In Knapsack Problems, 349–88. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_12.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Other Knapsack Problems." In Knapsack Problems, 389–424. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_13.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Stochastic Aspects of Knapsack Problems." In Knapsack Problems, 425–47. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Some Selected Applications." In Knapsack Problems, 449–82. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Introduction to NP-Completeness of Knapsack Problems." In Knapsack Problems, 483–93. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_16.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Basic Algorithmic Concepts." In Knapsack Problems, 15–42. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Kellerer, Hans, Ulrich Pferschy, and David Pisinger. "Advanced Algorithmic Concepts." In Knapsack Problems, 43–72. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-24777-7_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Knapsack"

1

Lemos, Dayllon V. X., Humberto J. Longo, Wellington S. Martins, and Les R. Foulds. "A GPU-based DP algorithm for solving multiple instances of the knapsack problem." In Simpósio em Sistemas Computacionais de Alto Desempenho. Sociedade Brasileira de Computação, 2023. http://dx.doi.org/10.5753/wscad.2023.235875.

Full text

Abstract:

The knapsack problem is a classic and fundamental optimisation problem that serves as a subproblem in various optimisation algorithms. Thus, it is of great importance that we manage to solve several instances of the knapsack problem in a fast and efficient way. In this work we present a parallel algorithm, based on dynamic programming, that can take advantage of parallelism as more knapsacks need to be solved. The algorithm makes use of fine-grained data parallelism and is easily mapped to GPU accelerators. Extensive experiments with diverse datasets demonstrate the superiority of the proposed algorithm, achieving relevant speedups compared to a serial algorithm.

APA, Harvard, Vancouver, ISO, and other styles

2

Kobayashi, Kunikatsu, Kohtaro Tadaki, Masao Kasahara, and Shigeo Tsujii. "A knapsack cryptosystem based on multiple knapsacks." In Its Applications (Isita2010). IEEE, 2010. http://dx.doi.org/10.1109/isita.2010.5649307.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Mahapatra, Priya Ranjan Sinha. "Classical knapsack to geometric knapsack: A journey." In 2011 3rd International Conference on Electronics Computer Technology (ICECT). IEEE, 2011. http://dx.doi.org/10.1109/icectech.2011.5941660.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Aggarwal, Gagan, and Jason D. Hartline. "Knapsack auctions." In the seventeenth annual ACM-SIAM symposium. New York, New York, USA: ACM Press, 2006. http://dx.doi.org/10.1145/1109557.1109677.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Morales, D., J. Roda, F. Almeida, C. Rodríguez, and F. García. "Integral knapsack problems." In the 9th international conference. New York, New York, USA: ACM Press, 1995. http://dx.doi.org/10.1145/224538.224564.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Pedrosa, Lehilton L. C., Mauro R. C. Silva, and Rafael C. S. Schouery. "Complexidade do Positional Knapsack Problem." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2022. http://dx.doi.org/10.5753/etc.2022.222786.

Full text

Abstract:

Neste resumo, apresentamos o Positional Knapsack Problem (PKP) e demonstramos que ele é NP-difícil. O PKP é uma variante do Knapsack Problem (KP) em que o valor de um item varia linearmente de acordo com a posição em que ele é adicionado. Essa mudança na valoração adiciona diversas propriedades não intuitivas ao problema que não valem para o KP e, de fato, o PKP não é uma generalização do KP. Para demonstrar a NP- dificuldade, reduzimos uma variante do Partition Problem a uma instância de PKP cuidadosamente construída, de forma a recuperar algumas propriedades normalmente esperadas para variantes do KP.

APA, Harvard, Vancouver, ISO, and other styles

7

Bendali, F., J. Mailfert, E. Mole Kamga, A. Quilliot, and H. Toussaint. "A Synchronized Knapsack Problem." In 2022 8th International Conference on Control, Decision and Information Technologies (CoDIT). IEEE, 2022. http://dx.doi.org/10.1109/codit55151.2022.9803883.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Vahdatpour, Mohammad Saleh. "Addressing the Knapsack Challenge through Cultural Algorithm Optimization." In 10th International Conference on Artificial Intelligence & Applications. Academy & Industry Research Collaboration Center, 2023. http://dx.doi.org/10.5121/csit.2023.131922.

Full text

Abstract:

The "0-1 knapsack problem" stands as a classical combinatorial optimization conundrum, necessitating the selection of a subset of items from a given set. Each item possesses inherent values and weights, and the primary objective is to formulate a selection strategy that maximizes the total value while adhering to a predefined capacity constraint. In this research paper, we introduce a novel variant of Cultural Algorithms tailored specifically for solving 0-1 knapsack problems, a well-known combinatorial optimization challenge. Our proposed algorithm incorporates a belief space to refine the population and introduces two vital functions for dynamically adjusting the crossover and mutation rates during the evolutionary process. Through extensive experimentation, we provide compelling evidence of the algorithm's remarkable efficiency in consistently locating the global optimum, even in knapsack problems characterized by high dimensions and intricate constraints.

APA, Harvard, Vancouver, ISO, and other styles

9

Martins, T. C., and M. S. G. Tsuzuki. "Solving Irregular Rotational Knapsack Problems." In Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007). IEEE, 2007. http://dx.doi.org/10.1109/isda.2007.4389691.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Martins, T. C., and M. S. G. Tsuzuki. "Solving Irregular Rotational Knapsack Problems." In Seventh International Conference on Intelligent Systems Design and Applications (ISDA 2007). IEEE, 2007. http://dx.doi.org/10.1109/isda.2007.57.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Knapsack"

1

Mamer, John W., and Kenneth E. Schilling. On the Growth of Random Knapsacks. Fort Belvoir, VA: Defense Technical Information Center, August 1988. http://dx.doi.org/10.21236/ada204653.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!