Skip to content

GKNAP: A Java and C++ package for solving the multidimensional knapsack problem

License

Notifications You must be signed in to change notification settings

shah314/gamultiknapsack

Repository files navigation

GKNAP: A Java and C++ package for solving the multidimensional knapsack problem

Shalin Shah

DOI badge DOI

A genetic algorithm implementation for the multidimensional knapsack problem. The multi-constraint (or multidimensional) knapsack problem is a generalization of the 0/1 knapsack problem. The multi-constraint knapsack problem has m constraints and one objective function to be maximized while all the m constraints are satisfied.

The implementation is similar to the one described in [Chu98], but its significantly different. It uses Lagrangian multipliers as constraint weights and compared to the paper, it finds close to optimum solutions much faster. (Convergence can be controlled using the parameters).

Please see this paper for a detailed description of the algorithm.

Cite this work

@article{shah2019gknap,
  title={GKNAP: A Java and C++ package for solving the multidimensional knapsack problem},
  author={Shah, Shalin},
  journal={Journal of Open Source Software},
  volume={4},
  number={42},
  pages={1756},
  year={2019}
}
Usage
The usage of this code base is to just compile the code and run it on the command line.
The code will output the solution found, the value of the objective function and 
the chosen items for the knapsack. The code requires a weing formatted file or an orlib formatted file.
The weing formatted files are available here.
The orlib formatted files are available here (used by P.C.Chu and J.E.Beasley).
The orlib formatted files are available here which are named mknapcb1.txt, mknapcb2.txt and so on.
Please note that these files contain multiple instances, so to run the algorithm, 
please use any one of the instances.

The distributions of the files are quite different between orlib and weing. 
If the algorithm is stuck, please increase Constants.DIFF_TOLERANCE on line 31 of GeneticAlgorithm.java.

The format of all files is described here.

Java implementation
I tested the code using JDK 1.8, but any JDK should work fine. 
If the code does not compile, please open an issue. 

Compile the Java code and then run GeneticAlgorithm.

javac *.java
java GeneticAlgorithm filename format

(The file name contains the instance in weing or orlib format)
(The format is either weing or orlib)
Example: 
java GeneticAlgorithm data.DAT weing

C++ implementation
The code was tested on a Mac with gcc version 8, downloaded using homebrew. 
If the code does not compile, please open an issue.
Compile the C++ code and then run the executable.

g++ cmultiknapsack.cpp
./a.out filename format

(The file name contains the instance in weing or orlib format)
(The format is either weing or orlib)
Example: 
./a.out data.DAT weing

(Please remove all comments and other extraneous text from data.DAT)
(See the tests directory for testcpp.sh and testjava.sh for an example run)

Dependencies
The code has no other dependencies. A JDK or a gcc compiler is all that is required.

Using the code as an API
If you want to use the code as an API call from your own code:
Java: In GeneticAlgorithm.java, please see the main method.
C++: In the C++ code, please see the main method.

The benchmark instances are available here. They have the following format:

 //This is the WEING1.DAT data file plus some comments, that are NOT part of the problem instance.
 
 2 28 // 2 knapsacks, 28 objects
 1898 440 22507 270 14148 3100 4650 30800 615 4975
 1160 4225 510 11880 479 440 490 330 110 560
 24355 2885 11748 4550 750 3720 1950 10500 // 28 weights
 600 600 // 2 knapsack capacities
 45 0 85 150 65 95 30 0 170 0
 40 25 20 0 0 25 0 0 25 0
 165 0 85 0 0 0 0 100 // #1 constr.
 30 20 125 5 80 25 35 73 12 15
 15 40 5 10 10 12 10 9 0 20
 60 40 50 36 49 40 19 150 // #2 constr.
 
 141278 // optimum value

The comments beginning with "//" are only for the purpose of explaining the format. Please remove all comments before running the algorithm.

The algorithm was run on a few benchmark instances:

Instance Optimum Found - Best Found - Worst Time (s)
Weing1 141278 141278 141278 0
Weing2 130883 130883 130883 1
Weing3 95677 95677 95677 1
Weing4 119337 119337 119337 0
Weing5 98796 98796 98796 0
Weing6 130623 130623 130623 0
Weing7 1095445 1095445 1095445 2
Weing8 624319 624319 624319 4
Sento1 7772 7772 7772 1
Sento2 8722 8722 8722 0
Weish01 4554 4554 4554 0
Weish02 4536 4536 4536 0
Weish03 4115 4115 4115 0
Weish04 4561 4561 4561 0
Weish05 4514 4514 4514 0
Weish06 5557 5557 5557 0
Weish07 5567 5567 5567 0
Weish08 5605 5605 5605 0
Weish09 5246 5246 5246 0
Weish10 6339 6339 6339 0
Weish11 5643 5643 5643 0
Weish12 6339 6339 6339 0
Weish13 6159 6159 6159 0
Weish14 6954 6954 6954 0
Weish15 7486 7486 7486 1
Weish16 7289 7289 7289 0
Weish17 8633 8633 8633 0
Weish18 9580 9580 9580 0
Weish19 7698 7698 7698 0
Weish20 9450 9450 9450 0
Weish21 9074 9074 9074 1
Weish22 8947 8947 8947 1
Weish23 8344 8344 8344 0
Weish24 10220 10220 10220 2
Weish25 9939 9939 9939 1
Weish26 9584 9584 9584 0
Weish27 9819 9819 9819 0
Weish28 9492 9492 9492 0
Weish29 9410 9410 9410 0
Weish30 11191 11191 11191 0
PB1 3090 3090 3076 9
PB2 3186 3186 3186 2
PB4 95168 95168 95168 1
PB5 2139 2139 2139 2
PB6 776 776 776 0
PB7 1035 1035 1035 0
HP1 3418 3404 3404 0
HP2 3186 3186 3186 4

References

[Ahuja00] “A greedy genetic algorithm for the quadratic assignment problem”, R. Ahuja, J. Orlin, A. Tiwari, Computers and Operations Research, vol. 27, issue 10 (Sept. 2000), 917--934, ACM (2000)

[Angeline95] “Adaptive and self-adaptive evolutionary computations”, P. Angeline, Computational Intelligence: A Dynamic Systems Perspective, IEEE press, 152—163 (1995)

[Coello02] “Theoretical and Numerical Constraint Handling Techniques used with Evolutionary Algorithms: A Survey of the State of the Art”, C. Coello, Computer Methods in Applied Mechanics and Engineering, 191 (11--12), 1245-1287, January 2002 (2002)

[Chu98] “A Genetic Algorithm for the Multidimensional Knapsack Problem”, PC Chu, JE Beasley, Journal of Heuristics, vol. 4, 6 —86 (1998)

[DeJong93] “On the state of evolutionary computation” K. De Jong and W. Spears, Proceedings of the Fifth ICGA, 618--623. Kaufmann, San Mateo, CA. (1993)

[Eshelman91] “The CHC adaptive search algorithm: How to have safe search when engaging in non-traditional genetic recombination”, L. Eshelman, Foundations of Genetic Algorithms, Morgan Kaufmann (1991)

[Goldberg89] “Genetic Algorithm in Search, Optimization and Machine Learning”, D. E. Goldberg, Addison Wesley publishing company, Massachusetts (1989)

[Gordon94] “A note on the performance of genetic algorithms on zero-one knapsack problems”, V. Gordon, A.P. Böhm, D. Whitley, Proceedings of the 1994 ACM symposium on Applied computing, 194--195 (1994)

[Greene00] “Partitioning sets with genetic algorithms”, W. Greene, Proceedings of the Thirteenth International Florida Artificial Intelligence Research Society Conference, 2000, AAAI press, 102—105 (2000)

[Grefen85] “Genetic algorithms for the traveling salesman problem”, J. Grefenstette, R. Gopal, B. Rosimaita, and D. V. Gucht, Proceedings of an International Conference on Genetic Algorithms and their Applications, pp. 160--168, Carnegie Mellon publishers (1985)

[Hill99] “A Monte-Carlo study of genetic algorithm initial population generation methods”, R. Hill, Proceedings of the 31st conference on winter simulation: Simulation---a bridge to the future - Volume 1, 1999, 543--547 (1999)

[Hinterding97] “Adaptation in Evolutionary Computation: A Survey”, R. Hinterding, Z. Michalewicz, A.E. Eiben, In Proc of the 4th IEEE Conf. on Evolutionary Computation (pp. 65-69) (1997)

[Holland75] “Adaptation in natural and artificial systems”, MIT press, Cambridge, Massachusetts (1975)

[Julstrom05] “Greedy, Genetic and Greedy Genetic Algorithms for the Quadratic Knapsack Problem”, B. Julstrom, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2005) vol. 1, 607—614 (2005)

[Julstrom95] “Very greedy crossover in a genetic algorithm for the traveling salesman problem”, B. Julstrom, Proceedings of the 1995 ACM Symposium on Applied Computing, 324--328 (1995)

[Khuri94] “The Zero/One Multiple Knapsack Problem and Genetic Algorithms”, S. Khuri, T. Back and J. Heitkoetter, Proceedings of the 1994 ACM Symposium on Applied Computing, 188---193, March 1994 (1994)

[Kirkpatrick83] “Optimization by simulated annealing”, S. Kirkpatrick, Science, Number 4598, 13 May 1983, volume 220, 4598, 671--680 (1983)

[Kotta98] “A Hybrid Genetic Algorithm for the 0-1 Multiple Knapsack Problem”, C. Kotta and J.M. Troya, Artificial Neural Networks and Genetic Algorithms 3, 251--255, Springer-Verlag 1998 (1998)

[Martello90] “Knapsack Problems Algorithms and Computer Implementations”, S. Martello and P. Toth, John Wiley and Sons (1990)

[Melikhov96] “Some new features in genetic solution of the traveling salesman problem”, K. Melikhov, Proceedings of ACEDC '96 PEDC, University of Plymouth, UK (1996)

[Miller93] “An Evaluation of Local Improvement Operators for Genetic Algorithms”, J. Miller, W. Potter, R. Gandham, C. Lapena, IEEE Transactions on Systems, Man and Cybernetics, vol. 23, number 5, 1340—1351 (1993)

[Pisinger05] “Where are the hard knapsack problems?”, D. Pisinger, Computers and Operations Research, vol. 32, No. 9 (September 2005), 2271—2284 (2005)

[Raidl98] “An Improved Genetic Algorithm for the Multiconstrained 0-1 Knapsack Problem”, G.R. Raidl, Evolutionary Computation Proceedings, 1998. IEEE World Congress on Computational Intelligence, 207—211, May 1998 (1998)

[Simes01] “An Evolutionary Approach to the Zero/One Knapsack Problem: Testing Ideas from Biology”, A. Simes, E. Costa, 5th International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA 2001), Prague, Czech Republic (2001)

[Smith96] “Self adaptation of mutation Rates in a Steady State Genetic Algorithm”, J. Smith, T. Fogarty, Proceedings of IEEE International Conference Evolutionary Computing ICEC ’96 (1996)

[Spears95] “Adapting Crossover in Evolutionary Algorithms”, W. Spears, Proceedings of 4th Annual Conf. on Evolutionary Computing, 367--384, (1995)

[Syswerda89] “Uniform crossover in genetic algorithms”, Proceedings of the 3rd international conference on genetic algorithms, Morgan Kaufman (1989)

[Whitley93] “Serial and Parallel Genetic Algorithms as Function Optimizers”, V. Gordon, L. Whitley, Proceedings of the 5th International Conference on Genetic Algorithms, 177--183, 1993 (1993)