Artículos de revistas: "KNAPSACK-PROBLEM"

1

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

2

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

3

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

4

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

5

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

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 (30 de junio de 2017): 737–45. http://dx.doi.org/10.31142/ijtsrd2237.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

7

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

8

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

9

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

10

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

11

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

Texto completo

Resumen

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

Los estilos APA, Harvard, Vancouver, ISO, etc.

12

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

13

Bramantya, Devan, I. Gede Santi Astawa, I. Wayan Supriana, Luh Gede Astuti, Ngurah Agus Sanjaya ER y 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, n.º 2 (16 de julio de 2022): 395. http://dx.doi.org/10.24843/jlk.2022.v11.i02.p18.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

14

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

15

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

16

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

17

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

18

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

19

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

20

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

21

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

22

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

23

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

24

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

25

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

26

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

27

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

28

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

29

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

30

Nomer, Hazem A. A., Khalid Abdulaziz Alnowibet, Ashraf Elsayed y 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.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

31

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

32

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

33

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

34

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

35

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

36

Abdullah, Rinaldy Ahmad, Abduh Riski y 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, n.º 2 (2 de septiembre de 2019): 75. http://dx.doi.org/10.19184/mims.v19i2.17270.

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

37

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

38

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

39

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

40

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

Texto completo

Resumen

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.

Los estilos APA, Harvard, Vancouver, ISO, etc.

41

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

42

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

43

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

44

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

45

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

46

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

47

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

48

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

49

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

50

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

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Artículos de revistas sobre el tema "KNAPSACK-PROBLEM"

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros