• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 32
  • 10
  • 8
  • 6
  • 4
  • 2
  • 2
  • 1
  • Tagged with
  • 74
  • 74
  • 28
  • 26
  • 22
  • 15
  • 13
  • 13
  • 10
  • 10
  • 9
  • 9
  • 8
  • 8
  • 8
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Lifted inequalities for 0-1 mixed integer programming

Richard, Jean-Philippe P. 08 1900 (has links)
No description available.
2

Knapsack problems with setup

Yang, Yanchun, Bulfin, Robert L. January 2006 (has links) (PDF)
Dissertation (Ph.D.)--Auburn University, 2006. / Abstract. Vita. Includes bibliographic references (p.94-95).
3

Large scale group network optimization

Shim, Sangho. January 2009 (has links)
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.
4

Product selection in semiconductor manufacturing by solving a dynamic stochastic multiple knapsack problem /

Perry, Thomas C., January 2004 (has links)
Thesis (Ph. D.)--Lehigh University, 2005. / Includes vita. Includes bibliographical references (leaves 164-166).
5

Solving Single and Multiple Plant Sourcing Problems with a Multidimensional Knapsack Model

Cherbaka, Natalie Stanislaw 01 December 2004 (has links)
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.
6

Single-row mixed-integer programs : theory and computations /

Fukasawa, Ricardo January 2008 (has links)
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
7

Enhancements of the non-linear knapsack cryptosystem : a thesis submitted in partial fulfilment of the requirements for the degree of Master of Science at the University of Canterbury /

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

Three set inequalities in integer programming

McAdoo, Michael John January 1900 (has links)
Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming is a useful tool for modeling and optimizing real world problems. Unfortunately, the time required to solve integer programs is exponential, so real world problems often cannot be solved. The knapsack problem is a form of integer programming that has only one constraint and can be used to strengthen cutting planes for general integer programs. These facts make finding new classes of facet-defining inequalities for the knapsack problem an extremely important area of research. This thesis introduces three set inequalities (TSI) and an algorithm for finding them. Theoretical results show that these inequalities will be of dimension at least 2, and can be facet defining for the knapsack problem under certain conditions. Another interesting aspect of these inequalities is that TSIs are some of the first facet-defining inequalities for knapsack problems that are not based on covers. Furthermore, the algorithm can be extended to generate multiple inequalities by implementing an enumerative branching tree. A small computational study is provided to demonstrate the effectiveness of three set inequalities. The study compares running times of solving integer programs with and without three set inequalities, and is inconclusive.
9

An Improved Genetic Algorithm for Knapsack Problems

Kilincli Taskiran, Gamze 07 April 2010 (has links)
No description available.
10

The Knapsack Problem, Cryptography, and the Presidential Election

McMillen, Brandon 27 June 2012 (has links)
No description available.

Page generated in 0.0604 seconds