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.

No description available.

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 solutions / The 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

No description available.

Dissertation (Ph.D.)--Auburn University, 2006. / Abstract. Vita. Includes bibliographic references (p.94-95).

Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Ellis L. Johnson; Committee Member: Brady Hunsaker; Committee Member: George Nemhauser; Committee Member: Jozef Siran; Committee Member: Shabbir Ahmed; Committee Member: William Cook. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Thesis (Ph. D.)--Lehigh University, 2005. / Includes vita. Includes bibliographical references (leaves 164-166).

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.

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

Thesis (M. Sc.)--University of Canterbury, 2006. / Typescript (photocopy). Includes bibliographical references (p. [93]-98). Also available via the World Wide Web.