UC Irvine

Since its inception, Benders Decomposition (BD) has been successfully applied to a wide range of large-scale mixed-integer (linear) problems that lie at the heart of operations research and supply chain management. The inherent capacity of BD for exploiting the structural properties of problems with complicating variables has made it one of the most prominent exact algorithms for solving large-scale optimization problems. Over the years, BD has grown in its ability to solve a wide range of challenging problems including variants of facility location problems, supply chain and network design problems, scheduling and routing problems, healthcare operations, machine learning, and variants of stochastic programming problems among several other applications. This dissertation is structured into three research papers. First, we introduce a general acceleration technique for BD by introducing deepest Benders cuts. As an application of BD on problems arising in the transportation and logistics sector, we introduce efficient and novel implementations of BD for variants of hub location problems. We further analyze effects of uncertainty in demand and revenues in hub location problems and propose novel modelling and solution methods based on robust and stochastic optimization techniques.

The key element of BD is the derivation of Benders cuts, which are often not unique. In the first chapter, we introduce a novel unifying Benders cut selection technique based on a geometric interpretation of cut ``depth'', produce deepest Benders cuts based on 1p-norms, and study their properties. Specifically, we show that deepest cuts resolve infeasibility through minimal deviation from the incumbent point, are relatively sparse, and may produce optimality cuts even when classical Benders would require a feasibility cut. Leveraging the duality between separation and projection, we develop a Guided Projections Algorithm for producing deepest cuts while exploiting the combinatorial structure or decomposablity of problem instances. We then propose a generalization of our Benders separation problem that brings several well-known cut selection strategies under one umbrella. In particular, by establishing its connection to our method, we provide systematic ways of selecting the normalization coefficients in the Minimal Infeasible Subsystems method.We also provide general implementation guidelines, which are useful beyond the scope of this study. Finally, in our tests on facility location problems, we show deepest cuts often reduce both runtime and number of Benders iterations, as compared to other cut selection strategies; and relative to classical Benders, use 1/3 the number of cuts and 1/2 the runtime. As an application of accelerating Benders decomposition, we model capacity allocation decisions within profit maximizing hub location problems to satisfy demand of commodities from different market segments. We present a strong deterministic formulation of the problem and describe two exact algorithms based on a Benders reformulation to solve large-size instances of the problem. We show that the subproblems can be broken into smaller and simpler problems in two phases. We prove that the first phase can be efficiently solved using a cutting-plane algorithm. To produce strong cuts, we cast the second phase as a multi-objective optimization problem. We show that non-dominated solutions to the second phase can be obtained by either a set of continuous maximum weighted matching problems, or by a series of continuous knapsack problems in a sequential manner. We further enhance the performance of the algorithms by integrating improved variable fixing techniques. We evaluate the efficiency and robustness of the algorithms through extensive computational experiments. Computational results show that large-scale instances with up to 500 nodes and three demand segments can be solved to optimality, and that the proposed algorithms generate cuts that provide significant speedups compared to using Pareto-optimal cuts. The proposed two-phase methodology for solving the Benders subproblem as well as the variable fixing and acceleration techniques can be used to solve other discrete location and network design problems. Finally, we extend the deterministic model by considering uncertainty associated with the demand to develop a two-stage stochastic program. To solve the stochastic version, we develop a Monte-Carlo simulation-based algorithm that integrates a sample average approximation scheme with the proposed Benders decomposition algorithms. We then extend the models by simultaneously incorporating two sources of uncertainty including stochastic demand and uncertain revenue. To incorporate uncertain revenues into the problem, we use robust optimization techniques and investigate two particular cases including interval uncertainty and discrete scenarios. We formulate robust-stochastic models with a max-min profit criterion and a min-max regret objective for the former and latter cases, respectively. We enhance the Benders decomposition algorithms coupled with sample average approximation scheme by novel acceleration techniques. We also conduct extensive computational experiments to analyze the effects of uncertainty under different settings and compare the quality of the solutions obtained from different modeling approaches under different parameter settings. Computational results demonstrate the efficiency of the proposed algorithms and justify the need for embedding both sources of uncertainty in decision making to provide robust solutions.