Consider the concept of the Utility Model [5]: the optimal allocation of resources of a server or network while meeting the absolute Quality of Service (QoS) requirements of users' multimedia sessions. Past algorithms and heuristics to solve the Utility Model mapped the problem onto a variant of the Combinatorial Knapsack Problem, with server utility (e.g. revenue) as the quantity to be optimized and with user QoS requirements expressed as constraints on the resource allocation. Both optimal (algorithmic) and fast but sub-optimal (heuristic) methods were derived to solve the resulting Multidimensional Multiconstraint Knapsack Problem (MMKP) and hence to perform admission control of proposed user sessions However, previous algorithms and heuristics were restricted to solving the Utility Model on an enterprise network (a network of less than 30 nodes), owing to the need in admission control to solve the problem in real time, typically a few seconds or less. The methods used for the path finding and admission processes had unfavorable computational complexities. As a result, only small (i.e. enterprise) networks could be treated in real time. Also, considerable time was wasted on frequently unnecessary traversals during upgrading. In this thesis we attempt to solve and implement the Utility Model using a modified version of a Multicommodity Flow algorithm, which has better computational complexity than Knapsack Algorithms or many heuristics and hence is capable of finding paths relatively quickly for larger networks. What's more, the Multicommodity flow algorithm used keeps essential information about the current networks and user sessions, thus further reducing the overall admission time.

Single-row mixed-integer programming (MIP) problems have been studied thoroughly under many different perspectives over the years. While not many practical applications can be modeled as a single-row MIP, their importance lies in the fact that they are simple, natural and very useful relaxations of generic MIPs. This thesis will focus on such MIPs and present theoretical and computational advances in their study. Chapter 1 presents an introduction to single-row MIPs, a historical overview of results and a motivation of why we will be studying them. It will also contain a brief review of the topics studied in this thesis as well as our contribution to them. In Chapter 2, we introduce a generalization of a very important structured single-row MIP: Gomory's master cyclic group polyhedron (MCGP). We will show a structural result for the generalization, characterizing all facet-defining inequalities for it. This structural result allows us to develop relationships with MCGP, extend it to the mixed-integer case and show how it can be used to generate new valid inequalities for MIPs. Chapter 3 presents research on an algorithmic view on how to maximally lift continuous and integer variables. Connections to tilting and fractional programming will also be presented. Even though lifting is not particular to single-row MIPs, we envision that the general use of the techniques presented should be on easily solvable MIP relaxations such as single-row MIPs. In fact, Chapter 4 uses the lifting algorithm presented. Chapter 4 presents an extension to the work of Goycoolea (2006) which attempts to evaluate the effectiveness of Mixed Integer Rounding (MIR) and Gomory mixed-integer (GMI) inequalities. By extending his work, natural benchmarks arise, against which any class of cuts derived from single-row MIPs can be compared. Finally, Chapter 5 is dedicated to dealing with an important computational problem when developing any computer code for solving MIPs, namely the problem of numerical accuracy. This problem arises due to the intrinsic arithmetic errors in computer floating-point arithmetic. We propose a simple approach to deal with this issue in the context of generating MIR/GMI inequalities.

Text in Afikaans / In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems. / Mathematical Sciences / D. Phil. (Operasionele Navorsing)

Uma revisão dos algoritmos e conjuntos de instâncias presentes na literatura do Problema da Mochila com Repetições (PMR) é apresentada nessa dissertação de mestrado. Os algoritmos e conjuntos de instâncias usados são brevemente descritos nesse trabalho, afim de que o leitor tenha base para entender as discussões. Algumas propriedades bem conhecidas e específicas do PMR, como a dominância e a periodicidade, são explicadas com detalhes. O PMR é também superficialmente estudado no contexto de problemas de avaliação gerados pela abordagem de geração de colunas aplicada na relaxação contínua do Bin Packing Problem (BPP) e o Cutting Stock Problem (CSP). Múltiplos experimentos computacionais e comparações são realizadas. Para os conjuntos de instâncias artificiais mais recentes da literatura, um simples algoritmo de programação dinâmica, e uma variante do mesmo, parecem superar o desempenho do resto dos algoritmos, incluindo aquele que era estado-da-arte. O modo que relações de dominância é aplicado por esses algoritmos de programação dinâmica têm algumas implicações para as relações de dominância previamente estudadas na literatura. O autor dessa dissertação defende a tese de que a escolha dos conjuntos de instâncias artificiais definiu o que foi considerado o melhor algoritmo nos trabalhos anteriores. O autor dessa dissertação disponibilizou publicamente todos os códigos e conjuntos de instâncias referenciados nesse trabalho. / A review of the algorithms and datasets in the literature of the Unbounded Knapsack Problem (UKP) is presented in this master's thesis. The algorithms and datasets used are brie y described in this work to provide the reader with basis for understanding the discussions. Some well-known UKP-speci c properties, such as dominance and periodicity, are described. The UKP is also super cially studied in the context of pricing problems generated by the column generation approach applied to the continuous relaxation of the Bin Packing Problem (BPP) and Cutting Stock Problem (CSP). Multiple computational experiments and comparisons are performed. For the most recent arti cial datasets in the literature, a simple dynamic programming algorithm, and its variant, seems to outperform the remaining algorithms, including the previous state-of-the-art algorithm. The way dominance is applied by these dynamic programming algorithms has some implications for the dominance relations previously studied in the literature. In this master's thesis we defend that choosing sets of arti cial instances has de ned what was considered the best algorithm in previous works. We made available all codes and datasets referenced in this master's thesis.

Uma revisão dos algoritmos e conjuntos de instâncias presentes na literatura do Problema da Mochila com Repetições (PMR) é apresentada nessa dissertação de mestrado. Os algoritmos e conjuntos de instâncias usados são brevemente descritos nesse trabalho, afim de que o leitor tenha base para entender as discussões. Algumas propriedades bem conhecidas e específicas do PMR, como a dominância e a periodicidade, são explicadas com detalhes. O PMR é também superficialmente estudado no contexto de problemas de avaliação gerados pela abordagem de geração de colunas aplicada na relaxação contínua do Bin Packing Problem (BPP) e o Cutting Stock Problem (CSP). Múltiplos experimentos computacionais e comparações são realizadas. Para os conjuntos de instâncias artificiais mais recentes da literatura, um simples algoritmo de programação dinâmica, e uma variante do mesmo, parecem superar o desempenho do resto dos algoritmos, incluindo aquele que era estado-da-arte. O modo que relações de dominância é aplicado por esses algoritmos de programação dinâmica têm algumas implicações para as relações de dominância previamente estudadas na literatura. O autor dessa dissertação defende a tese de que a escolha dos conjuntos de instâncias artificiais definiu o que foi considerado o melhor algoritmo nos trabalhos anteriores. O autor dessa dissertação disponibilizou publicamente todos os códigos e conjuntos de instâncias referenciados nesse trabalho. / A review of the algorithms and datasets in the literature of the Unbounded Knapsack Problem (UKP) is presented in this master's thesis. The algorithms and datasets used are brie y described in this work to provide the reader with basis for understanding the discussions. Some well-known UKP-speci c properties, such as dominance and periodicity, are described. The UKP is also super cially studied in the context of pricing problems generated by the column generation approach applied to the continuous relaxation of the Bin Packing Problem (BPP) and Cutting Stock Problem (CSP). Multiple computational experiments and comparisons are performed. For the most recent arti cial datasets in the literature, a simple dynamic programming algorithm, and its variant, seems to outperform the remaining algorithms, including the previous state-of-the-art algorithm. The way dominance is applied by these dynamic programming algorithms has some implications for the dominance relations previously studied in the literature. In this master's thesis we defend that choosing sets of arti cial instances has de ned what was considered the best algorithm in previous works. We made available all codes and datasets referenced in this master's thesis.

Nesse trabalho, estudamos um problema de otimização combinatorial conhecido por Problema da Mochila Compartimentada, que é uma extensão do clássico Problema da Mochila. O problema consiste em determinar as capacidades adequadas de vários compartimentos que podem vir a ser alocados em uma mochila e como esses compartimentos devem ser carregados, respeitando as restrições de capacidades dos compartimentos e da mochila. Busca-se maximizar o valor de utilidade total. O problema é muito pouco estudado na literatura, apesar de surgir naturalmente em aplicações práticas. Nesse estudo, propomos uma modelagem matemática não linear para o problema e verificamos algumas heurísticas para sua resolução. / In this work, we studied a combinatorial optimization problem called the Clustered Knapsack Problem, that is an extension of the standard Knapsack Problem. The problem is to determine the right capacities of several clusters which can be allocated in a knapsack and how these clusters should be placed so as to respect the constraints on the capacities of the clusters and the knapsack. The objective is to maximize a total utility value. The problem has seldom been studied in the literature, even though it appears naturally in practical applications. In this study, we propose a non-linear model for the problem and we insert some heuristics for its resolution.

Depuis le début des années 2000, le secteur social et médico-social connait des évolutions et des mutations importantes. D’un côté, le nombre de personnes prises en charge est en perpétuelle augmentation. D’un autre côté, les finances et les budgets mis à disposition des établissements ne cessent de se réduire, ce qui oblige les décideurs à s’adapter et à trouver de nouvelles solutions pour faire plus avec moins de moyens. Dans cette thèse, nous étudions un problème pratique auquel sont souvent confrontés les directeurs des établissements qui est l’élaboration de plans d’actions optimaux. Un plan d’actions est un ensemble d’actions qui sont mises en place afin d’améliorer à la fois les performances de l’établissement et la qualité de prise en charge de ses résidents.Élaborer un plan d’actions optimal consiste à identifier et choisir les meilleures actions qui améliorent tous les objectifs du plan tout en respectant quelques contraintes. Après la présentation du contexte pratique et théorique, nous fournissons une modélisation formelle du problème sous forme d’un problème de sac-à-dos multi-objectif.Puis nous présentons quelques méthodes de résolution à base d’indicateurs de qualité et de la dominance de Lorenz. Nous montrons que la méthode IBMOLS combinée avec l’indicateur de qualité R2 permet d’obtenir des solutions efficaces et d’intégrer facilement les préférences du décideur. Nous montrons également que dans un contexte où les préférences du décideur sont inconnues ou les objectifs ont tous la même importance, la dominance de Lorenz est un outil très efficace qui permet, d’un côté, d’intégrer l’équité dans le processus de recherche et, d’un autre côté, de réduire le nombre de solutions non dominées ainsi que le temps d’exécution. / Since the early 2000s, the social and medico-social sector is experiencing significant evolutions and mutations. On the one hand, the number of persons taken over is constantly increasing. On the other hand, the finances and budgets available to the structures are constantly decreasing. This forces decision-makers to adapt and find new solutions to do more with fewer resources. In this thesis, we study a practical problem that is often faced by the decision-makers, which is the elaboration of optimal action plans. An action plan is a set of actions that are realized to improve both the performance of the structure and the quality of service offred to its residents. Elaborating an optimal action plan consists of identifying and selecting the best actions that improve all the objectives of the plan while respecting some constraints. After presenting the practical and theoretical context, we provide a formal modeling of the problem as a multi-objective knapsack problem. Then, we present a number of solution methods based on quality indicators and Lorenz dominance. We show that combining IBMOLS method with R2 indicator allows obtaining efficient solutions and easily integrating the decision-maker preferences. We also show that in a context where decision-maker preferences are not known or all the objectives are considered equals, Lorenz dominance is a very efficient tool to incorporate equity into the search process and reduce the number of non-dominated solutions as well as the algorithm runtime.

Title: The knapsack and its applications Author: Romana Linkeová Department: Department of Algebra Supervisor: doc. Mgr. Pavel Příhoda, Ph.D., Department of Algebra Abstract: This thesis is focused on various aspects of cryptosystems based on NP (non-deterministic polynomial) complete knapsack problem. From the theory of complexity point of view, the less known parts of the proof of knapsack problem NP completeness are shown in detail. From the cryptographical point of view, a demonstration of breaking of the Merkle-Hellman cryptosystem (the basic de- sign of knapsack-type cryptosystems) is provided, showing that poor parameters choice can lead to easy obtaining of the whole private key. Another contribution of this thesis consists in a presented proposal of a new cryptosystem concept based on the matrix 0-1 knapsack problem. This concept was developed in order to prevent known attacks, however, in the thesis we provide a proof analogous to J. C. Lagarias and A. M. Odlyzko, 1985, which shows that an attack based on the LLL algorithm will be successful on the majority of the matrix 0-1 kna- psack problem cryptosystems. Finally, a list of modern cryptosystems based on the knapsack problem is provided and a cryptanalysis thereof is given. Keywords: knapsack problem, NP complete problems, LLL algorithm 1

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) has been and continues to be widely used by industries to minimize cost and effectively manage resources. Faster computers and innovative IP techniques have enabled the solution to many large-scale IPs. However, IPs are NP-hard and many IPs require exponential time to solve. Lifting is one of the most widely used techniques that helps to reduce computational time and is widely applied in today's commercial IP software. Lifting was first introduced by Gomory for bounded integer programs and a theoretical and computationally intractible technique to simultaneously lift sets of variables was introduced by Zemel in 1978. This thesis presents a new algorithm called the Maximal Simultaneous Lifting Algorithm (MSLA), to simultaneously uplift sets of binary integer variables into a cover inequality. These lifted inequalities result in strong inequalities that are facet defining under fairly moderate assumptions. A computational study shows that this algorithm can find numerous strong inequalities for random Knapsack (KP) instances. The pre-processing time observed for these instances is less than 1/50th of a second, which is negligible. These simultaneously lifted inequalities are easy to find and incorporating these cuts to KP instances reduced the solution time by an average of 41%. Therefore, implementing MSLA should be highly beneficial for large real-world problems.

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd W. Easton / Integer programming is an important discipline in operation research that positively impacts society. Unfortunately, no algorithm currently exists to solve IP's in polynomial time. Researchers are constantly developing new techniques, such as cutting planes, to help solve IPs faster. For example, DeLissa discovered the existence of equality cuts limited to zero and one coefficients for the multiple knapsack equality problem (MKEP). An equality cut is an improper cut because every feasible point satisfies the equality. However, such a cut always reduces the dimension of the linear relaxation space by at least one. This thesis introduces lifted equality cuts, which can have coefficients greater than or equal to two. Two main theorems provide the conditions for the existence of lifted equalities. These theorems provide the foundation for The Algorithm of Lifted Equality Cuts (ALEC), which finds lifted equality cuts in quadratic time. The computational study verifies the benefit of lifted equality cuts in random MKEP instances. ALEC generated millions of lifted equality cuts and reduced the solution time by an average of 15%. To the best of the author's knowledge, ALEC is the first algorithm that has found over 30.7 million cuts on a single problem, while reducing the solving time by 18%.