To see the other types of publications on this topic, follow the link: Knapsack.
Dissertations / Theses on the topic 'Knapsack'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Knapsack.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Yang, Yanchun Bulfin Robert L. "Knapsack problems with setup." Auburn, Ala., 2006. http://repo.lib.auburn.edu/2006%20Summer/Dissertations/YANG_YANCHUN_31.pdf.
Full text
2
SCATAMACCHIA, ROSARIO. "Knapsack Problems with Side Constraints." Doctoral thesis, Politecnico di Torino, 2017. http://hdl.handle.net/11583/2667802.
Full textAbstract:
The thesis considers a specific class of resource allocation problems in Combinatorial Optimization: the Knapsack Problems. These are paradigmatic NP-hard problems where a set of items with given profits and weights is available. The aim is to select a subset of the items in order to maximize the total profit without exceeding a known knapsack capacity. In the classical 0-1 Knapsack Problem (KP), each item can be picked at most once.
The focus of the thesis is on four generalizations of KP involving side constraints beyond the capacity bound. More precisely, we provide solution approaches and insights for the following problems: The Knapsack Problem with Setups; the Collapsing Knapsack Problem; the Penalized Knapsack Problem; the Incremental Knapsack Problem.
These problems reveal challenging research topics with many real-life applications. The scientific contributions we provide are both from a theoretical and a practical perspective. On the one hand, we give insights into structural elements and properties of the problems and derive a series of approximation results for some of them. On the other hand, we offer valuable solution approaches for direct applications of practical interest or when the problems considered arise as sub-problems in broader contexts.
3
Aslan, Murat. "The Cardinality Constrained Multiple Knapsack Problem." Master's thesis, METU, 2008. http://etd.lib.metu.edu.tr/upload/12610131/index.pdf.
Full textAbstract:
The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce.
In this study we consider the cardinality constrained multiple knapsack problem. We propose heuristic and optimization procedures that rely on the optimal solutions of the linear programming relaxation problem. Our computational results on the large-sized problem instances have shown the satisfactory performances of our algorithms.
4
Suri, Bharath. "Accelerating the knapsack problem on GPUs." Thesis, Linköpings universitet, ESLAB - Laboratoriet för inbyggda system, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-70406.
Full textAbstract:
The knapsack problem manifests itself in many domains like cryptography, financial domain and bio-informatics. Knapsack problems are often inside optimization loops in system-level design and analysis of embedded systems as well. Given a set of items, each associated with a profit and a weight, the knapsack problem deals with how to choose a subset of items such that the profit is maximized and the total weight of the chosen items is less than the capacity of the knapsack. There exists several variants and extensions of this knapsack problem. In this thesis, we focus on the multiple-choice knapsack problem, where the items are grouped into disjoint classes. However, the multiple-choice knapsack problem is known to be NP-hard. While many different heuristics and approximation schemes have been proposed to solve the problem in polynomial-time, such techniques do not return the optimal solution. A dynamic programming algorithm to solve the problem optimally is known, but has a pseudo-polynomial running time. This leads to high running times of tools in various application domains where knapsack problems must be solved. Many system-level design tools in the embedded systems domain, in particular, would suffer from high running when such a knapsack problem must be solved inside a larger optimization loop. To mitigate the high running times of such algorithms, in this thesis, we propose a GPU-based technique to solve the multiple-choice knapsack problem. We study different approaches to map the dynamic programming algorithm on the GPU and compare their performance in terms of the running times. We employ GPU specific methods to further improve the running times like exploiting the GPU on-chip shared memory. Apart from results on synthetic test-cases, we also demonstrate the applicability of our technique in practice by considering a case-study from system-level design. Towards this, we consider the problem of instruction-set selection for customizable processors.
5
Islam, Mohammad Tauhidul, and University of Lethbridge Faculty of Arts and Science. "Approximation algorithms for minimum knapsack problem." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2009, 2009. http://hdl.handle.net/10133/1304.
Full textAbstract:
Knapsack problem has been widely studied in computer science for years. There exist several
variants of the problem, with zero-one maximum knapsack in one dimension being
the simplest one. In this thesis we study several existing approximation algorithms for the
minimization version of the problem and propose a scaling based fully polynomial time approximation
scheme for the minimum knapsack problem. We compare the performance of
this algorithm with existing algorithms. Our experiments show that, the proposed algorithm
runs fast and has a good performance ratio in practice. We also conduct extensive experiments
on the data provided by Canadian Pacific Logistics Solutions during the MITACS
internship program.
We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional)
minimum knapsack problem and compare its performance with a generalization of a greedy
algorithm for minimum knapsack in d dimensions. Our experiments show that the e-
approximation scheme exhibits good performance ratio in practice.x, 85 leaves ; 29 cm
6
Kosuch, Stefanie. "Stochastic Optimization Problems with Knapsack Constraint." Paris 11, 2010. http://www.theses.fr/2010PA112154.
Full textAbstract:
Etant donné un ensemble d'objets, chacun ayant un poids et une valeur. Le problème de sac-à-dos consiste à choisir un sous-ensemble d'objets qui (i) respecte une certaine restriction du poids (la capacité du sac-à-dos) et (ii) dont la valeur totale est maximisée. Dans cette thèse nous étudions quatre problèmes d'optimisation stochastique avec contrainte de sac-à-dos: le problème de sac-à-dos avec recours simple, le problème de sac-à-dos avec contrainte probabiliste, le problème de sac-à-dos avec recours et un problème bi-niveau stochastique avec contrainte de sac-à-dos probabiliste. Les problèmes ont en commun que les poids dans la contrainte de sac-à-dos sont supposés être aléatoires. Nous proposons de résoudre les problèmes du sac-à-dos avec recours simple ou avec contrainte probabiliste en appliquant un algorithme « branch-and-bound ». Des bornes supérieures sont obtenues en résolvant des relaxations continues. Pour ceci, nous appliquons un algorithme de gradient stochastique. Concernant le cas du sac-à-dos avec recours, nous traitons dans un premier temps le problème avec des poids gaussiens et nous proposons des bornes inférieures et supérieures sur sa valeur optimale. Dans un deuxième temps, nous étudions le cas d’une distribution discrète des poids. Nous montrons que (si P n'est pas égal à NP) le problème déterministe équivalent n’admet pas d’algorithme d’approximation avec une garantie de performance égale à une valeur constante. Le problème bi-niveau stochastique avec contrainte de sac-à-dos probabiliste est d’abord reformulé comme un problème bilinéaire. Ce dernier étant difficile à résoudre à l’optimum, nous proposons de résoudre une relaxation avec un nouvel algorithme itératifGiven a set of objects each having a particular weight and value. The knapsack problem consists of choosing among these items a subset such that (i) the total weight of the chosen items does respect a given weight constraint (the capacity of the knapsack) and (ii) the total value of the chosen items is maximized. In this thesis, we study four stochastic optimization problems with knapsack constraint: the simple recourse knapsack problem, the chance-constrained knapsack problem, the two-stage knapsack problem and a bilievel problem with knapsack chance-constraint. All problems have in common that the item weights in the knapsack constraints are assumed to be random. We propose to solve the simple recourse and the chance-constrained knapsack problems using a branch-&-bound algorithm as framework. Upper bounds are obtained by solving relaxed, i. E. Continuous sub-problems. The latter is done by applying a stochastic gradient algorithm. Concerning the two-stage knapsack problem, we treat, in the first instance, the model where the item weights are assumed to be normally distributed and propose upper and lower bounds on the optimal solution value. Then, we study the problem with discretely distributed weights and show that its deterministic equivalent reformulation does not admit a constant factor approximation algorithm unless P=NP. The studied bilevel problem with knapsack chance-constraint is first of all reformulated as a deterministic equivalent bilinear problem. As the latter is generally hard to solve exactly, we propose to solve a relaxation using a novel iterative algorithm
7
Kaparis, Konstantinos. "Knapsack problems : inequalities, separation and heuristics." Thesis, Lancaster University, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.525341.
Full text
8
Kulanoot, Araya. "Algorithms for some hard knapsack problems." Thesis, Curtin University, 2000. http://hdl.handle.net/20.500.11937/1101.
Full textAbstract:
The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The specific problem that arises depends on the number of knapsacks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 0-1Knapsack Problem arises when there is one knapsack and one item of each type.Knapsack Problems have been intensively studied over the past forty years because of their direct application to problems arising in industry (for example, cargo loading, cutting stock, and budget control) and also for their contribution to the solution methods for integer programming problems.Several exact algorithms based on branch and bound and dynamic programming have been proposed to solve the Knapsack Problems. For some types of data instances, very efficient algorithms have been found. However, a number of hard knapsack instances have been identified. For example, subset sum and strongly correlated data types. This has motivated some researchers to develop specialized algorithms for particular hard problems.This thesis considers a number of hard Knapsack Problems with a single constraint. A number of specialized algorithms are developed. Our work focuses on some hard instances of the 0-1Knapsack Problem, the Bounded Knapsack Problem, the Unbounded Knapsack Problem and the Change-Making Problem.Chapter 1 provides the background of the Knapsack Problem including some important Knapsack Problems and standard types of data instances, terminology, and a summary of our work. Chapter 2 gives a review of the applications and the solution methods that have been proposed. The remaining chapters present the details of our specialized algorithms.Chapter 3 proposes algorithms for the hard 0-1Knapsack Problems instances of subset sum, strongly correlated, and inverse strongly correlated. The algorithms for the Bounded Knapsack Problem instances of strongly correlated and subset sum are also presented. Extensive computational results show that our algorithms are able to solve large problems of size up to one million variables in less than 7 seconds.Chapter 4 proposes algorithms for some hard Unbounded Knapsack Problems. Two algorithms one for the Unbounded Strongly Correlated Knapsack Problem (algorithm CKU1) and one for the Unbounded Subset Sum Problem (algorithm CKU2) are presented. Extensive computational results establish that our two algorithms are able to solve large problems with up to one million variables in less than 0.3 second.Finally, Chapter 5 proposes exact algorithms for the Change-Making Problem. The problem is a particular type of single Knapsack Problems. This chapter proposes two exact algorithms: algorithm CKUC for the Unbounded Change-Making Problem (UCMP) and algorithm CKBC for the Bounded Change-Making Problem (BCMP). The algorithms can solve large-sized problems, when the item types are generated in small ranges, in less than 51 milliseconds for UCMP and less than 3.5 seconds for BCMP.
9
Kulanoot, Araya. "Algorithms for some hard knapsack problems." Curtin University of Technology, School of Mathematics and Statistics, 2000. http://espace.library.curtin.edu.au:80/R/?func=dbin-jump-full&object_id=11692.
Full textAbstract:
The Knapsack Problems are among the simplest integer programs which are NP-hard. Problems in this class are typically concerned with selecting from a set of given items, each with a specified weight and value, a subset of items whose weight sum does not exceed a prescribed capacity and whose value is maximum. The specific problem that arises depends on the number of knapsacks (single or multiple) to be filled and on the number of available items of each type (bounded or unbounded). The classical 0-1Knapsack Problem arises when there is one knapsack and one item of each type.Knapsack Problems have been intensively studied over the past forty years because of their direct application to problems arising in industry (for example, cargo loading, cutting stock, and budget control) and also for their contribution to the solution methods for integer programming problems.Several exact algorithms based on branch and bound and dynamic programming have been proposed to solve the Knapsack Problems. For some types of data instances, very efficient algorithms have been found. However, a number of hard knapsack instances have been identified. For example, subset sum and strongly correlated data types. This has motivated some researchers to develop specialized algorithms for particular hard problems.This thesis considers a number of hard Knapsack Problems with a single constraint. A number of specialized algorithms are developed. Our work focuses on some hard instances of the 0-1Knapsack Problem, the Bounded Knapsack Problem, the Unbounded Knapsack Problem and the Change-Making Problem.Chapter 1 provides the background of the Knapsack Problem including some important Knapsack Problems and standard types of data instances, terminology, and a summary of our work. Chapter 2 gives a review of the applications and the solution methods that have been proposed. The remaining chapters ++present the details of our specialized algorithms.Chapter 3 proposes algorithms for the hard 0-1Knapsack Problems instances of subset sum, strongly correlated, and inverse strongly correlated. The algorithms for the Bounded Knapsack Problem instances of strongly correlated and subset sum are also presented. Extensive computational results show that our algorithms are able to solve large problems of size up to one million variables in less than 7 seconds.Chapter 4 proposes algorithms for some hard Unbounded Knapsack Problems. Two algorithms one for the Unbounded Strongly Correlated Knapsack Problem (algorithm CKU1) and one for the Unbounded Subset Sum Problem (algorithm CKU2) are presented. Extensive computational results establish that our two algorithms are able to solve large problems with up to one million variables in less than 0.3 second.Finally, Chapter 5 proposes exact algorithms for the Change-Making Problem. The problem is a particular type of single Knapsack Problems. This chapter proposes two exact algorithms: algorithm CKUC for the Unbounded Change-Making Problem (UCMP) and algorithm CKBC for the Bounded Change-Making Problem (BCMP). The algorithms can solve large-sized problems, when the item types are generated in small ranges, in less than 51 milliseconds for UCMP and less than 3.5 seconds for BCMP.
10
Chen, Yuning. "Hybrid Metaheuristics for Quadratic Knapsack Problems Iterated responsive threshold search for the quadratic multiple knapsack problem A “reduce and solve” approach for the multiple-choice multidimensional knapsack problem." Thesis, Angers, 2016. http://www.theses.fr/2016ANGE0062.
Full textAbstract:
Cette thèse considère quatre problèmes d’optimisation combinatoire connus sous le nom de Problèmes de Sac-à-Dos Quadratiques : le problème de sac-à-dos quadratique (QSP), le problème de sac-à-dos multiple quadratique (QMSP), le problème de sac-à-dos multiple quadratique généralisé (GQMSP) et le nouveau problème de sac-à-dos multiple quadratique bi-objectif (BO-QMSP) présenté dans cette thèse. Parmi eux, le QSP est le modèle de base tandis que les trois autres introduisent des contraintes ou des fonctions objectives supplémentaires. Ces problèmes ont de nombreuses applications pratiques. Étant donné qu’ils appartiennent à la famille NP-difficile, il est difficile de les résoudre dans le cas général. Pour cette raison, cette thèse est consacrée à la création d’approches métaheuristiques hybrides efficaces pour résoudre ces quatre problèmes difficiles. Plus précisément, nous développons une approche itérative d’exploration hyperplane pour le QSP, deux algorithmes hybrides ("Iterative responsive threshold search" et "Evolutionary path relinking") pour le QMSP, un algorithme mémétique pour le GQMSP et une approche hybride en deux étapes pour le BO-QMSP. Ces algorithmes partagent certains ingrédients fondamentaux (e.g., les opérateurs de mouvement de base et les heuristiques gloutonnes) qui avec quelques adaptations sont généralement applicables à d’autres problèmes de sac-à-dos quadratiques. Ils possèdent également un certain nombre de conceptions spécifiques aux problèmes étudiés. Tous les algorithmes ont été expérimentalement démontrés être en mesure de rivaliser favorablement avec les méthodes de l’état de l’artThis thesis considers four combinatorial optimization problems known under the name Quadratic Knapsack Problems: the quadratic (single) knapsack problem (QKP), the quadratic multiple knapsack problem (QMKP), the generalized quadratic multiple knapsack problem (GQMKP) and the new bi-objective quadratic multiple knapsack problem (BO-QMKP) introduced in this thesis. Among them, the QKP is the most basic model while the other three generalize upon it by introducing additional constraints or objective functions. These problems have a wide range of practical applications. Given that they belong to the NP-hard family, it is computationally difficult to solve them in the general case. For this reason, this thesis is devoted to developing effective hybrid metaheuristic approaches to tackle these four challenging problems. Specifically, we develop an iterated hyperplane exploration approach for the QKP, two hybrid metaheuristic algorithms (iterated responsive threshold search and evolutionary path relinking) for the QMKP, an effective memetic algorithm for the GQMKP and a hybrid two-stage approach for the BO-QMKP. These algorithms share some fundamental ingredients (e.g., move operators and greedy heuristics) which with small adaptations are generally applicable to other Quadratic Knapsack Problems. They also possess a number of problem-specific designs. All algorithms were experimentally demonstrated to be able to compete favourably with state-of-the-art methods
11
Tu, Zhiqi. "Enhancements of the Non-linear Knapsack Cryptosystem." Thesis, University of Canterbury. Computer Science and Software Engineering, 2006. http://hdl.handle.net/10092/1080.
Full textAbstract:
Nowadays all existing public key cryptosystems are classified into three categories relied on different mathematical foundations. The first one is based on the difficulty of factoring the product of two big prime numbers. The representatives are the RSA and the Rabin cryptosystems. The second one such as the ElGamal cryptosystem is based on the discrete logarithm problem. The last one is based on the NP-completeness of the knapsack problem. The first two categories survived crypto attacks, whereas the last one was broken and there has been no attempt to use such a cryptosystem. In order to save the last category, Kiriyama proposed a new public key cryptosystem based on the non-linear knapsack problem, which is an NP-complete problem. Due to the non-linear property of the non-linear knapsack problem, this system resists all known attacks to the linear knapsack problem. Based on his work, we extend our research in several ways. Firstly, we propose an encrypted secret sharing scheme. We improve the security of shares by our method over other existing secret sharing schemes. Simply speaking, in our scheme, it would be hard for outsiders to recover a secret even if somehow they could collect all shares, because each share is already encrypted when it is generated. Moreover, our scheme is efficient. Then we propose a multiple identities authentication scheme, developed on the basis of the non-linear knapsack scheme. It verifies the ownership of an entity's several identities in only one execution of our scheme. More importantly, it protects the privacy of the entities from outsiders. Furthermore, it can be used in resource-constrained devices due to low computational complexity. We implement the above schemes in the C language under the Linux system. The experimental results show the high efficiency of our schemes, due to low computational complexity of the non-linear knapsack problem, which works as the mathematical foundation of our research.
12
Becker, Henrique. "The unbounded knapsack problem : a critical review." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2017. http://hdl.handle.net/10183/163413.
Full textAbstract:
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.
13
Kilincli, Taskiran Gamze. "An Improved Genetic Algorithm for Knapsack Problems." Wright State University / OhioLINK, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=wright1270598986.
Full text
14
Bolton, Jennifer Elaine. "Synchronized simultaneous lifting in binary knapsack polyhedra." Thesis, Manhattan, Kan. : Kansas State University, 2009. http://hdl.handle.net/2097/2304.
Full text
15
Lopez, Rafaël. "Stochastic quadratic knapsack problems and semidefinite programming." Paris 11, 2009. http://www.theses.fr/2009PA112283.
Full textAbstract:
Dans cette thèse, nous présentons une étude détaillée de problèmes de sac-à-dos stochastiques quadratiques, ainsi que des applications de la Programmation Semidéfinie (SDP) pour un problème de télécommunications et pour une étude expérimentale pour des problèmes de Coupe Max et de CDMA. La première partie de cette thèse consiste en un rappel des notions et résultats utilisés par la suite. La seconde partie est consacrée à l’étude du problème du sac- à- dos stochastique, dont nous développons un nouveau modèle, à deux phases (recours) et à contraintes probabilistes. Nous en proposons plusieurs variantes. Nous présentons de multiples relaxations, basées sur la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin, nous proposons une heuristique d’approximation basée sur le résultat de la relaxation linéaire et la SDP. Nous montrons que la SDP donne des bornes significativement meilleures que la relaxation linéaire. Enfin nous proposons une heuristique d’approximation, basée sur le résultat de la relaxation linéaire et sur le résultat de la seconde relaxation SDP , dont nous détaillons les performances. La troisième partie de la thèse est centrée sur l’usage de la SDP sur des problèmes pratiques. La première application étudiée est sur un problème de détection multiutilisateur dans le CDMA. Nous développons un nouvel algorithme combinant SDP et une méta-heuristique VNS pour obtenir un signal de meilleure qualité. Nous détaillons les résultats expérimentaux de notre méthode et d’autres, basées sur SDP. La seconde application est une comparaison expérimentale de diverses relaxations pour le problème de la Coupe Max et dans le CDMA. Nous présentons les performances des relaxations Lagrangienne et SDP comparées à la relaxation linéaire, ainsi que celles de la décomposition spectrale dans le cas du CDMAIn this thesis, we study stochastic quadratic knapsack problems and applications of Semidefinite Programming for a telecommunication problem and for an experimental study of the MaxCut and CDMA problems. The first part of this thesis gives the prelimary notions and results necessary to develop and understand the contents of this thesis. The second part is the study of the stochastic quadratic knapsack problem, for which we develop a new formulation, using recourse (two-stage) and probabilistic contraints. We give multiple variants of this formulation. We propose various relaxations of this problems, based on the linear relaxation and on SDP. We show that SDP gives significantly better bounds than linear relaxation. Finally, we develop an approximation heuristic based on the result of the linear relaxation and of the second SDP relaxation, and give details of their respective performances. The third part of this thesis is dedicated to applications of SDP on pratical problems. The first application we study is a telecommunication problem : the multiuser detection problem in CDMA. We develop a new algorithm combining SDP and a VNS meta-heuristic to obtain a better signal quality. We detail the experimental results of our method and of other SDP based methods. The second application is an experimental comparison of various relaxations for the MaxCut problem and the CDMA problem. We detail the performances of Lagrangian and SDP relaxations compared to linear relaxation, and to the spectral decomposition in the CDMA case
16
Rhee, Donguk. "Faster fully polynomial approximation schemes for Knapsack problems." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/98564.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 61-62).
A fully polynomial time approximation scheme (FPTAS) is an algorithm that returns ... -optimal solution to a maximization problem of size n, which runs in polynomial time in both ... We develop faster FPTASs for several classes of knapsack problems. In this thesis, we will first survey the relevant literature in FPTASs for knapsack problems. We propose the use of floating point arithmetic rather than the use of geometric rounding in order to simplify analysis. Given a knapsack problem that yield an ... -optimal solution for disjoint subsets S and T of decision variables, we show how to attain ... -optimal solution for the knapsack problem for the set ... We use this procedure to speed up the run-time of FPTASs for: 1. The Integer Knapsack Problem, 2. The Unbounded Integer Knapsack Problem, 3. The Multiple-Choice Knapsack Problem, and, 4. The Nonlinear Integer Knapsack Problem, Using addition ideas, we develop a fast fully polynomial time randomized approximation scheme (FPTAS) for the 0-1 Knapsack Problem, which has the run-time of ...
by Donguk Rhee.
S.M.
17
McMillen, Brandon. "The Knapsack Problem, Cryptography, and the Presidential Election." Youngstown State University / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=ysu1340654189.
Full text
18
Al-Douri, Thekra. "Méthodes heuristiques pour les problèmes de type knapsack." Thesis, Amiens, 2018. http://www.theses.fr/2018AMIE0023/document.
Full textAbstract:
Les travaux de recherche de cette thèse s'articulent autour de la résolution du problème du sac à dos en min-max avec de multiples scénarios (en anglais, max-min knapsack problem with multi-scenarios). Cette thèse propose trois approches, plutôt complémentaires, en s'appuyant principalement sur l'aspect perturbation des solutions puis la reconstruction. En partant de ce principe, trois algorithmes approchés ont été étudiés, en partant d'une approche mono-solution vers des approches à base de population. Dans une première partie, un algorithme réactif a été proposé ; il s'appuie sur deux phases imbriquées dans une recherche itérative : la phase de restauration / exploration et la phase de perturbation. La première phase part d'une solution réalisable et tente de l'améliorer en utilisant une stratégie d'exploration spécifique. Cette dernière est basée sur une série d'échanges entre les éléments appartenant ou pas à la solution courante. La deuxième phase commence par construire une solution partielle, en supprimant certains éléments de la solution courante, alors qu'une stratégie de ré-optimisation tente de sélectionner de nouveaux éléments et de les inclure dans une solution dégradée. La stratégie de destruction tente également de diversifier le processus de recherche en dégradant la qualité des solutions dans le but d'éviter des stagnations locales. Dans une deuxième partie, une méthode à base de population a été proposée. Elle s'appuie sur trois phases. Une phase de construction de la population de départ par application d'un algorithme glouton aléatoire, une deuxième phase qui combine une série de solutions deux-à -deux, par l'utilisation de l'opérateur d'intersection et, une troisième phase qui agit sur les successeurs afin d'augmenter la qualité des solutions induites. Les deux dernières phases sont répétées jusqu'à la stabilité de la population. Dans une troisième partie, le problème est résolu en combinant le GRASP (Greedy Randomized Adaptive Search Procedure) et le Path-relinking. Cette approche combine deux stratégies: une stratégie de construction et une autre d'amélioration. D'une part, la première stratégie produit une solution (de départ) réalisable en appliquant le GRASP. D'autre part, chaque solution courante (de départ) est améliorée en appliquant une stratégie basée sur le path-relinking : partir d’un couple de solutions « départ-arrivée », puis tenter de reconstruire le lien entre ces deux solutions en espérant rencontrer des solutions de meilleures qualités sur le chemin. Ce processus est répété sur une série de solutionsThe aim of this thesis is to propose approximate algorithms for tackling the max-min Multi-Scenarios Knapsack Problem (MSKP). Three methods have been proposed (which can be considered as complementary), where each of them is based on the perturbation aspect of the solutions and their re-buildings. The proposed methods are declined in three parts. In the first part, we propose to solve the MSKP by using a hybrid reactive search algorithm that uses two main features: (i) the restoring/exploring phase and (ii) the perturbation phase. The first phase yields a feasible solution and tries to improve it by using an intensification search. The second phase can be viewed as a diversification search in which a series of subspaces are investigated in order to make a quick convergence to a global optimum. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature, whereby its obtained results are compared to those reached by recent methods available in the literature. The results show that the method is competitive and it is able to provide better solutions. The second part discusses a population-based method which combines three complementary stages: (i) the building stage, (ii) the combination stage and (iii) the two-stage rebuild stage. First, the building stage serves to provide a starting feasible solution by using a greedy procedure; each item is randomly chosen for reaching a starting population of solutions. Second, the combination stage tries to provide each new solution by combining subsets of (starting) solutions. Third, the rebuild stage tries to make an intensification in order to improve the solutions at hand. The proposed method is evaluated on a set of benchmark instances taken from the literature, where its obtained results are compared to those reached by the best algorithms available in the literature. The results show that the proposed method provides better solutions than those already published. In the third part, both greedy randomized adaptive search procedure and path-relinking are combined for tackling the MSKP. The proposed method iterates both building and improvement phases that are based upon an extended search process. The first phase yields a (starting) feasible solution for the problem by applying a greedy randomized search procedure. The second phase tries to enhance each current solution by applying the path-relinking based strategy. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature. The obtained results are compared to those reached by some best algorithms available in the literature. Encouraging results have been obtained
19
Al-Douri, Thekra. "Méthodes heuristiques pour les problèmes de type knapsack." Electronic Thesis or Diss., Amiens, 2018. http://www.theses.fr/2018AMIE0023.
Full textAbstract:
Les travaux de recherche de cette thèse s'articulent autour de la résolution du problème du sac à dos en min-max avec de multiples scénarios (en anglais, max-min knapsack problem with multi-scenarios). Cette thèse propose trois approches, plutôt complémentaires, en s'appuyant principalement sur l'aspect perturbation des solutions puis la reconstruction. En partant de ce principe, trois algorithmes approchés ont été étudiés, en partant d'une approche mono-solution vers des approches à base de population. Dans une première partie, un algorithme réactif a été proposé ; il s'appuie sur deux phases imbriquées dans une recherche itérative : la phase de restauration / exploration et la phase de perturbation. La première phase part d'une solution réalisable et tente de l'améliorer en utilisant une stratégie d'exploration spécifique. Cette dernière est basée sur une série d'échanges entre les éléments appartenant ou pas à la solution courante. La deuxième phase commence par construire une solution partielle, en supprimant certains éléments de la solution courante, alors qu'une stratégie de ré-optimisation tente de sélectionner de nouveaux éléments et de les inclure dans une solution dégradée. La stratégie de destruction tente également de diversifier le processus de recherche en dégradant la qualité des solutions dans le but d'éviter des stagnations locales. Dans une deuxième partie, une méthode à base de population a été proposée. Elle s'appuie sur trois phases. Une phase de construction de la population de départ par application d'un algorithme glouton aléatoire, une deuxième phase qui combine une série de solutions deux-à -deux, par l'utilisation de l'opérateur d'intersection et, une troisième phase qui agit sur les successeurs afin d'augmenter la qualité des solutions induites. Les deux dernières phases sont répétées jusqu'à la stabilité de la population. Dans une troisième partie, le problème est résolu en combinant le GRASP (Greedy Randomized Adaptive Search Procedure) et le Path-relinking. Cette approche combine deux stratégies: une stratégie de construction et une autre d'amélioration. D'une part, la première stratégie produit une solution (de départ) réalisable en appliquant le GRASP. D'autre part, chaque solution courante (de départ) est améliorée en appliquant une stratégie basée sur le path-relinking : partir d’un couple de solutions « départ-arrivée », puis tenter de reconstruire le lien entre ces deux solutions en espérant rencontrer des solutions de meilleures qualités sur le chemin. Ce processus est répété sur une série de solutionsThe aim of this thesis is to propose approximate algorithms for tackling the max-min Multi-Scenarios Knapsack Problem (MSKP). Three methods have been proposed (which can be considered as complementary), where each of them is based on the perturbation aspect of the solutions and their re-buildings. The proposed methods are declined in three parts. In the first part, we propose to solve the MSKP by using a hybrid reactive search algorithm that uses two main features: (i) the restoring/exploring phase and (ii) the perturbation phase. The first phase yields a feasible solution and tries to improve it by using an intensification search. The second phase can be viewed as a diversification search in which a series of subspaces are investigated in order to make a quick convergence to a global optimum. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature, whereby its obtained results are compared to those reached by recent methods available in the literature. The results show that the method is competitive and it is able to provide better solutions. The second part discusses a population-based method which combines three complementary stages: (i) the building stage, (ii) the combination stage and (iii) the two-stage rebuild stage. First, the building stage serves to provide a starting feasible solution by using a greedy procedure; each item is randomly chosen for reaching a starting population of solutions. Second, the combination stage tries to provide each new solution by combining subsets of (starting) solutions. Third, the rebuild stage tries to make an intensification in order to improve the solutions at hand. The proposed method is evaluated on a set of benchmark instances taken from the literature, where its obtained results are compared to those reached by the best algorithms available in the literature. The results show that the proposed method provides better solutions than those already published. In the third part, both greedy randomized adaptive search procedure and path-relinking are combined for tackling the MSKP. The proposed method iterates both building and improvement phases that are based upon an extended search process. The first phase yields a (starting) feasible solution for the problem by applying a greedy randomized search procedure. The second phase tries to enhance each current solution by applying the path-relinking based strategy. Finally, the proposed method is evaluated on a set of benchmark instances taken from the literature. The obtained results are compared to those reached by some best algorithms available in the literature. Encouraging results have been obtained
20
Moyer, Nathan Thomas. "A knapsack-type cryptographic system using algebraic number rings." Pullman, Wash. : Washington State University, 2010. http://www.dissertations.wsu.edu/Dissertations/Spring2010/n_moyer_032610.pdf.
Full text
21
Sharma, Kamana. "Simultaneously lifting sets of variables in binary Knapsack problems." Thesis, Manhattan, Kan. : Kansas State University, 2007. http://hdl.handle.net/2097/469.
Full text
22
Schulze, Britta [Verfasser]. "New Perspectives on Multi-Objective Knapsack Problems / Britta Schulze." Wuppertal : Universitätsbibliothek Wuppertal, 2017. http://d-nb.info/1135602387/34.
Full text
23
Morrison, Thomas Braden. "Synchronized simultaneous approximate lifting for the multiple knapsack polytope." Thesis, Kansas State University, 2012. http://hdl.handle.net/2097/13548.
Full textAbstract:
Master of ScienceDepartment of Industrial and Manufacturing Systems Engineering
Todd Easton
Integer programs (IPs) are mathematical models that can provide an optimal solution to a variety of different problems. They have the ability to maximize profitability and decrease wasteful spending, but IPs are NP-complete resulting in many IPs that cannot be solved in reasonable periods of time. Cutting planes or valid inequalities have been used to decrease the time required to solve IPs. These valid inequalities are commonly created using a procedure called lifting. Lifting is a technique that strengthens existing valid inequalities without cutting off feasible solutions. Lifting inequalities can result in facet defining inequalities, the theoretically strongest valid inequalities. Because of these properties, lifting procedures are used in software to reduce the time required to solve an IP. This thesis introduces a new algorithm for synchronized simultaneous approximate lifting for multiple knapsack problems. Synchronized Simultaneous Approximate Lifting (SSAL) requires O(|E1|SLP_|E1|+|E2|,m + |E1|2) effort, where |E1| and |E2| are the sizes of sets used in the algorithm and SLP is the time to solve a linear program. It approximately uplifts two sets simultaneously to creates multiple inequalities of a particular form. These new valid inequalities generated by SSAL can be facet defining. A small computational study shows that SSAL is quick to execute, requiring fractions of a second. Additionally, applying SSAL inequalities to large knapsack problem enabled commercial software to solve faster and also eliminate off the initial linear relaxation point.
24
Dreiding, Rebecca. "Allocating Homeland Security Screening Resources Using Knapsack Problem Models." VCU Scholars Compass, 2010. http://scholarscompass.vcu.edu/etd/2289.
Full textAbstract:
Since the events of September 11, 2001, the federal government is focused on homeland security and the fight against terrorism. This thesis addresses the idea of terrorist groups smuggling nuclear weapons through the borders of the United States. Security screening decisions are analyzed within maritime and aviation domains using discrete optimization models, specifically knapsack problems. The focus of the maritime chapters involves a risk-based approach for prescreening intelligence classifications for primary and secondary screening decisions given limited budget and resources. Results reveal that screening decisions are dependent on prescreening classification and the efficacy of the screening technologies. The screening decisions in the aviation security chapter highlight different performance measures to quantify the effectiveness of covering flights with the intent of covering targets. Results reveal that given scarce resources, such as screening devices capacities and budget, flights and targets can be covered with minimal expense to the system.
25
Talamantes, Alonso. "Lifted equality cuts for the multiple knapsack equality problem." Thesis, Kansas State University, 2017. http://hdl.handle.net/2097/35516.
Full textAbstract:
Master of ScienceDepartment 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%.
26
Escobar, Alvaro E. "The multidimensional 0-1 knapsack problem an empirical analysis /." Instructions for remote access. Click here to access this electronic resource. Access available to Kutztown University faculty, staff, and students only, 1990. http://www.kutztown.edu/library/services/remote_access.asp.
Full text
27
Kubik, Lauren Ashley. "Simultaneously lifting multiple sets in binary knapsack integer programs." Thesis, Manhattan, Kan. : Kansas State University, 2009. http://hdl.handle.net/2097/1460.
Full text
28
Barake, M. A. "PROBE : a meta-heuristic for combinatorial optimisation problems." Thesis, University of East Anglia, 2001. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.368139.
Full text
29
Cherfi, Nawal. "Méthodes de résolution hybrides pour les problème de type knapsack." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2008. http://tel.archives-ouvertes.fr/tel-00401980.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d'arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d'arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de "Branch and cut". Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales dans un schéma énumératif. Les approches heuristiques et l'algorithme exact que nous proposons sont comparés à d'autres heuristiques de la littérature et au Solveur de programmes linéaires Cplex . L'ensemble de ces tests numériques ont été menés sur des instances ardues de la littérature ainsi que sur des instances générées aléatoirement de taille modérée.
30
Han, Xin. "Online and approximation algorithms for bin-packing and knapsack problems." 京都大学 (Kyoto University), 2007. http://hdl.handle.net/2433/135979.
Full text
31
Evans, Lisa. "Cyclic group and knapsack facets with applications to cutting planes." Diss., Georgia Institute of Technology, 2002. http://hdl.handle.net/1853/30639.
Full text
32
Appleget, Jeffrey A. "Knapsack cuts and explicit-constraint branching for solving integer programs." Thesis, Monterey, California. Naval Postgraduate School, 1997. http://hdl.handle.net/10945/8601.
Full textAbstract:
Approved for public release; distribution is unlimitedEnhanced solution techniques are developed for solving integer programs (IPs) and mixed-integer programs (MIPs). Previously unsolvable problems can be solved with these new techniques. We develop knapsack cut-finding procedures for minimal cover cuts, and convert existing cut-strengthening theory into practical procedures that lift and tighten violated minimal cover valid inequalities to violated knapsack facets in polynomial time. We find a new class of knapsack cuts called 'non-minimal cover cuts' and a method of lifting them called 'deficit lifting.' Deficit lifting enables all of these cuts to be lifted and tightened to facets as well. Extensions of these techniques enable us to find cuts for elastic knapsack constraints and cuts for non-standard knapsack constraints. We also develop the new technique of 'explicit-constraint branching' (ECB). ECB enables the technique of constraint branching to be used on IPs and MIPs that do not have the structure required for known 'implicit constraint branching' techniques. When these techniques are applied to 84 randomly generated generalized assignment problems, the combination of knapsack cuts and explicit-constraint branching were able to solve 100% of the problems in under 1000 CPU seconds. Explicit constraint branching alone solved 94%, and knapsack cuts solved 93%. Standard branch and bound alone solved only 38%. The benefits of these techniques are also demonstrated on some real-world generalized assignment and set-partitioning problems
33
Akin, Haluk. "New Heuristics For the 0-1 Multi-Dimensional Knapsack Problems." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/4072.
Full textAbstract:
This dissertation introduces new heuristic methods for the 0-1 multi-dimensional knapsack problem (0-1 MKP). 0-1 MKP can be informally stated as the problem of packing items into a knapsack while staying within the limits of different constraints (dimensions). Each item has a profit level assigned to it. They can be, for instance, the maximum weight that can be carried, the maximum available volume, or the maximum amount that can be afforded for the items. One main assumption is that we have only one item of each type, hence the problem is binary (0-1). The single dimensional version of the 0-1 MKP is the uni-dimensional single knapsack problem which can be solved in pseudo-polynomial time. However the 0-1 MKP is a strongly NP-Hard problem. Reduced cost values are rarely used resources in 0-1 MKP heuristics; using reduced cost information we introduce several new heuristics and also some improvements to past heuristics. We introduce two new ordering strategies, decision variable importance (DVI) and reduced cost based ordering (RCBO). We also introduce a new greedy heuristic concept which we call the "sliding concept" and a sub-branch of the "sliding concept" which we call "sliding enumeration". We again use the reduced cost values within the sliding enumeration heuristic. RCBO is a brand new ordering strategy which proved useful in several methods such as improving Pirkul's MKHEUR, a triangular distribution based probabilistic approach, and our own sliding enumeration. We show how Pirkul's shadow price based ordering strategy fails to order the partial variables. We present a possible fix to this problem since there tends to be a high number of partial variables in hard problems. Therefore, this insight will help future researchers solve hard problems with more success. Even though sliding enumeration is a trivial method it found optima in less than a few seconds for most of our problems. We present different levels of sliding enumeration and discuss potential improvements to the method. Finally, we also show that in meta-heuristic approaches such as Drexl's simulated annealing where random numbers are abundantly used, it would be better to use better designed probability distributions instead of random numbers.Ph.D.
Department of Industrial Engineering and Management Systems
Engineering and Computer Science
Industrial Engineering PhD
34
Mouser, Philip Samuel. "Decomposition methods for the quadratic assignment and multidimensional knapsack problem." Thesis, University of East Anglia, 2007. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.437831.
Full text
35
Krishnan, Bharath Kumar. "A multiscale approximation algorithm for the cardinality constrained knapsack problem." Thesis, Massachusetts Institute of Technology, 2006. http://hdl.handle.net/1721.1/34612.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Civil and Environmental Engineering, 2006.Includes bibliographical references (leaves 83-86).
I develop a multiscale approximation algorithm for the cardinality constrained knapsack problem. The algorithm consists of three steps: a rounding and reduction step where a hierarchical representation of the problem data ranging from coarse to fine is generated, a solution step where a coarse solution is computed, and a refinement step where the accuracy of the solution is improved by refining the problem representation. I demonstrate that the algorithm is fully polynomial with a runtime complexity that improves upon the previous best known fully polynomial approximation scheme. Through an extensive computational study, I show that the running times of the algorithm is less than or equal to that of a commercial integer programming package with little loss in solution accuracy.
by Bharath Kumar Krishnan.
Ph.D.
36
Chakka, Varun Raj. "Models and algorithms for the Multiple Knapsack problem with conflicts." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2022.
Find full textAbstract:
In the Multiple Knapsack Problem with Conflicts, we are given a set of items, each with its own weight and profit, as well as a set of multiple knapsacks, each with its own capacity. The goal is to maximize the total profit of the items inserted in the knapsacks, while respecting the knapsack capacity and the incompatibility constraints between items..
The thesis is based on Basnet2018 research article. I developed some heuristic algorithms and tested them with various instances with a maximum case of 500 items and 15 knapsacks. The results of the computations are reported.
37
Cherfi, Nawal. "Méthodes de résolution hybrides pour les problèmes de type knapsack." Paris 1, 2008. http://www.theses.fr/2008PA010056.
Full textAbstract:
Dans cette thèse, nous nous intéressons aux problèmes du knapsack multidimensionnel à choix multiple. Ils interviennent essentiellement en télécommunication. Nous proposons de nouvelles méthodes hybrides de résolution exacte et approchée. Dans un premier temps, nous proposons des méthodes heuristiques en se basant sur les techniques de génération de colonnes et d’arrondi. Ensuite, nous abordons une méthode de recherche locale, dite méthode de branchement local, où des contraintes linéaires sont introduites pour intensifier et diversifier la recherche. Cette méthode est ensuite hybridée avec la génération de colonnes et une technique d’arrondi. Concernant la résolution exacte, nous nous basons sur une méthode de « branch and cut ». Nous commençons par proposer de nouvelles contraintes valides pour le problème. Ensuite, nous les associons à des contraintes de couverture locales et globales.
38
Maki, Jameel A. "Some metaheuristics for the graph bisection and the multiconstraint knapsack problems." Thesis, University of East Anglia, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.399809.
Full text
39
PALMEIRA, MARCIO DE MORAES. "ALGORITHM RELAX-AND-CUT FOR THE 0-1 QUADRATIC KNAPSACK PROBLEM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 1999. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=7404@1.
Full textAbstract:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICOConsideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima.
We consider the 0-1 Quadratic Knapsack Problem (QKP), which consists of maximizing a quadratic Boolean function subject to a linear capacity constraint. The problem has applications in several areas such as telecommunications, financial engineering, location problems, graph theory (Max Clique). We propose a Branch-and-Bound algorithm to solve the QKP to optimality based on lagrangian Relaxation. Initially, we linearize the formulation of the problem given above and then we relax-and-cut dinamicaly its continous relaxation using a few classes of valid inequalities. In the process the Subgradient Method is applied. We also propose a new primal heuristic for the QKP that has improved upon previous approaches, and finds an optimal solution for all of the instances we considered. The good quality of our upper and lower bounds is translated into small gaps at the root node of the enumeration tree (usually below 1%, even for difficult instances). That, coupled with tests for fixing variables, allowed optimality to be proven within only a few nodes of the enumeration tree. We provide a way to randomly generate instances of the QKP harder than those in the literature. We report computational results for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes; and also for Known instances of Max Clique problems.
40
Baitshenyetsi, Tumo. "Applying tree knapsack approaches to general network design : a case study / T. Baitshenyetsi." Thesis, North-West University, 2010. http://hdl.handle.net/10394/4434.
Full textAbstract:
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.
41
Fukasawa, Ricardo. "Single-row mixed-integer programs : theory and computations /." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24660.
Full textAbstract:
Thesis (Ph.D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2009.Committee Chair: William J. Cook; Committee Member: Ellis Johnson; Committee Member: George Nemhauser; Committee Member: Robin Thomas; Committee Member: Zonghao Gu
42
Dall'Olio, Giacomo. "Solving the logically constrained multiple choice multiple knapsack problem: A real case." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2016.
Find full textAbstract:
In questa tesi viene analizzato un problema di ottimizzazione proposto da alcuni esercizi commerciali che hanno la necessita` di selezionare e disporre i propri ar- ticoli in negozio. Il problema nasce dall’esigenza di massimizzare il profitto com- plessivo atteso dei prodotti in esposizione, trovando per ognuno una locazione sugli scaffali. I prodotti sono suddivisi in dipartimenti, dai quali solo un ele- mento deve essere selezionato ed esposto. In oltre si prevede la possibilita` di esprimere vincoli sulla locazione e compatibilita` dei prodotti. Il problema risul- tante `e una generalizzazione dei gia` noti Multiple-Choice Knapsack Problem e Multiple Knapsack Problem. Dopo una ricerca esaustiva in letteratura si `e ev- into che questo problema non `e ancora stato studiato. Si `e quindi provveduto a formalizzare il problema mediante un modello di programmazione lineare intera. Si propone un algoritmo esatto per la risoluzione del problema basato su column generation e branch and price. Sono stati formulati quattro modelli differenti per la risoluzione del pricing problem su cui si basa il column generation, per individuare quale sia il piu` efficiente. Tre dei quattro modelli proposti hanno performance comparabili, mentre l’ultimo si `e rivelato piu` inefficiente. Dai risul- tati ottenuti si evince che il metodo risolutivo proposto `e adatto a istanze di dimensione medio-bassa.
43
Kawahara, Jun. "Automated Competitive Analysis of Online Knapsack Problems and Randomized k-server Problems." 京都大学 (Kyoto University), 2009. http://hdl.handle.net/2433/123859.
Full text
44
Beyer, Carrie Austin. "Exact synchronized simultaneous uplifting over arbitrary initial inequalities for the knapsack polytope." Thesis, Kansas State University, 2011. http://hdl.handle.net/2097/8782.
Full textAbstract:
Master of ScienceDepartment of Industrial & Manufacturing Systems Engineering
Todd W. Easton
Integer programs (IPs) are mathematical models that can provide an optimal solution to a variety of different problems. They have been used to reduce costs and optimize organizations. Additionally, IPs are NP-complete resulting in many IPs that cannot be solved. Cutting planes or valid inequalities have been used to decrease the time required to solve IPs. Lifting is a technique that strengthens existing valid inequalities. Lifting inequalities can result in facet defining inequalities, which are the theoretically strongest valid inequalities. Because of these properties, lifting procedures are used in software to reduce the time required to solve an IP. The thesis introduces a new algorithm for exact synchronized simultaneous uplifting over an arbitrary initial inequality for knapsack problems. Synchronized Simultaneous Lifting (SSL) is a pseudopolynomial time algorithm requiring O(nb+n[superscript]3) effort to solve. It exactly uplifts two sets simultaneously into an initial arbitrary valid inequality and creates multiple inequalities of a particular form. This previously undiscovered class of inequalities generated by SSL can be facet defining. A small computational study shows that SSL is quick to execute, requiring on average less than a quarter of a second. Additionally, applying SSL inequalities to a knapsack problem enabled commercial software to solve problems that it could not solve without them.
45
Bolton, Thomas Charles. "Generating cutting planes through inequality merging on multiple variables in knapsack problems." Thesis, Kansas State University, 2015. http://hdl.handle.net/2097/19038.
Full textAbstract:
Master of ScienceIndustrial & Manufacturing Systems Engineering
Todd W. Easton
Integer programming is a field of mathematical optimization that has applications across a wide variety of industries and fields including business, government, health care and military. A commonly studied integer program is the knapsack problem, which has applications including project and portfolio selection, production planning, inventory problems, profit maximization applications and machine scheduling. Integer programs are computationally difficult and currently require exponential effort to solve. Adding cutting planes is a way of reducing the solving time of integer programs. These cutting planes eliminate linear relaxation space. The theoretically strongest cutting planes are facet defining inequalities. This thesis introduces a new class of cutting planes called multiple variable merging cover inequalities (MVMCI). The thesis presents the multiple variable merging cover algorithm (MVMCA), which runs in linear time and produces a valid MVMCI. Under certain conditions, an MVMCI can be shown to be a facet defining inequality. An example demonstrates these advancements and is used to prove that MVMCIs could not be identified by any existing techniques. A small computational study compares the computational impact of including MVMCIs. The study shows that finding an MVMCI is extremely fast, less than .01 seconds. Furthermore, including an MVMCI improved the solution time required by CPLEX, a commercial integer programming solver, by 6.3% on average.
46
Cherbaka, Natalie Stanislaw. "Solving Single and Multiple Plant Sourcing Problems with a Multidimensional Knapsack Model." Diss., Virginia Tech, 2004. http://hdl.handle.net/10919/29802.
Full textAbstract:
This research addresses sourcing decisions and how those decisions can affect the management of a company's assets. The study begins with a single-plant problem, in which one facility chooses, from a list of parts, which parts to bring in-house. The selection is based on maximizing the value of the selected parts, while remaining within the plant's capacity. This problem is defined as the insourcing problem and modeled as a multidimensional knapsack problem (MKP). The insourcing model is extended to address outsourcing and multiple plants. This multi-plant model, also modeled as an MKP, enables the movement of parts from one plant to another and consideration of a company-wide objective function (as opposed to a single-plant objective function as in the insourcing model).
The sourcing problem possesses characteristics that distinguish it from the standard MKP. One such characteristic is what we define as multiple attributes. To understand the multiple attribute characteristic, we compare the various dimensions in the multidimensional knapsack problem. A classification is given for an MKP as either having a single attribute (SA) or multiple attributes (MA). Mathematically, the problems of each attribute classification can be modeled in the same way with simply a different interpretation of the knapsack constraints. However, experimentation indicates that the MA-MKP is more difficult to solve than the SA-MKP. For small problems, with 100 variables and 5 constraints, the CPU time required to find the optimal solution for MA-MKP to SA-MKP problems has a ratio of 32:1.
To determine effective methods for addressing the MA-MKP, standard mixed integer programming techniques are tested. The results of this testing are that the exact approaches are not successful in dramatically reducing the solution time to the level of the SA problems. However, a simple heuristic that performs very well on the MA-MKP is presented. The heuristic utilizes variations on the benefit-to-cost ratio and strongest surrogate constraints. The results from experimentation for MA-MKP problem sets, generated using the methods for standard MKP test data sets in the literature, are presented and indicate that the heuristic performs well and improves with larger problems. The average gap between the heuristic solution and the optimal solution is 1.39% for 200-part problems and is reduced to 0.69% when the size of the problem is increased to 298 parts.
Although the MA characteristic reflects the sourcing problem, the actual data used in the eperimentation is generated with techniques presented in the literature for standard MKP test problems. Therefore, to more accurately represent the sourcing problem, industry data from a manufacturing facility is studied to identify further sourcing problem characteristics. As a result, industry-motivated data sets are generated that reflect the characteristics of industry data, yet maintain the structure of literature data sets to allow for easy comparison. It is found that both industry and industry-motivated data sets, although possessing the MA characteristic, are much easier to solve than SA problems. Indicators of difficulty appear to be the constraint tightness and a measure of the matrix sparsity. The sparsity is a significant factor because industry data tends to be very sparse, while data sets generated in the literature are completely dense. Another interesting result from the industry-motivated data sets with the single-plant problem is the tendency for a facility to prefer currently produced parts over insourcing new parts from outside the facility.
It is not uncommon for a company to have more than one facility with a particular capability. Therefore, the sourcing model is extended to include multiple facilities. With multiple-facilities, effectively all the parts are removed to form one list, and then each part is assigned to one of the facilities or outsourced externally. The multi-facility model is similar to the single-facility model with the addition of assignment constraints enforcing that each part can be assigned to only one facility. Experimentation is performed for the two-, three-, and four-facility models. The problem gets easier to solve as the number of facilities increases. With a greater number of facilities, it is likely that for each part one of facilities will dominate as the best option. Therefore, other solutions can quickly be eliminated and the problem solved more quickly. The two-facility problem is the most difficult; however, the heuristic performs well with an average gap of 0.06% between the heuristic and optimal solutions.
We conclude with a summary on experiences with modeling and solving the sourcing problem for a sheet metal fabrication facility. The model solved for this problem had over 1857 parts with 19 machines, which translates to over 70,000 variables and 38 constraints. Although extremely large compared to problems solved in the literature, this problem was solvable because of the unique structure of industry data. Our work with the facility saved the parent organization up to $4.16M per year and provided a tool that encourages a systematic and quantitative process for evaluating decisions related to sheet metal fabrication capacity.Ph. D.
47
Simms, Amy E. "A Stochastic Approach to Modeling Aviation Security Problems Using the KNAPSACK Problem." Thesis, Virginia Tech, 1997. http://hdl.handle.net/10919/36806.
Full textAbstract:
Designers, operators, and users of multiple-device, access
control security systems are challenged by the false alarm,
false clear tradeoff. Given a particular access control
security system, and a prespecified false clear standard,
there is an optimal (minimal) false alarm rate that can be
achieved. The objective of this research is to develop
methods that can be used to determine this false alarm rate.
Meeting this objective requires knowledge of the joint
conditional probability density functions for the security
device responses. Two sampling procedures, the static grid
estimation procedure and the dynamic grid estimation
procedure, are proposed to estimate these functions. The
concept of a system response function is introduced and the
problem of determining the optimal system response function
that minimizes the false alarm rate, while meeting the false
clear standard, is formulated as a decision problem and
proven to be NP-complete. Two heuristic procedures, the
Greedy algorithm and the Dynamic Programming algorithm, are
formulated to address this problem. Computational results
using simulated security data are reported. These results
are compared to analytical results, obtained for a
prespecified system response function form. Suggestions for
future research are also included.Master of Science
48
Cimren, Emrah. "Valid Inequalities for The 0-1 Mixed Knapsack Polytope with Upper Bounds." The Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1273804915.
Full text
49
Richard, Jean-Philippe P. "Lifted inequalities for 0-1 mixed integer programming." Diss., Georgia Institute of Technology, 2002. http://hdl.handle.net/1853/24590.
Full text
50
Li, Yaxian. "Lower bounds for integer programming problems." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/48959.
Full textAbstract:
Solving real world problems with mixed integer programming (MIP) involves efforts in modeling and efficient algorithms. To solve a minimization MIP problem, a lower bound is needed in a branch-and-bound algorithm to evaluate the quality of a feasible solution and to improve the efficiency of the algorithm. This thesis develops a new MIP model and studies algorithms for obtaining lower bounds for MIP.
The first part of the thesis is dedicated to a new production planning model with pricing decisions. To increase profit, a company can use pricing to influence its demand to increase revenue, decrease cost, or both. We present a model that uses pricing discounts to increase production and delivery flexibility, which helps to decrease costs. Although the revenue can be hurt by introducing pricing discounts, the total profit can be increased by properly choosing the discounts and production and delivery decisions. We further explore the idea with variations of the model and present the advantages of using flexibility to increase profit.
The second part of the thesis focuses on solving integer programming(IP) problems by improving lower bounds. Specifically, we consider obtaining lower bounds for the multi- dimensional knapsack problem (MKP). Because MKP lacks special structures, it allows us to consider general methods for obtaining lower bounds for IP, which includes various relaxation algorithms. A problem relaxation is achieved by either enlarging the feasible region, or decreasing the value of the objective function on the feasible region. In addition, dual algorithms can also be used to obtain lower bounds, which work directly on solving the dual problems.
We first present some characteristics of the value function of MKP and extend some properties from the knapsack problem to MKP. The properties of MKP allow some large scale problems to be reduced to smaller ones. In addition, the quality of corner relaxation bounds of MKP is considered. We explore conditions under which the corner relaxation is
tight for MKP, such that relaxing some of the constraints does not affect the quality of the lower bounds. To evaluate the overall tightness of the corner relaxation, we also show the worst-case gap of the corner relaxation for MKP.
To identify parameters that contribute the most to the hardness of MKP and further evaluate the quality of lower bounds obtained from various algorithms, we analyze the characteristics that impact the hardness of MKP with a series of computational tests and establish a testbed of instances for computational experiments in the thesis.
Next, we examine the lower bounds obtained from various relaxation algorithms com- putationally. We study methods of choosing constraints for relaxations that produce high- quality lower bounds. We use information obtained from linear relaxations to choose con- straints to relax. However, for many hard instances, choosing the right constraints can be challenging, due to the inaccuracy of the LP information. We thus develop a dual heuristic algorithm that explores various constraints to be used in relaxations in the Branch-and- Bound algorithm. The algorithm uses lower bounds obtained from surrogate relaxations to improve the LP bounds, where the relaxed constraints may vary for different nodes. We also examine adaptively controlling the parameters of the algorithm to improve the performance.
Finally, the thesis presents two problem-specific algorithms to obtain lower bounds for MKP: A subadditive lifting method is developed to construct subadditive dual solutions, which always provide valid lower bounds. In addition, since MKP can be reformulated as a shortest path problem, we present a shortest path algorithm that uses estimated distances by solving relaxations problems. The recursive structure of the graph is used to accelerate the algorithm. Computational results of the shortest path algorithm are given on the testbed instances.