>would correspond to an optimization problem that would take a thousand years to solve on a modern desktop computer
If this really is so, then the problem is tractable nowadays - a thousand 2016 desktop computers years is something we could do multiple times a day with a modern supercomputer, so definitely feasible.
Same for data, modern networked devices could provide data of sufficient quality.
That being said, the big one is of course to find the function to optimize. I had an idea about this not long ago - the issue communists have with capitalism is that it has a class divide in production. So why not try this: all consumer goods must be sold on a pseudo-market. So, after production, a second algorithm sells the products at such a price that supply and demand is solved.
Using the prices determined by this market, one calculates the ratio of labour (time x complexity) and resources per dollar of price found when watching supply and demand, and the optimization system could be run so as to attempt to maximize the ratio of labour+resources/price.
This way, people will get what they want the most, and the system should optimize for the best way to make people work the least, which seems like the primary contradiction between an individual's work as producer and consumer.
Of course, there would still be quite a few inefficiencies, but given the fact that the Soviet economy was not that far from that of the US, it could be a net positive in pure economic output? Especially since this wouldn't suffer from any economic crises at all.
What would remain is a way to incentivize innovation, maybe somehow by including successful innovation into the labour price of a commodity?
Of course, outside of this, there would also be serious political issues with the necessary centralization for this, and you'd need to find a way to trust the economic calculation process.
All in all, this feels... much more tractable to accomplish than what I would've thought. Maybe even tractable enough that it could be, in theory, implemented today, given sufficient political will and a way to get the most competent people possible on it, which of course is far from a given.