H. Milton Stewart School of Industrial and Systems Engineering (ISyE)
http://hdl.handle.net/1853/6047
Industrial engineering (IE) and operations research (OR) are fields of study intended for individuals who are interested in analyzing complex systems, formulating abstract models of these systems, and solving them with the intention of improving system performance.2019-04-20T22:35:05ZModels and algorithms for dynamic real-time freight train re-routing
http://hdl.handle.net/1853/60774
Models and algorithms for dynamic real-time freight train re-routing
Parcham-Kashani, Alborz
This dissertation focuses on solving a train re-routing problem in a near real-time context for a freight train carrier operating over a large network. A holistic evaluation framework is developed using a time-space network model. Computational results using data from a class I railroad in the United States are used to determine the subset of problem instances that can be solved using the evaluation framework by systematically evaluating all solutions. Solving the remaining problem instances is addressed by developing two solution methodologies that leverage the evaluation framework: an optimization-based approach and a search-based heuristic approach. A further problem variant is also introduced where rail terminal processing rate is a non-constant function of the traffic at the rail terminal. The above approaches are extended to address the problem variant. Computational results are presented for a comprehensive set of problem instances created using data from a class I railroad in the United States. Results indicate the tractability of the optimization-based approach for large-scale instances, practical solution time with reasonable compute resources, as well as the robustness of solution quality to increases in the number of candidate trains. The solution time of the search-based heuristic approach is furthermore shown to be robust to increases in network traffic volume. The results are discussed in detail, along with implications for future research.
2018-11-09T00:00:00ZParcham-Kashani, AlborzThis dissertation focuses on solving a train re-routing problem in a near real-time context for a freight train carrier operating over a large network. A holistic evaluation framework is developed using a time-space network model. Computational results using data from a class I railroad in the United States are used to determine the subset of problem instances that can be solved using the evaluation framework by systematically evaluating all solutions. Solving the remaining problem instances is addressed by developing two solution methodologies that leverage the evaluation framework: an optimization-based approach and a search-based heuristic approach. A further problem variant is also introduced where rail terminal processing rate is a non-constant function of the traffic at the rail terminal. The above approaches are extended to address the problem variant. Computational results are presented for a comprehensive set of problem instances created using data from a class I railroad in the United States. Results indicate the tractability of the optimization-based approach for large-scale instances, practical solution time with reasonable compute resources, as well as the robustness of solution quality to increases in the number of candidate trains. The solution time of the search-based heuristic approach is furthermore shown to be robust to increases in network traffic volume. The results are discussed in detail, along with implications for future research.Online sufficient dimensionality reduction for sequential high-dimensional time-series
http://hdl.handle.net/1853/60385
Online sufficient dimensionality reduction for sequential high-dimensional time-series
Li, Qingbin
In this thesis, we present Online Sufficient Dimensionality Reduction (OSDR) algorithm for real-time high-dimensional sequential data analysis.
2015-01-08T00:00:00ZLi, QingbinIn this thesis, we present Online Sufficient Dimensionality Reduction (OSDR) algorithm for real-time high-dimensional sequential data analysis.Stochastic algorithms for distributed optimization and machine learning
http://hdl.handle.net/1853/60256
Stochastic algorithms for distributed optimization and machine learning
Zhou, Yi
In the big data era, machine learning acts as a powerful tool to help us make predictions and decisions. It has strong ties to the field of optimization, in the way the latter provides methods and theory. While data tends to be collected in a distributed fashion, the standard machine learning models require centralizing the training data on one machine or in a data center, which incurs significant communication cost and puts data privacy at risk. To circumvent such an issue, a variety of distributed machine learning models have been proposed and studied in the literature. In this thesis, we focus on designing and analyzing stochastic algorithms for distributed machine learning that achieve the best communication and sampling complexities. The first part of this thesis is devoted to investigating randomized incremental gradient (RIG) methods for solving the class of finite-sum optimization problems, which is the core problem in distributed optimization. By developing and proving the optimality of the primal-dual gradient method, which covers the well-known Nesterov's accelerated gradient method as a special case, we propose its randomized version, namely the randomized primal-dual gradient (RPDG) method. RPDG only involves the computation of one randomly selected component function per iteration. Moreover, by providing a lower complexity bound for the class of RIG methods for finite-sum optimization, we demonstrate the optimality of RPDG, and this is the first time such an optimal RIG method has been developed for solving finite-sum optimization problems. In the second part of this thesis, we consider a distributed topology with a central authority, and study the distributed finite-sum optimization problems defined over such a star network topology. We propose an optimal RIG method, namely the random gradient extrapolation method (RGEM) and show that it does not require any exact gradient evaluations even at the initial point, but can still achieve the optimal communication and sampling complexities for solving distributed finite-sum optimization problems. In fact, without any full gradient computation, RGEM possesses iteration costs as low as pure stochastic gradient descent methods, but achieves a much faster and optimal linear rate of convergence for solving deterministic finite-sum problems. Moreover, we extend RGEM for stochastic finite-sum optimization, i.e., at each iteration only one randomly selected network agent needs to compute an estimator of its gradient by sampling from its local data. Note that for these problems, it is difficult to compute the exact gradients even at the initial point. In the third part of this thesis, we study another type of distributed topology, called the decentralized network topology, where there is no central authority in the distributed networks. Consider communication is the major bottleneck, we present a class of communication-efficient algorithms for solving stochastic decentralized optimization problems. We introduce a new stochastic decentralized primal-dual type method, called stochastic decentralized communication sliding (SDCS), where the agents can skip communications while solving their local subproblems iteratively. And we show that SDCS achieves the best-known communication complexities and not improvable sampling complexities. Preliminary numerical experiments are performed to show that SDCS can significantly save communication costs over some existing state-of-the-art decentralized methods in all our tested instances. Consider synchronization is another critical issue in decentralized optimization, we further extend the communication-sliding idea to the asynchronous setting. By randomly activating a subset of network agents per iteration, the proposed asynchronous stochastic decentralized type methods can maintain the communication and sampling complexities obtained by SDCS, but these methods can be applied to solve a broader class of decentralized stochastic problems, for example, composite loss functions with smooth structures.
2018-06-15T00:00:00ZZhou, YiIn the big data era, machine learning acts as a powerful tool to help us make predictions and decisions. It has strong ties to the field of optimization, in the way the latter provides methods and theory. While data tends to be collected in a distributed fashion, the standard machine learning models require centralizing the training data on one machine or in a data center, which incurs significant communication cost and puts data privacy at risk. To circumvent such an issue, a variety of distributed machine learning models have been proposed and studied in the literature. In this thesis, we focus on designing and analyzing stochastic algorithms for distributed machine learning that achieve the best communication and sampling complexities. The first part of this thesis is devoted to investigating randomized incremental gradient (RIG) methods for solving the class of finite-sum optimization problems, which is the core problem in distributed optimization. By developing and proving the optimality of the primal-dual gradient method, which covers the well-known Nesterov's accelerated gradient method as a special case, we propose its randomized version, namely the randomized primal-dual gradient (RPDG) method. RPDG only involves the computation of one randomly selected component function per iteration. Moreover, by providing a lower complexity bound for the class of RIG methods for finite-sum optimization, we demonstrate the optimality of RPDG, and this is the first time such an optimal RIG method has been developed for solving finite-sum optimization problems. In the second part of this thesis, we consider a distributed topology with a central authority, and study the distributed finite-sum optimization problems defined over such a star network topology. We propose an optimal RIG method, namely the random gradient extrapolation method (RGEM) and show that it does not require any exact gradient evaluations even at the initial point, but can still achieve the optimal communication and sampling complexities for solving distributed finite-sum optimization problems. In fact, without any full gradient computation, RGEM possesses iteration costs as low as pure stochastic gradient descent methods, but achieves a much faster and optimal linear rate of convergence for solving deterministic finite-sum problems. Moreover, we extend RGEM for stochastic finite-sum optimization, i.e., at each iteration only one randomly selected network agent needs to compute an estimator of its gradient by sampling from its local data. Note that for these problems, it is difficult to compute the exact gradients even at the initial point. In the third part of this thesis, we study another type of distributed topology, called the decentralized network topology, where there is no central authority in the distributed networks. Consider communication is the major bottleneck, we present a class of communication-efficient algorithms for solving stochastic decentralized optimization problems. We introduce a new stochastic decentralized primal-dual type method, called stochastic decentralized communication sliding (SDCS), where the agents can skip communications while solving their local subproblems iteratively. And we show that SDCS achieves the best-known communication complexities and not improvable sampling complexities. Preliminary numerical experiments are performed to show that SDCS can significantly save communication costs over some existing state-of-the-art decentralized methods in all our tested instances. Consider synchronization is another critical issue in decentralized optimization, we further extend the communication-sliding idea to the asynchronous setting. By randomly activating a subset of network agents per iteration, the proposed asynchronous stochastic decentralized type methods can maintain the communication and sampling complexities obtained by SDCS, but these methods can be applied to solve a broader class of decentralized stochastic problems, for example, composite loss functions with smooth structures.Data-driven reconfigurable supply chain design and inventory control
http://hdl.handle.net/1853/60237
Data-driven reconfigurable supply chain design and inventory control
Malladi, Satya Sarvani
In this dissertation, we examine resource mobility in a supply chain that attempts to satisfy geographically distributed demand through resource sharing, where the resources can be inventory and manufacturing capacity. Our objective is to examine how resource mobility, coupled with data-driven analytics, can result in supply chains that without customer service level reduction blend the advantages of distributed production-inventory systems (e.g., fast fulfillment) and centralized systems (e.g., economies of scale, less total buffer inventory, and reduced capital expenditures). We present efficient and effective solution methods for logistics management of multi-location production-inventory systems with transportable production capacity. We present a novel, generalized representation of demand uncertainty and propose data-driven responses to the manage a single location inventory system under such demands.
2018-05-18T00:00:00ZMalladi, Satya SarvaniIn this dissertation, we examine resource mobility in a supply chain that attempts to satisfy geographically distributed demand through resource sharing, where the resources can be inventory and manufacturing capacity. Our objective is to examine how resource mobility, coupled with data-driven analytics, can result in supply chains that without customer service level reduction blend the advantages of distributed production-inventory systems (e.g., fast fulfillment) and centralized systems (e.g., economies of scale, less total buffer inventory, and reduced capital expenditures). We present efficient and effective solution methods for logistics management of multi-location production-inventory systems with transportable production capacity. We present a novel, generalized representation of demand uncertainty and propose data-driven responses to the manage a single location inventory system under such demands.