In-Development TradeDangerous: power-user trade optimizer

eyeonus

E
I feel I should clarify that the solution isn't brute force, as it does indeed take amount of credits into account as well, but I didn't feel that was important in my explanation.

As to the limiting, I did suggest having profit per ton be a limiting factor, as it only "locks up" when it gets down to the least profitable of ~20+ items. The problem I saw with that was figuring out what a good limit would be, as it would not be good to have a fixed number, as that would either hurt the commanders with less money for being too large, or that of commanders with more money for being too small.

So, it seems to me like having it be in proportion to the total credits is the way to go, but what proportion? And should it rise and fall relative to the total credits linearly or geometrically?

I kind of wonder what the singing banana would think of this?
(Numberphile people will get my reference, I'm sure.)
 
Last edited:

eyeonus

E
As far as an alternate algorithm, my simple fit from a few posts ago would work, I think. Just to reiterate so no one has to go searching through the posts:
Step 1: Get list of items sorted in highest profit - lowest profit order. (Already done.)
Step 2: Fill hold with as much of item1 as possible based on the limiting factors of hold size, supply amount, and available credits.
Step 3: If there is space in the hold and money available, repeat Step 2 with item2, item3, etc. until either the hold is filled or the commander is too poor to buy more.

In the case where credits are high enough not to be a limiting factor, this will always produce the best route, and faster than the current algorithm.
It will almost definitely be sub-par when money is a limiting factor, but I don't know if it would be sub-par as in this produces a route that is 98% as good as "fastFit", or as in a route that is 35% as good. I also have no idea how to figure that out other than testing, so you mathematicians might want to step up if you do know how to not need to test.
 
Last edited:

Avi0013

Avi0013
eyeonus said:
As far as an alternate algorithm, my simple fit from a few posts ago would work, I think. Just to reiterate so no one has to go searching through the posts:
Step 1: Get list of items sorted is highest profit - lowest profit order. (Already done.)
Step 2: Fill hold with as much of item1 as possible based on the limiting factors of hold size, supply amount, and available credits.
Step 3: If there is space in the hold and money available, repeat Step 2 with item2, item3, etc. until either the hold is filled of the commander is too poor to buy more.

In the case where credits are high enough not to be a limiting factor, this will always produce the best route, and faster than the current algorithm.
It will almost definitely be sub-par when money is a limiting factor, but I don't know if it would be sub-par as in this produces a route that is 98% as good as "fastFit", or as in a route that is 35% as good. I also have no idea how to figure that out other than testing, so you mathmaticians might want to step up if you do know how to not need to test.
Click to expand...
Isn't that equivalent to what I did by commenting out the recursion (lines 674—691) and adding the following at 674?
Code: 
cr -= loadCostCr
cap -= maxQty
if cr <= 0 or maxQty <= 0:
    break

Also, obsessed as I am, I have successfully compiled a slightly modified version of BOUKNAP.c and called it from Python using ctypes. I DO NOT THINK we should be doing that, I'd much prefer the approximate solution to the unrestricted universe which we are discussing (specifically rounding down the Danztig optimum for the LBKP). I'm sorry, I'm just having too much fun researching this[wacko]

Tromador said:
Oxymoron :)
Click to expand...

It is faster than his "brute force" algorithm which is an exhaustive enumeration which will never finish in anything remotely like a real example!
 

Avi0013

Avi0013
eyeonus said:
In the case where credits are high enough not to be a limiting factor, this will always produce the best route, and faster than the current algorithm.
It will almost definitely be sub-par when money is a limiting factor, but I don't know if it would be sub-par as in this produces a route that is 98% as good as "fastFit", or as in a route that is 35% as good. I also have no idea how to figure that out other than testing, so you mathematicians might want to step up if you do know how to not need to test.
Click to expand...

We'll have to test. The dimensionality of the question we're dealing with is such that I don't think any guess can be made outside that the greedy solution is usually "closer" to optimal than further. We'll have to compare.

@eyeonus, May I suggest two options? Compare the loop-based approximation with a limited (3?) recursion operation with the original.
 

MarkAusten

MarkAusten
I think that the algorithm as written is not correct as my feeble attempts to see what it going on seem to imply that the recursive calls are being carried out far too often.

Using the Timbarichs/Vaucouleurs refinery to Jeterait/Isaev Settlement route which yielded a profitable trade list of 22 items as follows. This data is a few data old. as it is my test data set.

Code: 
Item                                    Profit Supply 
Industrial Materials/Insulating Membrane 1742  1
Metals/Gallium                           1143  6
Metals/Gold                              1067  6
Metals/Uranium                           932   9
Metals/Lithium                           930  14
Metals/Silver                            907  20
Industrial Materials/Semiconductors      896   3
Textiles/Conductive Fabrics              794   4
Metals/Tantalum                          731  65
Metals/Beryllium                         685   4
Metals/Palladium                         633   1
Industrial Materials/Superconductors     580   2
Metals/Indium                            443  48
Chemicals/Liquid Oxygen                  413   9
Metals/Titanium                          407  48
Metals/Cobalt                            399 107
Textiles/Synthetic Fabrics               219  11
Industrial Materials/Polymers            198 156
Metals/Copper                            123  38
Chemicals/Hydrogen Fuel                   58  63
Chemicals/Surface Stabilisers             48  60
Metals/Aluminium                          20 213

The recursive call should only continue until the point at which no items remain to add to the cargo and still do not fill the max cargo required.

For the route listed above and the current algorithm, starting at the 14th item and adding the rest of the items only totals 705 tons so there is no point in dealing with the rest of the list since it will never profit more than anything calculated so far.

This is not happening, the recursive calls are being made thousands of times. The number of times this method is called should be 14 for this route and no more and this is where the error lies.

I think!
 
Last edited:

Avi0013

Avi0013
Tromador said:
And that is a good summary of the problem. Computing a solution in n-dimensional space is never going to be trivial or quick.
Click to expand...

Here's a toy example I'm playing with. Six commodities.
Profit = (1, 6, 7, 8, 12, 20)
Supply = (12, 10, 8, 7, 9, 3)
Cost = (1, 3, 6, 9, 11, 15)

Assume at least 50 capacity (not multiple constraints for now) and 150 credits.

The efficiency (gain per ton) is: (1, 2, 1.167, 0.889, 1.091, 1.333) so our ordering is 2 --> 6 --> 3 --> 5 --> 1 --> 4

The greedy/Dantzig/LKBP solution is fill up from most efficient down: (0, 10, 8, 0, 2, 3) as 10 * 3 + 3 * 15 + 8 * 6 + 2 * 11 = 145 < 150 but adding another item 5 gets us to 156 credits.

The gain for the LKBP is 10 * 6 + 3 * 20 + 8 * 7 + 2 * 12 = 200

The actual BKP solution is (0, 10, 7, 0, 3, 3) for a profit of 205.

So selling one item 3, having 11 left over which all could be spent on an extra item 5 for a profit increase of 12 - 7 = 5.

What I'm seeing trying these is that for these simple cases, the LKBP is pretty close to the (I)BKP (e.g 200 vs 205) and that the perturbations are few. But my toy cases may not be realistic. @eyeonus, any way I could get a sample of actual data to play with? :)
 

Avi0013

Avi0013
MarkAusten said:
Firstly I think that the algorithm as written is not correct as my feeble attempts to see what it going on seem to imply that the recursive calls are being carried out far too often. Secondly there should be a way to arrange the items list so that as soon as a maximum profit is found the rest of the items can be ignored.

Possibly.

At the moment the items list is sorted by profit for 1 ton as Cr/ton descending and then cost per ton ascending and I don't think that this is optimal since it does not take into account the quantity available. I think that list should be sorted by total profit (Cr * qty / ton) in descending order so that the items that give the biggest total profit are at the top. In this way if the list has 2000 items of Hydrogen at 40 Cr / ton and 5 imperial slaves at 13,000 cr/ton then the hydrogen would be listed first since 2000*40 (80,000) is greater than 13000*5 (65,000).

At the moment the list would show the Imperial Slaves before the Hydrogen since 13,000 > 40.

The first pass would start at the first item and attempt to fill the hold in the current fashion. At the end of that iteration the total profit of the items in the hold is noted. Then the algorithm starts wit the second item and tries the same thing. At the end of this pass, if the total profit of the items in the hold is less than or equal to the previous iteration, the loop is exited, otherwise this become the best profit so far and the loop starts from the third item and so on.

I haven't tried this yet so I may be completely wrong, so I'll try a route or two that I know have 20 or more items and see what happens, but I think you will see what I'm try to achieve.

[Edit] The first try of this algorithm worked. I used Timbarichs/Vaucouleurs refinery to Jeterait/Isaev Settlement which yielded a profitable trade list of 22 items. this data is a few data old. as it is my test data set.

Code: 
Item                                    Profit Supply Total profit
Metals/Tantalum                           731     65     47515
Metals/Cobalt                             399    107     42693
Industrial Materials/Polymers             198    156     30888
Metals/Indium                             443     48     21264
Metals/Titanium                           407     48     19536
Metals/Silver                             907     20     18140
Metals/Lithium                            930     14     13020
Metals/Uranium                            932      9      8388
Metals/Gallium                           1143      6      6858
Metals/Gold                              1067      6      6402
Metals/Copper                             123     38      4674
Metals/Aluminium                           20    213      4260
Chemicals/Liquid Oxygen                   413      9      3717
Chemicals/Hydrogen Fuel                    58     63      3654
Textiles/Conductive Fabrics               794      4      3176
Chemicals/Surface Stabilisers              48     60      2880
Metals/Beryllium                          685      4      2740
Industrial Materials/Semiconductors       896      3      2688
Textiles/Synthetic Fabrics                219     11      2409
Industrial Materials/Insulating Membrane 1742      1      1742
Industrial Materials/Superconductors      580      2      1160
Metals/Palladium                          633      1       633

The best profit for a 720 ton cutter starts with the first item and yields 223,438 Cr. Starting with the second item yields 182,508 Cr and with the third item for 158,229 but does not fill the hold.

However, that seems to be way too easy so I'll play with this for a while to see what happens.....
Click to expand...

Mark, this is great, but what are your starting credits, or can I assume that you the 928,245 cr you would need to buy out the entire stock?
 

Avi0013

Avi0013
MarkAusten said:
The best profit for a 720 ton cutter starts with the first item and yields 223,438 Cr. Starting with the second item yields 182,508 Cr and with the third item for 158,229 but does not fill the hold.
Click to expand...

The actual optimal allocation assuming sufficient credits would return a profit of 245,077 (approximation is around 9% lower) and is:
Code: 
[TABLE="width: 336"]
[TR]
[TD]Metals/Tantalum[/TD]
[TD="align: right"]65[/TD]
[/TR]
[TR]
[TD]Metals/Cobalt[/TD]
[TD="align: right"]107[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Polymers[/TD]
[TD="align: right"]156[/TD]
[/TR]
[TR]
[TD]Metals/Indium[/TD]
[TD="align: right"]48[/TD]
[/TR]
[TR]
[TD]Metals/Titanium[/TD]
[TD="align: right"]48[/TD]
[/TR]
[TR]
[TD]Metals/Silver[/TD]
[TD="align: right"]20[/TD]
[/TR]
[TR]
[TD]Metals/Lithium[/TD]
[TD="align: right"]14[/TD]
[/TR]
[TR]
[TD]Metals/Uranium[/TD]
[TD="align: right"]9[/TD]
[/TR]
[TR]
[TD]Metals/Gallium[/TD]
[TD="align: right"]6[/TD]
[/TR]
[TR]
[TD]Metals/Gold[/TD]
[TD="align: right"]6[/TD]
[/TR]
[TR]
[TD]Metals/Copper[/TD]
[TD="align: right"]38[/TD]
[/TR]
[TR]
[TD]Metals/Aluminium[/TD]
[TD="align: right"]45[/TD]
[/TR]
[TR]
[TD]Chemicals/Liquid Oxygen[/TD]
[TD="align: right"]9[/TD]
[/TR]
[TR]
[TD]Chemicals/Hydrogen Fuel[/TD]
[TD="align: right"]63[/TD]
[/TR]
[TR]
[TD]Textiles/Conductive Fabrics[/TD]
[TD="align: right"]4[/TD]
[/TR]
[TR]
[TD]Chemicals/Surface Stabilisers[/TD]
[TD="align: right"]60[/TD]
[/TR]
[TR]
[TD]Metals/Beryllium[/TD]
[TD="align: right"]4[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Semiconductors[/TD]
[TD="align: right"]3[/TD]
[/TR]
[TR]
[TD]Textiles/Synthetic Fabrics[/TD]
[TD="align: right"]11[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Insulating Membrane[/TD]
[TD="align: right"]1[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Superconductors[/TD]
[TD="align: right"]2[/TD]
[/TR]
[TR]
[TD]Metals/Palladium[/TD]
[TD="align: right"]1[/TD]
[/TR]
[/TABLE]
 
Last edited:

Tromador

Tromador
223k vs 245k is 9% difference - which in my book makes it worth only 9% more processing time. If it takes much longer, it's not worth it, take the 223k and move on to the next trade.
 

Avi0013

Avi0013
Using the "proper" LKBP algorithm you get 244,464 and the difference is only 0.3%!! Note the LKBP algorithm means you just order the items in terms of efficiency (gain/cost) and fill up in order. No recursion or anything.

Code: 
 [TABLE]
[TR]
[TD="class: xl67"]Item[/TD]
[TD="class: xl67"]Profit[/TD]
[TD="class: xl67, width: 64"]Cost[/TD]
[TD="class: xl67, width: 64"]AvgCost[/TD]
[TD="class: xl67, width: 64"]Buying[/TD]
[TD="class: xl67, width: 64"]Supply[/TD]
[TD="class: xl67, width: 64"]Total[/TD]
[TD="class: xl67, width: 69"]price/cost[/TD]
[TD="class: xl67, width: 98"]Taken[/TD]
[TD="class: xl67, width: 78"]Optimal[/TD]
[/TR]
[TR]
[TD]Chemicals/Liquid Oxygen[/TD]
[TD="align: right"]413[/TD]
[TD="align: right"]159[/TD]
[TD="align: right"]167[/TD]
[TD="align: right"]572[/TD]
[TD="align: right"]9[/TD]
[TD="align: right"]3717[/TD]
[TD="align: right"]2.5974843[/TD]
[TD="align: right"]9[/TD]
[TD="align: right"]9[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Semiconductors[/TD]
[TD="align: right"]896[/TD]
[TD="align: right"]458[/TD]
[TD="align: right"]812[/TD]
[TD="align: right"]1354[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]2688[/TD]
[TD="align: right"]1.9563319[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]3[/TD]
[/TR]
[TR]
[TD]Chemicals/Hydrogen Fuel[/TD]
[TD="align: right"]58[/TD]
[TD="align: right"]32[/TD]
[TD="align: right"]90[/TD]
[TD="align: right"]90[/TD]
[TD="align: right"]63[/TD]
[TD="align: right"]3654[/TD]
[TD="align: right"]1.8125[/TD]
[TD="align: right"]63[/TD]
[TD="align: right"]63[/TD]
[/TR]
[TR]
[TD]Metals/Cobalt[/TD]
[TD="align: right"]399[/TD]
[TD="align: right"]232[/TD]
[TD="align: right"]629[/TD]
[TD="align: right"]631[/TD]
[TD="align: right"]107[/TD]
[TD="align: right"]42693[/TD]
[TD="align: right"]1.7198276[/TD]
[TD="align: right"]107[/TD]
[TD="align: right"]107[/TD]
[/TR]
[TR]
[TD]Textiles/Synthetic Fabrics[/TD]
[TD="align: right"]219[/TD]
[TD="align: right"]135[/TD]
[TD="align: right"]154[/TD]
[TD="align: right"]354[/TD]
[TD="align: right"]11[/TD]
[TD="align: right"]2409[/TD]
[TD="align: right"]1.6222222[/TD]
[TD="align: right"]11[/TD]
[TD="align: right"]11[/TD]
[/TR]
[TR]
[TD]Textiles/Conductive Fabrics[/TD]
[TD="align: right"]794[/TD]
[TD="align: right"]572[/TD]
[TD="align: right"]561[/TD]
[TD="align: right"]1366[/TD]
[TD="align: right"]4[/TD]
[TD="align: right"]3176[/TD]
[TD="align: right"]1.3881119[/TD]
[TD="align: right"]4[/TD]
[TD="align: right"]4[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Polymers[/TD]
[TD="align: right"]198[/TD]
[TD="align: right"]171[/TD]
[TD="align: right"]115[/TD]
[TD="align: right"]369[/TD]
[TD="align: right"]156[/TD]
[TD="align: right"]30888[/TD]
[TD="align: right"]1.1578947[/TD]
[TD="align: right"]156[/TD]
[TD="align: right"]156[/TD]
[/TR]
[TR]
[TD]Metals/Lithium[/TD]
[TD="align: right"]930[/TD]
[TD="align: right"]1147[/TD]
[TD="align: right"]1402[/TD]
[TD="align: right"]2077[/TD]
[TD="align: right"]14[/TD]
[TD="align: right"]13020[/TD]
[TD="align: right"]0.8108108[/TD]
[TD="align: right"]14[/TD]
[TD="align: right"]14[/TD]
[/TR]
[TR]
[TD]Metals/Titanium[/TD]
[TD="align: right"]407[/TD]
[TD="align: right"]597[/TD]
[TD="align: right"]914[/TD]
[TD="align: right"]1004[/TD]
[TD="align: right"]48[/TD]
[TD="align: right"]19536[/TD]
[TD="align: right"]0.681742[/TD]
[TD="align: right"]48[/TD]
[TD="align: right"]48[/TD]
[/TR]
[TR]
[TD]Metals/Uranium[/TD]
[TD="align: right"]932[/TD]
[TD="align: right"]2199[/TD]
[TD="align: right"]2388[/TD]
[TD="align: right"]3131[/TD]
[TD="align: right"]9[/TD]
[TD="align: right"]8388[/TD]
[TD="align: right"]0.423829[/TD]
[TD="align: right"]9[/TD]
[TD="align: right"]9[/TD]
[/TR]
[TR]
[TD]Metals/Copper[/TD]
[TD="align: right"]123[/TD]
[TD="align: right"]462[/TD]
[TD="align: right"]441[/TD]
[TD="align: right"]585[/TD]
[TD="align: right"]38[/TD]
[TD="align: right"]4674[/TD]
[TD="align: right"]0.2662338[/TD]
[TD="align: right"]38[/TD]
[TD="align: right"]38[/TD]
[/TR]
[TR]
[TD]Metals/Gallium[/TD]
[TD="align: right"]1143[/TD]
[TD="align: right"]4525[/TD]
[TD="align: right"]4666[/TD]
[TD="align: right"]5668[/TD]
[TD="align: right"]6[/TD]
[TD="align: right"]6858[/TD]
[TD="align: right"]0.2525967[/TD]
[TD="align: right"]6[/TD]
[TD="align: right"]6[/TD]
[/TR]
[TR]
[TD]Metals/Silver[/TD]
[TD="align: right"]907[/TD]
[TD="align: right"]3816[/TD]
[TD="align: right"]4359[/TD]
[TD="align: right"]4723[/TD]
[TD="align: right"]20[/TD]
[TD="align: right"]18140[/TD]
[TD="align: right"]0.2376834[/TD]
[TD="align: right"]20[/TD]
[TD="align: right"]20[/TD]
[/TR]
[TR]
[TD]Metals/Tantalum[/TD]
[TD="align: right"]731[/TD]
[TD="align: right"]3393[/TD]
[TD="align: right"]3543[/TD]
[TD="align: right"]4124[/TD]
[TD="align: right"]65[/TD]
[TD="align: right"]47515[/TD]
[TD="align: right"]0.2154436[/TD]
[TD="align: right"]65[/TD]
[TD="align: right"]65[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Insulating Membrane[/TD]
[TD="align: right"]1742[/TD]
[TD="align: right"]9772[/TD]
[TD="align: right"]9927[/TD]
[TD="align: right"]11514[/TD]
[TD="align: right"]1[/TD]
[TD="align: right"]1742[/TD]
[TD="align: right"]0.1782644[/TD]
[TD="align: right"]1[/TD]
[TD="align: right"]1[/TD]
[/TR]
[TR]
[TD]Metals/Gold[/TD]
[TD="align: right"]1067[/TD]
[TD="align: right"]8342[/TD]
[TD="align: right"]9207[/TD]
[TD="align: right"]9409[/TD]
[TD="align: right"]6[/TD]
[TD="align: right"]6402[/TD]
[TD="align: right"]0.127907[/TD]
[TD="align: right"]6[/TD]
[TD="align: right"]6[/TD]
[/TR]
[TR]
[TD]Chemicals/Surface Stabilisers[/TD]
[TD="align: right"]48[/TD]
[TD="align: right"]479[/TD]
[TD="align: right"]466[/TD]
[TD="align: right"]527[/TD]
[TD="align: right"]60[/TD]
[TD="align: right"]2880[/TD]
[TD="align: right"]0.1002088[/TD]
[TD="align: right"]60[/TD]
[TD="align: right"]60[/TD]
[/TR]
[TR]
[TD]Industrial Materials/Superconductors[/TD]
[TD="align: right"]580[/TD]
[TD="align: right"]6046[/TD]
[TD="align: right"]6137[/TD]
[TD="align: right"]6626[/TD]
[TD="align: right"]2[/TD]
[TD="align: right"]1160[/TD]
[TD="align: right"]0.0959312[/TD]
[TD="align: right"]2[/TD]
[TD="align: right"]2[/TD]
[/TR]
[TR]
[TD]Metals/Beryllium[/TD]
[TD="align: right"]685[/TD]
[TD="align: right"]7522[/TD]
[TD="align: right"]7595[/TD]
[TD="align: right"]8207[/TD]
[TD="align: right"]4[/TD]
[TD="align: right"]2740[/TD]
[TD="align: right"]0.0910662[/TD]
[TD="align: right"]4[/TD]
[TD="align: right"]4[/TD]
[/TR]
[TR]
[TD]Metals/Indium[/TD]
[TD="align: right"]443[/TD]
[TD="align: right"]5300[/TD]
[TD="align: right"]5376[/TD]
[TD="align: right"]5743[/TD]
[TD="align: right"]48[/TD]
[TD="align: right"]21264[/TD]
[TD="align: right"]0.0835849[/TD]
[TD="align: right"]48[/TD]
[TD="align: right"]48[/TD]
[/TR]
[TR]
[TD]Metals/Aluminium[/TD]
[TD="align: right"]20[/TD]
[TD="align: right"]310[/TD]
[TD="align: right"]300[/TD]
[TD="align: right"]330[/TD]
[TD="align: right"]213[/TD]
[TD="align: right"]4260[/TD]
[TD="align: right"]0.0645161[/TD]
[TD="align: right"]46[/TD]
[TD="align: right"]45[/TD]
[/TR]
[TR]
[TD]Metals/Palladium[/TD]
[TD="align: right"]633[/TD]
[TD="align: right"]10901[/TD]
[TD="align: right"]12243[/TD]
[TD="align: right"]11534[/TD]
[TD="align: right"]1[/TD]
[TD="align: right"]633[/TD]
[TD="align: right"]0.0580681[/TD]
[TD="align: right"]0[/TD]
[TD="align: right"]1[/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD="class: xl66"]Items[/TD]
[TD="align: right"]720[/TD]
[TD="align: right"]720[/TD]
[/TR]
[TR]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD][/TD]
[TD="class: xl66"]Profit[/TD]
[TD="class: xl65, align: right"]244,464[/TD]
[TD="class: xl65, align: right"]245,077[/TD]
[/TR]
[/TABLE]
 
Last edited:

Tromador

Tromador
Avi0013 said:
Using the "proper" LKBP algorithm you get 244,464 and the difference is only 0.3%!! Note the LKBP algorithm means you just order the items in terms of efficiency (gain/cost) and fill up in order. No recursion or anything.
Click to expand...

Functionally that comes down to 1 ton of cargo, which is completely irrelevant in game terms. Nobody, I mean but nobody is going to analyse that and complain it's wrong.
From a computation time perspective, whats the difference? (obviously we all have varying processor power so it's not a perfect metric, but anyway).
 

eyeonus

E
Avi0013 said:
Isn't that equivalent to what I did by commenting out the recursion (lines 674—691) and adding the following at 674?
Code: 
cr -= loadCostCr
cap -= maxQty
if cr <= 0 or maxQty <= 0:
    break
Click to expand...

No. what you did makes it fill the hold with item1 up to the max of supply of item1 or credit affordability, and then loop through all the other items to see if filling the hold up to the max of supply or credit affordability with them yields more profit, which only happens in the case where item1 doesn't have enough supply to fill the hold. Because of all the things you didn't do I pointed out, it will never return more than one item.
 
Last edited:

eyeonus

E
Avi0013 said:
We'll have to test. The dimensionality of the question we're dealing with is such that I don't think any guess can be made outside that the greedy solution is usually "closer" to optimal than further. We'll have to compare.

@eyeonus, May I suggest two options? Compare the loop-based approximation with a limited (3?) recursion operation with the original.
Click to expand...

loop-based approximation? You mean my simpleFit?

Yeah I can do that, the code would be pretty easy to write. Give me a couple hours, though, I just woke up.
 
Last edited:

eyeonus

E
Avi0013 said:
@eyeonus, any way I could get a sample of actual data to play with? :)
Click to expand...

Don't you have TD installed? The database contains all the data. Run 'trade.py export -T StationItem' and you'll end up with the entirety of the listings in the database in the data folder in a file called "StationItem.csv".
 

Avi0013

Avi0013
Tromador said:
Functionally that comes down to 1 ton of cargo, which is completely irrelevant in game terms. Nobody, I mean but nobody is going to analyse that and complain it's wrong.
From a computation time perspective, whats the difference? (obviously we all have varying processor power so it's not a perfect metric, but anyway).
Click to expand...

Agreed.

eyeonus said:
No. what you did makes it fill the hold with item1 up to the max of supply of item1 or credit affordability, and then loop through all the other items to see if filling the hold up to the max of supply or credit affordability with them yields more profit, which only happens in the case where item1 doesn't have enough supply to fill the hold. Because of all the things you didn't do I pointed out, it will never return more than one item.
Click to expand...

Doh! Doh! Doh! I keep forgetting that. Thanks!

eyeonus said:
loop-based approximation? You mean my simpleFit?

Yeah I can do that, the code would be pretty easy to write. Give me a couple hours, though, I just woke up.
Click to expand...

Cool. I'll have a general question in a different post, as if you're willing, I'd like you to try and implement the LBKP loop(s), or I may just piggyback off of your code. Safer than doing it on my own!

eyeonus said:
Don't you have TD installed? The database contains all the data. Run 'trade.py export -T StationItem' and you'll end up with the entirety of the listings in the database in the data folder in a file called "StationItem.csv".
Click to expand...
True, but as a lazy son-of-a-gun, I prefer to have the data I want to work with spoon-fed to me which would be as Mark posted earlier: Item, Cost, Profit, Supply. Which, of course is "trade.py trade FROM TO" so I should stop being so lazy! Thanks!
 

eyeonus

E
MarkAusten said:
I think that the algorithm as written is not correct as my feeble attempts to see what it going on seem to imply that the recursive calls are being carried out far too often.

Using the Timbarichs/Vaucouleurs refinery to Jeterait/Isaev Settlement route which yielded a profitable trade list of 22 items as follows. This data is a few data old. as it is my test data set.

Code: 
Item                                    Profit Supply 
Industrial Materials/Insulating Membrane 1742  1
Metals/Gallium                           1143  6
Metals/Gold                              1067  6
Metals/Uranium                           932   9
Metals/Lithium                           930  14
Metals/Silver                            907  20
Industrial Materials/Semiconductors      896   3
Textiles/Conductive Fabrics              794   4
Metals/Tantalum                          731  65
Metals/Beryllium                         685   4
Metals/Palladium                         633   1
Industrial Materials/Superconductors     580   2
Metals/Indium                            443  48
Chemicals/Liquid Oxygen                  413   9
Metals/Titanium                          407  48
Metals/Cobalt                            399 107
Textiles/Synthetic Fabrics               219  11
Industrial Materials/Polymers            198 156
Metals/Copper                            123  38
Chemicals/Hydrogen Fuel                   58  63
Chemicals/Surface Stabilisers             48  60
Metals/Aluminium                          20 213

The recursive call should only continue until the point at which no items remain to add to the cargo and still do not fill the max cargo required.

For the route listed above and the current algorithm, starting at the 14th item and adding the rest of the items only totals 705 tons so there is no point in dealing with the rest of the list since it will never profit more than anything calculated so far.

This is not happening, the recursive calls are being made thousands of times. The number of times this method is called should be 14 for this route and no more and this is where the error lies.

I think!
Click to expand...
The maximum number of recursive calls "fastFit" will do grows pretty fast, because each iteration of each loop at each recursion level might call another recursion.

For a station with 4 items for sale:
Code: 
0,                 1,                 2,                 3
|                  |                  |                  |
1,    2,    3      2,    3            3                  4
|     |     |      |     |            |
2,3   3     4      3,    4            4
| |   |            |
3 4   4            4
|
4

If we don't count the recursions that immediately exit due to having an offset larger than the total (the 4's in this example tree), it's 7 recursive calls.

Not counting the instant exits:
1 item = 0
2 items = 1
3 items = 3
4 items = 7
5 items = 15

That's looking like 2^n - 1 to me.
 
Last edited:

eyeonus

E
Added recursionLimitedFit and simpleFit fit functions to tradecalc. Pushed to my branch. Read the commit log, please.

EDIT: Oh yes, here's Mark's run with simpleFit:
Code: 
>python trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress
* Hop   1: .........1 origins
* Hop   2: .....1,519 origins .. 15,120-2,499,933cr gain, 21-3,472cr/ton
Orang/Bessel Gateway -> Orang/Bessel Gateway (score: 1647462.880436)

  Load from Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
      543 x Slavery/Imperial Slaves      14,325cr vs   17,539cr, 4 days vs 26 days
      177 x Legal Drugs/Wine                276cr vs    1,027cr, 4 days vs 26 days
    Expect to gain 1,878,129cr (2,608.51cr/ton)

  Load from Ju Shosi/De Lay Point (2.07Kls, BMk:N, Pad:L, Plt:Y, Shp:N, Out:Y, Ref:Y):
      628 x Weapons/Reactive Armour         833cr vs    2,815cr, 26 days vs 4 days
       92 x Weapons/Non-lethal Weapons      632cr vs    2,491cr, 26 days vs 4 days
    Expect to gain 1,415,724cr (1,966.28cr/ton)
  ----------------------------------------------------------------------------
Finish at Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 3,293,853cr (2,287cr/ton) => est 11,003,293,853cr total
(Took about 6 seconds per '=', on 1500+ origins, which is about 10 origins/second.)

(NOTE: I'm not using the server snapshot database, because it told me "sqlite3.DatabaseError: database disk image is malformed" when I tried, so instead I'm using the data from my testing environment, and I honestly don't know how old it is. (At most 4 days, though.))

EDIT: I should have probably mentioned that this is all using the new penalty formula I came up with, as well.

Same thing, latest data:
Code: 
>python trade.py run --fr="Orang/Bessel Gateway" --cap=720 --cr=11b --ly=24.73 --empty=37.61 --pad=L --hops=2 --jum=3 --loop --summary -vv --progress
* Hop   1: .........1 origins
* Hop   2: .....1,539 origins .. 5,040-2,981,520cr gain, 7-4,141cr/ton
Orang/Bessel Gateway -> Orang/Bessel Gateway (score: 1708820.401607)

  Load from Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y):
      720 x Slavery/Imperial Slaves      14,339cr vs   17,539cr, <1 hr vs 26 days
    Expect to gain 2,304,000cr (3,200cr/ton)

  Load from Ju Shosi/De Lay Point (2.07Kls, BMk:N, Pad:L, Plt:Y, Shp:N, Out:Y, Ref:Y):
      628 x Weapons/Reactive Armour         833cr vs    2,441cr, 26 days vs <1 hr
       92 x Weapons/Non-lethal Weapons      632cr vs    1,766cr, 26 days vs <1 hr
    Expect to gain 1,114,152cr (1,547.43cr/ton)
  ----------------------------------------------------------------------------
Finish at Orang/Bessel Gateway (89ls, BMk:N, Pad:L, Plt:N, Shp:Y, Out:Y, Ref:Y) gaining 3,418,152cr (2,373cr/ton) => est 11,003,418,152cr total
 
Last edited:

Avi0013

Avi0013
Great! Thank you.

You wrote:
When amount of credits isn't a limiting factor, this should produce the most profitable route 100% of the time.
Click to expand...

That's technically not true, and their is a counterexample in some of my previous posts. Using what Mark originally posted today, the "simpleFit" which is actually Dantzig's (inventor of simplex algorithm in linear programming) "greedy" algorithm which solves the Linear BKP (allowing fractions), shown here, is 0.3% suboptimal to the true BKP result shown here. My few experiments show that for most TD cases the difference remains really small.

Also, I'm glad you're sorting on profit and not profit/cost, as most of the time, the bigger constraint is capacity. Only in cases where the user does not have enough money to fill the hold (early on in the game, I reckon) would pivotting on profit/cost give a better result. That's the exception of users, not the rule.

Now off to download the new versions and do my best to beta test the living daylights out of them.
 

eyeonus

E
I said should.... So it's only 99.7% of the time. I'm okay with that.

Well, thank Oliver for that. The list gets passed in sorted on profit, with lower cost winning when profits are tied.

Oh yeah, that video that shows the thing never actually freezes, and hints as to why it's being so slow:
https://youtu.be/fkCjyXC1n2A
 
Last edited:
You must log in or register to reply here.
Back
Top Bottom