Theses Doctoral

Efficient Methods for Large-Scale Dynamic Optimization with Applications to Inventory Management Problems

Liu, Xujia

In this thesis, we study large-scale dynamic optimization problems in the context of inventory management. We analyze inventory problems with constraints coupling the items or facility locations in the inventory systems, and we propose efficient solutions that are asymptotically optimal or empirically near-optimal.

In Chapter 1, we analyze multi-item, single-location inventory systems with storage capacity limits which are formulated as both unconditional expected value constraints and unconditional probability constraints. We first show that problems with unconditional expected value constraints only can be solved to optimality through Lagrangian relaxation. Then, under an assumption on the correlation structure of the demands that is valid under most practical setting, we show that the original problem can be sandwiched between two other problems with expected value constraints only. One of these problems yields a feasible solution to the original problem that is asymptotically optimal as the number of items grows.

In Chapter 2, we consider the same problem but with conditional probability constraints, that impose limits on overflow frequency for every possible state in each period. We construct an efficient feasible solution in two steps. First, we solve an unconditional expected value constrained problem with reduced capacity. Second, in each period, given the state information, we solve a single-period convex optimization problem with a conditional expected value constraint. We further show that the heuristic is asymptotically optimal as number of items I grows. In addition, we design another efficient method for moderate values of I, which works empirically well in an extensive numerical study. Moreover, we extract key managerial insights from the numerical study which are critical to decision making in real business problems.

In Chapter 3, we analyze single-item, multi-location systems on inventory networks that can be described by directed acyclic graphs (DAG). We propose an innovative reformulation of the problem so that Lagrangian relaxation can still be applied, which, instead of decomposing the problem by facility location, aggregates the state information, leading to a tractable lower bound approximation for the problem. The Lagrange multiplier, which provides information on the value function from the lower bound dynamic program, is used in designing a feasible heuristic. An extensive numerical study is conducted which suggests that both the lower bound approximation and upper bound heuristic perform very well.


  • thumnail for Liu_columbia_0054D_17703.pdf Liu_columbia_0054D_17703.pdf application/pdf 1.49 MB Download File

More About This Work

Academic Units
Industrial Engineering and Operations Research
Thesis Advisors
Iyengar, Garud N.
Ph.D., Columbia University
Published Here
March 29, 2023