The two biggest challenges in solving practical optimization problems are computational intractability, and the presenceof uncertainty: most problems are either NP-hard, or have incomplete input data whichmakes an exact computation impossible.Recently, there has been a huge progress in our understanding of intractability, based on spectacular algorithmic and lower bound techniques. For several pro ...