09112019, 01:47 AM

#1

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.



09112019, 03:17 AM

#2

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



09112019, 04:19 AM

#3

error reading drive A:
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.
__________________
"Never stop learning, because life never stops teaching"
Last edited by arnelgp; 09112019 at 09:46 AM.



09112019, 04:59 AM

#4

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 NPcomplete. 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:


09112019, 08:10 AM

#5

Happy Retired Curmudgeon
Join Date: Feb 2001
Location: Suburban New Orleans, LA, USA
Posts: 14,727
Thanks: 93
Thanked 1,714 Times in 1,587 Posts

Re: How to find all combinations within a constraint
This is similar to issues in queuing theory where the issue is getting a mix of jobs done according to certain criteria. The "weighted heterogeneous job mix" has been studied and it is as much a bear as any other I've ever seen.
Generally, in queuing theory, you can choose for the MOST jobs in a fixed time period, or you can choose for the jobs by maximum priority (cost, in your case), or you can choose for the FEWEST (but implicitly, biggest) jobs. And there are a few more variants for which some solutions are known.
The issue we have here is that you have multiple criteria, which makes it an incredibly complex process to optimize. It doesn't help that since it is essentially a combinatorics problem, the time it will take to solve it might easily become a factorial, and you claim 1800+ possible orders. I won't even try to compute 1800 factorial, but let's say it is a BIG number. That means that mathematically, a "perfect" solution MIGHT exist but it might literally take years to find it.
The usual way to approach this in realworld computing that I have seen relates to fixing a hard goal  say, always pick highest priority (price) or always pick biggest job (biggest volume, in your case). There IS a queuing theory solution for optimizing largest jobs AND priority, but usually that means that the second criterion is a tiebreaker for cases where the first criterion isn't enough to help you make a decision.
You need to better define your selection criteria. This will probably start with a query to provide order for your selections, but will almost certainly include some code issues. You also need to consider deciding on some strict statements about what would be acceptable as a solution. Like, how close do you have to come to your boundaries?
Another thing to consider is that the question, as asked, may literally be insoluble using most algorithms I know, because you want to have the top three solutions. But most computerbased solutions of this type will be a bit TOO highly predictable. I.e. you can run the solution three time. You'll get the same answer three times. There will be no best, secondbest, thirdbest solution. Which means what YOU want is to optimize the same load based on three different goals to see if they differ in results. Which sometimes they won't.
Side note: Thanks for that Wikipedia link, MajP!
Side note for other readers not up on their computational theory: In computational complexity theory, a problem is NPcomplete when it can be solved by a restricted class of brute force search algorithms and it can be used to simulate any other problem with a similar algorithm. (From Wikipedia.org)
__________________
I'm a certified grandpa (3 times now) and proud of it.
Retired over one year and survived being home all day with the wife. She must really love me.
If I have helped you, please either click the thanks or click the scales.



09112019, 05:13 PM

#6

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



09152019, 09:19 AM

#7

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 01 knapsack problem. A very good discussion is here.
https://www.dyclassroom.com/dynamic...apsackproblem
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/binpa...ofusedbins/
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.
Last edited by MajP; 10132019 at 09:13 AM.



10142019, 09:42 AM

#8

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) 01 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 01 Knapsack. Maximize the value in X knapsacks. This is a heuristic.



Thread Tools 

Display Modes 
Rate This Thread 
Linear Mode


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

