bin packing
in [Programming SQL]
|
From: Gert-Jan Strik on 21 Oct 2009 12:32 For those interested, I have written a short series of articles on solving the bin packing problem. See http://www.xs4all.nl/~gertjans/sql/binpacking/intro.html -- Gert-Jan SQL Server MVP
From: --CELKO-- on 21 Oct 2009 22:42 >> For those interested, I have written a short series of articles on solving the bin packing problem. << I did a quick look tonight while babysitting; it seems to be cursors and loops -- things that are faster in procedural languages. If you have a copy of SQL FOR SMARTIES, look at Codd's T-JOIN and its solutions. The example is classrooms with (n) seats and (k) students in a class. It depends on a ordering. A proper SQL/RDBMS solution would give ALL valid answers. So if all items are of size one and all bins items are of capacity (n), then any bin can be filled with (n) items. This is a VERY large set of valid answers. Procedural code can stop with the first "near optimal" solution instead of all of them. A set-oriented language produces ALL answers. Oh, Good article!
From: TheSQLGuru on 22 Oct 2009 14:45 There are occassions in sql server where cursors are the most efficient mechanism to solve the problem. -- Kevin G. Boles Indicium Resources, Inc. SQL Server MVP kgboles a earthlink dt net "--CELKO--" <jcelko212(a)earthlink.net> wrote in message news:9668860f-c396-41a0-a36e-a4408e2a8768(a)z34g2000vbl.googlegroups.com... >>> For those interested, I have written a short series of articles on >>> solving the bin packing problem. << > > I did a quick look tonight while babysitting; it seems to be cursors > and loops -- things that are faster in procedural languages. If you > have a copy of SQL FOR SMARTIES, look at Codd's T-JOIN and its > solutions. The example is classrooms with (n) seats and (k) students > in a class. It depends on a ordering. > > A proper SQL/RDBMS solution would give ALL valid answers. So if all > items are of size one and all bins items are of capacity (n), then any > bin can be filled with (n) items. This is a VERY large set of valid > answers. > > Procedural code can stop with the first "near optimal" solution > instead of all of them. A set-oriented language produces ALL > answers. > > Oh, Good article!
From: Tony Rogerson on 22 Oct 2009 15:01 Rolling totals spring to mind. Tony. "TheSQLGuru" <kgboles(a)earthlink.net> wrote in message news:D7qdnfpkJacCOn3XnZ2dnUVZ_r-dnZ2d(a)earthlink.com... > There are occassions in sql server where cursors are the most efficient > mechanism to solve the problem. > > -- > Kevin G. Boles > Indicium Resources, Inc. > SQL Server MVP > kgboles a earthlink dt net > > > "--CELKO--" <jcelko212(a)earthlink.net> wrote in message > news:9668860f-c396-41a0-a36e-a4408e2a8768(a)z34g2000vbl.googlegroups.com... >>>> For those interested, I have written a short series of articles on >>>> solving the bin packing problem. << >> >> I did a quick look tonight while babysitting; it seems to be cursors >> and loops -- things that are faster in procedural languages. If you >> have a copy of SQL FOR SMARTIES, look at Codd's T-JOIN and its >> solutions. The example is classrooms with (n) seats and (k) students >> in a class. It depends on a ordering. >> >> A proper SQL/RDBMS solution would give ALL valid answers. So if all >> items are of size one and all bins items are of capacity (n), then any >> bin can be filled with (n) items. This is a VERY large set of valid >> answers. >> >> Procedural code can stop with the first "near optimal" solution >> instead of all of them. A set-oriented language produces ALL >> answers. >> >> Oh, Good article! > >
From: --CELKO-- on 22 Oct 2009 17:16
Wikipedia has a good intro article on the topic. The classic book is: Knapsack Problems: Algorithms and Computer Implementations (Wiley- Interscience Series in Discrete Mathematics and Optimization) by Silvano Martello and Paolo Toth (Paperback - Nov 1990) The bad news is that it is out of print and the price is so high I might sell my copy on EBay! They had FORTRAN programs that were fairly complicated. Today, the algorithm research has moved to modern languages with parallelism. The simple greedy FFD (First Fit Descending) algorithm works very well in the real world. Standardized packages were designed to fit into standardized bins for shipping so thing were meant to fit together. But when FFD fails, it can be really bad. This is not a good SQL problem and you need a constraint language with parallelism. Cursors will not help because they are not parallel. Strik did a nice job on the problem and kept the code simple (if he gets the Martello-Toth book he can translate their FORTRAN to T-SQL for more improvements); but the truth is that this not an SQL problem. Would you write an accounting package in ICON? |