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.

Thesis: S.M., Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2019 / Cataloged from PDF version of thesis. / Includes bibliographical references. / Machine-Learning Interatomic Force-Fields have shown great promise in increasing time- and length-scales in atomistic simulations while retaining the high accuracy of the reference calculations that they are trained on. Most proposed models aim to learn the potential energy surface of a system of atoms as a function of atomic coordinates and species and obtain the forces acting on the atoms as the negative of the gradient of the global energy with respect to the atomic positions. For the time evolution of an atomistic system in molecular dynamics, however, only atomic forces are required. This thesis examines the construction of a direct approach for learning atomic forces, thereby bypassing the need for learning an energy-based model. Predicting atomic forces directly requires the careful consideration of incorporating the symmetries of 3D space into the model. The construction of an efficient, direct, and symmetry-preserving deep learning model that can predict atomic forces in a fully end-to-end fashion is shown. The model's accuracy, its computational efficiency for training as well as its computational efficiency at time of prediction are evaluated. Finally, the approach is used in the simulation of different small organic molecules and the resulting Molecular Dynamics simulations are analyzed. / by Simon Lutz Batzner. / S.M. / S.M. Massachusetts Institute of Technology, Computation for Design and Optimization Program

Background Somatic mutations accumulate in human cells throughout life. Some may have no adverse consequences, but some of them may lead to cancer. A cancer genome is typically unstable, and thus more mutations can accumulate in the DNA of cancer cells. An ongoing problem is to figure out which mutations are drivers - play a role in oncogenesis, and which are passengers - do not play a role. One way of addressing this question is through inspection of somatic mutations in DNA of cancer samples from a cohort of patients and detection of patterns that differentiate driver from passenger mutations. Results We propose QuaDMutEx an QuadMutNetEx, a method that incorporates three novel elements: a new gene set penalty that includes non-linear penalization of multiple mutations in putative sets of driver genes, an ability to adjust the method to handle slow- and fast-evolving tumors, and a computationally efficient method for finding gene sets that minimize the penalty, through a combination of heuristic Monte Carlo optimization and exact binary quadratic programming. QuaDMutNetEx is our proposed method that combines protein-protein interaction networks to the method elements of QuaDMutEx. In particular, QuaDMutEx incorporates three novel elements: a non-linear penalization of multiple mutations in putative sets of driver genes, an ability to adjust the method to handle slow- and fast-evolving tumors, and a computationally efficient method for finding gene sets that minimize the penalty. In the new method, we incorporated a new quadratic rewarding term that prefers gene solution set that is connected with respect to protein-protein interaction networks. Compared to existing methods, the proposed algorithm finds sets of putative driver genes that show higher coverage and lower excess coverage in eight sets of cancer samples coming from brain, ovarian, lung, and breast tumors. Conclusions Superior ability to improve on both coverage and excess coverage on different types of cancer shows that QuaDMutEx and QuaDMutNetEx are tools that should be part of a state-of-the-art toolbox in the driver gene discovery pipeline. It can detect genes harboring rare driver mutations that may be missed by existing methods.