Optimization problems of location-assignment correspond to a wide range of real situations, such as factory network design. However most of the previous works seek in most cases at minimizing a cost function. Traffic incidents routinely impact the performance and the safety of the supply. These incidents can not be totally avoided and must be regarded. A way to consider these incidents is to design a network on which multiple assignments are performed. Precisely, the problem we focus on deals with power supplying that has become a more and more complex and crucial question. Many international companies have customers who are located all around the world; usually one customer per country. At the other side of the scale, power extraction or production is done in several sites that are spread on several continents and seas. A strong willing of becoming less energetically-dependent has lead many governments to increase the diversity of supply locations. For each kind of energy, many countries expect to deal ideally with 2 or 3 location sites. As a decrease in power supply can have serious consequences for the economic performance of a whole country, companies prefer to balance equally the production rate among all sites as the reliability of all the sites is considered to be very similar. Sharing equally the demand between the 2 or 3 sites assigned to a given area is the most common way. Despite the cost of the network has an importance, it is also crucial to balance the loading between the sites to guarantee that no site would take more importance than the others for a given area. In case an accident happens in a site or in case technical problems do not permit to satisfy the demand assigned to the site, the overall power supply of this site is still likely to be ensured by the one or two available remaining site(s). It is common to assign a cost per open power plant and another cost that depends on the distance between the factory or power extraction point and the customer. On the whole, such companies who are concerned in the quality service of power supply have to find a good trade-off between this factor and their overall functioning cost. This situation exists also for companies who supplies power at the national scale. The expected number of areas as well that of potential sites, can reach 100. However the targeted size of problem to be solved is 50. This thesis focuses on devising an efficient methodology to provide all the solutions of this bi-objective problem. This proposal is an investigation of close problems to delimit the most relevant approaches to this untypical problem. All this work permits us to present one exact method and an evolutionary algorithm that might provide a good answer to this problem. / Master of Science

Over the years, phased array antennas have provided electronic scanning with high gain and low sidelobe levels for many radar and satellite applications. The need for higher bandwidth as well as greater scanning ability has led to research in the area of aperiodically spaced antenna arrays. Aperiodic arrays use variable spacing between antenna elements and generally require fewer elements than periodically spaced arrays to achieve similar far field pattern performance. This reduction in elements allows the array to be built at much lower cost than traditional phased arrays. This thesis introduces the concept of aperiodic phased arrays and their design via optimization algorithms, specifically Particle Swarm Optimization. An axial mode helix is designed as the antenna array element to obtain the required half power beamwidth and bandwidth. The final optimized aperiodic array is compared to a traditional periodic array and conclusions are made. / Master of Science

In this thesis, we present variants of Shor and Zhurbenko's r-algorithm, motivated by the memoryless and limited memory updates for differentiable quasi-Newton methods. This well known r-algorithm, which employs a space dilation strategy in the direction of the difference between two successive subgradients, is recognized as being one of the most effective procedures for solving nondifferentiable optimization problems. However, the method needs to store the space dilation matrix and update it at every iteration, resulting in a substantial computational burden for large-sized problems. To circumvent this difficulty, we first develop a memoryless update scheme. In the space transformation sense, the new update scheme can be viewed as a combination of space dilation and reduction operations. We prove convergence of this new algorithm, and demonstrate how it can be used in conjunction with a variable target value method that allows a practical, convergent implementation of the method. For performance comparisons we examine other memoryless and limited memory variants, and also prove a modification of a related algorithm due to Polyak that employs a projection on a pair of Kelley's cutting planes. These variants are tested along with Shor's r-algorithm on a set of standard test problems from the literature as well as on randomly generated dual transportation and assignment problems. Our computational experiments reveal that the proposed memoryless space dilation and reduction algorithm (VT-MSDR) and the proposed modification of the Polyak-Kelly cutting plane method (VT-PKC) provide an overall competitive performance relative to the other methods tested with respect to solution quality and computational effort. The r-Algorithm becomes increasingly more expensive with an increase in problem size, while not providing any gain in solution quality. The fixed dilation (with no reduction) strategy (VT-MSD) provides a comparable, though second-choice, alternative to VT-MSDR. Employing a two-step limited memory extension over VT-MSD sometimes helps in improving the solution quality, although it adds to computational effort, and is not as robust a procedure. / Master of Science

This thesis is concerned with the development of algorithms for simulation optimization (SO), a special case of stochastic optimization where the objective function can only be evaluated through noisy observations from a simulation. Deterministic techniques, when directly applied to simulation optimization problems fail to converge due to their inability to handle randomness thus requiring sophisticated algorithms. However, many existing algorithms dedicated for simulation optimization often show poor performance on implementation as they require extensive parameter tuning. To overcome these shortfalls with existing SO algorithms, we develop ADALINE, a line search based algorithm that eliminates the need for any user defined parameters. ADALINE is designed to identify a local minimum on continuous and integer ordered feasible sets. ADALINE on a continuous feasible set mimics deterministic line search algorithms, while it iterates between a line search and an enumeration procedure on integer ordered feasible sets in its quest to identify a local minimum. ADALINE improves upon many of the existing SO algorithms by determining the sample size adaptively as a trade-off between the error due to estimation and the optimization error, that is, the algorithm expends simulation effort proportional to the quality of the incumbent solution. We also show that ADALINE converges ``almost surely'' to the set of local minima. Finally, our numerical results suggest that ADALINE converges to a local minimum faster, outperforming other advanced SO algorithms that utilize variable sampling strategies. To demonstrate the performance of our algorithm on a practical problem, we apply ADALINE in solving a surgery rescheduling problem. In the rescheduling problem, the objective is to minimize the cost of disruptions to an existing schedule shared between multiple surgical specialties while accommodating semi-urgent surgeries that require expedited intervention. The disruptions to the schedule are determined using a threshold based heuristic and ADALINE identifies the best threshold levels for various surgical specialties that minimizes the expected total cost of disruption. A comparison of the solutions obtained using a Sample Average Approximation (SAA) approach, and ADALINE is provided. We find that the adaptive sampling strategy in ADALINE identifies a better solution quickly than SAA. / Ph. D. / This thesis is concerned with the development of algorithms for simulation optimization (SO), where the objective function does not have an analytical form, and can only be estimated through noisy observations from a simulation. Deterministic techniques, when directly applied to simulation optimization problems fail to converge due to their inability to handle randomness thus requiring sophisticated algorithms. However, many existing algorithms dedicated for simulation optimization often show poor performance on implementation as they require extensive parameter tuning. To overcome these shortfalls with existing SO algorithms, we develop ADALINE, a line search based algorithm that minimizes the need for user defined parameter. ADALINE is designed to identify a local minimum on continuous and integer ordered feasible sets. ADALINE on continuous feasible sets mimics deterministic line search algorithms, while it iterates between a line search and an enumeration procedure on integer ordered feasible sets in its quest to identify a local minimum. ADALINE improves upon many of the existing SO algorithms by determining the sample size adaptively as a trade-off between the error due to estimation and the optimization error, that is, the algorithm expends simulation effort proportional to the quality of the incumbent solution. Finally, our numerical results suggest that ADALINE converges to a local minimum faster than the best available SO algorithm for the purpose. To demonstrate the performance of our algorithm on a practical problem, we apply ADALINE in solving a surgery rescheduling problem. In the rescheduling problem, the objective is to minimize the cost of disruptions to an existing schedule shared between multiple surgical specialties while accommodating semi-urgent surgeries that require expedited intervention. The disruptions to the schedule are determined using a threshold based heuristic and ADALINE identifies the best threshold levels for various surgical specialties that minimizes the expected total cost of disruption. A comparison of the solutions obtained using traditional optimization techniques, and ADALINE is provided. We find that the adaptive sampling strategy in ADALINE identifies a better solution more quickly than traditional optimization.

Critical infrastructures such as power grids, transportation networks, water systems, gas networks, and others have become increasingly reliant on each other for functional facilities in recent years. Consequently, coordinating these interdependent networks has become crucial for synergistic operation. Since these infrastructures are generally managed by different entities, this dissertation presents decentralized optimization algorithms and solution methods tailored to address various coordination challenges. First, this dissertation presents a decentralized framework for coordinating optimization models of power and transportation networks for the integration of electric vehicles with minimal information exchange. Since the transportation optimization model is in a mixed-integer program (MIP) form, a novel decentralized optimization algorithm that guarantees optimality and convergence for the decentralized coordination of MIPs is proposed. Moreover, the proposed decentralized optimization algorithm is further improved to tackle the unique challenges of intertwined power and water networks, where boundary variables (variables shared by two optimization models) are discontinuous. Therefore, the mixed-integer boundary-compatible decentralized optimization algorithm is proposed to coordinate MIPs with discontinuous boundary variables. Second, in addition to the coordination of infrastructure from the economic perspective, this dissertation also focuses on resilient and uncertainty-aware coordination of the power grid and other critical infrastructures. For power distribution system restoration after disasters, the coordination of emergency response resources such as mobile energy resources and repair crews is proposed. However, the computational requirement of the restoration model is high; therefore, a computationally efficient power distribution system restoration approach is investigated. Moreover, with the increasing penetration of variable renewable energy sources like solar energy, the necessity to consider uncertainties in the operation and planning of the power grid is heightened. Therefore, the efficacy of the proposed decentralized optimization algorithms in coordinating mixed-integer programs under uncertainty is validated by coordinating the chance-constrained optimization models of the power grid and other critical infrastructures.

2024 / With the exponential growth of data generation, optimizing databases and its underlying storage structure has emerged as an area of extensive and critical research. This thesis addresses an important aspect of this challenge by introducing an innovative approach to optimize Log Structured Merge Trees (LSM Trees), a state-of-the-art storage structure primarily created for write-heavy database applications without compromising on read operations. It uses Bayesian optimization via the BoTorch library to fine-tune the LSM tree configurations to balance across different workload configurations and address the longstanding challenge of dynamic workload adaptability. A pivotal aspect of this approach is the adaptation of Bayesian optimization to explore the LSM Tree parameter space intelligently by separately handling categorical and continuous variables and enabling a better, more complex examination of the cost surface. This is done by comprehensively analyzing the LSM Tree structure, its amplification issues, and understanding the overall operational mechanics of this storage structure. The proposed solution is implemented not only on the classic LSM Tree module, but also on hybrid LSM Tree structures and their compaction strategies. The proposed solution approaches this problem by combining the BoTorch framework with an established analytical cost model for evaluation that serves as the objective function for the optimization process. This approach addresses a notable limitation of using the closed-form cost function to predict design decisions which solve a Linear Program instead of a Linear Integer Program and treats all values as continuous parameters, which does not accurately reflect the discrete nature of certain design decisions. Experimental validation on diverse workloads demonstrate the efficiency of the proposed approach and show significant performance gains over traditional tuning methods. This thesis contributes to the growing research on database optimization strategies and help database administrators tune the performance of the LSM Tree structure with minimal manual intervention by providing an incremental step towards self-tuning database management systems, where tuning and optimization can be automated and help in paving the way for better, more reliable storage solutions.

Time-delay dynamical systems are used to model many real-world engineering systems, where the future evolution of a system depends not only on current states but also on the history of states. For this reason, the study of stability and control of time-delay systems is of theoretical and practical importance. In this thesis, we develop several stability analysis frameworks for dynamical systems in the presence of communication and computation time-delays, and apply our results to different challenging engineering problems. The thesis first considers delay-independent stability of positive monotone systems. We show that the asymptotic stability of positive monotone systems whose vector fields are homogeneous is independent of the magnitude and variation of time-varying delays. We present explicit expressions that allow us to give explicit estimates of the decay rate for various classes of time-varying delays. For positive linear systems, we demonstrate that the best decay rate that our results guarantee can be found via convex optimization. We also derive a set of necessary and sufficient conditions for asymptotic stability of general positive monotone (not necessarily homogeneous) systems with time-delays. As an application of our theoretical results, we discuss delay-independent stability of continuous-time power control algorithms in wireless networks. The thesis continues by studying the convergence of asynchronous fixed-point iterations involving maximum norm pseudo-contractions. We present a powerful approach for characterizing the rate of convergence of totally asynchronous iterations, where both the update intervals and communication delays may grow unbounded. When specialized to partially asynchronous iterations (where the update intervals and communication delays have a fixed upper bound), or to particular classes of unbounded delays and update intervals, our approach allows to quantify how the degree of asynchronism affects the convergence rate. In addition, we use our results to analyze the impact of asynchrony on the convergence rate of discrete-time power control algorithms in wireless networks. The thesis finally proposes an asynchronous parallel algorithm that exploits multiple processors to solve regularized stochastic optimization problems with smooth loss functions. The algorithm allows the processors to work at different rates, perform computations independently of each other, and update global decision variables using out-of-date gradients. We characterize the iteration complexity and the convergence rate of the proposed algorithm, and show that these compare favourably with the state of the art. Furthermore, we demonstrate that the impact of asynchrony on the convergence rate of the algorithm is asymptotically negligible, and a near-linear speedup in the number of processors can be expected. / Tidsfördröjningar uppstår ofta i tekniska system: det tar tid för två ämnen attblandas, det tar tid för en vätska att rinna från ett kärl till ett annat, och det tar tid att överföra information mellan delsystem. Dessa tidsfördröjningar lederofta till försämrad systemprestanda och ibland även till instabilitet. Det är därförviktigt att utveckla teori och ingenjörsmetodik som gör det möjligt att bedöma hur tidsfördröjningar påverkar dynamiska system. I den här avhandlingen presenteras flera bidrag till detta forskningsområde. Fokusligger på att karaktärisera hur tidsfördröjningar påverkar konvergenshastigheten hos olinjära dynamiska system. I kapitel 3 och 4 behandlar vi olinjära system varstillstånd alltid är positiva. Vi visar att stabiliteten av dessa positiva system är oberoende av tidsfördröjningar och karaktäriserar hur konvergenshastigheten hos olinjära positiva system beror på tidsfördröjningarnas storlek. I kapitel 5 betraktar vi iterationer som är kontraktionsavbildningar, och analyserar hur deras konvergens påverkas av begränsade och obegränsade tidsfördröjningar. I avhandlingens sistakapitel föreslår vi en asynkron algoritm för stokastisk optimering vars asymptotiska konvergenshastighet är oberoende av tidsfördröjningar i beräkningar och i kommunikation mellan beräkningselement. / <p>QC 20151204</p>

Nonlinear Energy Sinks (NESs) are a promising technique for passively reducing the amplitude of vibrations. Through nonlinear stiffness properties, a NES is able to passively absorb energy. Unlike a traditional Tuned Mass Damper (TMD), NESs do not require a specific tuning and absorb energy from a wide range of frequencies. However, each NES is only efficient over a limited range of excitations. In addition, NES efficiency is extremely sensitive to perturbations in design parameters or loading, demonstrating a nearly discontinuous efficiency. Therefore, in order to optimally design a NES, uncertainties must be accounted for. This thesis focuses on optimally selecting parameters to design an effective NES system through optimization under uncertainty. For this purpose, a specific algorithm is introduced that makes use of clustering techniques to segregate efficient and inefficient NES behavior. SVM and Kriging approximations as well as new adaptive sampling techniques are used for the optimization under uncertainty. The variables of the problems are either random design variables or aleatory variables. For example, the excitation applied to the main vibrating system is treated as aleatory. In an effort to increase the range of excitations for which NESs are effective, a combination of NESs configured in parallel is considered. Optimization under uncertainty is performed on several examples with varying design parameters as well as different numbers of NESs (from 1 to 10). Results show that combining NESs in parallel is an effective method to increase the excitation range over which a NES is effective.

The contributions of this research are a scalable formulation and solution method for decentralized unit commitment, experimental results comparing decentralized unit commitment solution times to conventional unit commitment methods, a demonstration of the benefits of faster unit commitment computation time, and extensions of decentralized unit commitment to handle system network security constraints. We begin with a discussion motivating the shift from centralized power system control architectures to decentralized architectures and describe the characteristics of such an architecture. We then develop a formulation and solution method to solve decentralized unit commitment by adapting an existing approach for separable convex optimization problems to the nonconvex domain of unit commitment. The potential computational speed benefits of the novel decentralized unit commitment approach are then further investigated through a rolling-horizon framework that represents how system operators make decisions and adjustments online as new information is revealed. Finally, the decentralized unit commitment approach is extended to include network contingency constraints, a crucial function for the maintenance of system security. The results indicate decentralized unit commitment holds promise as a way of coordinating system operations in a future decentralized grid and also may provide a way to leverage parallel computing resources to solve large-scale unit commitment problems with greater speed and model fidelity than is possible with conventional methods.

published_or_final_version / Mathematics / Master / Master of Philosophy