MA336exam00pdf

Exam questions and solutions in PDF

MA336exam98

Exam questions and solutions in LaTex

MA336exam99

Exam questions and solutions in LaTex

MA336exam01

Exam questions and solutions in LaTex

MA336exam01pdf

Exam questions and solutions in PDF

MA336exam00

Exam questions and solutions in LaTex

MA336exam98pdf

Exam questions and solutions in PDF

Orthogonal packing of identical rectangles within isotropic convex regions

A mixed integer continuous nonlinear model and a solution method for the problem of orthogonally packing identical rectangles within an arbitrary convex region are introduced in the present work. The convex region is assumed to be made of an isotropic material in such a way that arbitrary rotations of the items, preserving the orthogonality constraint, are allowed. The solution method is based on a combination of branch and bound and active-set strategies for bound-constrained minimization of smooth functions. Numerical results show the reliability of the presented approach. (C) 2010 Elsevier Ltd. All rights reserved.

Interior point algorithm for linear programming used in transmission network synthesis

This article presents a well-known interior point method (IPM) used to solve problems of linear programming that appear as sub-problems in the solution of the long-term transmission network expansion planning problem. The linear programming problem appears when the transportation model is used, and when there is the intention to solve the planning problem using a constructive heuristic algorithm (CHA), ora branch-and-bound algorithm. This paper shows the application of the IPM in a CHA. A good performance of the IPM was obtained, and then it can be used as tool inside algorithm, used to solve the planning problem. Illustrative tests are shown, using electrical systems known in the specialized literature. (C) 2005 Elsevier B.V. All rights reserved.

O problema biobjetivo da árvore geradora quadrática em adjacência de arestas

The Quadratic Minimum Spanning Tree Problem (QMST) is a version of the Minimum Spanning Tree Problem in which, besides the traditional linear costs, there is a quadratic structure of costs. This quadratic structure models interaction effects between pairs of edges. Linear and quadratic costs are added up to constitute the total cost of the spanning tree, which must be minimized. When these interactions are restricted to adjacent edges, the problem is named Adjacent Only Quadratic Minimum Spanning Tree (AQMST). AQMST and QMST are NP-hard problems that model several problems of transport and distribution networks design. In general, AQMST arises as a more suitable model for real problems. Although, in literature, linear and quadratic costs are added, in real applications, they may be conflicting. In this case, it may be interesting to consider these costs separately. In this sense, Multiobjective Optimization provides a more realistic model for QMST and AQMST. A review of the state-of-the-art, so far, was not able to find papers regarding these problems under a biobjective point of view. Thus, the objective of this Thesis is the development of exact and heuristic algorithms for the Biobjective Adjacent Only Quadratic Spanning Tree Problem (bi-AQST). In order to do so, as theoretical foundation, other NP-hard problems directly related to bi-AQST are discussed: the QMST and AQMST problems. Bracktracking and branch-and-bound exact algorithms are proposed to the target problem of this investigation. The heuristic algorithms developed are: Pareto Local Search, Tabu Search with ejection chain, Transgenetic Algorithm, NSGA-II and a hybridization of the two last-mentioned proposals called NSTA. The proposed algorithms are compared to each other through performance analysis regarding computational experiments with instances adapted from the QMST literature. With regard to exact algorithms, the analysis considers, in particular, the execution time. In case of the heuristic algorithms, besides execution time, the quality of the generated approximation sets is evaluated. Quality indicators are used to assess such information. Appropriate statistical tools are used to measure the performance of exact and heuristic algorithms. Considering the set of instances adopted as well as the criteria of execution time and quality of the generated approximation set, the experiments showed that the Tabu Search with ejection chain approach obtained the best results and the transgenetic algorithm ranked second. The PLS algorithm obtained good quality solutions, but at a very high computational time compared to the other (meta)heuristics, getting the third place. NSTA and NSGA-II algorithms got the last positions

Uma análise experimental de algoritmos exatos aplicados ao problema da árvore geradora multiobjetivo

The Multiobjective Spanning Tree Problem is NP-hard and models applications in several areas. This research presents an experimental analysis of different strategies used in the literature to develop exact algorithms to solve the problem. Initially, the algorithms are classified according to the approaches used to solve the problem. Features of two or more approaches can be found in some of those algorithms. The approaches investigated here are: the two-stage method, branch-and-bound, k-best and the preference-based approach. The main contribution of this research lies in the fact that no research was presented to date reporting a systematic experimental analysis of exact algorithms for the Multiobjective Spanning Tree Problem. Therefore, this work can be a basis for other research that deal with the same problem. The computational experiments compare the performance of algorithms regarding processing time, efficiency based on the number of objectives and number of solutions found in a controlled time interval. The analysis of the algorithms was performed for known instances of the problem, as well as instances obtained from a generator commonly used in the literature

Searching for larval support for majoid families (Crustacea : Brachyura) with particular reference to Inachoididae Dana, 1851

We re-evaluated the larval support for families within majoids using the Wilcoxon signed-rank test with emphasis on Inachoididae. To accomplish our objectives, we added 10 new taxa, two of which are traditionally assigned to the family of special interest, to a previous larval database for majoids, and re-appraised the larval characters used in earlier studies. Phylogenetic analysis was performed with PAUP* using the heuristic search with 50 replicates or the branch-and-bound algorithm when possible. Multi-state transformation series were considered unordered; initially characters were equally weighted followed by successive weighting, and trees were rooted at the Oregoniidae node. Ten different topological constraints were enforced for families to evaluate tree length under the assumption of monophyly for each taxonomic entity. Our results showed that the tree length of most constrained topologies was not considerably greater than that of unconstrained analysis in which most families nested as paraphyletic taxa. This may indicate that the present larval database does not provide strong support for paraphyly of the taxa in question. For Inachoididae, although the Wilcoxon signed-rank test rejected a significant difference between unconstrained and constrained cladograms, we were unable to provide a single synapomorphy for this clade. Except for the conflicting position of Leurocyclus and Stenorhynchus, the two clades correspond to the traditional taxonomic arrangement. Among inachoidids, the clade (Anasimus (Paradasygyius (Collodes + Pyromaia))) is supported, whereas for inachids, the clade (Inachus (Macropodia + Achaeus)) is one of the most supported clades within majids. As often stated, only additional characters will provide a better test for the monophyly of Inachoididae and other families within Majoidea.

O problema de corte de placas defeituosas

O problema tratado neste trabalho consiste em cortar uma placa retangular em peças menores retangulares, de modo que a perda seja minimizada. A placa, entretanto, contém defeitos bem localizados. Propomos uma abordagem em grafo E/OU para representação das soluções possíveis e um método de enumeração implícita para determinar a solução ótima. Resultados computacionais demonstram a efetividade da abordagem.

Global optimization approach for the H2-norm model reduction problem

A branch and bound algorithm is proposed to solve the H2-norm model reduction problem for continuous-time linear systems, with conditions assuring convergence to the global optimum in finite time. The lower and upper bounds used in the optimization procedure are obtained through Linear Matrix Inequalities formulations. Examples illustrate the results.

Otimização global para os problemas de redução H2 de modelos e redução H2 da ordem do controlador

A branch and bound algorithm is proposed to solve the H2-norm model reduction problem and the H2-norm controller reduction problem, with conditions assuring convergence to the global optimum in finite time. The lower and upper bounds used in the optimization procedure are obtained through linear matrix inequalities formulations. Examples illustrate the results.