Dept. of Industrial and Enterprise Systems Engineering
http://hdl.handle.net/2142/16358
Wed, 01 Apr 2015 03:18:13 GMT2015-04-01T03:18:13ZClustering, coverage and aggregation methods for large networks
http://hdl.handle.net/2142/72930
Clustering, coverage and aggregation methods for large networks
The work in this thesis presents methods for clustering and aggregation of large dynamic networked systems, typically consisting of numerous units/subsystems with complex interactions. Networked system models are used in many scientific and real world applications, for example to describe functional relationships among neurons in the brain, to achieve consensus in the design of communication and controller actuation rules in multi-agent systems, and to estimate multiple service demands in web-based software systems in order to enhance service quality by web cluster relocation. The level of complexity in modeling, analysis, and control synthesis for these systems increases combinatorially with the number of constituent elements in the network. This thesis presents methods for obtaining concise aggregated representations of such systems, while capturing important and relevant interconnectivity information.
In the first part of this thesis, we develop a theoretical framework for aggregating systems that are represented by directed weighted graphs. In this framework, we formulate an optimization problem, with the goal of minimizing a dissimilarity function that captures the distance between the representative and the original graphs. We propose a class of dissimilarity measures and introduce the notion of composite graph sets allowing us to compare directed weighted graphs that contain different numbers of nodes. The dissimilarity measures capture node similarities based on node connectivity, and in the simplest case reduce to metrics previously defined for equal-sized undirected unweighted graphs. The representative graph is determined by systematically identifying and aggregating similar nodes of the original graph into supernodes, and then determining the inter supernode connectivities. The key challenge herein is in overcoming the computational complexity that arises in iteratively solving two combinatorial optimization problems corresponding to evaluating and minimizing the cost function (dissimilarity measure). In our formulation, using the composite graph sets, only a single optimization problem is needed in every iteration. Further, we introduce a maximum entropy based soft aggregation approach for node clustering, and propose a multi-scaled aggregation method whose central part incorporates the Deterministic Annealing algorithm. Specifically, we solve a sequence of relaxed minimization problems by allowing soft cluster associations; as we gradually decrease the level of softness, the solution for the original problem is approached. We discuss graph structures for which this aggregation method is provably effective, and provide comprehensive simulation examples demonstrating this efficacy.
As a special case, we study the reduction of Markov chains. By viewing a Markov chain as a directed weighted graph, the graph aggregation techniques we propose are directly applicable. If we consider nearly completely decomposable Markov chains, that is, chains whose transition matrices P can be written as a perturbation added to a completely decomposable (reducible) chain P*, i.e., P = P* + eC, then we provide sufficient conditions under which our method guarantees recovery of the decomposable sub-chain structure indicated by P*, thus yielding easily verifiable conditions to corroborate results given by perturbation theory. We then derive upper bound on how close the stationary distribution of aggregated Markov chain is to the aggregated stationary distribution of the original Markov chain. The effectiveness of this method has been demonstrated through numerous examples at a variety of scales. We further apply this aggregation method to reduce systems consisting of interactive stochastic processes that can be represented by graph models. In particular, we study seismic activities at different geological locations, with parametric generative models characterizing the influences among every location. In this scenario, ensemble interactions within the system can be discovered by clustering the underlying graph model.
In the second part of this thesis, we consider dynamic clustering and coverage problems. The goal is to use a small number of resources to provide continuous and sufficient coverage for a large number of moving objects. We integrate control-theoretic methods, specifically Lyapunov-based analysis, into our aggregation framework. Specifically, we adaptively compute the actuation rules for all resources to achieve the tracking objective, in addition to a set of optimal resource locations for fixed time-instances. For systems where moving objects are driven by acceleration fields, we show that a dynamic control is necessary to achieve dynamic coverage, and provide closed-form solutions for the resource dynamics. The algorithms we propose guarantee asymptotic tracking of cluster group dynamics, and we further establish continuity and boundedness of the corresponding control laws. The algorithm has been successfully applied to many systems with a large number of dynamic sites, and we provide examples in this thesis to corroborate the results.
Clustering; Maximum Entropy Principle; Dynamic Coverage Control; Deterministic Annealing
Wed, 21 Jan 2015 00:00:00 GMThttp://hdl.handle.net/2142/729302015-01-21T00:00:00ZCentralized and distributed resource allocation with applications to signal processing in communications
http://hdl.handle.net/2142/72870
Centralized and distributed resource allocation with applications to signal processing in communications
Nowadays, wired and wireless networks are used everywhere and everyday. With the increasing popularity of multiuser communication systems, their optimal performance has become a crucial field of study during the last decades. A factor that greatly determines such performance is the optimal allocation of the resources available to the agents in the network. This dissertation provides a set of optimization techniques applicable to rigorously address and deeply analyze multiuser resource allocation problems in different areas, ranging from signal processing, to communications and networking. More specifically, this work focuses on the three main topics that we briefly describe next.
First, we study the maximum sum-utility achieved when a noncooperative approach is used to allocate the spectrum in a communication system adopting a dynamic spectrum management framework. In particular, we turn our attention to the case in which the users in the system are endowed with infinite power budgets. This asymptotic analysis, based on the linear complementarity problem theory, leads us characterize the behavior of the system's utility as the power budget is increased toward infinity, and thus draw interesting conclusions on the efficiency of the Nash equilibrium and the Braess-type paradox, among others.
Second, we propose a novel class of distributed algorithms for the optimization of nonconvex and nonseparable sum-utility functions subject to convex coupling constraints. Even though, we focus on utility functions of the Difference of Convex (DC) type, further generalizations are possible. Moreover, the obtained iterative schemes are provable convergent to stationary points of such optimization problems. Among the different applications of our Successive Convex Approximationsbased algorithms, we direct our attention to a novel resource allocation problem in the emerging field of physical layer based security, and to the well-known MIMO (Multiple-Input-Multiple-Output) Cognitive Radio sum-rate maximization problem. For the former application, we develop a mathematically rigorous analysis of the nondifferentiable and nonconvex game (of the generalized type) proposed to optimally allocate the network resources in this context; and finally, we apply our algorithms to find relaxed equilibrium points of the mentioned game. For the second application, our theory provides, for the first time, a provable convergent algorithm.
The third major topic of this dissertation analyzes a multiuser maximization problem where the utility function has a particular structure, namely, it is the sum of continuous maximum functions, subject to private and coupling constraints. We follow two different approaches in order to design provable convergent algorithms to address this problem. These approaches are based on simpler reformulations of the nondifferentiable and nonconcave optimization problem of interest. A careful analysis relating such problems is also developed. The cited results pave the way to devise (possibly distributed) algorithms for different system designs in the context of physical layer based security, ranging from the secrecy sum-rate maximization to the Max-Min fairness problem. It is important to emphasize that, different from the simple networks models considered in the physical layer security literature, the system designs studied in this dissertation involve networks composed of multiple legitimate users and friendly jammers, and a single eavesdropper, where the main users communicate over multiple (either orthogonal or non-orthogonal) subchannels.
Finally, it is worth mentioning that most of the tools and results developed in this work are general enough to encompass applications in many fields different from those described above. This dissertation highlights how the introduction of optimization theory in different signal processing applications has motivated several significant developments in the former field, in particular in the area of multiuser distributed optimization. Future research directions are provided at the end of each chapter.
Distributed optimization; Resource allocation; Nash equilibrium; Game theory; Difference of convex programming; Nonconvex and nondifferentiable optimization; Successive convex approximation; Multiuser systems; Dynamic spectrum management; Cooperative physical layer security; Cognitive radio
Wed, 21 Jan 2015 00:00:00 GMThttp://hdl.handle.net/2142/728702015-01-21T00:00:00ZRecognizing expressive movement in arm gestures using Hidden Markov Models
http://hdl.handle.net/2142/72866
Recognizing expressive movement in arm gestures using Hidden Markov Models
Movement is one of the most basic human skills that used for communicating and interacting with the environment. Although we have an intuitive understanding of our gestures, it is hard to explain their quality. One would describe the human gestures as a collection of various actions for performing different tasks. True, but it does not explain how the tasks are performed, which is essential for having a more natural representation of movement. In this work we use Laban Movement Analysis (LMA), which is an analytic and experiential system for interpreting human body movement, to understand the expressive aspects of human gestures and we try to recognize them in hand movement using a supervised learning method with Hidden Markov Models (HMMs),;
We first define the weight, space, and time characteristics of movement, which are described as the Basic Effort Factors (BEF) in LMA and we construct a classifier for each BEF using HMMs. We use a Microsoft Kinect to capture the body movement and try to recognize the quality of each BEF in hand gestures. Various preprocessing are done on the motion data to extract features that can describe the movement qualities. We use a windowing technique to segment the gestures into smaller sequences and allow for continuous gesture recognition. Various experiments are done to identify the optimal features and the parameters of each model, and we also address different problems in implementing the models.;
Our research showed promising results in recognizing and distinguishing the BEFs of hand movement. The importance of this research is in developing systems that require deeper and more natural understanding of body movement, such as systems for recognizing musical gestures and dance, or producing computer animation.
Gesture Recognition; Laban Movement Analysis; Expressive Movement; Hidden Markov Models
Wed, 21 Jan 2015 00:00:00 GMThttp://hdl.handle.net/2142/728662015-01-21T00:00:00ZUncapacitated Lot-Sizing Problems With Setup Interactions
http://hdl.handle.net/2142/72551
Uncapacitated Lot-Sizing Problems With Setup Interactions
Lot-sizing problems focus on determining a minimal total production cost schedule. These production costs are generally composed of three components: a variable production cost, an inventory holding cost, and a setup cost. The optimal solution balances the holding costs against the setup and variable costs. In most of the research in this area, product interaction is incorporated by considering the products to be in competition for fixed production capacities. However, there exist problems in which distinct products are more closely coupled.; This dissertation focuses on the effect of setup interactions on the uncapacitated lot-sizing problem (ULSP) with time varying demand patterns. We consider three major instances of setup interactions in the ULSP: the Joint Replenishment Problem (JRP), the Weak Interaction Problem (WIP), and the Strong Interaction Problem (SIP). For each of the problems computational complexity boundaries are established. The general instance of all three problems is shown to be NP-Complete. Membership in this computationally intractable class of problems, necessitates the development of strong bounding techniques and effective branching rules which can be incorporated into an exact solution procedure. Each problem is formulated as a linear integer program. Different formulations are presented which exploit various properties of the problems. Relationships between the formulations and the problems are demonstrated.; A dual ascent procedure is developed for the JRP. The procedure exploits the structure of a Lagrangean dual of the problem. Efficient schemes are employed to solve the resulting sub-problems and to determine ascent directions. Branching rules and penalties based on the problem structure are incorporated into an exact numerical procedure. Testing indicates that these bounds can be used to obtain up to a tenfold improvement in performance over a well-known commercial solver (IBM/OSL). For the WIP, bounding procedures and heuristics are presented which yield near optimal solutions with minimal computational effort. Finally, bounding schemes based on a Lagrangean decomposition that result in a WIP are presented for the SIP. This new bounding technique is incorporated into an enumerative solution procedure which reduces the computational effort required to solve the SIP by 50 to 95 percent.
Engineering, Industrial; Operations Research
Fri, 01 Jan 1993 00:00:00 GMThttp://hdl.handle.net/2142/725511993-01-01T00:00:00ZDisjunctive normal formula based supervisory control policy for general Petri nets
http://hdl.handle.net/2142/50715
Disjunctive normal formula based supervisory control policy for general Petri nets
A Petri net (PN) is said to be live if it is possible to re any transition, although not
immediately, from every reachable marking. A liveness enforcing supervisory policy (LESP)
determines which controllable transition is to be prevented from ring at a marking, to
ensure the supervised Petri net (PN) is live.
A LESP is said to be minimally restrictive if the following property is true { if a minimally
restrictive LESP prevents the ring of a transition at a marking, then all other LESPs should
do the same.
We restrict our attention to a class of general Petri nets (PN) structures, where the
existence of an LESP for an instance initialized at a marking, implies the existence of an
LESP when the same instance is initialized with a larger initial marking. We show that the
minimally restrictive LESP for an instance N from this class is characterized by a collection of
boolean formulae f tc(N)gtc2Tc , where Tc is the set of controllable transitions in the PN. The
literals in tc(N) are true if and only if the token-load of speci c places meet a threshold.
Consequently, appropriately placed threshold-sensors, which detect if the token-load of a
place is greater than or equal to a predetermined threshold, provide su cient information
to implement the minimally restrictive LESP.
Petri Nets
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/507152014-09-16T00:00:00ZMilitary budget decisions: inferring trade-offs using decision analysis
http://hdl.handle.net/2142/50665
Military budget decisions: inferring trade-offs using decision analysis
This thesis uses a decision analytic framework to assess how the United States Army makes trade-offs involving monetary resources and the potential loss of human life. Data for the study looks at the Army budget for a four year period from 2008-2011, with a focus on spending for combat and suicide prevention, and the loss of life experienced in both areas. This data is used to answer two research questions: (i) Does available data suggest the Army makes consistent trade-offs between money and human life? (ii) How can value using inferred trade-offs be used for decisions relating to the Army budget?
To answer the research questions, a basic model is derived from the data. Curve-fitting of historical data is used to infer trade-offs, as a causal relationship is assumed to exist between the spending level and the loss of lives. For the purposes of this study, the best curve-fit is assumed to represent an indifference by the decision maker to increased spending along the line if it results in a corresponding decreased loss of life. In response to the first question, the model shows that there is the potential that the Army makes inconsistent trade-offs across these areas, and explores the possible implications if these trade-offs are truly inconsistent. After addressing the possible implications of the model developed, the model is used to address the second question by showing how a value-based model can be used for the decision of budget allocation for the Army, which is especially pressing given the recently imposed budget cap that impact the US Department of Defense. Limitations of the study are addressed, along with areas for future research to expand on the initial results presented in this study.
Decision Analysis; Military Decision Making; Trade-Off Analysis
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/506652014-09-16T00:00:00ZVisualization impacts on utility functions and multiattribute utility copula approach toward electronic product recovery techniques
http://hdl.handle.net/2142/50608
Visualization impacts on utility functions and multiattribute utility copula approach toward electronic product recovery techniques
This thesis provides an initial analysis incorporating two different decision fields: aircraft repair and end-of-life electronic product recovery. The relationship between visuals of aircraft damage and user manipulation of cost models were studied in relation to their effect on the user’s understanding of the decision problem. The analysis involved using metrics to show the understanding of the attributes, tradeoffs needed and any alterations to the preference function. Lifecycle analysis was conducted on cellphones in order to understand the impact that electronic waste can have on the environment. A multiattribute utility copula approach was used in analyzing the behavior of EOL processing activities on the part of an OEM. This decision-making tool was used in order to incorporate the firm’s preferences while accounting for uncertainty with the incoming disposed cellphone feedstock used for demonstration.
The results generated during this thesis work indicated several important issues. The use of damage visuals along with model interaction caused changes in valuation of attributes and willingness to make tradeoffs among them. There were also changes in the risk attitudes as shown by shifts in the utility curves between studies. This has implications for how visualization and interaction can be used to assess and direct risk behavior in many different fields. The lifecycle analysis results indicated areas of the cellphone that were most impactful on the environment. This baseline estimate also gave insight into possible redesign options based on minimization of negative environmental impact. The multiattribute utility copula approach results described a process of determining among different specific EOL processing activities. The extraction of sub-assemblies was determined as the best decision alternative to recapture value at the disposal stage of the product lifecycle. The copula structure can be used to take into account a firm’s preferences as well as attribute valuation providing a powerful straightforward tool for decision-making under uncertainty in various fields other than electronic product recovery options.
Product End-Of-Life Recovery; Remanufacturing; Utility Functions; Utility Copula
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/506082014-09-16T00:00:00ZStochastic sequential assignment problem
http://hdl.handle.net/2142/50503
Stochastic sequential assignment problem
The stochastic sequential assignment problem (SSAP) studies the allocation of available distinct workers with deterministic values to sequentially-arriving tasks with stochastic parameters so as to maximize the expected total reward obtained from the assignments. The difficulty and challenge in making the assignment decisions is that the assignments are performed in real-time; specifically, pairing a worker with a task is done without knowledge of future task values. This thesis focuses on studying practical variations and extensions of the SSAP, with the goal of eliminating restricting assumptions so that the problem setting converges to that of real-world problems.
The existing SSAP literature considers a risk-neutral objective function, seeking an assignment policy to maximize the expected total reward; however, a risk-neutral objective function is not always desirable for the decision-maker since the probability distribution function (pdf) of the total reward might carry a high probability of low values. To take this issue into account, the first part of this dissertation studies the SSAP under a risk-sensitive objective function. Specifically, the assignments are performed so as to minimize the threshold probability, which is the probability of the total reward failing to achieve a specified target (threshold). A target-dependent Markov decision process (MDP) is solved, and sufficient conditions for the existence of a deterministic Markov optimal policy are provided. An approximate algorithm is presented, and convergence of the approximate value function to the optimal value function is established under mild conditions.
The second part of this thesis analyzes the limiting behavior of the SSAP as the number of assignments approaches infinity. The optimal assignment policy for the basic SSAP has a threshold structure and involves computing a new set of breakpoints upon the arrival of each task, which is cumbersome for large-scale problems. To address this issue, the second part of this dissertation focuses on obtaining stationary (time-independent) optimal assignment policies that maximize the long-run expected reward per task and are much easier to perform in real-world problems. An exponential convergence rate is established for the convergence of the expected total reward per task to the optimal value as the number of tasks approaches infinity. The limiting behavior of the SSAP is studied in two different settings. The first setting assumes an independent and identically distributed (IID) sequence of arriving tasks with observable distribution functions, while the second problem considers the case where task distributions are unobservable and belong to a pool of feasible distributions.
The next part of this dissertation basically brings the first two parts together, studying the limiting behavior of the target-dependent SSAP, where the goal is finding an assignment policy that minimizes the probability of the long-run reward per task failing to achieve a given target value. It is proven that the above-mentioned stationary policy (mentioned in the previous paragraph), which achieves the long-run expected reward per task, minimizes the long-run threshold probability in this problem as well. These two objective functions being optimized simultaneously by one assignment policy is interesting, since the threshold criteria, by definition, deviates from the expected total reward criteria; i.e., although it attempts to avoid hitting below a given target level as much as possible, it does not automatically and necessarily guarantee a reasonable performance in terms of the expected reward.
Finally, stochasticity in the SSAP is extended to worker values in the last part of this thesis, where the worker values are assumed to be random variables, taking on new values upon each task arrival. Four models are introduced which analyze this problem from different aspects; e.g., the distribution function of worker values being identical or distinct, the worker values in a given time period being dependent on those in the preceding time periods (or within the same time period), worker values being deterministic but assumed to be functions of time (possibly deteriorating with time), and task values being independent or dependent on each other. For each of these models an optimal assignment policy is presented so as to maximize the expected total reward.
sequential assignment; Markov decision process; stationary policy; hidden Markov model; threshold criteria; risk measure
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/505032014-09-16T00:00:00ZMultiattribute utility functions for the deep borehole filter restoration problem
http://hdl.handle.net/2142/50440
Multiattribute utility functions for the deep borehole filter restoration problem
The energy problem is one of the biggest challenges facing the World in the 21st century. It is related to the issues of natural resource extraction, resource depletion, power generation, environmental degradation, and atmospheric change such as global warming. Since more than 80% of the world’s primary energy is generated from fossil fuels (coal, oil, gas), emissions of carbon dioxide (CO2) from all fossil-fuel burnings are the largest cause of climate change. Global climate disruption, in turn, impacts on human health, flora, and fauna. The global energy demand is expected to double by 2050 and that is inevitably due to global population growth, global economic growth, and continued urbanization. To meet the increasing demand for energy and to avoid catastrophic climate change, increases in energy efficiency and increases in the fraction of low carbon energy sources are required.
Uranium is a good energy source, because it has high energy density and nuclear power does not contribute to carbon dioxide emissions. However, difficulties in uranium mining cause large worldwide shortages of uranium for power generation. Decision makers in uranium mining are often challenged by various uncertainties in their decision problems (financial, technological, geological) and multiple objectives (increase profits, decrease radiation hazards, improve safety of operations, preserve environments). This dissertation studies multiattribute utility functions for modeling such challenging decision problems using the example of the deep borehole filter restoration problem from the uranium extraction industry. In this problem, the filter of the production borehole (or well) is periodically contaminated or clogged, causing significant uranium output reduction. The efficient modeling of this decision-making problem is of paramount importance for uranium mining worldwide and requires normative decision analysis.
Motivated by the complexity of multiattribute decision problems under uncertainty and multiple objectives, this dissertation considers a set of open research problems related to the number of attributes and their degree of ‘interdependence under uncertainty,’ formally, utility dependence and independence. This dissertation characterizes the special functional forms of multiattribute utility functions (MUFs) under the partial utility independence (PUI) condition, verifies their applicability to the deep borehole filter restoration problem, evaluates the alternatives of the decision problem by three different approaches, and introduces novel methods for excluding redundant utility assessments.
In Part I of this work we present our study: (1) what are the objectives and the corresponding attributes (i.e. factors or criteria of the decision-making process) of the deep borehole filter restoration problem from the well-field manager’s point of view, (2) does the ultimate decision maker find these attributes good or not, (3) does utility independence (UI) among the attributes exist in this decision problem, (4) whether or not the canonical functional forms from the theory of decision analysis are applicable to this decision problem, (5) are the decision analysis tests easy for the experts in the uranium extraction industry to use? For this, we create new tests for assessing interdependence among the attributes of the decision problem. In the first experiment with Test 1, 105 professionals in uranium mining were requested to provide their preferences among the four most important attributes from the well-field manager’s point of view. In the second experiment with the more formal Test 2, 40 experts were asked to provide their preferences from among three of these four attributes.
Based on the results of the experimental study, with 95% confidence we can conclude that the proportion of the population (thousands) of experts who assert utility independence of the attributes is at most 0.23. The results imply that the conventional approach, the assumption of utility independence, may not be valid for our decision problem.
In Part II, we evaluate five alternatives of the deep borehole filter restoration problem by constructing a multiattribute utility function (MUF) utilizing two different approaches: (i) under the assumption of utility independence of attributes, and (ii) with the existing (assessed from the decision maker) partial utility independence of the attributes. The four most important attributes were selected by the ultimate decision maker, the Deputy Director General of a transnational corporation. We first assume utility independence of the attributes and utilize the corresponding multilinear form of the MUF. We then utilize the general decomposition approach for constructing the MUF under the assessed partial utility independence conditions. Finally, we compare the results of these two approaches and the results of the profit analysis.
By direct assessments, (i) we find that utility independence among the attributes of the deep borehole filter restoration problem is not a valid assumption, (ii) we verify that the decision maker’s preferences assert partial utility independence, (iii) we illustrate the assessments required under partial utility independence assertions, (iv) we compare the decisions made using the assumption of utility independence and the existing partial utility independence conditions, and (v) determine that the assumption of utility independence yields recommendations, which are different from the true preferences of the decision maker. Our results also demonstrate that the assessments required for the construction of the MUF by the utility independence approach is easier for the decision maker (DM), but the DM is more comfortable with the partial utility independence conditions. To our knowledge, this is the first practical study on the comparison of profit analysis, the utility independence approach, and the partial utility independence approach in a complex real life multiattribute decision problem.
In Part III, we present algorithms for excluding redundant assessments from the set of assessments required for construction of the multiattribute utility function. In complex decision problems, the number of utility assessments, and, therefore, the number of questions for the decision maker, increases dramatically. It is thus very important to check the consistency of the assessments and eliminate all redundant utility assessments. With the efficient algorithms introduced in this dissertation, the elimination of the redundant utility assessments is considerably simplified.
The results of this dissertation were applied to an important and complex decision problem in the uranium extraction industry, the deep borehole filter restoration problem. The decision modeling proposed in this dissertation should also help decision makers in addressing the worldwide 14% shortage of uranium needed for nuclear power generation.
Decision analysis; multiattribute utility functions; the World’s biggest challenge; energy problem; uranium mining; in situ leach mining; deep borehole filter restoration problem; borehole recovery problem; nuclear power; twos-complement exclusion algorithm; ternary-decimal exclusion algorithm; partial utility independence; utility assessments; preference elicitation; decision maker; evaluation of alternatives; multiple attributes; uncertainty; eliminating redundancy; excluding duplicate terms; experimental study; confidence intervals
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/504402014-09-16T00:00:00ZDynamic decision-making under uncertainties: algorithms based on linear decision rules and applications in operating models
http://hdl.handle.net/2142/50389
Dynamic decision-making under uncertainties: algorithms based on linear decision rules and applications in operating models
This thesis is to propose efficient and robust algorithms based on Linear
Decision Rule (LDR), which expand the applicability of the existing LDR methods. Representative and complex operation models are analyzed and solved by the proposed approaches. The research motivation and scope are provided in Chapter 1.
Chapter 2 introduces the generic LDR method and the contributions of this thesis to the LDR literature. To extend the LDR method to nonlinear objectives, two methods are proposed. The first is an iterative LDR (ILDR) method that tackles general concave differentiable nonlinear terms in the objective function. The second treats quadratic terms in the objective function by a Second-Order Cone approximation. The details and implementation of the proposed methods are presented in Chapter 3 and Chapter 4.
Chapter 3 utilizes the Robust Optimization approach to derive an ILDR solution for a multi-period hydropower generation problem that has a nonlinear objective function. The methodology results in tractable second-order cone formulations. The performance of the ILDR approach is compared with the Sampling Stochastic Dynamic Programming (SSDP) policy derived using historical data.
In Chapter 4, a joint pricing and inventory control problem of a perishable product with a fixed lifetime is analyzed. Both the backlogging and lost-sales cases are discussed. The analytic results shed new light on perishable inventory management, and the proposed approach provides a significantly simpler proof of a classical structural result in the literature. Two heuristics were proposed, one of which is a modification and improvement of an existing heuristic. The other one is an LDR based approach, which approximates the dynamics and the objective function by robust counterparts. The robust counterpart for the backlogging case is tight, and it leads to a satisfactory performance of less than 1% loss of optimality. Although the robust counterpart for the lost-sales case is not tight in the current numerical study, the gap between the LDR method and the SDP benchmark is less than 5% on average.
Chapter 5 summarizes the contributions of the thesis and discusses about potential improvements. One important working project, an approximate dynamic programming based on LDR (ADP-LDR) approach, is introduced for future research.
dynamic decision-making; stochastic optimization; robust optimization; second-order cone programming; reservoir management; supply chain management; perishable product management
Tue, 16 Sep 2014 00:00:00 GMThttp://hdl.handle.net/2142/503892014-09-16T00:00:00Z