Go Back   Access World Forums > Microsoft Access Discussion > Modules & VBA

 
Reply
 
Thread Tools Rate Thread Display Modes
Old 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
NLindley7 is on a distinguished road
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.

NLindley7 is offline   Reply With Quote
Old 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
CJ_London is a glorious beacon of light CJ_London is a glorious beacon of light CJ_London is a glorious beacon of light CJ_London is a glorious beacon of light CJ_London is a glorious beacon of light
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
CJ_London is offline   Reply With Quote
Old 09-11-2019, 04:19 AM   #3
arnelgp
error reading drive A:
 
arnelgp's Avatar
 
Join Date: May 2009
Location: somewhere out there
Posts: 8,569
Thanks: 68
Thanked 2,745 Times in 2,630 Posts
arnelgp is just really nice arnelgp is just really nice arnelgp is just really nice arnelgp is just really nice arnelgp is just really nice
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
File Type: zip 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.
arnelgp is offline   Reply With Quote
Old 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
MajP has a spectacular aura about MajP has a spectacular aura about
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
MajP is offline   Reply With Quote
The Following User Says Thank You to MajP For This Useful Post:
The_Doc_Man (09-11-2019)
Old 09-11-2019, 08:10 AM   #5
The_Doc_Man
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
The_Doc_Man is a splendid one to behold The_Doc_Man is a splendid one to behold The_Doc_Man is a splendid one to behold The_Doc_Man is a splendid one to behold The_Doc_Man is a splendid one to behold The_Doc_Man is a splendid one to behold The_Doc_Man is a splendid one to behold
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 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)
__________________
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.
The_Doc_Man is offline   Reply With Quote
Old 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
Micron has a spectacular aura about Micron has a spectacular aura about
Re: How to find all combinations within a constraint

cross posted
https://www.mrexcel.com/forum/micros...onstraint.html
Micron is online now   Reply With Quote
Old 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
MajP has a spectacular aura about MajP has a spectacular aura about
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
File Type: accdb KnapSackBinPacking V3.accdb (908.0 KB, 7 views)


Last edited by MajP; 10-13-2019 at 09:13 AM.
MajP is offline   Reply With Quote
Old 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
MajP has a spectacular aura about MajP has a spectacular aura about
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
File Type: accdb KnapSackBinPacking V7.accdb (992.0 KB, 6 views)

MajP is offline   Reply With Quote
Reply

Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
How to violate a constraint? iaccess14 General 51 04-07-2014 05:27 AM
Constraint Problems scotthutchings Tables 1 03-11-2011 09:40 AM
constraint problem jesse Queries 6 01-19-2011 08:31 AM
DDL Constraint Syntax Bechert Tables 0 09-13-2006 08:02 PM
FK Constraint 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


Powered by vBulletin®
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
(c) copyright 2017 Access World