There are many practical decision problems that fall into the category of network flow problems: numerous examples of applications can be found in areas such as telecommunications, logistics, distributions, engineering, computer science and so on. One of the most popular and valuable tools to solve network flow problems of a topological nature is the use of linear programming models. An important extension of these models is that of integer programming models that deal with problems where some, or all, of the variables are required to assume integer variables. A significant application in this class of problems is the knapsack problem that arises in different contexts such as loading containers in aircraft or satisfying the demand for various lengths of cloth which must be cut from fixed length bolts of fabric. In this study, the feasibility of representing a network flow model in a tree network model and subsequently solving it using a tree knapsack approach is investigated. To compare and validate the proposed technique, a specific case study was chosen from the literature that can be used as a basis for the research project. The said study was an oil pipeline design problem, addressed by Brimberg et al. (2003). This focuses on the optimal design of an oil pipeline network for the South Gabon oil field in Africa. The objective was to reduce oil transportation costs to a major port. Following an overview of different network flow and knapsack models, an overview of the said matter is presented. A description of the proposed tree knapsack approach and the application of this approach to the given problem is given. Results have indicated that it is feasible to apply a tree knapsack approach to solve network flow problems. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.

Computational grids are distributed systems composed of heterogeneous computing resources which are distributed geographically and administratively. These highly scalable systems are designed to meet the large computational demands of many users from scientific and business orientations. This dissertation address problems related to the allocation of the computing resources which compose a grid. First, the design of a pan-Canadian grid is presented. The design exploits the maturing stability of grid deployment toolkits, and introduces novel services for efficiently allocating the grids resources. The challenges faced by this grid deployment motivate further exploration in optimizing grid resource allocations. The primary contribution of this dissertation is one such technique for allocating grid resources. By applying a utility model to the grid allocation options, it is possible to quantify the relative merits of the various possible scheduling decisions. Indeed, a number of utility heuristics are derived to provide quality-of-service policies on the grid; these implement scheduling policies which favour efficiency and also allow users to intervene with urgent tasks. Using this model, the allocation problem is then formulated as a knapsack problem. Formulation in this manner allows for rapid solution times and results in nearly optimal allocations. The combined utility/knapsack approach to grid resource allocation is first presented in the allocation of single resource type, processors. By evaluating the approach with novel utility heuristics using both random and real workloads, it is shown to result in efficient schedules which have characteristics that match the intended policies. Additionally, two design and analysis techniques are performed to optimize the design of the utility/knapsack scheduler; these techniques play a significant role in practical adoption of the approach. Next, the utility/knapsack approach is extended to the allocation of multiple resource types. This extension generalizes the grid allocation solution a wider variety of resources, including processors, disk storage, and network bandwidth. The general technique, when combined with new heuristics for the varied resource types, is shown to result in improved performance against reference strategies. This dissertation concludes with a novel application of the utility/knapsack approach to fault-tolerant task scheduling. Computational grids typically feature many techniques for providing fault tolerance to the grid tasks, including retrying failed tasks or replicating running tasks. By applying the utility/knapsack approach, the relative merits of these varied techniques can be quantified, and the overall number of failures can be decreased subject to resource cost considerations.

Several techniques were studied to select and prioritize technologies for a complex system. Based on the findings, a method called Pareto Optimization and Selection of Technologies (POST) was formulated to efficiently explore the combinatorial technology space. A knapsack problem was selected as a benchmark problem to test-run various algorithms and techniques of POST. A Monte Carlo simulation using the surrogate models was used for uncertainty quantification. The concepts of graph theory were used to model and analyze compatibility constraints among technologies. A probabilistic Pareto optimization, based on the concepts of Strength Pareto Evolutionary Algorithm II (SPEA2), was formulated for Pareto optimization in an uncertain objective space. As a result, multiple Pareto hyper-surfaces were obtained in a multi-dimensional objective space; each hyper-surface representing a specific probability level. These Pareto layers enabled the probabilistic comparison of various non-dominated technology combinations. POST was implemented on a technology exploration problem for a 300 passenger commercial aircraft. The problem had 29 identified technologies with uncertainties in their impacts on the system. The distributions for these uncertainties were defined using beta distributions. Surrogate system models in the form of Response Surface Equations (RSE) were used to map the technology impacts on the system responses. Computational complexity of technology graph was evaluated and it was decided to use evolutionary algorithm for probabilistic Pareto optimization. The dimensionality of the objective space was reduced using a dominance structure preserving approach. Probabilistic Pareto optimization was implemented with reduced number of objectives. Most of the technologies were found to be active on the Pareto layers. These layers were exported to a dynamic visualization environment enabled by a statistical analysis and visualization software called JMP. The technology combinations on these Pareto layers are explored using various visualization tools and one combination is selected. The main outcome of this research is a method based on consistent analytical foundation to create a dynamic tradeoff environment in which decision makers can interactively explore and select technology combinations.

The aim of the research presented in this thesis is to investigate the use of various optimisation heuristics in the fields of automated cryptanalysis and automated cryptographic function generation. These techniques were found to provide a successful method of automated cryptanalysis of a variety of the classical ciphers. Also, they were found to enhance existing fast correlation attacks on certain stream ciphers. A previously proposed attack of the knapsack cipher is shown to be flawed due to the absence of a suitable solution evaluation mechanism. Finally, a new approach for finding highly nonlinear Boolean functions is introduced.

Made available in DSpace on 2016-12-12T20:22:53Z (GMT). No. of bitstreams: 1 LEANDERSON ANDRE.pdf: 2236080 bytes, checksum: a52e91a8b1a8e6a12497786254e94344 (MD5) Previous issue date: 2015-08-27 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Nature offers a wide range of phenomena that inspire the development of new technologies. The researchers from the area of Natural Computing abstracts the concept of optimization from various biological processes such as the evolution of species, the behavior of social groups, the search for food, among others. Such computer systems that have a similarity to natural biological systems are called biologically plausible. The development of biologically plausible algorithms gets interesting by the fact that biological systems are able to handle extremely complex problems. In this way, symbiotic relationships are one of several phenomena that can be observed in nature. These relationships consist of interactions that organisms carry out with each other resulting in benefit or disadvantage to those involved. In an optimization context, symbiotic relationships can be used to perform exchange of information between populations of candidate solutions to a given problem. Thus, this work highlights the concepts involving symbiotic relationships that may be important for the development of computer systems to solve complex problems. The main discussion presented in this study refers to the use of symbiotic relationships between populations of candidate solutions co-evolving in an ecological context. According to the analogy, populations interact with each other according to a specific symbiotic relationship in order to evolve their solutions. The proposed model is applied to several continuous benchmark functions with a high number of dimensions (D = 200) and in several benchmark instances of the multiple knapsack problem. The results obtained so far were promising concerning the application of symbiotic relationships. Finally, the conclusions are presented and some future directions for research are suggested. / A Natureza apresenta uma grande variedade de fenômenos que inspiram o desenvolvimento de novas tecnologias. Os pesquisadores da área de Computação Natural abstraem o conceito de otimização de vários processos biológicos, tais como a evolução das espécies, comportamento de grupos sociais, busca por comida, dentre outros. Tais sistemas computacionais que apresentam uma semelhança com os sistemas biológicos naturais são chamados de biologicamente plausíveis. O desenvolvimento de algoritmos biologicamente plausíveis se torna interessante pelo fato de que os sistemas biológicos são capazes de lidar com problemas extremamente complexos. As relações simbióticas são um dos vários fenômenos que podem ser observados na natureza. Essas relações consistem de interações que organismos realizam entre si resultando em benefícios ou prejuízos para os envolvidos. Em um contexto de otimização, as relações simbióticas podem ser utilizadas para realizar a troca de informação entre populações de soluções candidatas para um dado problema. Desta forma, este trabalho destaca os conceitos que envolvem as relações simbióticas que podem ser importantes para o desenvolvimento de sistemas computacionais para a resolução de problemas complexos. A principal discussão apresentada nesse trabalho refere-se a utilização de relações simbióticas entre populações de soluções candidatas, coevoluindo em um contexto ecológico. Com essa analogia, cada população interage com uma outra de acordo com uma relação simbiótica específica, com o objetivo de evoluir suas soluções. O modelo apresentado é aplicado a várias funções benchmark contínuas com um número alto de dimensões (D = 200) e várias instâncias benchmark do problema da mochila múltipla. Os resultados obtidos se mostraram promissores considerando a aplicação das relações simbióticas. Por fim, as conclusões são apresentadas e algumas direções para pesquisas futuras são sugeridas.

Nesta tese é abordado o problema da mochila compartimentada e o problema de corte de estoque unidimensional acoplado ao problema dimensionamento de lotes. Para o problema da mochila compartimentada é apresentada a versão unidimensional e proposta a versão bidimensional, denominados como problema da mochila compartimentada unidimensional e problema da mochila compartimentada bidimensional, respectivamente. Para o problema de corte de estoque acoplado ao dimensionamento de lotes são apresentadas três variações: uma máquina para produzir um tipo de objeto; uma máquina para produzir vários tipos de objetos; múltiplas máquinas para produzir vários tipos de objetos. Algumas formulações matemáticas de programação inteira e inteira-mista, decomposições dos problemas em problema mestre e subproblemas e heurísticas baseadas no método geração de colunas são propostas para os problemas da mochila compartimenta e o problema acoplado. Em específico, para o problema acoplado são aplicadas decomposições Dantzig-Wolfe, que podem ser por período, por máquina ou por período e máquina. Além disso, uma heurística baseada em grafo E/OU é proposta para o problema da mochila compartimentada bidimensional / In this thesis we present the constrained compartmentalized knapsack problem and the one dimensional cutting stock problem integrated with the capacitated lot sizing problem. For the constrained compartmentalized knapsack problem, the one dimensional version is presented and the two dimensional version is proposed, called one-dimensional compartmentalized knapsack problem and two-dimensional compartmentalized knapsack problem, respectively. For the cutting stock problem integrated with the capacitated lot sizing problem three variations are considered: one machine to produce one type of object; one machine to produce multiple types of objects; multiple machines to produce multiple types of objects. Some integer and mixed programming formulations, decompositions of the problems in master problem and subproblems and heuristics based on column generation method are proposed for the compartmentalized knapsack problem and the cutting stock problem integrated with the capacitated lot sizing problem. In particular, the period, the machine, and the period and machine Dantzig- Wolfe decompositions are applied for the integrated problem. Moreover, a heuristic based on the graph AND/OR is proposed for the two-dimensional compartmentalized knapsack problem. Computational results show that these mathematical formulations and methods provide good solutions

[pt] Um importante ramo do estudo de logística é aquele que se preocupa com a otimização da eficiência do uso de recursos de transporte. No segmento de aviação da Petrobras, que transporta cerca de 20 por cento de todos os passageiros offshore do planeta, otimizações são bastante significativas e podem gerar importantes benefícios econômicos (menor custo total), logísticos (maior disponibilidade de recursos), ambientais (menores emissões de gases poluentes) e de segurança (menor exposição aos riscos da atividade). Por estes motivos, é imperativo que se busque formas de aumentar a eficiência do uso das aeronaves contratadas, maximizando sua utilização dentro de limites permitidos por normas de voo offshore, limites de fadiga de tripulantes, limites operacionais dos aeroportos de origem e destino, além de limites de capacidades de cada aeronave. Neste sentido, o objetivo deste estudo é apresentar o desenvolvimento de soluções para redução dos custos da operação aérea, buscando o máximo aproveitamento das aeronaves contratadas, a partir de uma proposta de otimização da programação de voos através da resolução de um resolução de uma formulação de Programação Linear Inteira, que estende um Problema de Múltiplas Mochilas, respeitando as limitações impostas por regulamentação e necessidades operacionais. Foi desenvolvida uma ferramenta computacional e os resultados obtidos a partir deste trabalho foram implementados nas operações da Petrobras e fazem parte do Plano de Resiliência desta empresa. Os ganhos econômicos obtidos representam uma redução de 100 milhões de reais no quinquênio do Plano de Negócios e Gestão 2020-2024, o que comprova o benefício das soluções implementadas. / [en] An important field of the logistics study is one that is concerned with optimizing the efficiency of the use of transport resources. In Petrobras aviation segment, which transports about 20 percent of all offshore passengers worldwide, optimizations are quite significant and can generate important economic (lower total cost), logistical (increased availability of resources), environmental (lower emissions of polluting gases) and safety (reduced exposure to the risks of the activity) benefits. For these reasons, it is imperative to seek ways to increase efficiency in the use of contracted aircrafts, maximizing their use within the boundaries imposed by offshore flight rules, crew fatigue restrictions, operational restrictions of the origin and destination airports, in addition to capacity limits for each aircraft. Hereupon, the objective of this study is to present the development of solutions to reduce the costs of aerial operation, seeking the maximum use of contracted aircrafts, based on a proposal to optimize the flight schedule through the resolution of an Integer Linear Programming formulation that extends a Multiple Knapsack Problem, but within the boundaries imposed by regulations and operational needs. A computational tool was developed and results obtained from this work were implemented in Petrobras operations, and are part of this company s Resilience Plan. The economic gains obtained represent a reduction of USD 27 million in the five-year period of the 2020-2024 Business Plan, which proves the benefit of the implemented solutions.

No / A membrane-inspired evolutionary algorithm (MIEA) is a successful instance of a model linking membrane computing and evolutionary algorithms. This paper proposes the analysis of dynamic behaviors of MIEAs by introducing a set of population diversity and convergence measures. This is the first attempt to obtain additional insights into the search capabilities of MIEAs. The analysis is performed on the MIEA, QEPS (a quantum-inspired evolutionary algorithm based on membrane computing), and its counterpart algorithm, QIEA (a quantum-inspired evolutionary algorithm), using a comparative approach in an experimental context to better understand their characteristics and performances. Also the relationship between these measures and fitness is analyzed by presenting a tendency correlation coefficient to evaluate the importance of various population and convergence measures, which is beneficial to further improvements of MIEAs. Results show that QEPS can achieve better balance between convergence and diversity than QIEA, which indicates QEPS has a stronger capacity of balancing exploration and exploitation than QIEA in order to prevent premature convergence that might occur. Experiments utilizing knapsack problems support the above made statement.

Submitted by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:31:58Z No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Erika Demachki (erikademachki@gmail.com) on 2016-03-17T17:35:15Z (GMT) No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-17T17:35:15Z (GMT). No. of bitstreams: 2 Dissertação - Santiago Valdés Ravelo - 2011.pdf: 730949 bytes, checksum: 92c89c8c1f240082004834898896b9ba (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2011-02-18 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work considers three relevant NP-hard problems. The firstone is the one-dimensional cutting stock problem in which the non-used material in the cutting patterns may be used in the future. For this problem we analyze the existing mathematical models, propose new models, design a heuristic and two metaheuristic approaches, being their performances improved by using parallel programming, and solve instances, practical and randomly generated, from the literature. The computational experiments were quite good for all tested instances. The second problem we consider is the stable roommates problem (a variant of the stable matching problem). For this we give two mathematical programming models, sequential and parallel implementations of a Tabu Search, and a Branch-andBound. Also, we report computational experiments to instances of the problem. The last problem we consider is the compartmentalized knapsack problem (a generalization of the knapsack problem) for which we analyze a quadratic integer model and give a linear integer model. We design a greedy heuristic and a GRASP algorithm, that uses path-relinking, and solve randomly generated instances. All parallel implementations use Graphics Processing Units (GPUs). / Este trabalho considera três problemas, NP-difíceis, relevantes de estudo em otimização combinatória. O primeiro deles é o problema de corte uni-dimensional de objetos, onde o material não usado pelos padrões de corte pode ser usado no futuro. Para este problema analisamos os modelos matemáticos existentes, propomos novos modelos, projetamos uma heurística construtiva e duas metaheurísticas, sendo seus desempenhos melhorados com programação paralela, e resolvemos instâncias, práticas e aleatórias, encontradas na literatura; sendo os experimentos computacionais muito bons para todas as intânciastestadas.Osegundoproblemaqueconsideramoséoproblemadoscompanheiros estáveis (stable roommates problem), uma variante do problema de emparelhamento estável (stable matching problem). Para este propomos dois modelos matemáticos, uma implementação sequencial e uma paralela de uma Tabu Search, e um Branch-andBound. Também reportamos experimentos computacionais para instâncias do problema. O último problema considerado é o da mochila compartimentada (uma generalização do problema clássico da mochila), para o qual analisamos uma modelagem quadrática inteira e propomos um modelo linear inteiro; também projetamos uma heurística gulosa, um algoritmo GRASP, que usa path-relinking, e resolvemos intâncias geradas aleatóriamente. Todas as implementações em paralelo usam unidades de processamento gráfico (Graphics Processing Units, GPUs).

Le conflit entre la demande de services multimédia en multidiffusion à haut débit (MBMS) et les limites en ressources radio demandent une gestion efficace de l'allocation des ressources radio (RRM) dans les réseaux 3G UMTS. À l'opposé des travaux existant dans ce domaine, cette thèse se propose de résoudre le problème de RRM dans les MBMS par une approche d’optimisation combinatoire. Le travail commence par une modélisation formelle du problème cible, désigné comme Flexible Radio Resource Management Model (F2R2M). Une analyse de la complexité et du paysage de recherche est effectuée à partir de ce modèle. Tout d’abord on montre qu'en assouplissant les contraintes de code OVSF, le problème de RRM pour les MBMS peut s'apparenter à un problème de sac à dos à choix multiples (MCKP). Une telle constatation permet de calculer les limites théoriques de la solution en résolvant le MCKP similaire. En outre, l'analyse du paysage montre que les espaces de recherche sont accidentés et constellés d'optima locaux. Sur la base de cette analyse, des algorithmes métaheuristiques sont étudiés pour résoudre le problème. Nous montrons tout d'abord que un Greedy Local Search (GLS) et un recuit simulé (SA) peuvent trouver de meilleures solutions que les approches existantes implémentées dans le système UMTS, mais la multiplicité des optima locaux rend les algorithmes très instables. Un algorithme de recherche tabou (TS) incluant une recherche à voisinage variable (VNS) est aussi développé et comparé aux autres algorithmes (GLS et SA) et aux approches actuelles du système UMTS ; les résultats de la recherche tabou dépassent toutes les autres approches. Enfin les meilleures solutions trouvées par TS sont également comparées avec les solutions théoriques générées par le solveur MCKP. On constate que les meilleures solutions trouvées par TS sont égales ou très proches des solutions optimales théoriques. / The high throughputs supported by the multimedia multicast services (MBMS) and the limited radio resources result in strong requirement for efficient radio resource management (RRM) in UMTS 3G networks. This PhD thesis proposes to solve the MBMS RRM problem as a combinatorial optimization problem. The work starts with a formal modeling of the problem, named as the Flexible Radio Resource Management Model (F2R2M). An in-depth analysis of the problem complexity and the search landscape is done from the model. It is showed that, by relaxing the OVSF code constraints, the MBMS RRM problem can be approximated as a Multiple-Choice Knapsack Problem (MCKP). Such work allows us to compute the theoretical solution bounds by solving the approximated MCKP. Then the fitness landscape analysis shows that the search spaces are rough and reveal several local optimums. Based on the analysis, some metaheuristic algorithms are studied to solve the MBMS RRM problem. We first show that a Greedy Local Search (GLS) and a Simulated Annealing (SA) allow us to find better solutions than the existing approaches implemented in the UMTS system, however the results are instable due to the landscape roughness. Finally we have developed a Tabu Search (TS) mixed with a Variable Neighborhood Search (VNS) algorithm and we have compared it with GLS, SA and UMTS embedded algorithms. Not only the TS outperforms all the other approaches on several scenarios but also, by comparing it with the theoretical solution bounds generated by the MCKP solver, we observe that TS is equal or close to the theoretical optimal solutions.