On mixing sets arising in chance-constrained programming (Q2429465)

This article considers chance-constrained, mixed-integer programming problems with knapsack constraints. The first section outlines the background to this problem including the practical applications, survey of the literature and preliminary definitions of chance-constrained problems. The second section introduces mixing sets that are relevant to chance-constrained problems with a knapsack constraint and presents useful background properties of these sets. This is followed by a section containing the proposed valid inequalities for the mixing set with a cardinality constraint. The author also derives necessary and sufficient conditions for these inequalities to be facet defining for the convex hull defined by the solutions. A polynomial time, exact separation algorithm for these inequalities is also provided. The fourth section then describes an alternative, polynomial size, formulation for the same problem, which is based on disjunctive programming and is an improvement to the current non-polynomial formulation where the constraints can be separated in polynomial time. The results presented in the previous sections are extended in section 5, where the mixing set is combined with a knapsack constraint. Valid inequalities are provided and proven for this case too. The next section describes the problem of combining mixing sets using a blending approach with a cardinality or knapsack constraint, and a useful example of how the proposed alternative reformulation works in practice is given. This very interesting article concludes with a section containing the results of computational experimentation, consisting of lot-sizing problems solved in a branch-and-cut framework, which demonstrates the efficiency in using the proposed valid inequalities for this type of problems.