Decision rule-based method in solving adjustable robust capacity expansion problem

We consider adjustable robust capacity expansion problems (ARCEPs), where decision makers have flexibility to dynamically expand the capacity after new demand information is observed. The prevalent method to solve these problems is to approximate the policy space of the problems via affine policies (also known as linear decision rules). Although this method enjoys computational tractability, it may not be worst-case optimal. In this paper, we first explore the structure of the optimal policy for ARCEPs and we verify that linear decision rules are not optimal for a general multi-facility case. We then investigate the special cases of the problem and show that linear decision rules are worst-case optimal for the single-facility single-customer case given some mild assumptions. Based on this result, we propose tractable lower bounds for the worst-case costs of the single-facility multi-customer case and the general multi-facility cases to measure the suboptimality of the upper bounds provided by the linear decision-rule based method. An elimination strategy based on the Fourier–Motzkin elimination is also proposed to improve the upper bounds. The numerical studies in this paper verify the performance of the proposed lower bounds and show that the elimination strategy can improve the upper bounds, even when a few variables are eliminated.