背包問題是整數規劃中一個特殊的模式，雖然它可以運用一般整數規劃法則來處理， 但是由於它只含有一個限制，所以發展出更有效的法則也是可能的。在過去十幾年當 中，已發表出很多研究論文，這些研究結果已推動吾人對這問題作更進一步的探討， 並導出更有效的求解法則。 本文分六章共二十節，內容大致如下： （一）緒論。 （二）討論背包問題一些重要的求解法則及其性質與應用。 （三）討論陷縮背包問題（The collapsing knapsack problem ）之應用及求解法則 ，決定元由整數擴大為混合的情形（實數）。 （四）結論與建議。

The topic of this thesis is a cryptosystem, precisely a public key encryption scheme, that is based on the knapsack problem. At first we formulate terms like \mathcal{NP} -complete problem, one-way function, hard-core predicate, public key encryption scheme and semantic security which we connect in this thesis. After that we present the knapsack problem. Then we prove that the knapsack problem with appropriate parameters has a property that leads to semantic security of the encryption scheme which we present afterwards. This public key encryption scheme is based on the scheme proposed by Vadim Lyubashevsky, Adriana Palacio and Gil Segev. Powered by TCPDF (www.tcpdf.org)

Dans cette thèse, nous nous intéressons à l'étude des capacités de la méta heuristique d'optimisation par colonie de fourmis (Ant Colony Optimization - ACO) pour résoudre des problèmes d’optimisation combinatoire multi-objectif. Dans ce cadre, nous avons proposé une taxonomie des algorithmes ACO proposés dans la littérature pour résoudre des problèmes de ce type. Nous avons mené, par la suite, une étude expérimentale de différentes stratégies phéromonales pour le cas du problème du sac à dos multidimensionnel mono-objectif. Enfin,nous avons proposé un algorithme ACO générique pour résoudre des problèmes d'optimisation multi-objectif. Cet algorithme est paramétré par le nombre de colonies de fourmis et le nombre de structures de phéromone considérées. Il permet de tester et de comparer, dans un même cadre,plusieurs approches. Nous avons proposé six variantes de cet algorithme dont trois présentent de nouvelles approches et trois autres reprennent des approches existantes. Nous avons appliqué et comparé ces variantes au problème du sac à dos multidimensionnel multi-objectif / In this thesis, we investigate the capabilities of Ant Colony Optimization (ACO) metaheuristic to solve combinatorial and multi-objective optimization problems. First, we propose a taxonomy of ACO algorithms proposed in the literature to solve multi-objective problems. Then, we studydifferent pheromonal strategies for the case of mono-objective multidimensional knapsackproblem. We propose, finally, a generic ACO algorithm to solve multi-objective problems. Thisalgorithm is parameterised by the number of ant colonies and the number of pheromonestructures. This algorithm allows us to evaluate and compare new and existing approaches in thesame framework. We compare six variants of this generic algorithm on the multi-objectivemultidimensional knapsack problem

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

Neste trabalho apresentamos dois modelos de otimização e um método heurístico de solução para tratar um problema de comprovação fiscal em exportações de commodities no Brasil. Dos modelos de otimização, um foi desenvolvido baseado no Problema de Dimensionamento de Lotes e outro no Problema da Mochila. O governo brasileiro estimula as exportações no país através de alguns benefícios fiscais, alguns desses, sendo possíveis através da comprovação fiscal das exportações de mercadorias acompanhadas de notas fiscais de tipo de operação de fim específico para a exportação. Os benefícios deixam de ser concedidos a partir da perda do prazo da comprovação fiscal da nota fiscal, que é realizado utilizando a Declaração Única de Exportação (DU-E). Cada nota fiscal possui uma data de emissão, dias de isenção fiscal, o percentual da alíquota de ICMS cobrado dependendo do estado emissor, os itens e suas quantidades. As decisões visam estabelecer as combinações de quais notas fiscais devem ser comprovadas em cada embarque de produtos para o mercado exterior, obedecendo às suas datas de isenção de modo a minimizar os impostos pagos devido aos vencimentos dos prazos de despachos das notas. Os resultados obtidos por meio do modelo matemático mostram que a política otimizada de embarque dos produtos das notas fiscais apresenta uma redução dos custos em aproximadamente 39% em determinadas situações. / In this paper we present two optimization models and a heuristic method to deal with a problem of export tax on Brazilian commodities. Regarding the optimization models, one was developed based on the lot-sizing problem and an other on the knapsack problem. The Brazilian government encourages local exportation through tax benefits, some of them being possible by the taxation of exported goods being accompanied by invoices of an operation type that is specific for the purpose of the export. These benefits cease to be granted as a result of exceeding the tax invoice verification period, which is granted using the Single Export Declaration (DU-E). Each invoice has a date issue, days of tax exemption, the percentage of the ICMS tax rate charged depending on the issuing state, the items and their quantities. The decisions aim to establish the combinations of which invoices must be presented for each shipment of products to the foreign market, obeying their exemption dates in order to minimize the taxes paid due the maturity of the delivery times on the documents. The results obtained using the mathematical model show that the optimized shipping policy for invoiced products presents a 39% reduction in costs in certain situations.

Block type quay walls are commonly used as berthing structures both in Turkey and worldwide. In this study, stability analysis of block type quay wall is carried out using pseudo-static method. A computer program named QSAP (using Excel spreadsheet) has been developed for the design of block type quay walls. QSAP has been prepared based on the rules of Turkish Seismic Design Codes for Coastal Structures, 2008. Reliability of this program is verified by a comparative study of Derince Port block type quay wall, damaged in Marmara earthquake (1999), with manual solution and field measurements. A newly introduced placement methodology &ldquo / Knapsack&rdquo / is also studied with QSAP and the results are compared with the conventional placement method.

Every knapsack problem may be relaxed to a cyclic group problem. In 1969, Gomory found the subadditive characterization of facets of the master cyclic group problem. We simplify the subadditive relations by the substitution of complementarities and discover a minimal representation of the subadditive polytope for the master cyclic group problem. By using the minimal representation, we characterize the vertices of cardinality length 3 and implement the shooting experiment from the natural interior point. The shooting from the natural interior point is a shooting from the inside of the plus level set of the subadditive polytope. It induces the shooting for the knapsack problem. From the shooting experiment for the knapsack problem we conclude that the most hit facet is the knapsack mixed integer cut which is the 2-fold lifting of a mixed integer cut. We develop a cutting plane algorithm augmenting cutting planes generated by shooting, and implement it on Wong-Coppersmith digraphs observing that only small number of cutting planes are enough to produce the optimal solution. We discuss a relaxation of shooting as a clue to quick shooting. A max flow model on covering space is shown to be equivalent to the dual of shooting linear programming problem.

The accurate determination of gender of biological samples has valuable applications in medical and forensic investigations. Gender determination based on length variations in the X-Y homologous amelogenin gene, is part of most commercial multiplex DNA profiling kits. The first report of a failure of the amelogenin sex test was in 1998 when two normal males were typed as female. Subsequently, several amelogenin Y (AMELY) negative males have been reported. This study represents the first report of this phenomenon in the black South African population. This study determined the size of the Y-chromosome deletion that resulted in the failure of the amelogenin sex test in two black South African AMELY-negative males by typing specific DNA markers surrounding the amelogenin locus. Through deletion size and Y-chromosome microsatellite haplotypes, the relationship between the samples was investigated. The samples were sequenced at the amelogenin gene and typed for thirteen sites on the short arm of the Y-chromosome. In order to determine the Y-chromosome haplotypes, eleven Y-chromosome microsatellite markers were typed. These samples had the same size deletion of approximately 3 Mb. The Y-chromosome haplotypes indicated that these were probably independent events. The frequency of AMELY-negative males is rare in this population sample of 8,344 individuals, with a frequency of 0.065% in the black South African sample population. Notwithstanding, tests performed for detecting the presence of male DNA based on the presence of the amelogenin gene alone should be reconsidered, as this study confirms that these deletions do occur in the African population. The impact of the results generated in this study on the medical and forensic practise of DNA testing is significant. / Thesis (Ph.D. (Biochemistry))--North-West University, Potchefstroom Campus, 2011.

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.

The accurate determination of gender of biological samples has valuable applications in medical and forensic investigations. Gender determination based on length variations in the X-Y homologous amelogenin gene, is part of most commercial multiplex DNA profiling kits. The first report of a failure of the amelogenin sex test was in 1998 when two normal males were typed as female. Subsequently, several amelogenin Y (AMELY) negative males have been reported. This study represents the first report of this phenomenon in the black South African population. This study determined the size of the Y-chromosome deletion that resulted in the failure of the amelogenin sex test in two black South African AMELY-negative males by typing specific DNA markers surrounding the amelogenin locus. Through deletion size and Y-chromosome microsatellite haplotypes, the relationship between the samples was investigated. The samples were sequenced at the amelogenin gene and typed for thirteen sites on the short arm of the Y-chromosome. In order to determine the Y-chromosome haplotypes, eleven Y-chromosome microsatellite markers were typed. These samples had the same size deletion of approximately 3 Mb. The Y-chromosome haplotypes indicated that these were probably independent events. The frequency of AMELY-negative males is rare in this population sample of 8,344 individuals, with a frequency of 0.065% in the black South African sample population. Notwithstanding, tests performed for detecting the presence of male DNA based on the presence of the amelogenin gene alone should be reconsidered, as this study confirms that these deletions do occur in the African population. The impact of the results generated in this study on the medical and forensic practise of DNA testing is significant. / Thesis (Ph.D. (Biochemistry))--North-West University, Potchefstroom Campus, 2011.