A typical example of a stochastic constraint problem is that of modeling portfolio optimization under the assumption that the portfolio return stochastically dominates a reference return, such as an index. This paper describes ways in which constraint-based ideas can be applied to stochastic optimization problems.

Crudely, stochastic domination of one variable by another means that the second variable can be expected to be larger than the first. There are two notions of stochastic dominance that are relevant here: first order and second order. Adding first-order dominance constraints to an optimization problem leads to a situation where the feasible region fails to be convex.

The paper describes a new relaxation of a first-order constrained optimization model obtained by using second-order stochastic domination (SSD). This relation has a convex feasible set. The authors derive a number of valid constraints for the problem, and generate disjunctive cuts that are valid for the relaxed problem. They further develop three heuristics for constructing feasible solutions. The methods are applied to a number of instances of the portfolio optimization problem. The authors’ SSD relaxation method is compared to the usual linear programming (LP) relaxation (which is obtained by introducing binary variables). The SSD relaxation shows a significantly smaller relative optimality gap, and at the same time is able to handle instances where the usual LP relaxation runs out of memory.

The efficacy of the three heuristics is also compared. The paper assumes familiarity with disjunctive cuts and the lift-and-project procedure. The details of the authors’ contribution are presented explicitly, so the paper can be fairly easily followed.