THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

SELECT Hints, Tips, Tricks FROM Hugo Kornelis WHERE RDBMS = 'SQL Server'

Bin packing part 4: The set-based disaster

This blog has moved! You can find this content at the following new location:

https://SQLServerFast.com/blog/hugo/2008/10/bin-packing-part-4-the-set-based-disaster/

Published Monday, October 27, 2008 2:28 AM by Hugo Kornelis

Attachment(s): ImEx4.zip

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Peso said:

October 27, 2008 3:45 AM
 

Hugo Kornelis said:

Hi Peso,

Apologies for the delayed response - and thanks for the link.

I didn't yet have time to cimpletely dig to the bottom of that query. I do see that it's for a related, but not the same problem. This query will find a combination of packages for a single bin, and find the one that comes as close to the size as possible (either above or below it). To use it for bin packing, one would have to change it so that it will not return combinations that exceed the specified size, and then add logic to remove the packages used from the list and then repeat for the next bin.

I plan to take a more detailed look at the approach taken later, when I have more time available. It looks interesting enough to warrant further study, so once more - thanks for the link!

Best, Hugo

October 31, 2008 7:58 AM
 

RBarryYoung said:

I am relieved to see that you have not fallen into the fallacy of binary thinking seen in so many Cursor vs. non-Cursor arguments.  Cursors and pure Set-based SQL are hardly the only two choices, particularly on SQL Server.  Both recursive CTE's and pseudocursors can solve a huge range of problems that are not tractable to set-based solutions and usually significantly faster than Cursors (though admittedly, the later has supportability questions).

But the obvious thing to try for a restricted scheduling type problem like this one is a more general purpose programming language instead of relying solely on a data management and modification language like SQL.  Using .Net code, whether client-based or SQLCLR based seems like the best bet.

November 3, 2008 9:49 AM
 

Peso said:

Yes. The algorithm was originally written for fetching exact sum only, but has been widened to get closest of undersum or oversum, if exact sum is not found.

The algorithm in the link is only a part of the complete problem, but it handles the core, to find the sum and which amounts that supports to the solution.

It will be a trivial task to update inventory and remove items found in the algorithm, and run the algorithm again.

I am looking forward to your investigations.

November 7, 2008 1:35 PM
 

Peso said:

November 22, 2008 5:20 AM
 

Peso said:

November 23, 2008 9:34 AM
 

Peso said:

If you change the last SELECT to this instead

SELECT theSum,

COUNT(*) AS theCount

FROM (

SELECT SUM(d.faceValue * ((v.number * d.maxItems / d.permCount) % d.maxItems)) AS theSum

FROM @Data AS d

INNER JOIN TallyNumbers AS v ON v.number <= @comb

GROUP BY v.number

HAVING SUM(d.faceValue * ((v.number * d.maxItems / d.permCount) % d.maxItems)) > 0

) AS d

GROUP BY theSum

ORDER BY COUNT(*) DESC,

theSum

You can see which sum you can combine the most times with original data.

In my case, I can see that the sum of 1550 can be combined for 800 different combinations.

November 23, 2008 9:44 AM
 

fred said:

when are you going to update your blog?

October 27, 2009 1:38 PM
 

cinahcaM madA said:

Going to have to second Fred's question. I just noticed that it's been a year to the day. Come on Hugo, surely you can come up with some topic to post about?

October 27, 2009 3:04 PM
 

Hugo Kornelis said:

And I'll third Fred's question.

The problem is not lack of topics - hell, I still have to finish this very series about bin packing, and the next part will be the most fun of them all!

The real problem is three-fold: A combination of (a) lack of spare time; (b) other interests that nibble away at what little spare time is left; and (c) a certain amount of blog-tiredness. I have not only not been wposting for a year, I've also not been reading any blogs for about half a year now.

The good news is that I have been kicking by own butt lately to resume blogging. And I have already done some prep work for the next post (though it's still far from finished). With still very little time to spare, I can't make any promises on an ETA for the next part, but I can assure you that it's still in the pipeline, and that I will finish it. One day.

Thanks for maintaining interest in my blog, even after such a long period of neglect from me.

October 27, 2009 5:26 PM
 

fred said:

No worries dude.....maybe you can hire a jr dba as an assistant. keep up the good work!

October 29, 2009 10:18 PM
 

Joey said:

Here ia another approach which is relatively fast

http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=80857

and also http://www.rapidpig.com

August 10, 2010 8:25 AM
 

SELECT Hints, Tips, Tricks FROM Hugo Kornelis WHERE RDBMS = 'SQL Server' said:

One of the most common techniques authors use to keep their readers interested is to leave them with

October 17, 2011 6:11 PM

Leave a Comment

(required) 
(required) 
Submit

About Hugo Kornelis

Hugo is co-founder and R&D lead of perFact BV, a Dutch company that strives to improve analysis methods and to develop computer-aided tools that will generate completely functional applications from the analysis deliverable. The chosen platform for this development is SQL Server. In his spare time, Hugo likes to visit the SQL Server newsgroups, in order to share and enhance his knowledge of SQL Server.
Privacy Statement