In the literature, a large number of metaheuristic search techniques have been proposed up to present time and some of those have been used in structural optimization. Scatter search is one of those techniques which has proved to be effective when solving combinatorial and nonlinear optimization problems such as scheduling, routing, financial product design and other problem areas. Scatter search is an evolutionary method that uses strategies based on a composite decision rules and search diversification and intensification for generating new trial points. Broodly speaking, this thesis is concerned with the use and application of scatter search technique in structural optimization. A newly developed optimization algorithm called modified scatter search is modified which is computerized in a software called SOP2012. The software SOP2012 is integrated with well-known structural analysis software SAP2000 using application programming interface for size optimum design of steel structures. Numerical studies are carried out using a test suite consisting of five real size design examples taken from the literature. In these examples, various steel truss and frame structures are designed for minimum weight according to design limitations imposed by AISC-ASD (Allowable Stress Design Code of American Institute of Steel Construction). The results reveal that the modified scatter search technique is very effective optimization technique for truss structures, yet its performance can be assessed ordinary for frame structures.

Many important applications in the real world that can be modelled as combinatorial optimization problems are actually dynamic in nature. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. Moreover, dynamic combinatorial problems, when addressed, are typically tackled within an application context. <br /><br /> In this thesis, dynamic combinatorial problems are addressed collectively by adopting an evolutionary based algorithmic approach. On the plus side, their ability to manipulate several solutions at a time, their robustness and their potential for adaptability make evolutionary algorithms a good choice for solving dynamic problems. However, their tendency to converge prematurely, the difficulty in fine-tuning their search and their lack of diversity in tracking optima that shift in dynamic environments are drawbacks in this regard. <br /><br /> Developing general methodologies to tackle these conflicting issues constitutes the main theme of this thesis. First, definitions and measures of algorithm performance are reviewed. Second, methods of benchmark generation are developed under a generalized framework. Finally, methods to improve the ability of evolutionary algorithms to efficiently track optima shifting due to environmental changes are investigated. These methods include adapting genetic parameters to population diversity and environmental changes, the use of multi-populations as an additional means to control diversity, and the incorporation of local search heuristics to fine-tune the search process efficiently. <br /><br /> The methodologies developed for algorithm enhancement and benchmark generation are used to build and test evolutionary models for dynamic versions of the travelling salesman problem and the flexible manufacturing system. Results of experimentation demonstrate that the methods are effective on both problems and hence have a great potential for other dynamic combinatorial problems as well.

In today's world, it is becoming increasingly important to be able to design high performance integrated circuits (ICs) and have them run at as low power as possible. Gate sizing and threshold voltage (Vt) assignment optimizations are one of the major contributors to such trade-offs for power and performance of ICs. In fact, the ever increasing design sizes and more aggressive timing requirements make gate sizing and Vt assignment one of the most important CAD problems in physical synthesis. A promising gate sizing optimization algorithm has to satisfy requirements like being scalable to tackle very large design sizes, being able to optimally utilize a large (but finite) number of possible gate configurations available in standard cell library based on different gate sizes and/or threshold voltages (Vt) and/or gate lengths (Lg), and also, being able to handle non-convex cell delays in modern cell libraries. The work in this thesis makes use of the research-oriented infrastructure made available as part of the ISPD (International Symposium on Physical Design) 2012 Gate Sizing Contest that addresses the issues encountered in modern gate sizing problems. We present a two-phase optimization approach where Lagrangian Relaxation is used to formulate the optimization problem. In the first phase, the Lagrangian relaxed subproblem is iteratively solved using a greedy algorithm, while in the second phase, a cell downsizing and Vt upscaling heuristic is employed to further recover power from the timing-feasible and power-optimized sizing solution obtained at the end of first phase. We also propose a multi-core implementation of the first-phase optimizations, which constitute majority of the total runtime, to take advantage of multi-core processors available today. A speedup of the order of 4 to 9 times is seen on different benchmarks as compared to serial implementation when run on a 2 socket 6-core machine. Compared to the winner of ISPD 2012 contest, we further reduce leakage power by 17.21% and runtime by 87.92%, on average, while obtaining feasible sizing solutions on all the benchmark designs. / text

Les tâches réalisées en traitement d'image tendent à devenir de plus en plus complexes. Par exemple, dans le contexte routier, les systèmes d'aide à la conduite, (Advanced driver-assistance systems), visent à une automatisation complète de la tâche de conduite. L’évaluation de la fiabilité représente un enjeu important pour ce type d’application. Face à la difficulté des tâches à réaliser, les chaînes de traitements sont souvent divisées en de nombreuses étapes de calculs de sorte qu'il est difficile de caractériser les sorties de la chaîne en fonction des perturbations des entrées. Les étapes du traitement consistent le plus souvent en des problèmes formulés comme la minimisation d'une énergie. Cette énergie est généralement difficile à optimiser, ce qui nécessite la mise en œuvre de méthodes d’optimisation adaptées. Dans cette thèse, nous cherchons à caractériser la solution d’un traitement à partir des calculs réalisés au cours de l’étape d'optimisation. Cette approche nous a permis de proposer des indices de stabilité de la solution dans le cadre de deux méthodes d’optimisation discrètes : la coupure de graphe et la programmation dynamique. Tout d’abord, nous nous sommes intéressés au problème de la reconstruction stéréoscopique en contexte routier et au dé-bruitage, dans le cadre de l’optimisation par coupure de graphe. Les modèles issus de l’interprétation bayésienne amènent à optimiser des énergies qui ne peuvent pas être traitées avec les schémas d’optimisation classiques par fusion binaire. Nous avons proposé un schéma adapté qui met en jeu des fusions binaires par expansion et par saut. L’application de ce schéma aux problèmes de la reconstruction stéréoscopique et au dé-bruitage, nous a permis d’obtenir des solutions possédant les caractéristiques que nous recherchions : des contours d’objets nets et des dégradés progressifs dans les zones homogènes. Ensuite, dans le contexte de la programmation dynamique, nous avons réinterprété l’a priori mis en jeu dans la méthode de reconstruction Semi-Global Matching ainsi que certaines de ses variantes. Nous avons proposé d’ajouter un paramètre à ces méthodes afin de modifier les directions privilégiées par l’a priori. Enfin, nous avons proposé des indices de stabilité de la solution dans le cadre de la coupure de graphe et de la programmation dynamique. La prise en compte de ces indices, dans une étape de raffinement des solutions, permet une amélioration des résultats / Problems solved by image processing tend to be more and more complex. For instance, in road context, ADAS (Advanced driver-assistance systems) aim to a completely automatic diving tack. Evaluating system reliability is an important challenge in that case. These tasks being hard to perform, processing chains are often divide in numerous processing steps. As a consequence, characterizing the output using the input of the chain is not obvious. Most of the time, image processing steps are formulate as an energy minimization. These energies are often hard to minimize and need to apply suitable optimization methods. In this thesis, we aim to characterize the solution during the optimization step. Using this approach, we proposed stability index with two discrete optimization methods : graph-cut and dynamic optimization. First, we focused on stereoscopic reconstruction problem in road context and on denoising problem using graph-cut. Models obtained by Bayesian interpretation lead to optimize energies witch cannot be handled by classical binary fusion optimization scheme. We proposed a suitable scheme composed of fusion by expansion and fusions by step. When this scheme is apply to stereoscopic reconstruction and denoising, obtained solution have the wanted characteristics : sharp edges and shading in homogeneous areas. Next, in dynamic programming context, we reinterpreted the prior used in Semi-Global Matching (SGM) stereoscopic reconstruction method and in some of its variants. We proposed an additional parameter in order to modify the favored direction in the prior. At last, we proposed stability index of the solution in graph-cut and dynamic programing context. Using this index in a solution refinement step shows improvements

Financial markets use auctions to provide accurate liquidity snapshots for traded instruments. Combination orders, such as time spreads require the atomic trading of more than one security contract. In order to auction such complex order types, a new design, which considers all contingent instruments simultaneously, is required. This work develops an optimization model and a software implementation of the dualsided multi-unit combinatorial auction problem. The optimization objective is finding an equilibrium price vector and a winner selection such that the auction turnover is maximized. The auction requirements are modeled as a discrete optimization problem, suitable for standard integer programming solvers. The model’s correctness and tractability are tested using synthetically generated orders as well as real market data. Test results with both synthetic and authentic orders produced equilibrium prices within 3% of the expected instrument valuations, using closing prices as a benchmark, indicating high accuracy of the solutions. The use of combinatorial auctions exposes greater liquidity and overall turnover, both valuable to exchanges that receive large numbers of combination orders.

Decision diagrams have recently emerged as a promising approach for difficult scheduling problems, along with other challenging discrete optimization problems. Decision diagrams can offer a compact representation of the solution space, and has the ability to capture complex constraints that are hard to model or express in other techniques. This thesis explores two standard construction methods for relaxed decision diagrams, top-down construction and incremental refinement. The techniques are compared on their ability to handle scheduling problems with multiple time windows and precedence constraints. The construction methods are evaluated on several metrics, including generated bound, execution time, and the size of the diagram, on instances of the problem with up to 200 tasks. The results show that incremental refinement generates smaller diagrams with good bounds when compared to the top-down compilation algorithm; the reduction in diagram size and increase in bounds for incremental refinement comes at the expense of execution time compared to top-down compilation.

[pt] A manutenção tem relevante participação estratégica em uma companhia, fundamental para o sucesso das organizações, a atuação deste setor envolve a redução do tempo de máquinas paradas, contribuindo com a eficiência do processo e diminuição dos custos operacionais. A intervenção preventiva é um importante tipo de manutenção, seu propósito é diminuir as falhas fundamentada em um planejamento com intervalos definidos de tempo, no entanto, determinar o melhor período não é uma atividade trivial. O intuito deste trabalho é utilizar dos conceitos de programação matemática para formular um modelo que auxilie na definição de um cronograma de manutenção preventiva, visando encontrar o melhor intervalo de tempo para intervenção na máquina baseado em informações de custos, tempo de atendimento e capacidade de mão de obra. O modelo matemático foi aplicado ao ambiente ferroviário com a finalidade de certificar a viabilidade de utilização dos métodos de Pesquisa Operacional, os resultados obtidos comprovaram se tratar de uma boa ferramenta para aplicação. Frente ao modelo atual, o cronograma de manutenção preventiva desenvolvido neste trabalho proporcionou uma economia de 40 por cento para a companhia, além do aumento médio de 30 por cento de disponibilidade a cada trimestre das máquinas de modelo Socadora. / [en] Maintenance has a relevant strategic role in a company, fundamental to the success of organizations, the performance of this sector involves reducing the time of machine downtime, contributing to the efficiency of the process and reduction of operating costs. Preventive intervention is an important type of maintenance, its purpose is to reduce failures based on planning with defined time intervals, however, determining the best period is not a trivial activity. The purpose of this work is to use mathematical programming concepts to formulate a model that helps define a preventive maintenance schedule, aiming to find the best time interval for machine intervention based on cost information, service time and hand capacity. of work. The mathematical model was applied to the railway environment in order to certify the feasibility of using Operational Research methods, the results obtained proved to be a good tool for application. Compared to the current model, the preventive maintenance schedule developed in this work provided savings of 40 percent for the company, in addition to an average increase of 30 percent in availability each quarter of Socadora model machines.

This research work deals with the design and optimization of a large composite structure. In design of large structural systems, it is customary to divide the problem into many smaller independent/semi-independent local design problems. For example, the wing structure design problem is decomposed into several local panel design problem. The use of composite necessitates the inclusion of ply angles as design variables. These design variables are discrete in nature because of manufacturing constraint. The multilevel approach results into a nonblended solution with no continuity of laminate layups across the panels. The nonblended solution is not desirable because of two reasons. First, the structural integrity of the whole system is questionable. Second, even if there is continuity to some extent, the manufacturing process ends up being costlier. In this work, we develop a global local design methodology to design blended composite laminates across the whole structural system. The blending constraint is imposed via a guide based approach within the genetic algorithm optimization scheme. Two different blending schemes are investigated, outer and inner blending. The global local approach is implemented for a complex composite wing structure design problem, which is known to have a strong global local coupling. To reduce the computational cost, the originally proposed local one dimensional search is replaced by an intuitive local improvement operator. The local panels design problem arises in global/local wing structure design has a straight edge boundary condition. A postbuckling analysis module is developed for such panels with applied edge displacements. A parametric study of the effects of flexural and inplane stiffnesses on the design of composite laminates for optimal postbuckling performance is done. The design optimization of composite laminates for postbuckling strength is properly formulated with stacking sequence as design variables. Next, we formulate the stacking sequence design (fiber orientation angle of the layers) of laminated composite flat panels for maximum supersonic flutter speed and maximum thermal buckling capacity. The design is constrained so that the behavior of the panel in the vicinity of the flutter boundary should be limited to stable limit cycle oscillation. A parametric study is carried out to investigate the tradeoff between designs for thermal buckling and flutter. In an effort to include the postbuckling constraint into the multilevel design optimization of large composite structure, an alternative cheap methodology for predicting load paths in postbuckled structure is presented. This approach being computationally less expensive compared to full scale nonlinear analysis can be used in conjunction with an optimizer for preliminary design of large composite structure with postbuckling constraint. This approach assumes that the postbuckled stiffness of the structure, though reduced considerably, remains linear. The analytical expressions for postbuckled stiffness are given in a form that can be used with any commercially available linear finite element solver. Using the developed approximate load path prediction scheme, a global local design approach is developed to design large composite structure with blending and local postbuckling constraints. The methodology is demonstrated via a composite wing box design with blended laminates. / Ph. D.

Generalized hill climbing (GHC) algorithms provide a unifying framework for describing several discrete optimization problem local search heuristics, including simulated annealing and tabu search. A necessary and a sufficient convergence condition for GHC algorithms are presented. The convergence conditions presented in this dissertation are based upon a new iteration classification scheme for GHC algorithms. The convergence theory for particular formulations of GHC algorithms is presented and the implications discussed. Examples are provided to illustrate the relationship between the new convergence conditions and previously existing convergence conditions in the literature. The contributions of the necessary and the sufficient convergence conditions for GHC algorithms are discussed and future research endeavors are suggested. / Ph. D.

Identifying a globally optimal solution for an intractable discrete optimization problem is often cost prohibitive. Therefore, solutions that are within a predetermined threshold are often acceptable in practice. This dissertation introduces the concept of B-acceptable solutions where B is a predetermined threshold for the objective function value. It is difficult to assess a priori the effectiveness of local search algorithms, which makes the process of choosing parameters to improve their performance difficult. This dissertation introduces the B-acceptable solution probability in terms of B-acceptable solutions as a finite-time performance measure for local search algorithms. The B-acceptable solution probability reflects how effectively an algorithm has performed to date and how effectively an algorithm can be expected to perform in the future. The B-acceptable solution probability is also used to obtain necessary asymptotic convergence (with probability one) conditions. Upper and lower bounds for the B-acceptable solution probability are presented. These expressions assume particularly simple forms when applied to specific local search strategies such as Monte Carlo search and threshold accepting. Moreover, these expressions provide guidelines on how to manage the execution of local search algorithm runs. Computational experiments are reported to estimate the probability of reaching a B-acceptable solution for a fixed number of iterations. Logistic regression is applied as a tool to estimate the probability of reaching a B-acceptable solution for values of B close to the objective function value of a globally optimal solution as well as to estimate this objective function value. Computational experiments are reported with logistic regression for pure local search, simulated annealing and threshold accepting applied to instances of the TSP with known optimal solutions. / Ph. D.