Home Forum Contact

 Access World Forums How to find all combinations within a constraint
 Register FAQ Members List Social Groups Top Posters Search Today's Posts

 09-11-2019, 01:47 AM #1 NLindley7 Newly Registered User   Join Date: Sep 2019 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts How to find all combinations within a constraint I am after some code/advice for Access. I have a list of Order Numbers(Unique) and what cubic metres that each are, I also have a cost benefit per Order. I would like to run some code to be able to find every combination of Orders but within a given constraint of Cubic size (65Cube) to find the most cost effect mix of Orders in the minimum amount of results (Lowest Container Loads) So if I had for instance 9x PO's below, in this case due to them all being 20Cube, the minimum you could build would be 3 containers, but which combo would (not duplicating) output the highest cost benefit. 11111 20Cu £600 22222 20Cu £2,500 33333 20Cu £30,000 44444 20Cu £10,000 55555 20Cu £300 66666 20Cu £23,000 77777 20Cu £50,000 88888 20Cu £100 99999 20Cu £1,000 There are 84x Combinations in this case and top three would be: 333333 666666 777777 222222 444444 999999 111111 555555 888888 In the real case, there shall be 1800+ PO's and all of different cube.
 09-11-2019, 03:17 AM #2 CJ_London Super Moderator   Join Date: Feb 2013 Location: UK Posts: 11,347 Thanks: 40 Thanked 3,670 Times in 3,538 Posts Re: How to find all combinations within a constraint think you need to provide a more realistic example and expected result to take into account different cubages. for example if 111 was 5 cubes and same cost of £600 would that be placed in the first container because of cubage, or remain in the last container because of cost? And to be clear, from your example you are not trying to balance out cost so each container has roughly the same cost - you want a very expensive container and a cheaper container. __________________ CJ_London _______________________ A little thanks goes a long way. If you have found this post useful, please tick the thanks button
09-11-2019, 04:19 AM   #3
arnelgp

Join Date: May 2009
Location: somewhere out there
Posts: 8,569
Thanks: 68
Thanked 2,745 Times in 2,630 Posts
Re: How to find all combinations within a constraint

if you can give more sample (in xlxs) for me to further test.
on the attached, 2 queries.
qry_PO is simple select query.
qry_Combination uses a function to combine 3 po's from highest value to lowest.
Attached Files
 containerCombo.zip (41.5 KB, 4 views)

__________________
"Never stop learning, because life never stops teaching"

Last edited by arnelgp; 09-11-2019 at 09:46 AM.

 09-11-2019, 04:59 AM #4 MajP Newly Registered User   Join Date: May 2018 Location: USA baby Posts: 1,891 Thanks: 38 Thanked 572 Times in 539 Posts Re: How to find all combinations within a constraint This is known as a knapsack problem in combinatorial mathematics. It can be very difficult to solve if you have many different sizes. The problem is NP-complete. If all your sizes are 20 then we know the solution is three items and can be solved easily, but say you have sizes from 1cu to 60 cu. There may be solution sets with 1 item up to a solution sets with 60 items. Doing that in sql would likely not be doable in a reasonable amount of time, without writing code to write the queries. This can get very hard to compute. So more details would be needed on what you really have. https://en.wikipedia.org/wiki/Knapsack_problem
 The Following User Says Thank You to MajP For This Useful Post: The_Doc_Man (09-11-2019)
 09-11-2019, 05:13 PM #6 Micron AWF VIP   Join Date: Oct 2018 Location: Ontario, Canada Posts: 1,229 Thanks: 10 Thanked 231 Times in 219 Posts Re: How to find all combinations within a constraint
09-15-2019, 09:19 AM   #7
MajP
Newly Registered User

Join Date: May 2018
Location: USA baby
Posts: 1,891
Thanks: 38
Thanked 572 Times in 539 Posts
Re: How to find all combinations within a constraint

Although the OP does no longer seem interested, this is an interesting problem. So if anyone is interested here is a demo answering two questions, with a more realistic data set. My data set is about 5k items, with cost ranging from 5 to 10 (The cost could be anything cube, weight, money. The OP had cube). The value ranges from about 2k to 24k. And the capacity is 65 cube (although it is changeable on the form).

I did not really understand the OPs question, but here is two possible answers to two questions.
1) What is the most value you can pack into a crate limited to 65cube. I solved this using a 0-1 knapsack problem. A very good discussion is here.
https://www.dyclassroom.com/dynamic-...apsack-problem

In my code you run a single knapsack optimization and then the next time those already assigned items are not available. So if you click the run knapsack button three times you get the best optimization from the remaining items. This is not the same as doing a multiple knapsack problem. In that case ahead of time you determine how many knapsacks to fill for overall value. That problem is harder.

2) The second possible questions is what is the overall least amount of crates to fill. This is known as a binpacking optimization. My solution use a first fill heuristic algorithm and it is not guaranteed to be optimal. A good discussion is here
https://www.geeksforgeeks.org/bin-pa...-of-used-bins/
If you run the code it will fill 592 crates and the theoretical optimal is 581 (assumes all crates completely filled). Not bad. If I get time I will try to add an improving algorithm. It takes items from two or more bins and tries to swap them around to see if an improvement is possible.

Given that I will throw out a challenge. Using the data set, beat a single bin packed with a total value of > than \$191,052 and pack all items with less than 592 total bins.
Attached Files
 KnapSackBinPacking V3.accdb (908.0 KB, 7 views)

Last edited by MajP; 10-13-2019 at 09:13 AM.

10-14-2019, 09:42 AM   #8
MajP
Newly Registered User

Join Date: May 2018
Location: USA baby
Posts: 1,891
Thanks: 38
Thanked 572 Times in 539 Posts
Re: How to find all combinations within a constraint

In case anyone is interested I also added the multi knapsack algorithm. This algorithm answers the question if given items of different "weights" and "values" and X amount of knapsacks (bins), what is the overall maximum value you can place into the X bins.

If interested a very good resource for the family of knapsack problems is provided. The algorithms come from this resource.
http://www.or.deis.unibo.it/kp/KnapsackProblems.pdf
Someone scanned the whole 300 page book.

So the database demos three solutions to three questions
1) 0-1 Knapsack. Maximize the value in a single knapsack (bin). This is an exact solution using dynamic programming.
2) Binpack. Minimize the total number of bins to pack all items. This is a heuristic using first fill.
3) Multi 0-1 Knapsack. Maximize the value in X knapsacks. This is a heuristic.
Attached Files
 KnapSackBinPacking V7.accdb (992.0 KB, 6 views)

 Thread Tools Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Access World     Access World News     Site Suggestions     Introduce Yourself     The Watercooler Microsoft Access Discussion     General     Tables     Queries     Forms     Reports     Macros     Modules & VBA     Theory and practice of database design     Access Web Microsoft Access Reference     Access FAQs     Code Repository     Sample Databases     Microsoft Access Tutorials     Microsoft Access User Groups Apps and Windows     SQL Server     Crystal Reports     Visual Basic     VB.NET     Word     Excel     Web Design and Development         ASP and ASP.NET         PHP & MySQL     Windows     Other Software     Hardware Questions and Answers Non-Access Issues     Politics & Current Events     Debates     Gaming     Sports, Health & Fitness     Gadgets     Small Business

 Similar Threads Thread Thread Starter Forum Replies Last Post iaccess14 General 51 04-07-2014 05:27 AM scotthutchings Tables 1 03-11-2011 09:40 AM jesse Queries 6 01-19-2011 08:31 AM Bechert Tables 0 09-13-2006 08:02 PM Pauldohert SQL Server 0 07-26-2006 05:05 AM

All times are GMT -8. The time now is 10:48 PM.

 Microsoft Access Help General Tables Queries Forms Reports Macros Modules & VBA Theory & Practice Access FAQs Code Repository Sample Databases Video Tutorials Featured Forum post Sponsored Links