Stochastic programming

Stochastic programming appeared with the numerical methods to simulate physical phenomenon. In fact, it's deeply linked with the computational abilities, which, up to recently, were really poor. As a consequence, we couldn't afford for a full resolution on our problem (even with a super-computer like Crays. It can be used anytime you can describe your problem as the minimization of an energy.

Imgine hanlding a physical system, in a initial state. The idea is to perform a random update of this state. You randomly pick up an element of your system and check toward which point it would evolve given the current state. If the system is on a lower energy state, then you perform the update, otherwise you perform the update according to a a priori given probability. And you iterate this procedure.

The classic example is the Monte-Carlo algorithm used for a set of magnetic particles. The current state is the knowledge of spin up/spin down for each particle. You pick up one of them, and you check if the change of spin would decrease or increase the global energy.

The stochastic programming has two main features - non intensive computing (at least, less than the full resolution) - avoid to be stuck in local minima (unstable state)