How to find all combinations within a constraint

[NLindley7]

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.

 

[CJ_London]

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.

 

[arnelgp]

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.

 

[MajP]

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_Doc_Man]

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 real-world 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 tie-breaker 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 computer-based 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, second-best, third-best 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 NP-complete 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)

 

[Deleted member 147267]

cross posted
https://www.mrexcel.com/forum/micro...-find-all-combinations-within-constraint.html

 

[MajP]

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-programming/0-1-knapsack-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-packing-problem-minimize-number-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.

 

[MajP]

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.

 

[mjdemaris]

@MajP forgive me for reviving an old thread...

What does 'cube' relate to in this situation? Are we talking cubic feet or a box of some kind?

With my basic understanding so far...it sounds like this could be useful in determining how to optimize loading 53 foot trailers and pallets. I've been working on trying to lower our freight cost/order quantity ratio. I placed an order that was not optimal - meaning the quantity filling one pallet put it in a higher freight class and therefore increased the freight cost. By doing some simple math and asking our suppliers how many we could fit on one pallet to stay within a specified class, I was able to come up with a solution.

However, we are looking at purchasing more items from one supplier and attempting to optimize each pallet/truck load to minimize the freight cost ratio. In this case, there are at least five different sized boxes, and pallet size remains constant at 40 x 48 inches (I believe). So, in calculating freight class, multiply the 3 dimensions, then divide that product (cubic feet) by the weight. This gives you the density, which is then used to determine the class.

So, I am going to have a look-see at your knapsack app and try to determine how to use it for a pallet/trailer load. If successful, I may be able to modify it for a colleague to use to maximize trailer loads when shipping product out. (Currently done manually/eye-balling)

Mike

 

[MajP]

In this case these are perfectly square containers. Real world problems with different size boxes would be more complex. There are 2d Knapsack problems.

Containers Loading Optimization with Python

How can we use heuristic algorithms to find the right strategy to load a maximum number of pallets in a sea container?

towardsdatascience.com

or even 3d Knapsack problems

https://scholar.uwindsor.ca/cgi/viewcontent.cgi?article=5986&context=etd#:~:text=A%20three%2Ddimensional%20knapsack%20problem,of%20packed%20boxes%20is%20maximized.&text=A%20Mixed%20Integer%20Linear%20Programming,as%20vertical%20stability%20are%20considered.

Finding true optimal solutions is very hard. Finding very good solutions using heuristics can be "relatively" easy.
With that said, there is a ton of applications out there to do just this. You may be able to find some free or cheap code tailored to your exact needs.