Title: A Transformation-Proximal Bundle Algorithm for Solving Large-Scale Multistage Adaptive Robust Optimization Problems,
Abstract: This paper presents a novel transformation-proximal bundle algorithm to solve
multistage adaptive robust mixed-integer linear programs (MARMILPs). By
explicitly partitioning recourse decisions into state decisions and local
decisions, the proposed algorithm applies affine decision rule only to state
decisions and allows local decisions to be fully adaptive. In this way, the
MARMILP is proved to be transformed into an equivalent two-stage adaptive
robust optimization (ARO) problem. The proposed multi-to-two transformation
scheme remains valid for other types of non-anticipative decision rules besides
the affine one, and it is general enough to be employed with existing two-stage
ARO algorithms for solving MARMILPs. The proximal bundle method is developed
for the resulting two-stage ARO problem. We perform a theoretical analysis to
show finite convergence of the proposed algorithm with any positive tolerance.
To quantitatively assess solution quality, we develop a scenario-tree-based
lower bounding technique. Computational studies on multiperiod inventory
management and process network planning are presented to demonstrate its
effectiveness and computational scalability. In the inventory management
application, the affine decision rule method suffers from a severe
suboptimality with an average gap of 34.88%, while the proposed algorithm
generates near-optimal solutions with an average gap of merely 1.68%.