Research article · 2019 · Full text
International Journal of Statistics and Applied MathematicsGreedy solution method for knapsack problems with R
Volume 4(3) · Pages 54–62
Research areasOptimization and Packing ProblemsAdvanced Manufacturing and Logistics OptimizationOptimization and Mathematical Programming
Abstract
Author-writtenThe Knapsack problems contained in integer programming are one of the combinatoral optimization methods that maximize utility without exceeding the capacity. Different methods have been developed for the solution of Knapsack problems. In this study, Branch boundary algorithm, Balas algorithm and Greedy algorithm are used. Among these, R program code was developed for Greedy algorithm and sample problems were solved in different models. Results were also obtained using the pomQM package program for 3, 5, 7, 10, 30 and 50 variables. All results were compared using the developed R code. The objective function values, constraint values and capacity values of the problems are produced by random in R program. Even when the number of variables for single and two-dimensional, pure (0-1) binary problems is large, it can be obtained optimal or close to optimality results with Greedy method. As a result, R-code was developed without any problem of size and number of constraints.
Summary
Source-checkedPlain-language reading of the full paper, prepared with AI and checked against the text. Each point links to the authors' own words.
Why it matters
- Knapsack problems are a type of combinatorial optimization used in integer programming to maximize utility while staying within a specific capacity. View evidence ↗
- Heuristic algorithms are beneficial for enterprises when problems have too many constraints or cannot be expressed algebraically, as they reduce solution costs. View evidence ↗
- The Greedy algorithm is particularly advantageous among heuristics due to its lower computational cost and broad applicability. View evidence ↗
The question
- The study aims to determine if the Greedy heuristic algorithm provides solutions close to those produced by classical algorithms. View evidence ↗
What they did
- The researchers compared the Branch and Bound algorithm, the Balas algorithm, and a custom-developed Greedy algorithm implemented in R. View evidence ↗
- The pomQM package was used to obtain results for problems containing 3, 5, 7, 10, 30, and 50 variables. View evidence ↗
- Problem parameters, including objective function values, constraint values, and capacity values, were randomly generated using R. View evidence ↗
What they found
- In a two-dimensional pure knapsack problem, the Greedy algorithm and the branch and bound algorithm both yielded a result of Z=688. View evidence ↗
- Comparison data indicates that the Greedy algorithm generally provides results that are either optimal or very close to optimal. View evidence ↗
- The Greedy algorithm's results tend to deviate slightly from the optimal as the number of constraints increases. View evidence ↗
- The pomQM package was unable to provide a solution for the 50-variable sample problem, whereas the R-based Greedy code could. View evidence ↗
What it means
- The authors conclude that their R program codes are superior to packages like pomQM for large problems because they lack limits on variables, constraints, and iterations. View evidence ↗
- The authors recommend further development of R solutions for other heuristic algorithms to create a comprehensive package for researchers. View evidence ↗
Visual summary
3 visualsIllustrations explain the paper; charts are replotted from the paper's own table values.
Algorithm Comparison Workflow
AI-generated conceptual illustration (A computer monitor displaying a coding environment and a physical knapsack bag filled with various geometric objects). It explains the idea and does not show study data.
View source evidence ↗
3: Classical Algorithm... vs Greedy Algorithm R...
Replotted from Table 13 (page 8) of the original paper. Every bar is the paper's own table value.
View source evidence ↗
5: Classical Algorithm... vs Greedy Algorithm R...
Replotted from Table 13 (page 8) of the original paper. Every bar is the paper's own table value.
View source evidence ↗Figures & tables
From the original paper
Table 1
Table 2
Table 3
Table 4
Table 5
Table 7
Table 6
Table 9
Table 10
Table 11
Table 13
Table 12Introduction
Optimization problems cannot be used for many reasons in today's enterprises. The main reason for this is that the problems cannot be expressed algebraically or the number of constraints is high. In such cases, the choice of heuristic algorithms will help to solve the problem with less cost and therefore will be of great benefit for the enterprise. Artificial neural networks, genetic algorithms, tabu search, ant colony and Greedy algorithm are widely used heuristic algorithms. Apart from these, there are many intuitive or meta intuitive algorithms developed to solve the problem. However, the Greedy algorithm has the advantage that it has less computational cost compared to other heuristic algorithms, can be solved by using less algorithms and can be applied to any problem. The use of the Greedy algorithm for local or instant results is a matter of debate, but its use is quite common. The reason why Greedy algorithm is preferred for heuristic algorithms is that it has such advantages. In addition, the Greedy algorithm, which is included in many algorithms, helps to obtain healthier results with this algorithm and to develop new hybrid algorithms. For example, among the classical methods, the most commonly used branch boundary algorithm reduces the scope of the problem by trimming the branches and decreases the processing load. Or, it can be more economical to find the optimal point for finding the randomly selected point with the Greedy approach in the cutting plane method. The Greedy algorithm is not only useful in classical algorithms, but also in heuristic algorithms. Greedy has been found to be of great benefit in the determination of the population to be randomly assigned to the genetic algorithm solution, and the creation of a banned list in taboo search (Gerşil & Palamutçuoğlu, 2013; Alpay, 2008) [1,2] . In this study, the solution of knapsack problems with Greedy algorithm is discussed. For this purpose, the sample problems were solved and solved with the help of the classical methods of the branch boundary algorithm and the Balas algorithm and the R program codes developed based on the Greedy algorithm (R Development Core Team, 2018) [3] . Different softwares are used in the literature to solve integer programming problems. However, these softwares are usually limited by the number of variables and iterations. For this reason, writing code for problem solving is important in order to eliminate both the variable and iterative constraints and to obtain the solutions in a shorter time with the desired methods.
In addition, typed codes allow to solve new problems encountered by making arrangments on them. Considering these situations, it is preferred to make the solution with R which is one of the most used programs in statistics.
Review of literatüre
The knapcask problems are one of the most common integer programming problems. Studies on integer programming are usually based on classical algorithms or heuristic algorithms that have come to the fore in recent years. The Greedy algorithm included in these algorithms is preferred for problems that other algorithms cannot solve or this intuition is used in some algorithms, which has increased the importance of the algorithm. Especially its yielding the best results for the problems that can be expressed as matroid has increased the confidence in Greedy's intuition. When the studies on the solution of integer programming problems with the Greedy algorithm were examined, Lagodimos and Leopoulos (2000) [4] first pointed out the problem of planning the personnel shifts of a food company. They addressed the problem under certain constraints and solved the problem with the proposed Greedy algorithm. As a result, the algorithm performed well in terms of both solution time and quality. In a study to align DNA sequences, Zhang et al . (2000) [5] concluded that the Greedy algorithm provided a tenfold resolution of the appropriate data compared to the traditional programming. They stated that an application of the algorithm in the study was used in the UniGene database. Biller et al . ( 2005) [6] used the Greedy algorithm in their study in the automotive industry and showed that it gave the optimal solution. At the end of the study, they stated that with a few price changes, much better benefits could be obtained. Berberler (2009) [7] conducted a doctoral study on the types of knapsack and their application. In the study, the problem of can knapsack was dealt with knapsack terminology and solved with the help of the genetic algorithm to obtain optimum results for the knapsack. Liu (2001) [8] conducted a simulation study on the solution of 0-1 knapsack problems using Greedy and dynamic programming methods. Gorski et al . (2012) [9] showed that two-dimensional knapsack problems can be solved efficiently by the Greedy algorithm. For this purpose, they have appropriately divided the weightings in the constraints. They also stated that the Greedy method produced suitable solutions in a shorter time. When the studies done so far are examined, it is see that though different programs (WinQSB, pomQM, Gams, etc.) have been developed for the solution of knapsack problems, the number of commonly used package programs is low. In addition, packet programs developed for classical methods are limited by the number of constraints and number of variables. Apart from this, studies to solve such problems with an heuristic algorithm are insufficient. Therefore, it is important to write code with a commonly used package program like R now. With the developed R program codes, solutions can be found for 0-1 and pure knapsack problems in shorter time without variable number constraint.
Materials and methods
Let's assume that someone has n number of unbrokable products and that these products are intended to be filled into a knapsack with a limited volume. Each of these products has a specific c ij benefit (utility) value for the knapsack owner and each of them has an existing a j weight (j = 1, 2, …, n). Provided that the b j capacities do not exceed, the knapsack owner would like to create a combination of products that will provide the most benefit to him. The decision variables x j are the number of j products to be taken into the knapsack. In terms of the definition of these decision variables, knapsack problems are classified as non-negative knapsack and (0-1) binary knapsack problems. So a general knapsack model is expressed as follows (Winston, 2014) [10] ; Objective function:
The model given by the inequality under the above constraints (1) is called the non-negative or pure knapsack problem. If the x j limit is changed to 0 or 1, the problem becomes a 0-1 knapsack problem. In this case the model is expressed as follows (Schrijver) [11] ;
Objective function
In this case, the decision variables of the inequality in the knapsack problem (2) take the value of 0-1. In the model given with the inequality (1), it is possible to put more than one product of the same type into the bag. However, the decision variables in this model should be defined in the form of 0-1 to determine whether to put the jth product in the knapsack (Özkan) [12] . The problem of the knapsack where some of the variables take integers and others take real values turns into a mixed integer problem model. In this case the model; Objective function:
(3) numbered is like inequality. Numerous algorithms have been developed to solve integer programming problems. Some of the most common algorithms used in the solution of knapsack problems are given below.
Branch and boundary algorithm
One of the most popular methods for integer programming problems, the branch and boundary algorithm has been in use since the 1960s. This algorithm is among the classical solution methods. The method searches for optimal solutions to the problem and ultimately determines the optimum value. The problem is initially addressed as a linear programming problem. At this stage, the branching process is started by looking at the real valued results. The branching phase continues until the integer results are found. When searching for solutions, the branching is terminated when the appropriate solution cannot be found. The branch and boundary algorithm can be compared to the decision trees in terms of shape. The branch and boundary algorithm is a suitable method for many problems, but it should be remembered that it has exponential complexity. To reduce this complexity, the branch boundary algorithm can be used in combination with Gomory trimming or an heuristic method (Greedy algorithm, genetic algorithm, etc.) some branches can be pruned.
Balas algorithm
Balas algorithm 0-1 is used for integer problems. All the possible results with the algorithm are searched for optimal solution. When applying the method, the values 0 and 1 are matched for all variables. If we want to express mathematically, all variables are determined to be 0 and 1. This means that there are 2 number of variables of solutions for the problem. The optimal result is the solution, but for large-scale problems this method is useless.
Greedy algorithm
The Greedy algorithm is an heuristic method. This algorithm consciously or unconsciously is the most widely used method in daily life. It aims to find local results, not an optimal result. According to the objective function, it will try to find the values that will make the benefit maximum or the cost minimum by using very few and sometimes no algorithms. Calculation costs are quite low. The biggest advantage in comparison with other heuristics is that it finds a solution for every problem. Nevertheless, it should be noted that these solutions may not be optimal (Durmuş, 2018; Pan & Zhang, 2018) [13,14] . The use of the Greedy algorithm in other methods both reduces the costs of the methods and allows the emergence of new hybrid algorithms. Considering the advantages of the Greedy algorithm, its importance is better understood. Therefore, R codes written in the study were written with Greedy terminology.
Results
In this section, classical algorithms for different knapsack problems and pomQM package program have been obtained. The same problems were solved by using R program codes developed using the Greedy algorithm. The main goal here is to show that local results can be obtained by the Greedy algorithm.
In literature, knapsack problems are usually single-conditional to "weight" or "volume"; Sometimes a multi-conditional mathematical model is created in terms of "weight" and "volume". For this reason, both single and two restricted knapsack problems were discussed in our study. Since three or more restricted knapsack problems were not found in the literature, they were not included in the study.
One dimensional 0-1 knapsack problem
An example of 8 variables is given below to one dimensional 0-1 knapsack problem.
Objective function
When the problem given by the above (4) inequality is solved by the branch method from the classical methods, the results of each branch must be calculated separately. Results for this example were found to be 𝑥 1 = 𝑥 1 = 𝑥 3 = 𝑥 5 = 𝑥 6 = 𝑥 8 = 1, 𝑥 4 = 𝑥 7 = 0 and 𝑍 = 52.
When the problem is solved by Balas method, 2 8 solutions are obtained. These solutions also include optimal results. As a result, the optimal value is the same as the branch and boundary algorithm. The following algorithm is followed to solve the problem with Greedy (Pan & Zhang, 2018) [14] :
Step 1. All the benefit values 𝑟 𝑗 = (𝑐 𝑗 /𝑎 𝑗 ) are calculated (knapsack is the maximization problem)
Step 2. The utility values (𝑟 𝑗 ) are sorted. If there is the same benefit value, their order is randomly determined.
Step 3. The most benefit item is put in the bag. The next benefit value is considered. If it does not exceed the capacity, it is placed in the bag and if it exceeds, the next item is checked.
Step 4. If all items have been checked, the solution is terminated. Otherwise, return to step 3. R program codes are given in Table 1 for Greedy algorithm. According to these steps, the Greedy algorithm solution of the knapsack problem is given in Table 2. Solution is found as 𝑥 1 = 𝑥 1 = 𝑥 3 = 𝑥 5 = 𝑥 6 = 𝑥 8 = 1, 𝑥 4 = 𝑥 7 = 0 𝑎𝑛𝑑 𝑍 = 52. The solution of the problem of 0-1 knapsack problem given by the equality (4) with the R program is as in Table 3; [1] "Z= 52" [1] "xj values:" [1] 1 1 1 0 1 1 0 1 When the problem given by the above ( 5) inequality was solved by the branch boundary algorithm, the results were found as 𝑥 6 = 24, 𝑥 1 = 𝑥 2 = 𝑥 3 = 𝑥 4 = 𝑥 5 = 𝑥 7 = 𝑥 8 = 𝑥 9 = 𝑥 10 = 0 and 𝑍 = 288. Because the problem is pure integer programming, the solution with the Balas algorithm cannot be applied to this problem.
| xj | cj | aj | rj=cj/aj | rank |
|---|---|---|---|---|
| x1 | 1 | 20 | 0.05 | 7 |
| x2 | 5 | 50 | 0.1 | 3 |
| x3 | 10 | 100 | 0.1 | 4 |
| x4 | 3 | 150 | 0.02 | 8 |
| x5 | 8 | 70 | 0.11 | 2 |
| x6 | 12 | 200 | 0.06 | 5 |
| x7 | 9 | 150 | 0.06 | 6 |
| x8 | 16 | 30 | 0.53 | 1 |
Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.
View original table image
The following algorithm steps can be defined to solve the problem with Greedy:
Step 1. All the benefit 𝑟 𝑗 = (𝑐 𝑗 /𝑎 𝑗 ) values are calculated.
Step 2. The utility values are sorted. If there is the same benefit value, their order is randomly determined.
Step 3. The item that yields the most benefit is put into a bag not to exceed the capacity The next benefit value is considered. If it does not exceed the capacity, it is put in a bag not to exceed the capacity and if it exceeds, the next item is checked.
Step 4. If all items have been checked, the solution is terminated. Otherwise, return to step 3. R program codes are given in Table 4. According to these steps, the solution of the knapsack problem is as in Table 5. Thus, the Greedy solution for the problem is found as 𝑥 6 = 24, 𝑥 1 = 𝑥 2 = 𝑥 3 = 𝑥 4 = 𝑥 5 = 𝑥 7 = 𝑥 8 = 𝑥 9 = 𝑥 10 = 0 and 𝑍 = 288. The solution of one dimensional pure knaksack problem by R program is given in Table 6.
| xj | cj | aj | rj=cj/aj | rank |
|---|---|---|---|---|
| x1 | 6 | 2 | 3 | 3 |
| x2 | 1 | 1 | 1 | 8 |
| x3 | 10 | 2 | 5 | 2 |
| x4 | 6 | 3 | 2 | 6 |
| x5 | 3 | 1 | 3 | 4 |
| x6 | 12 | 1 | 12 | 1 |
| x7 | 7 | 5 | 1.4 | 7 |
| x8 | 2 | 2 | 1 | 9 |
| x9 | 1 | 3 | 0.33 | 10 |
| x10 | 12 | 4 | 3 | 5 |
Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.
View original table image
> capacity <-24 > one_knapsack_pure(object, subject, capacity) [1] "Z= 288" [1] "x j values:"
Two-dimensional 0-1 knapsack problem
The following problem is solved based on the differences between the benefit values and the effect on the capacity and the results are given (Bakır & Altunkaynak, 2003) [15] . Objective function:
The problem given by ( 6) inequality is 2 dimensional and 7 variables. The benefit values for solving this problem with the Greedy algorithm are given in Table 7. The solution of the decision variables given in Table 5 according to the steps of Greedy algorithm is given in Table 8. The solution of the problem with the Greedy algorithm was found to be 𝑥 5 = 0, 𝑥 1 = 𝑥 2 = 𝑥 3 = 𝑥 4 = 𝑥 6 = 𝑥 7 = 1 and 𝑍 = 361. The solution of the problem with the branch and boundary algorithm, Balas algorithm and R program were found to be the same. R program codes are given in Table 9 and the result of the R program is given in Table 10.
| xj | Weight (≤ 25) | Volume (≤ 400) |
|---|---|---|
| x2=1 | 25-3=22 | 400-35=365 |
| x7=1 | 22-4=18 | 365-100=265 |
| x6=1 | 18-0.1=17.9 | 265-25=240 |
| x4=1 | 17.9-0.5=17.4 | 240-68=172 |
| x1=1 | 17.4-2=15.4 | 172-15=157 |
| x3=1 | 15.4-9=6.4 | 157-105=52 |
| x5=0 |
Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.
View original table image
| xj | cj | a1j | a2j | r1j | r2j | r1j- r2j | rank |
|---|---|---|---|---|---|---|---|
| x1 | 35 | 2 | 15 | 17.5 | 2.33 | 15.17 | 5 |
| x2 | 85 | 3 | 35 | 28.3 | 2.42 | 25.88 | 1 |
| x3 | 135 | 9 | 105 | 15 | 1.28 | 13.72 | 6 |
| x4 | 10 | 0.5 | 68 | 20 | 0.14 | 19.86 | 4 |
| x5 | 25 | 2 | 125 | 12.5 | 0.20 | 12.30 | 7 |
| x6 | 2 | 0.1 | 25 | 20 | 0.08 | 19.92 | 3 |
| x7 | 94 | 4 | 100 | 23.5 | 0.94 | 22.56 | 2 |
Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.
View original table image
Table 9: R program codes for two-dimensional 0-1 knapsack problem two_knapsack_01 <-function(object, subject1, subject2, capacity1, capacity2) { variable <-c(1:length(object)) benefit1 <-object/subject1 benefit2 <-object/subject2 benefit <-benefit1 -benefit2 place <-order(benefit, decreasing = T) matrix <-cbind(variable, object, subject1, subject2, benefit, place) benefit_matrix <-matrix[order(matrix[,5], decreasing = T),] x <-1 final = 0 s <-0 array <-c(x) while (nrow(matrix
Two-dimensional pure knapsack problem
The problem given by equation ( 6) above can be re-modeled as pure knapsack. The Greedy solution for the newly defined problem was found to be 𝑥 2 = 8, 𝑥 6 = 4, 𝑥 1 = 𝑥 3 = 𝑥 4 = 𝑥 5 = 𝑥 7 = 0 and 𝑍 = 688. R program codes are given in Table 11. The solution of the problem by R program is given in Table 12. The same results were obtained in the solution of the problem by the branch and boundary algorithm. Since the problem is pure integer programming, the Balas solution cannot be applied. { variable <-c(1:length(object)) benefit1 <-object/subject1 benefit2 <-object/subject2 benefit <-benefit1 -benefit2 place <-order(benefit, decreasing = T) matrix <-cbind(variable, object, subject1, subject2, benefit, place) benefit_matrix <-matrix[order(matrix[,5], decreasing = T),] x <-1 final = 0 s <-0 array <-c(x) while (nrow(matrix
Conclusion
Ready-to-use software programs developed to solve integer programming problems are limited by the number of variables, constraints and iterations. Therefore, software development for the solution of problems is necessary for the solution of larger problems. Because in real-life problems the number of variables and constraints is high. As mentioned earlier, this study was designed to investigate whether Greedy's heuristic algorithm gives close solutions compared to classical algorithms. In this respect, different models are discussed. The solutions of the problems were determined by the appropriate classical algorithm (pomQM package) and the Greedy algorithm (R program). Single and two dimensional knapsack problems can be solved with the help of developed R program. These program codes are not limited to constraint (max 30), variable (max 30) or iteration number (max 10.000) as in pomQM and similar package programs, so they can produce solutions for large problems. Table 13 shows the results of pomQM and R program for 3, 5, 7, 10, 30 and 50 variables for single and two constrained problems. The objective function values, constraint values and capacity values of the problems discussed within the scope of the study were randomly generated by giving the minimum and maximum range in R. The variable numbers in the table have been chosen to be solved with pomQM. The 50-variable sample was added to the table to show that the pomQM package could not provide a solution. Table 13 clearly shows that the Greedy algorithm provides optimal results or results very close to the optimal. In addition, when the number of constraints increases, it is seen that the results of the Greedy algorithm are slightly different from the optimal. However, these differences are negligible except for very risky problems (patient treatment, amount of medication, crisis management, etc.). In addition, it was observed that the pomQM package caused a number of iterations errors in some 30 variable models.
| Knapsack Problem | Number of Constraints | Number of Variables | Classical Algorithm PomQM Program | Greedy Algorithm R Program |
|---|---|---|---|---|
| 0-1 Integer | 1 | 3 | 15 | 15 |
| 5 | 19 | 19 | ||
| 10 | 48 | 48 | ||
| 20 | 29 | 29 | ||
| 30 | 48 | 46 | ||
| 50 | - | 66 | ||
| 2 | 3 | 11 | 11 | |
| 5 | 6 | 6 | ||
| 10 | 33 | 33 | ||
| 20 | 221 | 178 | ||
| 30 | 32 | 29 | ||
| 50 | - | 15 | ||
| Pure Integer | 1 | 3 | 20 | 20 |
| 5 | 34 | 34 | ||
| 10 | 315 | 315 |
Table text extracted from the original PDF; superscript letters are shown inline. The original table image is below.
View original table image
References
11 in the original paper- Gerşil M. ve Palamutçuoğlu, T. Ders Çizelgeleme Probleminin Melez Genetik Algoritmalar İle Performans Analizi, Niğde Üniversitesi İİBF Dergisi. 2013; 6(1):242-262.
- Alpay Ş. Tam Zamanlı Montaj Hatlarında Çok Amaçlı Karışık Model Sıralama İçin Rota Birleştirmeli Açgözlü Rassallaştırılmış Uyarlamalı Arama Yordamı, Eskişehir Osmangazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi. 2008; 21(1):153-170.
- Lagodimos, A.G. ve Leopoulos V. Greedy Heuristic Algorithms for Manpower Shift Planning, International Journal of Production Economics. 2000' 68:95-106.
- Zhang Z, Schwartz S, Wagner L, ve Miller W. A Greedy Algorithm for Aligning DNA Sequences, Journal of Computational Biology. 2000; 7(1/2):203-214.
- Biller S, Chan LMA, Simchi-Levi, D ve Swann, J. Dynamic Pricing and The Direct-To-Customer Model in The Automotive Industry", Electronic Commerce Research. 2005; 5(2):309-334.
- Liu L. Solving 0-1 Knapsack Problems by Greedy Method and Dynamic Programming Method", Advanced Materials Research. 2011; 282:570-573.
- Gorski J, Paquete L, ve Pedrosa F. Greedy Algorithms for A Class of Knapsack Problems With Binary Weights, Computers & Operations Research. 2012; 39: 498-511.
- Winston WL. Operations Research Applications and Algorithms, Canada: Brooks/Cole Cengage Learning, 2014.
- Özkan Ş. Yöneylem Araştırması Nicel Karar Teknikleri, İstanbul: Nobel Akademik Yayıncılık, 1999.
- Durmuş B. Tamsayılı Programlamada Klasik ve Greedy Sezgisel Algortima Sonuçlarının Karşılaştırılması, Yüksek Lisans Tezi, Muğla Sıtkı Koçman Üniversitesi, Fen Bilimleri Enstitüsü, Muğla, 2018.
- Bakır MA. ve Altunkaynak B. Tamsayılı Programlama Teori Modeller ve Algoritmaları, Ankara: Nobel Yayın Dağıtım, 2003.