Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2007. / Includes bibliographical references (p. 81-89). / Thle Mannesmann process is the preferred method in the oil industry for fabrication of hollow pipes. The critical phenomenon in this process is the formation of a small round hole at the center of the cylindrical billet ahead of the piercing plug. In this work the crack initiation that leads to the creation of tile small hole has been modeled. The Gurson-Tvergaard-Needlemnan model of porous plasticity is used to simulate the Mannesmann effect. The appearance of a crack at the center of the cylindrical bar is demonstrated and the stress profiles, plastic equivalent strain profiles and porosity distribution during the deformation process are analyzed. The influence of various parameters in the model on the evolution of porosity in tile specimen is studied. Other simple ductile fracture criteria that are proposed in literature are also implemented. An interface model for fracture using the discontinuous Galerkin framework combined with a cohesive fracture law is implemented. This approach and its advantages are illustrated in the application of tensile loading of a simple beam specimen. / by Sudhir Chiluveru. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008. / Includes bibliographical references (leaves 73-74). / The steady increase of congestion in air traffic networks has resulted in significant economic losses and potential safety issues in the air transportation. A potential way to reduce congestion is to adopt efficient air traffic management policies, such as, optimally scheduling and routing air traffic throughout the network. In recent years, several models have been proposed to predict and manage air traffic. This thesis focuses on the comparison of two such approaches to air traffic flow management: (i) a discrete Mixed Integer Program model, and (ii) a continuous flow-based model. The continuous model is applied in a multi-commodity setting to take into account the origins and destinations of the aircraft. Sequential quadratic programming is used to optimize the continuous model. A comparison of the performance of the two models based on a set of large scale test cases is provided. Preliminary results suggest that the linear programming relaxation of the discrete model provides results similar to the continuous flow-based model for high volumes of air traffic. / by Thi Vu Phu. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2009. / Vita. Cataloged from PDF version of thesis. / Numerical methods and algorithms have developed and matured vastly over the past three decades now that computational analysis can be performed on almost any personal computer. There is a need to be able to teach and present this material in a manner that is easy for the reader to understand and be able to go forward and use. Three popular course at MIT were without lecture notes; in this thesis the lecture notes are presented. The first chapter covers material taught in Numerical Methods for Partial Differential Equations (2.097/6.339/16.920) specifically the Integral Equation Methods section of this course, chapter two shows the notes for the course Introduction to Numerical Simulation (2.096/6.336/16.910), and chapter three contains the notes for the class Foundations of Algorithms and Computational Techniques in Systems Biology (6.581/20.482). These course notes give a broad overview of many algorithms and numerical methods that one can use to solve many problems that span many fields - from biology to aerospace to electronics to mechanics. / by Laura L. Proctor. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2007. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 57-61). / Conventional fast integral equation solvers seem to be ideal approaches for simulating 3-D nanophotonic devices, as these devices are considered to be open structures, generating fields in both an interior channel and in the infinite exterior domain. However, many devices of interest, such as optical ring resonator filters or waveguides, have channels that can not be terminated without generating numerical reflections. Therefore, designing absorbers for these channels is a new problem for integral equation methods, as integral equation methods were initially developed for problems with finite surfaces. In this thesis we present a technique to eliminate reflections, making the channel volume conductive outside the domain of interest. The surface integral equation (SIE) method is employed to take advantage of the piecewise homogeneous medium. The Poggio-Miller-Chang-Harrington-Wu (PM-CHW) formulation is formed and the boundary element method is employed to construct and solve a linear system. Moreover, the block Toeplitz matrix property and using FFT helps reduce memory requirement, and accelerate the circulant matrix vector product. Numerical experiments are presented to demonstrate that this method can effectively reduce reflections to 1%, and is easily incorporated in an fast integral equation solver. / by Lei Zhang. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2007. / Includes bibliographical references (p. 173-177). / In recent years, many groups have numerically modeled the near-anode region of a Hall thruster in attempts to better understand the associated physics of thruster operation. Originally, simulations assumed a continuum approximation for electrons and used magnetohydrodynamic fluid equations to model the significant processes. While these codes were computationally efficient, their applicability to non-equilibrated regions of the thruster, such as wall sheaths, was limited, and their accuracy was predicated upon the notion that the energy distributions of the various species remained Maxwellian at all times. The next generation of simulations used the fully-kinetic particle-in-cell (PIC) model. Although much more computationally expensive than the fluid codes, the full-PIC codes allowed for non-equilibrated thruster regions and did not rely on Maxwellian distributions. However, these simulations suffered for two main reasons. First, due to the high computational cost, fine meshing near boundaries which would have been required to properly resolve wall sheaths was often not attempted. Second, PIC is inherently a statistically noisy method and often the extreme tails of energy distributions would not be adequately sampled due to high energy particle dissipation. The current work initiates a third generation of Hall thruster simulation. A PIC-Vlasov hybrid model was implemented utilizing adaptive meshing techniques to enable automatically scalable resolution of fine structures during the simulation. The code retained the accuracy and versatility of a PIC simulation while intermittently recalculating and smoothing particle distribution functions within individual cells to ensure full velocity space coverage. A non-Monte Carlo collision technique was also implemented to reduce statistical noise. / (cont.) This thesis details the implementation and thorough benchmarking of that new simulation. The work was conducted with the aid of Delta Search Labs' supercomputing facility and technical expertise. The simulation was fully-parallelized using MPI and tested on a 128 processor SGI Origin machine. We gratefully acknowledge that funding for portions of this work has been provided by the United States Air Force Research Laboratory and the National Science Foundation. / by Justin M. Fox. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2006. / Includes bibliographical references (leaves 73-75). / In this thesis, we use a semidefinite relaxation based branch-and-bound method to solve nonconvex quadratic programming problems. Firstly, we show an interval branch-and-bound method to calculate the bounds for the minimum of bounded polynomials. Then we demonstrate four SDP relaxation methods to solve nonconvex Box constrained Quadratic Programming (BoxQP) problems and the comparison of the four methods. For some lower dimensional problems, SDP relaxation methods can achieve tight bounds for the BoxQP problem; whereas for higher dimensional cases (more than 20 dimensions), the bounds achieved by the four Semidefinite programming (SDP) relaxation methods are always loose. To achieve tight bounds for higher dimensional BoxQP problems, we combine the branch-and-bound method and SDP relaxation method to develop an SDP relaxation based branch-and-bound (SDPBB) method. We introduce a sensitivity analysis method for the branching process of SDPBB. This sensitivity analysis method can improve the convergence speed significantly. / (cont.) Compared to the interval branch-and-bound method and the global optimization software BARON, SDPBB can achieve better bounds and is also much more efficient. Additionally, we have developed a multisection algorithm for SDPBB and the multisection algorithm has been parallelized using Message Passing Interface (MPI). By parallelizing the program, we can significantly improve the speed of solving higher dimensional BoxQP problems. / by Sha Hu. / S.M.

Shale gas development is transforming the energy landscape in the United States. Advances in production technologies, notably the dual application of horizontal drilling and hydraulic fracturing, allow the extraction of vast deposits of trapped natural gas that, until recently, were uneconomic to produce. The objective of this work is to develop mixed-integer programming models to support upstream operators in making faster and better decisions that ensure low-cost and responsible natural gas production from shale formations. We propose a multiperiod mixed-integer nonlinear programming (MINLP) model along with a tailored solution strategy for strategic, quality-sensitive shale gas development planning. The presented model coordinates planning and design decisions to maximize the net present value of a field-wide development project. By performing a lookback analysis based on data from a shale gas producer in the Appalachian Basin, we find that return-to-pad operations are the key to cost-effective shale gas development strategies. We address impaired water management challenges in active development areas through a multiperiod mixed-integer linear programming (MILP) model. This model is designed to schedule the sequence of fracturing jobs and coordinate impaired- and freshwater deliveries to minimize water management expenses, while simultaneously maximizing revenues from gas sales. Based on the results of a real-world case study, we conclude that rigorous optimization can support upstream operators in cost-effectively reducing freshwater consumption significantly, while also achieving effective impaired water disposal rates of less than one percent. We also propose a multiperiod MINLP model and a tailor-designed solution strategy for line pressure optimization in shale gas gathering systems. The presented model determines when prospective wells should be turned in-line, and how the pressure profile within a gathering network needs to be managed to maximize the net present value of a development project. We find that backoff effects associated with turn-in line operations can be mitigated through preventive line pressure manipulations. Finally, we develop deterministic and stochastic MILP models for refracturing planning. These models are designed to determine whether or not a shale well should be restimulated, and when exactly to refracture it. The stochastic refracturing planning model explicitly considers exogenous price forecast uncertainty and endogenous well performance uncertainty. Our results suggest that refracturing is a promising strategy for combatting the characteristically steep decline curves of shale gas wells.

No description available.

Software Defined Networking (SDN) is an emerging paradigm for network design and management. By providing network programmability and the separation of control and data planes, SDN offers salient features such as simplified and centralized management, reduced complexity, and accelerated innovation. Using SDN, the control and management of network devices are performed by centralized software, called controllers. In particular, Software-Defined Wide Area Networks (SD-WANs) have made considerable headway in recent years. However, SDN can be a double-edged sword with regard to network resilience. The great reliance of SDN on the logically centralized control plane has heightened the concerns of research communities and industries about the resilience of the control plane. Although the controller provides flexible and fine-grained resilience management features that contribute to faster and more efficient failure detection and containment in the network, it is the Achilles' heel of SDN resilience. The resilience of control plane has a great impact on the functioning of the whole system. The challenges associated with the resilience of the control plane should be addressed properly to benefit from SDN's unprecedented capabilities. This dissertation investigates the aforementioned issues by categorizing them into two groups. First, the resilient design of the control plane is studied. The resilience of the control plane is strongly linked to the Controller Placement Problem (CPP), which deals with the positioning and assignment of controllers to the forwarding devices. A resilient CPP needs to assign more than one controller to a switch while it satisfies certain Quality of Service (QoS) requirements. We propose a solution for such a problem that, unlike most of the former studies, takes both the switch-controller/inter-controller latency requirements and the capacity of the controllers into account to meet the traffic loads of switches. The proposed algorithms, one of which has a polynomial-time complexity, adopt a clique-based approach in graph theory to find high-quality solutions heuristically. Second, due to the high dynamics of SD-WANs in terms of variations in traffic loads of switches and the QoS requirements that further affect the incurred load on the controllers, adjustments to the controller placement are inevitable over time. Therefore, resilient switch reassignment and incremental controller placement are proposed to reuse the existing geographically distributed controllers as much as possible or make slight modifications to the controller placement. This assists the service providers in decreasing their operational and maintenance costs. We model these problems as variants of the problem of scheduling on parallel machines while considering the capacity of controllers, reassignment cost, and resiliency (which have not been addressed in the existing research work) and propose approximation algorithms to solve them efficiently. To sum up, CPP has a great impact on the resilience of SDN control plane and subsequently the correct functioning of the whole network. Therefore, tailored mechanisms to enhance the resiliency of the control plane should be applied not only at the design stage of SD-WANs but also during their lifespan to handle the dynamics and new requirements of such networks over time. / Graduate

Clustering problems often arise in the fields like data mining, machine learning and computational biology to group a collection of objects into similar groups with respect to a similarity measure. For example, clustering can be used to group genes with related expression patterns. Covering problems are another important class of problems, where the task is to select a subset of objects from a larger set, such that the objects in the subset "cover" (or contain) a given set of elements. Covering problems have found applications in various fields including wireless and sensor networks, VLSI, and image processing. For example, covering can be used to find placement locations of the minimum number of mobile towers to serve all the customers of a region. In this dissertation, we consider an interesting collection of geometric clustering and covering problems, which are modeled as optimization problems. These problems are known to be $\mathsf{NP}$-hard, i.e. no efficient algorithms are expected to be found for these problems that return optimal solutions. Thus, we focus our effort in designing efficient approximation algorithms for these problems that yield near-optimal solutions. In this work, we study three clustering problems: $k$-means, $k$-clustering and Non-Uniform-$k$-center and one covering problem: Metric Capacitated Covering. $k$-means is one of the most studied clustering problems and probably the most frequently used clustering problem in practical applications. In this problem, we are given a set of points in an Euclidean space and we want to choose $k$ center points from the same Euclidean space. Each input point is assigned to its nearest chosen center, and points assigned to a center form a cluster. The cost per input point is the square of its distance from its nearest center. The total cost is the sum of the costs of the points. The goal is to choose $k$ center points so that the total cost is minimized. We give a local search based algorithm for this problem that always returns a solution of cost within $(1+\eps)$-factor of the optimal cost for any $\eps > 0$. However, our algorithm uses $(1+\eps)k$ center points. The best known approximation before our work was about 9 that uses exactly $k$ centers. The result appears in Chapter \ref{sec:kmeanschap}. $k$-clustering is another popular clustering problem studied mainly by the theory community. In this problem, each cluster is represented by a ball in the input metric space. We would like to choose $k$ balls whose union contains all the input points. The cost of each ball is its radius to the power $\alpha$ for some given paramater $\alpha \ge 1$. The total cost is the sum of the costs of the chosen $k$ balls. The goal is to find $k$ balls such that the total cost is minimized. We give a probabilistic metric partitioning based algorithm for this problem that always returns a solution of cost within $(1+\eps)$-factor of the optimal cost for any $\eps > 0$. However, our algorithm uses $(1+\eps)k$ balls, and the running time is quasi-polynomial. The best known approximation in polynomial time is $c^{\alpha}$ that uses exactly $k$ balls, where $c$ is a constant. The result appears in Chapter \ref{sec:kcluster}. Non-Uniform-$k$-center is another clustering problem, which was posed very recently. Like in $k$-clustering here also each cluster is represented by a ball. Additionally, we are given $k$ integers $r_1,\ldots,r_k$, and we want to find the minimum dilation $\alpha$ and choose $k$ balls with radius $\alpha\cdot r_i$ for $1\le i\le k$ whose union contains all the input points. This problem is known to be notoriously hard. No approximation is known even in the special case when $r_i$'s belong to a set of three integers. We give an LP rounding based algorithm for this special case that always returns a solution of cost within a constant factor of the optimal cost. However, our algorithm uses $(2+\eps)k$ balls for some constant $\epsilon$. We also show that this special case can be solved in polynomial time under a practical assumption. Moreover, we prove that the Euclidean version of the problem is also as hard as the general version. These results appear in Chapter \ref{sec:nukc}. Capacitated Covering is a generalization of the classical set cover problem. In the Metric Capacitated Covering problem, we are given a set of balls and a set of points in a metric space. Additionally, we are given an integer that is referred to as the capacity. The goal is to find a minimum subset of the input set of balls, such that each point can be assigned to the chosen balls in a manner so that the number of points assigned to each ball is bounded by the capacity. We give an LP rounding based algorithm for this problem that always returns a solution of cost within a constant factor of the optimal cost. However, we assume that we are allowed to expand the balls by a fairly small constant. If no expansion is allowed, then the problem is known to not admit any constant approximation. We discuss our findings in Chapter \ref{sec:capa}. As mentioned above, for many of the problems we consider, we obtain results that improve the best known approximation bounds. Our findings make significant progress towards better understanding the internals of these problems, which have impact across the disciplines. Also, during the course of our work, we have designed tools and techniques, which might be of independent interest for solving similar optimization problems. Finally, in Chapter \ref{sec:conclude}, we conclude our discussion and pose some open questions, which we consider as our potential future work.