Relevant bibliographies by topics / KNAPSACK-PROBLEM / Journal articles
To see the other types of publications on this topic, follow the link: KNAPSACK-PROBLEM.

Journal articles on the topic 'KNAPSACK-PROBLEM'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 May 2024

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'KNAPSACK-PROBLEM.'

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.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Ross, K. W., and D. H. K. Tsang. "The stochastic knapsack problem." IEEE Transactions on Communications 37, no. 7 (July 1989): 740–47. http://dx.doi.org/10.1109/26.31166.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Han, Xin, and Kazuhisa Makino. "Online minimization knapsack problem." Theoretical Computer Science 609 (January 2016): 185–96. http://dx.doi.org/10.1016/j.tcs.2015.09.021.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Hochbaum, Dorit S. "A nonlinear Knapsack problem." Operations Research Letters 17, no. 3 (April 1995): 103–10. http://dx.doi.org/10.1016/0167-6377(95)00009-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Chung, Chia-Shin, Ming S. Hung, and Walter O. Rom. "A hard knapsack problem." Naval Research Logistics 35, no. 1 (February 1988): 85–98. http://dx.doi.org/10.1002/1520-6750(198802)35:1<85::aid-nav3220350108>3.0.co;2-d.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Schulze, Britta, Michael Stiglmayr, Luís Paquete, Carlos M. Fonseca, David Willems, and Stefan Ruzika. "On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem." Mathematical Methods of Operations Research 92, no. 1 (February 12, 2020): 107–32. http://dx.doi.org/10.1007/s00186-020-00702-0.

Full text
Abstract:
Abstract In this article, we introduce the rectangular knapsack problem as a special case of the quadratic knapsack problem consisting in the maximization of the product of two separate knapsack profits subject to a cardinality constraint. We propose a polynomial time algorithm for this problem that provides a constant approximation ratio of 4.5. Our experimental results on a large number of artificially generated problem instances show that the average ratio is far from theoretical guarantee. In addition, we suggest refined versions of this approximation algorithm with the same time complexity and approximation ratio that lead to even better experimental results.
APA, Harvard, Vancouver, ISO, and other styles
6

Nair, Dr Prabha Shreeraj. "Clustered Genetic Algorithm to solve Multidimensional Knapsack Problem." International Journal of Trend in Scientific Research and Development Volume-1, Issue-4 (June 30, 2017): 737–45. http://dx.doi.org/10.31142/ijtsrd2237.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Hu, Zhi Jun, and Rong Li. "Ant Colony Optimization Algorithm for the 0-1 Knapsack Problem Based on Genetic Operators." Advanced Materials Research 230-232 (May 2011): 973–77. http://dx.doi.org/10.4028/www.scientific.net/amr.230-232.973.

Full text
Abstract:
0-1 knapsack problem is a typical combinatorial optimization question in the design and analysis of algorithms. The mathematical description of the knapsack problem is given in theory. The 0-1 knapsack problem is solved by ant colony optimistic algorithm that is improved by introducing genetic operators. To solve the 0-1 knapsack problem with the improved ant colony algorithm, experimental results of numerical simulations, compared with greedy algorithm and dynamic programming algorithm, have shown obvious advantages in efficiency and accuracy on the knapsack problem.
APA, Harvard, Vancouver, ISO, and other styles
8

Dang, Binh Thanh, and Tung Khac Truong. "Binary salp swarm algorithm for discounted {0-1} knapsack problem." PLOS ONE 17, no. 4 (April 7, 2022): e0266537. http://dx.doi.org/10.1371/journal.pone.0266537.

Full text
Abstract:
While the classical knapsack problem has been the object to be solved by optimization algorithm proposals for many years, another version of this problem, discounted {0-1} knapsack problem, is gaining a lot of attention recently. The original knapsack problem requires selecting specific items from an item set to maximize the total benefit while ensuring that the total weight does not exceed the knapsack capacity. Meanwhile, discounted {0-1} knapsack problem has more stringent requirements in which items are divided into groups, and only up to one item from a particular group can be selected. This constraint, which does not exist in the original knapsack problem, makes discounted {0-1} knapsack problem even more challenging. In this paper, we propose a new algorithm based on salp swarm algorithm in the form of four different variants to resolve the discounted {0-1} knapsack problem. In addition, we also make use of an effective data modeling mechanism and a greedy repair operator that helps overcome local optima when finding the global optimal solution. Experimental and statistical results show that our algorithm is superior to currently available algorithms in terms of solution quality, convergence, and other statistical criteria.
APA, Harvard, Vancouver, ISO, and other styles
9

Xiao, Meng, and Yun Yao Zhou. "Discussion on Knapsack Problem Optimization Algorithm Based on Complex Network." Applied Mechanics and Materials 556-562 (May 2014): 3354–56. http://dx.doi.org/10.4028/www.scientific.net/amm.556-562.3354.

Full text
Abstract:
This passage is to put forward knapsack problem optimization algorithm based on complex network (KOABCN). Knapsack problem has extremely wide application in a great number of fields. For instance, knapsack problem can be applied in information coding, budget control, project choosing, material cutting, cargo loading and unloading as well as Internet information safety. Since 1950’s, knapsack problem has been one of the most heated topics in algorithm and complexity research. Therefore, knapsack will still be largely focused in the next period of research.
APA, Harvard, Vancouver, ISO, and other styles
10

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
11

Azwar, Nurul Azri, Parapat Gultom, and Sawaluddin Sawaluddin. "Discrete Optimization Model in Constructing Optimal Decision Tree." SinkrOn 7, no. 3 (August 13, 2022): 2108–15. http://dx.doi.org/10.33395/sinkron.v7i3.11592.

Full text
Abstract:
Decision trees have been well studied and widely used in knowledge discovery and decision support systems. One of the applications of binary integer programming to form decision trees or decision making is the knapsack problem. The knapsack problem is an integer programming problem that involves only one constraint. The knapsack problem is generally illustrated with a bag and an item. The problem to be solved is to maximize the price of goods with a certain capacity that can be loaded by a bag with a certain capacity too. In solving the knapsack problem, it can generally be done directly. In this paper we are interested to show how the implicit enumeration method solves the knapsack problem to form an optimal decision tree
APA, Harvard, Vancouver, ISO, and other styles
12

Hou, Wenjun, and Marek Perkowski. "Quantum-based algorithm and circuit design for bounded Knapsack optimization problem." Quantum Information and Computation 20, no. 9&10 (August 2020): 766–86. http://dx.doi.org/10.26421/qic20.9-10-4.

Full text
Abstract:
The Knapsack Problem is a prominent problem that is used in resource allocation and cryptography. This paper presents an oracle and a circuit design that verifies solutions to the decision problem form of the Bounded Knapsack Problem. This oracle can be used by Grover Search to solve the optimization problem form of the Bounded Knapsack Problem. This algorithm leverages the quadratic speed-up offered by Grover Search to achieve a quantum algorithm for the Knapsack Problem that shows improvement with regard to classical algorithms. The quantum circuits were designed using the Microsoft Q# Programming Language and verified on its local quantum simulator. The paper also provides analyses of the complexity and gate cost of the proposed oracle. The work in this paper is the first such proposed method for the Knapsack Optimization Problem.
APA, Harvard, Vancouver, ISO, and other styles
13

Bramantya, Devan, I. Gede Santi Astawa, I. Wayan Supriana, Luh Gede Astuti, Ngurah Agus Sanjaya ER, and I. Gusti Agung Gede Arya Kadyanan. "Rancangan dan Analisis Model Algoritma Genetika Untuk Menyelesaikan Permasalahan Knapsack 2 Dimensi." JELIKU (Jurnal Elektronik Ilmu Komputer Udayana) 11, no. 2 (July 16, 2022): 395. http://dx.doi.org/10.24843/jlk.2022.v11.i02.p18.

Full text
Abstract:
The knapsack problem is problem that is still often found in everyday life, one of which is the problem of selecting goods to be transported into containers for delivery of goods. This knapsack problem can be solved by using various optimization algorithms, one of which is the genetic algorithm. This study aims to design a genetic algorithm model to solve the 2-dimensional knapsack problem. 2-dimensional knapsack problem is a knapsack problem that has 2 constraints and in this study, the constraints used were weight and volume.. The evaluation results of the genetic algorithm will be compared with dynamic programming. From the evaluation results that have been carried out, it can be concluded that genetic algorithms can produce near-optimal results with faster computational times than dynamic programming.
APA, Harvard, Vancouver, ISO, and other styles
14

Bosov, A. A., A. V. Gоrbоvа, and N. V. Khalipova. "Substantiation of a heuristic algorithm in the knapsack problem." Science and Transport Progress, no. 42 (December 25, 2012): 170–75. http://dx.doi.org/10.15802/stp2012/9390.

Full text
Abstract:
Introduction: Formed knapsack problem in terms of set functions and is a heuristic algorithm. The goal: to prove that the heuristic algorithm is essential. Some facts from [2]. The equivalence of the limit order to E.Borelyu and convergence in measure. The theorem about the need to set a maximum of function. The situation is quite the algorithm: We present three cases where a heuristic algorithm is sufficient. Counterexample: An Rear take from [1], and given the addition heuristic algorithm, which allows to obtain the solution of the knapsack problem. Vector optimization: With the knapsack problem is tied vector optimization of investment activities. Conclusions: The proposed algorithm for solving the knapsack problem and for additive functions algorithm for Pareto solutions of vector optimization for the two indicators. Appendix: an agenda for the Maple solutions knapsack problem.
APA, Harvard, Vancouver, ISO, and other styles
15

Monaci, Michele, and Ulrich Pferschy. "On the Robust Knapsack Problem." SIAM Journal on Optimization 23, no. 4 (January 2013): 1956–82. http://dx.doi.org/10.1137/120880355.

Full text
APA, Harvard, Vancouver, ISO, and other styles
16

Cheng, Jianqiang, Erick Delage, and Abdel Lisser. "Distributionally Robust Stochastic Knapsack Problem." SIAM Journal on Optimization 24, no. 3 (January 2014): 1485–506. http://dx.doi.org/10.1137/130915315.

Full text
APA, Harvard, Vancouver, ISO, and other styles
17

Okada, Shinkoh, and Mitsuo Gen. "Fuzzy multiple choice knapsack problem." Fuzzy Sets and Systems 67, no. 1 (October 1994): 71–80. http://dx.doi.org/10.1016/0165-0114(94)90209-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
18

Gallo, G., and B. Simeone. "On the supermodular knapsack problem." Mathematical Programming 45, no. 1-3 (August 1989): 295–309. http://dx.doi.org/10.1007/bf01589108.

Full text
APA, Harvard, Vancouver, ISO, and other styles
19

Chen, Kai, and Sheldon M. Ross. "An adaptive stochastic knapsack problem." European Journal of Operational Research 239, no. 3 (December 2014): 625–35. http://dx.doi.org/10.1016/j.ejor.2014.06.027.

Full text
APA, Harvard, Vancouver, ISO, and other styles
20

Gaivoronski, Alexei A., Abdel Lisser, Rafael Lopez, and Hu Xu. "Knapsack problem with probability constraints." Journal of Global Optimization 49, no. 3 (July 1, 2010): 397–413. http://dx.doi.org/10.1007/s10898-010-9566-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
21

Burkard, Rainer E., and Ulrich Pferschy. "The inverse-parametric knapsack problem." European Journal of Operational Research 83, no. 2 (June 1995): 376–93. http://dx.doi.org/10.1016/0377-2217(95)00014-h.

Full text
APA, Harvard, Vancouver, ISO, and other styles
22

D’Ambrosio, Claudia, Fabio Furini, Michele Monaci, and Emiliano Traversi. "On the Product Knapsack Problem." Optimization Letters 12, no. 4 (January 3, 2018): 691–712. http://dx.doi.org/10.1007/s11590-017-1227-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Shiode, Shōgo, Hiroaki Ishi, and Toshio Nishida. "A stochastic linear knapsack problem." Naval Research Logistics 34, no. 5 (October 1987): 753–59. http://dx.doi.org/10.1002/1520-6750(198710)34:5<753::aid-nav3220340514>3.0.co;2-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
24

Marques, Fabiano do Prado, and Marcos Nereu Arenales. "The constrained compartmentalised knapsack problem." Computers & Operations Research 34, no. 7 (July 2007): 2109–29. http://dx.doi.org/10.1016/j.cor.2005.08.011.

Full text
APA, Harvard, Vancouver, ISO, and other styles
25

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
26

Ghadi, Yazeed Yasin, Tamara AlShloul, Zahid Iqbal Nezami, Hamid Ali, Muhammad Asif, Hanan Aljuaid, and Shahbaz Ahmad. "An efficient optimizer for the 0/1 knapsack problem using group counseling." PeerJ Computer Science 9 (April 14, 2023): e1315. http://dx.doi.org/10.7717/peerj-cs.1315.

Full text
Abstract:
The field of optimization is concerned with determining the optimal solution to a problem. It refers to the mathematical loss or gain of a given objective function. Optimization must reduce the given problem’s losses and disadvantages while maximizing its earnings and benefits. We all want optimal or, at the very least, suboptimal answers because we all want to live a better life. Group counseling optimizer (GCO) is an emerging evolutionary algorithm that simulates the human behavior of counseling within a group for solving problems. GCO has been successfully applied to single and multi-objective optimization problems. The 0/1 knapsack problem is also a combinatorial problem in which we can select an item entirely or drop it to fill a knapsack so that the total weight of selected items is less than or equal to the knapsack size and the value of all items is as significant as possible. Dynamic programming solves the 0/1 knapsack problem optimally, but the time complexity of dynamic programming is O(n3). In this article, we provide a feature analysis of GCO parameters and use it to solve the 0/1 knapsack problem (KP) using GCO. The results show that the GCO-based approach efficiently solves the 0/1 knapsack problem; therefore, it is a viable alternative to solving the 0/1 knapsack problem.
APA, Harvard, Vancouver, ISO, and other styles
27

Selvi, V. "Clustering Analysis of Greedy Heuristic Method in Zero_One Knapsack Problem." International Journal of Emerging Research in Management and Technology 6, no. 7 (June 29, 2018): 39. http://dx.doi.org/10.23956/ijermt.v6i7.181.

Full text
Abstract:
Knapsack problem is a surely understood class of optimization problems, which tries to expand the profit of items in a knapsack without surpassing its capacity, Knapsack can be solved by several algorithms such like Greedy, dynamic programming, Branch & bound etc. The solution to the zero_one knapsack problem (KP) can be viewed as the result of a sequence of decision. Clustering is the process of resolving that type of applications. Different clustering application for grouping elements with equal priority. In this paper we are introducing greedy heuristic algorithm for solving zero_one knapsack problem. We will exhibit a relative investigation of the Greedy, dynamic programming, B&B and Genetic algorithms regarding of the complexity of time requirements, and the required programming efforts and compare the total value for each of them. Greedy and Genetic algorithms can be used to solve the 0-1 Knapsack problem within a reasonable time complexity. The worst-case time complexity (Big-O) of both algorithms is O(N). Using the greedy method, the algorithm can produce high quality clusters while reduce time the best partioning avoid the memory confinement problem during the process.
APA, Harvard, Vancouver, ISO, and other styles
28

Hertrich, Christoph, and Martin Skutella. "Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 9 (May 18, 2021): 7685–93. http://dx.doi.org/10.1609/aaai.v35i9.16939.

Full text
Abstract:
The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard Knapsack Problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a Knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum Knapsack solution is sufficient to find optimum Knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed Knapsack solution: for Knapsack instances consisting of n items, an RNN of depth five and width w computes a solution of value at least 1 - O(n^2 sqrt(w)) times the optimum solution value. Our results build upon a classical dynamic programming formulation of the Knapsack Problem as well as a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the Knapsack Problem. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various Shortest Path Problems, the Longest Common Subsequence Problem, and the Traveling Salesperson Problem.
APA, Harvard, Vancouver, ISO, and other styles
29

Goebbels, Steffen, Frank Gurski, and Dominique Komander. "The knapsack problem with special neighbor constraints." Mathematical Methods of Operations Research 95, no. 1 (December 28, 2021): 1–34. http://dx.doi.org/10.1007/s00186-021-00767-5.

Full text
Abstract:
AbstractThe knapsack problem is one of the simplest and most fundamental NP-hard problems in combinatorial optimization. We consider two knapsack problems which contain additional constraints in the form of directed graphs whose vertex set corresponds to the item set. In the one-neighbor knapsack problem, an item can be chosen only if at least one of its neighbors is chosen. In the all-neighbors knapsack problem, an item can be chosen only if all its neighbors are chosen. For both problems, we consider uniform and general profits and weights. We prove upper bounds for the time complexity of these problems when restricting the graph constraints to special sets of digraphs. We discuss directed co-graphs, minimal series-parallel digraphs, and directed trees.
APA, Harvard, Vancouver, ISO, and other styles
30

Nomer, Hazem A. A., Khalid Abdulaziz Alnowibet, Ashraf Elsayed, and Ali Wagdy Mohamed. "Neural Knapsack: A Neural Network Based Solver for the Knapsack Problem." IEEE Access 8 (2020): 224200–224210. http://dx.doi.org/10.1109/access.2020.3044005.

Full text
APA, Harvard, Vancouver, ISO, and other styles
31

Gong, Qiao Qiao, Yong Quan Zhou, and Yan Yang. "Artificial Glowworm Swarm Optimization Algorithm for Solving 0-1 Knapsack Problem." Advanced Materials Research 143-144 (October 2010): 166–71. http://dx.doi.org/10.4028/www.scientific.net/amr.143-144.166.

Full text
Abstract:
In this paper, an artificial glowworm swarm optimization algorithm for solving 0-1 knapsack problem is proposed, and the detailed realization of the algorithm is illustrated. According to intelligent algorithm for knapsack problem, the question of sensitive parameter’s choice is avoided under the greed idea. Simulation results show that the artificial glowworm swarm optimization algorithm for solving 0-1 knapsack problems is feasible and effective.
APA, Harvard, Vancouver, ISO, and other styles
32

Man, Zi Bin, and Ting Hong Zhao. "A Master-Slave Model NGA and its Application in the Multidimensional 0-1 Knapsack Problem." Applied Mechanics and Materials 433-435 (October 2013): 566–69. http://dx.doi.org/10.4028/www.scientific.net/amm.433-435.566.

Full text
Abstract:
The Multidimensional 0-1 knapsack problem is a NP hard problem, though there are many algorithm is used to solve the problem, but there is still not a good solution to solving the problem. This paper improved niche genetic algorithm, established a master-slave mode niche genetic algorithm, and carried on adaptive setting the individual Euclidean distance criterion, making it can changed with the evolving algebra incremental. At last, used master-slave niche genetic algorithm to solve the Multidimensional 0-1 knapsack problem, test results showed, the algorithm has good applicability and superiority in solving the Multidimensional 0-1 knapsack problem.
APA, Harvard, Vancouver, ISO, and other styles
33

Wang, Hong. "A New Hybrid Particle Swarm Optimization for Solving the Knapsack Problem." Applied Mechanics and Materials 328 (June 2013): 266–70. http://dx.doi.org/10.4028/www.scientific.net/amm.328.266.

Full text
Abstract:
A Knapsack Problem is a typical NP complete problem. For solving Knapsack problem, A new improved Particle Swarm Optimization algorithm was proposed in this paper, the new algorithm combine Dantzigs theory of Knapsack Problem and crossover and mutation operation of Genetic Algorithm. According their fitness values, individuals are improved firstly by crossover, Daviss sequence crossover method and reverse mutation method are used respectively in the course of crossover and mutation. Numerical examples illustrate the validity and efficiency of the new hybrid Particle Swarm Optimization.
APA, Harvard, Vancouver, ISO, and other styles
34

Salman, Ayed A., Imtiaz Ahmad, and Mahmad G. H. Omran. "Stochastic Diffusion Binary Differential Evolution to Solve Multidimensional Knapsack Problem." International Journal of Machine Learning and Computing 6, no. 2 (April 2016): 130–33. http://dx.doi.org/10.18178/ijmlc.2016.6.2.586.

Full text
APA, Harvard, Vancouver, ISO, and other styles
35

Regita, Yulia Dewi, Kiswara Agung Santoso, and Ahmad Kamsyakawuni. "Algoritma Elephant Herding Optimization: Permasalahan Multiple Constraints Knapsack 0-1." Majalah Ilmiah Matematika dan Statistika 18, no. 1 (March 1, 2018): 13. http://dx.doi.org/10.19184/mims.v18i1.17241.

Full text
Abstract:
Optimization problems are often found in everyday life, such as when determining goods to be a limited storage media. This causes the need for the selection of goods in order to obtain profits with the requirements met. This problem in mathematics is usually called a knapsack. Knapsack problem itself has several variations, in this study knapsack type used is multiple constraints knapsack 0-1 which is solved using the Elephant Herding Optimization (EHO) algorithm. The aim of this study is to obtain an optimal solution and study the effectiveness of the algorithm comparing it to the Simplex method in Microsoft Excel. This study uses two data, consisting of primary and secondary data. Based on the results of parameter testing, the proven parameters are nClan, nCi,α,β and MaxGen have a significant effect. The final simulation results have also shown a comparison of the EHO algorithm with the Simplex method having a very small percentage deviation. This shows that the EHO algorithm is effective for completing optimization multiple constraints knapsack 0-1. Keywords: EHO Algorithm, Multiple Constraints Knapsack 0-1 Problem.
APA, Harvard, Vancouver, ISO, and other styles
36

Abdullah, Rinaldy Ahmad, Abduh Riski, and Ahmad Kamsyakawuni. "PENERAPAN ALGORITMA PENGUINS SEARCH OPTIMIZATION (PeSOA) DAN ALGORITMA MIGRATING BIRDS OPTIMIZATION (MBO) PADA PERMASALAHAN KNAPSACK 0-1." Majalah Ilmiah Matematika dan Statistika 19, no. 2 (September 2, 2019): 75. http://dx.doi.org/10.19184/mims.v19i2.17270.

Full text
Abstract:
Every person would want maximum profit with as little as possible resources or capital. One example in everyday life is the problem of limited storage media but is required to get the maximum benefit. From this problem comes the term known as the knapsack problem. One of the problems with Knapsack is knapsack 0- 1, where knapsack 0-1 is a problem of storing goods where the item will be completely inserted or not at all. Completion of knapsack 0-1 problems can be helped using a metaheuristic algorithm. Metaheuristic algorithms include the Penguins Search Optimization (PeSOA) algorithm and the Migration Birds Optimization (MBO) algorithm. This study aims to determine the resolution of knapsack 0-1 problems using the Penguins Search Optimization (PeSOA) algorithm and the Migration Birds Optimization (MBO) algorithm and compare the optimal solutions obtained. This research method is divided into three main parts. First take data that includes the name of the item, the purchase price, the selling price and the weight of each item. The second is applying the Penguins Search Optimization (PeSOA) algorithm and the Migration Birds Optimization algorithm (MBO) on 0-1 knapsack problems. The third program is made to facilitate the calculation of data with the help of Matlab R2015b software. The results of this study found that both algorithms both reached the optimal solution, but the convergence and running time obtained were different. The Migrating Birds Optimization (MBO) algorithm is faster converging than the Penguins Search Optimization (PeSOA) algorithm to get the optimal solution. And also the Migrating Birds Optimization (MBO) algorithm has better running time than the Penguins Search Optimization (PeSOA) algorithm to achieve maximum iteration. Keywords: Whale optimization algorithm, multi knapsack 0-1 problem with multiple constraints.
APA, Harvard, Vancouver, ISO, and other styles
37

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
38

Pferschy, Ulrich, and Joachim Schauer. "The Knapsack Problem with Conflict Graphs." Journal of Graph Algorithms and Applications 13, no. 2 (2009): 233–49. http://dx.doi.org/10.7155/jgaa.00186.

Full text
APA, Harvard, Vancouver, ISO, and other styles
39

Dudkin, F. A., and A. V. Treyer. "Knapsack problem for Baumslag–Solitar groups." Sibirskii zhurnal chistoi i prikladnoi matematiki 18, no. 4 (December 1, 2018): 43–56. http://dx.doi.org/10.33048/pam.2018.18.404.

Full text
APA, Harvard, Vancouver, ISO, and other styles
40

Plotkin, Artyom V. "Fast algorithm for quadratic knapsack problem." Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy 9, no. 1 (2022): 76–84. http://dx.doi.org/10.21638/spbu01.2022.108.

Full text
Abstract:
The paper considers a quadratic programming problem with a strictly convex separable objective function, a single linear constraint, and two-sided constraints on variables. This problem is commonly called the Convex Knapsack Separable Quadratic Problem, or CKSQP for short. We are interested in an algorithm for solving CKSQP with a linear time complexity. The papers devoted to this topic contain inaccuracies in the description of algorithms and ineffective implementations. In this work, the existing difficulties were overcome.
APA, Harvard, Vancouver, ISO, and other styles
41

Kleywegt, Anton J., and Jason D. Papastavrou. "The Dynamic and Stochastic Knapsack Problem." Operations Research 46, no. 1 (February 1998): 17–35. http://dx.doi.org/10.1287/opre.46.1.17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
42

Leontiev, V. K., and E. N. Gordeev. "Generating Functions in the Knapsack Problem." Doklady Mathematics 98, no. 1 (July 2018): 364–66. http://dx.doi.org/10.1134/s1064562418050198.

Full text
APA, Harvard, Vancouver, ISO, and other styles
43

Korutcheva, E., M. Opper, and B. Lopez. "Statistical mechanics of the knapsack problem." Journal of Physics A: Mathematical and General 27, no. 18 (September 21, 1994): L645—L650. http://dx.doi.org/10.1088/0305-4470/27/18/001.

Full text
APA, Harvard, Vancouver, ISO, and other styles
44

Elgabli, Anis, and Vaneet Aggarwal. "Deadline and Buffer Constrained Knapsack Problem." IEEE Transactions on Circuits and Systems for Video Technology 29, no. 5 (May 2019): 1564–68. http://dx.doi.org/10.1109/tcsvt.2019.2902759.

Full text
APA, Harvard, Vancouver, ISO, and other styles
45

van Hoeij, M. "Factoring Polynomials and the Knapsack Problem." Journal of Number Theory 95, no. 2 (August 2002): 167–89. http://dx.doi.org/10.1016/s0022-314x(01)92763-5.

Full text
APA, Harvard, Vancouver, ISO, and other styles
46

Andonov, R., V. Poirriez, and S. Rajopadhye. "Unbounded knapsack problem: Dynamic programming revisited." European Journal of Operational Research 123, no. 2 (June 2000): 394–407. http://dx.doi.org/10.1016/s0377-2217(99)00265-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
47

Lasserre, Jean B., and Eduardo S. Zeron. "Solving the knapsack problem via -transform." Operations Research Letters 30, no. 6 (December 2002): 394–400. http://dx.doi.org/10.1016/s0167-6377(02)00161-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
48

Caprara, Alberto, and Michele Monaci. "On the two-dimensional Knapsack Problem." Operations Research Letters 32, no. 1 (January 2004): 5–14. http://dx.doi.org/10.1016/s0167-6377(03)00057-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
49

Han, Xin, Qinyang Chen, and Kazuhisa Makino. "Online knapsack problem under concave functions." Theoretical Computer Science 786 (September 2019): 88–95. http://dx.doi.org/10.1016/j.tcs.2018.03.025.

Full text
APA, Harvard, Vancouver, ISO, and other styles
50

Sarin, Sanjiv, and Mark H. Karwan. "The linear multiple choice knapsack problem." Operations Research Letters 8, no. 2 (April 1989): 95–100. http://dx.doi.org/10.1016/0167-6377(89)90008-4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'KNAPSACK-PROBLEM' for other source types:
Dissertations / Theses
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!

To the bibliography