Multistage Adaptive Robust Binary Optimization: Uncertainty Set Lifting versus Partitioning through Breakpoints Optimization

Abstract

Two methods for multistage adaptive robust binary optimization are investigated in this work. These methods referred to as binary decision rule and finite adaptability inherently share similarities in dividing the uncertainty set into subsets. In the binary decision rule method, the uncertainty is lifted using indicator functions which result in a nonconvex lifted uncertainty set. The linear decision rule is further applied to a convexified version of the lifted uncertainty set. In the finite adaptability method, the uncertainty set is divided into partitions and a constant decision is applied for each partition. In both methods, breakpoints are utilized either to define the indicator functions in the lifting method or to partition the uncertainty set in the finite adaptability method. In this work, we propose variable breakpoint location optimization for both methods. Extensive computational study on an illustrating example and a larger size case study is conducted. The performance of binary decision rule and finite adaptability methods under fixed and variable breakpoint approaches is compared.

Keywords

• adaptive optimization
• decision rule
• scenario tree
• uncertainty set
• lifting
• robust optimization