In bin packing problems, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used. It is a combinatorial NP-hard problem.
The Reduction Method of Martelo and Toth in the paper Martelo, S., and Toth, P. (1990) "Lower bounds and reduction procedures for the bin packing problem", Discrete Applied Mathematics, 22:59-70, is an excellent heuristic method for finding very good solutions to the problem quite fast. Also, special-purpose Genetic Algorithms for bin packing are presented in Falkenauer E. (1998) "Genetic Algorithms and Grouping Problems", Wiley (also fast).
Now, the bin-packing problem, as well as its close relatives number-partitioning, knapsack, and equal-piles, are known to exhibit "phase-transitions", meaning that depending on the characteristics of the distribution of the objects' sizes and the capacity of the bins, it may be either very easy to find an optimal solution (because there are many and nicely distributed), or else it can take truly exponential time to find one (of the very few) optimal solutions, but this is only relevant if you want the exact optimal solution.
There are also methods based on the observations of Karmarkar & Karp for number partitioning (so-called "Complete-Anytime Algorithm" by Korf, he had a paper published in the journal Artificial Intelligence) that can be suitably modified for bin packing.
A much older reference for fast (low complexity) polynomial approximation algorithms is from founding father of CS David Johnson "Fast Algorithms for Bin Packing" (the reference dates back from 1974). And a much more recent reference is
Lewis, R. (2009), "A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing", Computers and Operations Research 36 (7): 2295–2310.
You may also read the wikipedia entry for more references...
The Reduction Method of Martelo and Toth in the paper Martelo, S., and Toth, P. (1990) "Lower bounds and reduction procedures for the bin packing problem", Discrete Applied Mathematics, 22:59-70, is an excellent heuristic method for finding very good solutions to the problem quite fast. Also, special-purpose Genetic Algorithms for bin packing are presented in Falkenauer E. (1998) "Genetic Algorithms and Grouping Problems", Wiley (also fast).
Now, the bin-packing problem, as well as its close relatives number-partitioning, knapsack, and equal-piles, are known to exhibit "phase-transitions", meaning that depending on the characteristics of the distribution of the objects' sizes and the capacity of the bins, it may be either very easy to find an optimal solution (because there are many and nicely distributed), or else it can take truly exponential time to find one (of the very few) optimal solutions, but this is only relevant if you want the exact optimal solution.
There are also methods based on the observations of Karmarkar & Karp for number partitioning (so-called "Complete-Anytime Algorithm" by Korf, he had a paper published in the journal Artificial Intelligence) that can be suitably modified for bin packing.
A much older reference for fast (low complexity) polynomial approximation algorithms is from founding father of CS David Johnson "Fast Algorithms for Bin Packing" (the reference dates back from 1974). And a much more recent reference is
Lewis, R. (2009), "A General-Purpose Hill-Climbing Method for Order Independent Minimum Grouping Problems: A Case Study in Graph Colouring and Bin Packing", Computers and Operations Research 36 (7): 2295–2310.
You may also read the wikipedia entry for more references...
Thanks Ioannis Christou for your kind answer However, my problem is not an exert Bin Packing Problem. It is a kind of bin packing problem with some extra constrains. Such as, if an item is placed in a Bin 'A', all other available items can't put into bin 'A", only a subset of other items can put in bin 'A' those satisfy a constrain 'C'. This constrain 'C' is depend on the item(s) those are already in Bin 'A'. I looking for a GA to solve this special Bin Packing problem.
If you want to apply GAs, then you should definitely read chapter 7 of Falkenaouer's book "Genetic Algorithms and Grouping Problems", as I mentioned. The constraints that you mention might be used in the assignment phase where an object is about to be added to a bin (where a feasibility check will decide whether to allow the operation or not); nevertheless, the reduction method of Martello and Toth now no longer seems applicable as it cannot take into account the constraints on what subsets are allowed and what are not (BTW, this problem as you phrase it now, has more similarities with the Line-Balancing Problem, where precedence constraints dictate what can go in a workstation (bin) and what not).
Personally I didn't examine the bin packing problem, but I came across many papers that present successful implementation of swarm algorithms for this kind of issue (e.g., http://www.sciencedirect.com/science/article/pii/S037722170700567X). Generally swarm algorithms are considered to be faster than GA so maybe you should try with them.
maybe the following link and paper are useful to solve the bin packing problem:
Article A Logarithmic Additive Integrality Gap for Bin Packing
maybe the following link can help you :
Article Recent advances on two-dimensional bin packing problems
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence