More reforge strangeness;

Stat weights as the unholy thread (str 3.09, hit 0.78, haste 0.75, crit 0.62, mastery 0.24, expertise 0.66) hit cap of 961 and expertise cap of 781.

It tells me to leave my [Heart of Rage] unreforged, sacreficing 128 haste and my [Drape of Inimitable Fate] un-reforged as well, losing 50 expertise. Both of those together seem like a strange trade off, meaning you lose 128 haste (96 dps) and 50 expertise (33 dps) for 50 crit (31 dps) and 128 expertise (84.48 dps).

It seems to be trying too hard to get expertise for some reason. As I said in my post before, it leaves HoR un-reforged on some calculations, despite there never being a situation where you would want to do so.

currently cannot access the link to get to the simulator

My host seems to have a problem, my guild forum is also unavailable, I hope it will soon be back.

By the way, I have updated the sim, in the optimizer part. This should avoid the unreforged item when there is only one stat on it that is Hit or Expertise.

what about uploading it to a free file hoster for the time being?

Ok for the reforge, but what about the stats being completely wrong in the stats summary after import?

Simulated annealing will only give you an approximation and quadratic programming won't work because the function to be optimized is not quadratic (it isn't linear either, although that's closer). You probably want nonlinear integer programming.

I've been doing some work on a gear/gem/reforging/enchant optimizer in my spare time. Let's take the very simple case of gear alone, ignoring all other factors (gemming and reforging are essentially the same optimization problems). The question we have to answer is this: given multiple item choices for each slot and a set of weights for each stat, can we find the optimal combination of items more efficiently than enumerating every possible item set and calculating the result of multiplying the stat weights by the sum of the stats on the items in each set? The number of item sets is the product of the number of item options you have for each slot, so it's easy to see that this blows up really quickly given sixteen slots and multiple items in each. Reforging is worse; with something like 6 reforging options per item, you're looking at something like 2.8 trillion reforging possibilities, were you to take a naive approach (although you can easily cut this down by not considering reforging into sub-optimal secondary stats excluding hit/exp).

If not for the hit and expertise caps, we absolutely could beat enumerating them all -- because the item values could then be calculated independently. You could write a greedy algorithm that simply takes the item with the highest calculated score for each slot. Unfortunately this won't work, because the hit and expertise caps mean that item values can't be calculated independent of their set.

I spent a little time investigating solving this with 1-0 integer programming, as it is an instance of the set partitioning problem (by definition NP-Hard), but I don't think it is possible now. Even construction the decision matrix governing item inclusion in sets requires enumerating all sets and storing them in memory... The problem appears intractable. In the short-term, I'm going to implement a naive exhaustive search, which will give an optimum result, if inefficiently.

If you continue with this, I would recommend using a solver library, rather than attempting to roll your own algorithm. Try Microsoft Solver Foundation - Express Edition - Home. Intuition tells me that this should be solved with an integer programming formulation similar to set partitioning, but I can't figure out how to make it work.

Something like:
Variables:
one variable per piece of gear, takes 0-1 value to indicate its presence in the set with the multiplier being the calculated value of that piece of gear (in a minimization problem, this would be the cost)

Constraints: 16, one for each slot (input matrix)
for each gear slot:
(x1 xor x2 xor x3 xor ... xor xn) to ensure we select one and only one piece of gear per slot (rings and trinkets are treated as one slot since we do that combination before optimization)

Ah, you only need to store in-memory the best reforge set you've seen so far and the replace it when you get a better one. Don't generate all the reforging options sets and then make another pass over all of them to find the best one -- instead get the score of each item set as you create it, and dispose the object immediately unless it is better than your previous best. This way you only need to have memory allocated for two item sets at any time; the best one you've seen previously and the one you just generated.

The time complexity is still O(numReforgeOptionPerPiece ^ numPiecesReforged), but space complexity is constant.

Edit: It has occurred to me that 129 million sets might be too many to evaluate in a reasonable amount of time anyway. I'll implement this tomorrow night and let you know what kind of running time I get.

If anyone has experience with integer programming problems or optimization problems in general, send me a PM. I want to talk to you.

On the reforging, this problem is as Anathem pointed out.... the *optimal* reforge calculation will always run in non-polynomial time - ie take effing forever. If someone comes up with an efficient solution to finding the optimal setup... please let me know so I can jack your work, publish a paper and retire o0.

You have two choices:
1 - find the optimal setup, this *will* be an exhaustive search, you can try to optimize it... but its still exhaustive
2 - accept an approximate solution, that may or may not be identical to the optimal solution (local vs. global maxima).

Since our dataspace is finite, you *can* pre-compute optimal values for various gear combinations and store them... even then it will be huge unless you place limitations on storing, ie - only plate gear within 1 tier jump or something or you'll just explode the memory cost in a nasty nasty way.

What is the current big O value of the algorithm that runs the optimization?

delete

delete