During the last decade, there have been major advances in solving a class of large-scale real world combinatorial optimization problems. Such problems are formulated as Travelling Salesman Problems (TSP), some involving up to thousands of cities. These achievements, mainly due to the use of so called polyhedral techniques, have established the importance of the polyhedral study for various combinatorial optimization problems. This thesis studies polyhedral structures of two well known combinatorial problems: (i) precedence constrained single machine scheduling and (ii) TSP, both Symmetric TSP (STSP) and Asymmetric TSP (ATSP). These problems are of both theoretical interest and practical importance. Better knowledge of the polyhedral descriptions of these problems may facilitate the polyhedral study of more complex scheduling and routing problems. For the scheduling problem, we present two classes of facetial inequalities, which suffice to describe the linear system of the scheduling problem when the precedence constraints are series-parallel. We also propose a cutting plane procedure based on these facet cuts. The computational results show the procedure yields feasible schedules with relative deviations from the optimum less than 0.25% on the average and less than 1% in the empirical worst case. For TSPs, we explore a Hamiltonian path approach to the polyhedral study. We propose various facet extension techniques for deriving large classes of facets from known facets. In the STSP case, we propose new clique lifting results. In the ATSP case, we develop a Tree Composition method, which generates all non-spanning clique tree facetial inequalities. / Business, Sauder School of / Graduate

Analog computer methods are developed for iterative parameter optimization and continuous identification of linear systems with time delay. A unified treatment of structural sensitivity analysis is presented. New results are presented on the simultaneous generation of the second-order sensitivity functions for a class of systems. To test the theory, a simple controller is proposed for a linear time-invariant process with time delay. The controller parameters are to be adjusted so that the process output closely approximates some desired output, while remaining insensitive to fluctuations in the plant delay. For this purpose, an iterative procedure is used to minimize a combined error-sensitivity performance index. Two continuous identification methods are presented. The first of these is an output error method derived using structural sensitivity analysis, while the second is an equation error method. It is assumed that processes to be identified can be represented by linear differential-difference equations. Unknown parameters in these equations are determined by a steepest descent technique. Both methods are applied for the first time to the important problem, of identifying constant and time varying time delays. The two methods are compared, and the equation error method is found to be superior. It is shown that this method is stable in the linear region in parameter space, and is always stable if all process delays are known. Techniques leading to a more economical implementation of the equation error method are presented. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

Closed-loop optimization deals with problems in which candidate solutions are evaluated by conducting experiments, e.g. physical or biochemical experiments. Although this form of optimization is becoming more popular across the sciences, it may be subject to rather unexplored resourcing issues, as any experiment may require resources in order to be conducted. In this thesis we are concerned with understanding how evolutionary search is affected by three particular resourcing issues -- ephemeral resource constraints (ERCs), changes of variables, and lethal environments -- and the development of search strategies to combat these issues. The thesis makes three broad contributions. First, we motivate and formally define the resourcing issues considered. Here, concrete examples in a range of applications are given. Secondly, we theoretically and empirically investigate the effect of the resourcing issues considered on evolutionary search. This investigation reveals that resourcing issues affect optimization in general, and that clear patterns emerge relating specific properties of the different resourcing issues to performance effects. Thirdly, we develop and analyze various search strategies augmented on an evolutionary algorithm (EA) for coping with resourcing issues. To cope specifically with ERCs, we develop several static constraint-handling strategies, and investigate the application of reinforcement learning techniques to learn when to switch between these static strategies during an optimization process. We also develop several online resource-purchasing strategies to cope with ERCs that leave the arrangement of resources to the hands of the optimizer. For problems subject to changes of variables relating to the resources, we find that knowing which variables are changed provides an optimizer with valuable information, which we exploit using a novel dynamic strategy. Finally, for lethal environments, where visiting parts of the search space can cause the permanent loss of resources, we observe that a standard EA's population may be reduced in size rapidly, complicating the search for innovative solutions. To cope with such scenarios, we consider some non-standard EA setups that are able to innovate genetically whilst simultaneously mitigating risks to the evolving population.

This thesis is concerned with estimation and control of linear distributed parameter systems. For the estimation of linear deterministic continuous-time distributed parameter systems, a linear deterministic distributed parameter filter that yields the state estimate based on noiseless linear measurements available over the complete occupied spatial domain is derived by consideration of a Lyapunov type of stability. The general results are then specialized to the case when noiseless linear measurements are available at only several points in the spatial domain. A numerical example illustrates its use in an overall control scheme. For the estimation of linear stochastic discrete-time distributed parameter systems, a linear discrete-time distributed parameter filter having a predictor-corrector structure, that yields the minimum-variance estimate of the state based on noise-corrupted linear measurements assumed available at only several spatial locations, is derived. The filtered estimate and the filtering error are shown to satisfy an orthogonal projection lemma, whence a Wiener-Hopf equation is derived. The filter is implementable on-line and a numerical example illustrates its use. The optimal pointwise regulation control problem for linear stochastic discrete-time distributed parameter systems is treated through application of dynamic programming. The separation of the complete control scheme into the estimation and control subsystems is shown. Its usefulness is illustrated in a numerical example. By first expanding Green's function and then considering the limiting behaviour of the corresponding discrete-time results on estimation and control obtained previously, solutions of the continuous-time linear minimum-variance filtering estimation and optimal pointwise regulation control problems for linear stochastic continuous-time distributed parameter systems are obtained. Further, a separation theorem is obtained and Kalman's duality theorem extended. For the pointwise regulation control problem of linear stochastic discrete-time distributed parameter systems, the case of unknown noise characteristics is treated. Based on an examination of the open-loop-optimal feedback control approach, a suboptimal control scheme is proposed. A filter that is adaptively selected on-line based on minimizing an instantaneous cost functional so derived from the original one as to realize a trade-off between control and estimation costs is put forward. A numerical example shows the effectiveness of the suboptimal control scheme in comparison with the optimal one. / Applied Science, Faculty of / Electrical and Computer Engineering, Department of / Graduate

M.Sc. (Computer Science) / Chapter 1 is a summary in which the problems- discussed in this study, as well as the relationship between them are shown. The algorithmic notation used when discussing the problems are also defined. In chapter 2 the three classes of algorithms for finding a minimum spanning tree, i.e. the algorithms of Prim, Kruskal and SolIin are discussed. PASCAL implementations of all the algorithms are presented. We also report on our computational experience with these implementations. It was found that the implementation of the Prim algorithm was very efficient, while implementations of the Kruskal algorithm also gave good results. Implementations of the Sollin algorithm were less efficient, because of the complex data structures involved. Algorithms for finding an optimum arborescence or branching in a network have independently been proposed by Edmonds, Chu & Liu as well as Bock. Tarjan as well as Camerini et al subsequently discussed aspects of the efficient implementation of the algorithm. In chapter 3 we draw attention to the related work of Fulkerson by reformulating the Edmonds-Fulkerson algorithm and giving a simple proof of the correctness of the algorithm. We also discuss and present an implementation of the algorithm and report on our computational experience. From the results presented it is clear that the number of cycles encountered during the first phase of the algorithm has a significant effect on the efficiency of the algorithm...

In this thesis, we address a multi-objective personnel scheduling problem where personnel’s workload is uncertain and propose a two-stage robust modelling approach with demand uncertainty. In the first stage, we model a multi-objective personnel scheduling problem without incorporating demand coverage and, in the second stage, we minimize over or under-staffing after the realization of the demand and the assignments from the first stage. Two solution approaches are introduced for this model. The first approach solves the proposed model through a cutting plane strategy known as Benders dual cutting plane method, and the second approach reformulates the problem based on the strong duality theory. As a case study, the proposed model and the first solution approach are applied to an existing scheduling problem in the pathology department at The Ottawa Hospital. It is shown that the proposed model is successful at reducing the unmet demand while maintaining the performance with respect to other metrics when compared against the deterministic alternative.

No description available.

The optimization of photovoltaic (PV) power generation system requires an accurate system performance model capable of validating the PV system optimization design. Currently, many commercial PV system modeling programs are available, but those programs are not able to model PV systems on a distorted ground level. Furthermore, they were not designed to optimize PV systems that are already installed. To solve these types of problems, this thesis proposes an optimization method using model simulations and a MATLAB-based PV system performance model. The optimization method is particularly designed to address partial shading issues often encountered in PV system installed on distorted ground. The MATLAB-based model was validated using the data collected from the Cal Poly Gold Tree Solar Field. It was able to predict the system performance with 96.4 to 99.6 percent accuracy. The optimization method utilizes the backtracking algorithm already installed in the system and the pitch distance to control the angle of the tracker and reduces solar panels partial shading on the adjacent row to improve system output. With pitch distances reduced in the backtracking algorithm between 2.5 meters and 3 meters, the inverter with inter-row shading can expect a 10.4 percent to 28.9 percent increase in power production. The implementation and calibration of this optimization method in the field this spring was delayed due to COVID-19. The field implementation is now expected to start this summer.

The aim of the thesis is to rationalize the water heaters welding area in Tatramat company - ohrievače s.r.o. The rationalization consists of three parts. The first part deals with the arrangement of the workplaces, the second part re-evaluates the monthly production planning. The third part describes in detail the production of one type, which based on simulations created in the simulation software Witness, compares the recorded time in company informartion system Orfert to the real production time in the operation. Each individual part offers optimization proposals and merging them into one unit, will create an efficient, transparent and economically value adding rationalization of the water heaters welding area.

Diplomová práca sa zaoberá návrhom a realizáciou inteligentného optimalizačného modulu pre podnikový informačný systém. Optimalizačný modul bude vytvárať celoročné plány údržby s rovnomerným množstvom údržbárskych aktivít v jednotlivých týždňoch a plány pre výrobu s pravidelnými odstávkami. V úvode je uvedený prehľad použiteľných optimalizačných metód, z ktorých sú vybrané metódy pre ďalšiu fázu, testovanie. Nelineárna metóda najmenších štvorcov z Matlab Optimization Toolbox, genetický algoritmus a ABC algoritmus budú otestované na zadanej plánovacej úlohe. Na základe výsledkov testu bude najlepšia metóda implementovaná v podnikovom informačnom systéme. Takto doplnený informačný systém umožňuje vytvárať kvalitnejšie plány údržby a tým zvýšiť celkovú efektivitu podniku.