Shalizi's post also points out that if you relax any of the requirements, you can get answers much more quickly, and also notice that modern computers & algorithms run vastly faster. As a matter of fact, linear optimization is one of the best examples of progress:

Grötschel, an expert in optimization, observes that a benchmark production planning model solved using linear programming would have taken 82 years to solve in 1988, using the computers and the linear programming algorithms of the day. Fifteen years later – in 2003 – this same model could be solved in roughly 1 minute, an improvement by a factor of roughly 43 million.

(1988 is, incidentally, way after the cited short paper pointing out the impossibility of computing in time, IIRC.)

Given that CEV is all about extrapolating, making consistent, simplifying and unifying aggregate preferences, I wouldn't take linear programming as much more relevant to CEV as, say, various ruminations about NP or EXP-time.