bin packing
in [Programming SQL]
|
From: --CELKO-- on 24 Oct 2009 18:17 >> Thanks for the tip. I found the Martello-Toth book online, including their FORTRAN code. I am studying it now. If it leads to an improved SQL Server implementation, I will let the world know. << I did not know it was on line! And I have not found my original copy. I remember the FORTRAN as a nightmare with lots of GOTOs that I could not convert to Structured code in Turbo Pascal. Yes, please keep posting. It is a useful thing to have in an RDBMS toolbox.
From: --CELKO-- on 24 Oct 2009 18:42 A related problem is finding the best subset summation. Given a multi- set of positive weights w[i] and a target value, W, find the subset(s) that is closest to but does not exceed W. The obvious checks are 1) When ALL w[i] > W, there is no answer 2) When SUM(w) = W, there is one answer the whole multi-set 3) When SUM(w) > W, there is at least one answer I am interested because I have a Manufacturing client who runs into this in his machine shop when he has to cut raw materials. How can we cut off some of the desired lengths, so that as little as possible of this raw material is left over?
From: Michael Coles on 31 Oct 2009 23:39 For those that are interested, the authors have made the ebook available for free through the Universit� di Bologna, where one of the authors is (or was?) employed: http://www.or.deis.unibo.it/knapsack.html -- Thanks Michael Coles SQL Server MVP Author, "Expert SQL Server 2008 Encryption" (http://www.apress.com/book/view/1430224649) ---------------- "Gert-Jan Strik" <sorrytoomuchspamalready(a)xs4all.nl> wrote in message news:4AE2FF38.9F2DF23A(a)xs4all.nl... > Thanks for the tip. I found the Martello-Toth book online, including > their FORTRAN code. I am studying it now. If it leads to an improved SQL > Server implementation, I will let the world know. > > -- > Gert-Jan > SQL Server MVP > > > --CELKO-- wrote: >> >> 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?
From: Gert-Jan Strik on 9 Nov 2009 18:43 --CELKO-- wrote: > > >> Thanks for the tip. I found the Martello-Toth book online, including their FORTRAN code. I am studying it now. If it leads to an improved SQL Server implementation, I will let the world know. << > > I did not know it was on line! And I have not found my original > copy. I remember the FORTRAN as a nightmare with lots of GOTOs that > I could not convert to Structured code in Turbo Pascal. > > Yes, please keep posting. It is a useful thing to have in an RDBMS > toolbox. I have looked at the Martello-Toth theories. It is interesting, particularly if the set is small, and the programming language is a 3rd generation language. For SQL and/or big sets, the approach is pretty much useless. But who knows, I might change my mind in a year or so... Anyway, the stuff did trigger me, because there is a rather big difference between the situation where most "packages" are less than half the bin size, and situations where a large percentage of packages are larger than half the bin size. The (best) solution I wrote is very good for the first situation, but not particularly good for the second situation. IMO, the latest addition to the series ( http://www.xs4all.nl/~gertjans/sql/binpacking/solution6.html ) changes that... So if you are ready for big chunks of code, then read and enjoy. -- Gert-Jan SQL Server MVP
From: --CELKO-- on 10 Nov 2009 13:12
>> So if you are ready for big chunks of code, then read and enjoy. << Right now I am swimming in small chunks of code :) I am working on the fourth edition of SQL FOR SMARTIES right now. Let's see if I can get your stuff into the book. I just spoke at PASS and I am now at SQL Connections; I cannot do anything until I get home. |