Browsing by Subject "Integer programming"
Now showing 1 - 7 of 7
- Results Per Page
- Sort Options
Item Applications of network optimization in cybersecurity and service parts logistics(2019-05-09) Karatas, Murat, Ph. D.; Kutanoglu, Erhan; Hanasusanto, Grani A; Hasenbein, John J; Iyoob, IlyasWe develop and analyze novel network-based optimization models for two very important network-related applications: cybersecurity and service parts logistics. We consider one cybersecurity network problem and two service parts logistics network problems. The goal is to find tractable solutions to all three problems by creating carefully designed network-based models. The first problem we consider involves decision making in a cybersecurity environment. The goal here is to find the optimal locations to place defensive investments in a cyber physical system so that the probability of being compromised by a persistent attacker is minimized. We use Markov Decision Processes (MDPs) to show that the problem involves stochastic decision making, and we approach it using a network interdiction model. Initially, we create an MDP to come up with a description of a cyber physical network and try to find the optimal attack strategy for a persistent hacker. We show that the results of our MDP model are the same as those of the so called s-t reliability problem, a well-studied #P network problem. To tackle the exponential increase in the state space and the calculation time of the MDP with respect to the size of the cyber physical network, we create a mixed integer program (MIP) to come up with an attacker’s strategy, and develop it further to include a defender by creating a network interdiction model. We show that the results coming from the MIP and MDP model are the same, thus providing a tractable solution to the cybersecurity problem as well as the related s-t reliability problem. The second problem we consider involves decision making in a Service Parts Logistics (SPL) problem. Modifying the traditional assumption of failure based replacements in post-sales service models, we incorporate Condition Based Replacement (CBR) policies into SPL. We utilize the Internet of Things (IoT) and sensors to operationalize the continuous monitoring of the conditions of the parts in the network. We create a model to decide on strategic network design and spare parts stocking, as well as the customer to network facility allocations. Despite the focused work on high value, low demand logistics models such as SPL in the literature, there has not been a study of integrated SPL problems involving CBR policies. Along with the facility location, customer-to-facility allocation and part stock level decisions for given fill-rate based service levels, the CBR-extended SPL model also finds the optimal conditions to replace the parts at each customer. After a careful development of the part degradation process using a Continuous Time Markov Chain model, we incorporate the CBR policies into the integrated SPL model, which turns out to be a Mixed Integer Program with Quadratic Constraints (MIQCP). Our results show that the CBR flexibility brings in significant savings in the objective function (total costs of the network) when compared to the optimal solutions of the failure-based replacement (FBR) policies. Moreover, in almost all problem instances under a wide variety of conditions, replacing the parts at failure is never optimal even if such policy is allowed as part of CBR. Finally, our results show that the network topology and network design decisions interact with the replacement conditions optimal for each customer. The third problem we consider is an extension of the second problem, SPL problem with CBR, to incorporate on-request 3D printing of spare parts from a common material using Additive Manufacturing (AM) methods. Here we extend the model to include multiple parts as well as the potentially different holding costs and reliability levels for printed parts. Fortunately, we show that the extended model can also be represented as an MIQCP. In our extensive tests with multiple parts and under a wide variety of conditions, AM optimal solutions improve upon those of the traditional SPL model with conventionally manufactured and stocked parts. This additional improvement is on top of the improvements obtained with CBR.Item A column generation approach for stochastic optimization problems(2006) Wang, Yong Min; Bard, Jonathan F.; Morton, David P.Understanding how uncertainty effects the dynamics and behavior of an organization is a critical aspect of system design. Models and methods that take uncertainty into account can lead to significant reductions in cost. This dissertation investigates the use of stochastic optimization models for the following applications: (1) a generalized assignment problem (GAP) with uncertain resource capacity and unknown processing times and (2) a shift planning and scheduling problem (SPSP) with unknown demand that arises in the construction of the workforce at US Postal Service mail processing and distribution centers. In the models, the first stage decisions are made before the uncertainty is revealed. For the GAP, the first stage decisions correspond to an assignment of jobs to agents. Penalties are incurred when the assignments do not permit all demand to be satisfied. For the SPSP, the number of full-time and part-time employees, as well as the number of full-time shifts by type, must be specified before the demand is known. In the second stage, feasibility is addressed by allocating overtime and calling in temporary workers to handle spikes in the mail volume. This dissertation consists of three parts: (i) the development and analysis of stochastic integer programming models for the GAP and the SPSP, (ii) the estimation of the demand distributions from historical data for the Dallas processing and distribution center, and (iii) the development of column generation algorithms to solve the associated stochastic integer programs. In the first part, the stochastic integer programming models are formulated for the two applications and the value of the stochastic solutions is presented. The second part begins with an analysis of the weekly demand and a test of hypothesis concerning the existence of an end-of-month effect, i.e., that the week at the end of the month might have larger volume. The hypothesis is rejected. After removing outliers, it is shown that the demand is approximated well by a normal distribution. In the last part of the dissertation, a branch-and-price algorithm is developed and used to solve the two applications. Experimental results demonstrate the algorithm’s effectiveness.Item Models to predict and influence consumer demand : applications to television advertising and solar panel adoption(2019-08) Souyris, Sebastián; Balakrishnan, Anant; Duan, Jason; Seshadri, Sridhar; Lai, Guoming; Tompaidis, Stathis; Rai, VarunThis dissertation consists of two independent essays that share the common goal of predicting and influencing consumer demand: (i) Scheduling Advertising on Television; and (ii) Peer Effects in the Diffusion of Solar Panels: A Dynamic Discrete Choice Approach. These essays are data-driven problems of operations and management science, which we address using optimization and econometrics.Item Multicommodity network flow models with FIFO transshipment handling policies(2011-08) Mohapatra, Chinmoy; Balakrishnan, Anantaram; Morton, David P.Integer multicommodity network flow (MCNF) models have applications in various areas like logistics, freight transportation, telecommunication and manufacturing. In this thesis we study an extension of the integer MCNF problem (MCNF-FIFO) where commodities are handled (processed) in a first-in-first-out (FIFO) order at each transshipment location and resource capacities are shared across arcs in the network. The objective of the MCNF-FIFO model is to find feasible routes for all commodities from their origins to destinations while minimizing the total transportation and holding cost or the sum of delivery times. We formulate the MCNF-FIFO problem on a time-space network and develop three different integer-programming (IP) formulations for the FIFO constraints, and two IP formulations for the flow conservations requirements. Since these formulations have a very large number of variables and constraints, we develop various algorithmic strategies to obtain good quality solutions quickly. The first strategy is to reduce the problem size by using properties of the optimal solution. We develop novel problem reduction and decomposition techniques that eliminate variables and constraints, and decompose the problem into smaller components. To further reduce the problem size, we classify the FIFO constraints into different categories by utilizing the relationships between different commodities, and provide specialized formulations for each of these categories so as to reduce the number of FIFO constraints significantly. The second strategy is to develop heuristic algorithms that provide near-optimal solutions to the MCNF-FIFO problem. Our first algorithm is an optimization-based heuristic that solves a relaxed MCNF-FIFO model with a limited number of FIFO constraints. Then, it removes the remaining infeasibilities in the solution of the relaxed MCNF-FIFO model using a repair heuristic to obtain a feasible solution. We develop two other heuristic algorithms that are stand-alone construction heuristics that build a feasible solution from scratch. To assess the effectiveness of the modeling and algorithmic enhancements, we implement the methods and apply them to three real life test instances. Our tests show that the problem reduction techniques are very effective in reducing the solution times. Among the heuristic algorithms, the optimization-based heuristic performs the best to find near-optimal solutions quickly.Item Optimization models and methods for transportation services(2015-08) Lin, Sifeng; Balakrishnan, Anantaram; Bard, Jonathan F.; Mirchandani, Prakash; Hasenbein , John; Dimitrov, NedialkoManaging transportation services efficiently is essential to both public and private sectors. This dissertation addresses three scheduling problems in modern transportation systems: the network design problem, the train dispatching problem, and the service route design problem. The transportation network design problem with service requirements designs arcs on a directed network and route commodities on the designed arcs so that i) commodities satisfy service requirements and ii) the total cost is minimized. We develop three mathematical programming models: a compact but weak arc-flow formulation, a large but strong path-flow formulation, and a hybrid formulation that uses both the arc-flow and the path-flow representations. We show that the hybrid formulation can significantly strengthen the LP formulation without introducing many variables. To find a good hybrid formulation, we develop columnization and decolumnization algorithms that uses the LP relaxation information to identify commodities that should use the path-flow representation. We also develop valid inequalities for commodities using the path-flow representation. The train dispatching problem schedules the movements of trains on scarce railroad tracks so as to improve the average velocity of trains. We develop a mathematical programming model and strengthen the model using valid inequalities. Besides, we present a heuristic to find a feasible solution quickly, which can serve as the warm-start solution to the MIP solver. For the third problem, we seek to design vehicle routes to deliver and pickup orders for a major grocery chain. We design a GRASP that can incorporate various operational requirements, including warehouse loading capacity, loading sequence, time window requirements, truck volume and weight capacities, and driver time limits. Our GRASP procedure consists of two phases: the solution construction (Phase I) and the Tabu search (Phase II). We show that the neighborhood structure of solutions is highly degenerate, which limits the solution space explored by the Tabu search. We apply the Tabu search with random variable neighborhood to increase the solution space explored.Item OQGRG: a multi-start algorithm for global solution of nonlinear and mixed integer programs(2001) Ugray, Zsolt Gyula; Lasdon, Leon S.Economical, managerial, engineering, and natural systems are often represented by nonlinear equations and inequalities, using discrete and continuous variables. Global Optimization provides methodologies to find the global solutions for the prescriptive models that attempt to describe, predict, and optimize their behavior. OQGRG, the algorithm presented in this dissertation, was developed to solve problems in this large target class of mixed integer, nonlinear, constrained optimization models that often have multiple local optima. OQGRG is a multi-start, 2-stage, global optimization algorithm that combines the efficiency of the Scatter Search meta-heuristic and the power of a reduced gradient nonlinear solver. It uses OptQuest as the implementation of Scatter Search and Lsgrg2 as a nonlinear local solver. OQGRG is written in standard ANSI C, and a GAMS interface provides access to many test problems available in the literature. The effectiveness of the algorithm is demonstrated by solving 155 of 159 test problems within 1% of their best known solutions.Item The vehicle routing problem on tree networks : exact and heuristic methods(2011-12) Kumar, Roshan; Waller, S. Travis; Machemehl, Randy B.The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions.