Physics computing - Napsack Problem

[noodnutt]

Hi all

I have a relatively functional Napsack code that works well in Excel and am hoping someone is familiar with the issue enough to assist me get it setup in access.

If you are not familiar with Napsacking, a brief lay explanation is imagine you have varying objects of differing size you need to pack into a napsack, you have and best fit all those items required into the space.

These are my items ( criteria )

Step. 1 - From: S
Step. 2 - To: N
Step. 3 - Where: HDC
Step. 4 - Max spots: 22
Step. 5 - Max Weight: 24,500

My end result I am looking for is; The code collects all records that meet Steps 1 to 3, then pair them up so that they match Steps 4 to 5, then assigns a value in snfRunNo Field.

Am really looking forward to your comments and any assistance or suggestions.

Big thanks in advance.
Mick.

[The Frog]

I'm intrigued. This looks quirky enough to actually be useful in the
real world. In order to move this to Access I think we would need to
see your logic in more detail. Is there a way you can share what
you've got? Is there a website that details the issue in the way
you've solved it?

--
Cheers

The Frog

[noodnutt]

Hey there Frog.

This principle is already in use in other databases.

The contract I work on gets its data from another company's database that uses an Optimiser which does relatively the same as this although it just matches customer to DC to a max of 22 spots.

Detail example:

LoadID_____PONo_____From_____To_____DC_____Spots_____Weight_____RunNo
111111 T1234 S N HDC 2 250
222222 T2345 S N HDC 20 22000
333333 T3456 S W LDC 22 24500

So in this example, the code would combine LoadID's 111111 & 222222 as they are both in the South heading North to the HDC and there spots do not exceed 22, and it equates to no more than 24,500kg's.

On average I get around 175 - 200 records totalling approx. 1500 spots a day that I have to compile into groups of 22 and 24 spots which could equate to around 85 - 90 loads to spread across my fleet.

The LoadID, PO and other fields are not so important, code needs to do repeat cycles to pair up and tag that combinations RunNo field with the same matching number so that when I select one of the runs I can see if it is in actual fact combined properly so I can then allocated it to a driver.

There will be variables that this code cannot foresee, specifically, 14 pallet Rigid Only access loads, Dropdeck Mezzanine floor loads which are different as with Hi-Cube which also get calculated differently.

Generally the From - To combinations are:

From To
S N
S W
W S
W N
N S
N W

And the combination of spots is anywhere from 1 to 24, and they can weight anything from 50kg's to 24,500kg's which is the max legal standard weight for a single Tri-axle trailer we can carry in my state.

Hope this is enough burley to get you nibbling and look deeper.

You can also check this link:

http://en.wikipedia.org/wiki/Knapsack_problem

It gives you a full overview of the principles of the Napsack Problem.

Looking forward to your thoughts.

Cheers
Mick.

[noodnutt]

And see what happens when you're tired @ 1.37am :)

Poor Old East seems to have missed out.

Neglected to include

From To
E W
E S
E N

Dóh..

Mick.

[David Hare-Scott]

You would need to do this in VBA. I suppose that already have, in which
case it ought to port from Excel to Access VBA quite well.

This problem is known for being computationally expensive, you may find that
as the amount of data increases you hit a wall were the time to get a result
becomes impossibly long. You have to either write a better algorithm or do
it in a compiled language on a faster machine, or both.

This is not a matter of presentation of data or data management (Access is
good at that) but one of computation. Why do you think transferring to
Access might be an advantage? If it works in Excel why port it?

For those who might be googling it is usually spelled 'knapsack problem'.

David

[noodnutt]

Hi David

The reason for the leap is merely an evolutionary step in which to consolidate many separate processes into a single self contained system.

Prior to my taking over this entire process, none were allowed to interfere with the prehistoric setup as per the head honcho's instructions. Time has a way of softening attitudes and I have been afforded some latitude in experimenting with slightly more modern thought processes.

With the above in mind, the following is the current flow path in our painful day.

I import an externally provided .txt file into my spreadsheet, do my thing, then export it into another spreadsheet where it gets converted to another format so that it can be imported into another worksheet that the Fleet Controller uses to monitor the movements and times.

Then, after he is finished, his spreadsheet is backed up into 2 different formats for the head office to pick apart.

To this day, I'm still like, WTF...

Back to your question: This will be totally separate so not porting from Excel, there will be no bridging it across the two programs.

As for the memory aspect sucking the life out of our stone-age network, no doubt that will be an issue, but! as it will only ever have to deal with chunks of approx 175 - 250 records per day, I'm not expecting super major issues.

The criteria will be that once it is paired and I commit it to a route and plan it, then it will be tagged as done by changing it's snfStatus = 2, so when the program runs again it won't bother looking at it again.

So to put it in the simplest If, Then, Else format it would be something like:

For Each Record
If snfStatus = 1 then
' run the Knapsack Code
Else
' move to the next record
End if
Next

It's all in the trying that makes it interesting.

Thanks again for your input David.

Cheers
Mick.

[The Frog]

Hi there,

Had a chance to explore the problem a bit now and my conclusion is
that your fastest way to move your processes to a relational database
like Access would be to do a code port for the calculation method you
have in Excel. You may have this as a mix of formulas on a worksheet
and vba in Excel, and this would probably be best IMO to be
constructed as a class in Access that can be instantiated then pass
in the values to crunch, and return a result. Encapsulation of the
solution logic I think will be very helpful here. It also means if
you need to reuse it or replace it you can do so quite easily without
having to refactor all your other code. Defining an interface for the
class is probably a good idea here too. Keep things to a standard.

Out of curiosity which version of the knapsack problem are you
solving for? Multi knapsack? Is this also being combined with the
traveling salesman problem?

--
Cheers

The Frog

[noodnutt]

Frog

I most certainly appreciate you investing your time in this, although I have absolutely no clue as to what you presented.

My Excel prowess is slightly higher than my Access skills and they are basic at best as I refer to reference text and NG's for many tasks.

This is not my code, and the guy who put it together is no longer working for the company that supplied this code, so I'm fairly certain I won't be infringing on any rights when I post it here.

You, or someone else maybe able to make sense of it and see how it can be translated into a comparable Access clone.

If it looks like being a monumental task I may just stick with the manual planning approach and scrap the semi-automated vision.

Cheers
Mick.

Sub KnapShack()

If MsgBox("Clear Existing?", vbYesNo) = vbYes Then
Range("AI6:AI5000").ClearContents
End If


'***** PHASE 1 - GROUP STRAIGHT 22's *****
grp = 1

'Find the DC
For rw = 6 To 50000

'skip already grouped lines
If Range("AI" & rw).Value <> "" Then
GoTo nextrw
End If

cDC = Range("K" & rw).Value
cZone = Range("Y" & rw).Value
cStack = Range("N" & rw).Value
cWeight = Range("O" & rw).Value

If cDC = "" Then Exit For

tStack = 22 - cStack
tWeight = 24500 - cWeight

If tStack = 0 Then
nrw = rw
GoTo release:
End If
'Look for best match
For nrw = 6 To 50000

If nrw = rw Then
GoTo nextnrw
End If

nDC = Range("K" & nrw).Value
NZone = Range("Y" & nrw).Value

If nDC = "" Then Exit For

If (nDC & NZone) = (cDC & cZone) Then

If Range("AI" & nrw).Value <> "" Then
GoTo nextnrw
End If

nStack = Range("N" & nrw).Value
nWeight = Range("O" & nrw).Value

If (nStack = tStack) And (nWeight < tWeight) Then
'FOUND
release:
Range("AI" & rw).Value = grp
Range("AI" & nrw).Value = grp
grp = grp + 1
Exit For
End If
End If
nextnrw:

Next nrw

Application.StatusBar = "Running Row " & rw

nextrw:

Next rw


'***** PHASE 2 - SUM UP COMBINATIONS *****
If MsgBox("Run Phase 2 (Closest Match)?", vbYesNo) = vbAbort Then GoTo ext:


'Find the DC
For rw = 6 To 50000

'skip already grouped lines
If Range("AI" & rw).Value <> "" Then
GoTo nextrw2:
End If

cDC = Range("K" & rw).Value
cZone = Range("Y" & rw).Value
cStack = Range("N" & rw).Value
cWeight = Range("O" & rw).Value

If cDC = "" Then Exit For

tStack = 22 - cStack
tWeight = 24500 - cWeight

If tStack = 0 Then
nrw = rw
GoTo release2
End If

'Look for best match
For nrw = 6 To 50000

If nrw = rw Then
GoTo nextnrw2:

End If

nDC = Range("K" & nrw).Value
NZone = Range("Y" & nrw).Value

If nDC = "" Then
grp = grp + 1
Exit For
End If

If (nDC & NZone) = (cDC & cZone) Then

If Range("AI" & nrw).Value <> "" Then
GoTo nextnrw2
End If

nStack = Range("N" & nrw).Value
nWeight = Range("O" & nrw).Value

If (nStack <= tStack) And (nWeight < tWeight) Then
'FOUND
release2:
Range("AI" & rw).Value = grp
Range("AI" & nrw).Value = grp
tStack = tStack - nStack

If tStack = 0 Then
grp = grp + 1
Exit For
End If

End If
End If
nextnrw2:

Next nrw

nextrw2:

Application.StatusBar = "Running Row " & rw

Next rw

ext:

End Sub

[David Hare-Scott]

You major task would be to replace all the Excel specific calls such as
Range(). If my understanding of Excel is still working these are used to
read values from sheets into variables and to write back the results.
Probably you need to open several recordsets to do this is Access VBA. But
first you need to design the underlying tables to store the data. It is
very importent here that you nail down in your understanding (if you haven't
already) the difference between locating data by its position in sheets and
by referring to table names, key values and field names. In the latter the
concept of data being "N-dimensional" is not very useful.

There are also some 'magic numbers' in the code such as 22; 24,5000; 50,000
that you need to understand. Probably these ought to be parameterised in
the function call or made into references to controls on a form depending on
what they do. Controlling your code through embedded unnamed constants is
*very* inflexible not to mention obscure.

The logically constructions such as For..Next, If ..Then...Else will
translate. I notice some Gotos which might be tidied up using Do... While,
Do...Until, Exit this or that. While tidying up some error management and
comments could be added so the next bloke working on the thing isn't in the
same situation. As it stands it is hard to follow the code and if it is
going to take three weeks to get a result you will have to apply the Vulcan
Nerve Pinch to stop it.

As for the efficiency or suitability of the algorithm I have no idea.

David

[noodnutt]

Hi David

Apologies for late reply.

No stress, I appreciate your thoughts.

I just have to get my brainbox unwrapped from Excel VB back into the world of Access VB.

With regards to the 'Magic Numbers' they are:

Max No of Spaces: 22
Max Weight: 24,500 Kg's

And with regards to the 50,000 it relates to the Row(Count) which I'm not sure why it was so high as I never saw anything closer than 300 rows of data.

Anyways, I have put it on the back-burner for a good while and am focusing in other areas now, will have another look at this down the line.

Thanks again

Cheers
Mick.

[Aikistan]

Must you use Access for this? Excel can do this with 0 code using the Solver Add-n. Sorry for the late reply.

Stan