Optimization taking infinitely long

Got a report from @trader-payne that

With the below config and the current binaries, the allocation optimizer will run for an indefinitely long time

id = "0x3f74870f80ff7449fe4c6ff257da5fa72734c970"
network_subgraph_endpoint = "https://api.thegraph.com/subgraphs/name/graphprotocol/graph-network-arbitrum"
max_allocations = 999
whitelist = []
blacklist = []
frozenlist = []
pinnedlist = []
allocation_lifetime = 28
gas = 0
min_signal = 100
verbose = true
num_reported_options = 2
execution_mode = "actionqueue"
opt_mode = "fast"

By changing opt_mode to "optimal", the optimizer behavior is not deterministic

with high max_allocation (999), the optimizer can run for a long time
with max_allocation being smaller (150), optimizer can return quickly or fail with Tried to allocate more stake than is available

We should make improvements that bounds the optimization runtime -> for ideas, check the shape of signal for top 999 subgraphs on Arbitrum

Observed indeterministic result operating on this set of files allocation.csv indexer.csv network.csv subgraph.csv

One fix is to filter out NaN values from allocated results

for x in sum(xs; dims=1)
        isnan(x) || x ≤ σmax || error("Tried to allocate more stake than is available $(x) </= $(σmax)")
    end

But we should figure out why is NaN returned in the first place

Also note that the available stake fails due to x being double of σmax (1.834530930339968e7 </= 9.17265465169984e6)

For some real number N, for all k > N, optimizek will return infeasible results

sum(xs; dims = 1) = [2.36152938e7 2.36152937e7 2.3615293700000003e7 2.3615293799999997e7 2.36152936e7 2.36152936e7 2.36152934e7 2.36152935e7 2.36152935e7 2.36152934e7 2.36152933e7 2.36152932e7 2.36152931e7 2.36152932e7 2.3615293e7 2.36152931e7 2.36152931e7 2.36152928e7 2.36152931e7 2.36152927e7 2.36152929e7 2.36152925e7 2.36152926e7 2.36152929e7 2.36152926e7 2.3615292700000003e7 2.36152926e7 2.36152923e7 2.36152924e7 2.36152925e7 2.36152922e7 2.3615292299999997e7 2.36152919e7 2.36152923e7 2.36152921e7 2.3615291599999998e7 2.3615291699999996e7 2.36152921e7 2.36152921e7 2.3615292099999998e7 2.3615291699999996e7 2.36152916e7 2.36152917e7 2.36152916e7 2.3615291700000003e7 2.36152915e7 2.3615291700000003e7 2.36152914e7 2.3615290799999997e7 2.36152912e7 2.3615291300000004e7 2.3615291199999996e7 2.3615291200000003e7 2.36152912e7 2.36152911e7 2.3615291299999997e7 2.3615291099999998e7 2.36152915e7 2.36152909e7 2.3615290799999997e7 2.36152911e7 2.36152909e7 2.3615289999999996e7 2.3615290699999996e7 2.36152906e7 2.3615290700000003e7 2.36152905e7 2.36152906e7 2.36152906e7 NaN NaN NaN NaN NaN 4.977077774238013e-309 NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN NaN -1.908026540346257e291 -6.520110662023887e295 9.605646529158622e307 2.3385812164148918e299 3.454168996612607e299 -1.949070513474421e289 3.974126e-318 4.710995e-318 5.987186e-318 3.0084651902552006e277 NaN 6.969777680648553e-306]

opt works after fixes in https://github.com/graphprotocol/allocation-optimizer/commit/c5596fdfd3f9d051ecd68285bbd986610d2cd83c , https://github.com/graphprotocol/allocation-optimizer/commit/4438cf56851d9a4e154a60013e12b89b128bd644, https://github.com/graphprotocol/allocation-optimizer/commit/8e4f8a0b87a67ac115879b04d5f63d0912c4ed79

graphprotocol / allocation-optimizer

Optimization taking infinitely long #41