Dissertation > Excellent graduate degree dissertation topics show

A New Algorithm for Knapsack Problem: Reduce Dimension and Recursive Algorithm

Author: ZhongHaiLin
Tutor: YeXiangQi
School: Jiangxi Normal University
Course: Applied Mathematics
Keywords: Integer Linear Programming Knapsack problem Invalid variable Dimensionality reduction recursive algorithm
CLC: TP301.6
Type: Master's thesis
Year: 2008
Downloads: 177
Quote: 0
Read: Download Dissertation

Abstract


Knapsack problem is an important value in project selection, material cutting , cargo loading applications . From the computational complexity theory , the knapsack problem is a classical NP-hard problem . This paper analyzes the characteristics of single constrained integer linear programming (ILP, knapsack problem ) , cut invalid variables to simplify the problem and design a new algorithm for the problem - dimensionality reduction recursive algorithm , the text is divided into four chapters . In chapter twelve , the background of the knapsack problem and the algorithm to be used . The third chapter gives some properties of the knapsack problem and the critical nature of the proof , and designed on the basis of a new algorithm . In the fourth chapter of the specific issues of numerical experiments further verified the feasibility of the algorithm from the instance .

Related Dissertations

  1. Research on Combinatorial Optimization Problem Based on DNA Self-Assemble,TP399-C8
  2. Segmentation based on two-dimensional human pose estimation consistency,TP391.41
  3. Multi-objective artificial fireflies swarm optimization algorithm and its application,TP301.6
  4. Study on the Optimization of Earthwork Allocation in Harbin Qunli New District,TU751
  5. The Improvement of Genetic Algorithm and It’s Application on Knapsack Problem and Function Optimization,TP18
  6. Research on the Combinational Optimization in Shuffled Frog Leaping Algorithm,TP301.6
  7. Research on Modified Particle Swarm Optimization and Its Application,TP301.6
  8. The Research of Artificial Fish Swarm Algorithm and Its Application,TP301.6
  9. The Research of a Multi-objective Evolutionary Algorithm Based on Steady-state,O221.6
  10. Research on Lock Capacity on the Minjiang River Downstream,U641.7
  11. The Numerical Algorithm for the Linear Congruential Equations with Single Modulus / Multi-modulus and Its Application in Cryptography,TN918.1
  12. MPI-based parallel genetic algorithm for 0-1 knapsack problem Applied Research,TP18
  13. Based upon digestion items identified global optimization method coreference resolution,TP391.1
  14. Further Examination for Iterative Siphon Control in Petri Nets,TP301.1
  15. Application Research of Particle Swarm Optimization in Conbinatiorial Optimization Problems,TP301.6
  16. Genetic Algorithms Research and Application mode - based alternative,TP18
  17. On the Multi-population Ant Colony Optimization Algorithm,TP301.6
  18. Research on the Design of Reverse Logistics Network of Electronic Waste,F713.2
  19. Research on Cutting Plane Algorithm for Directed Chinese Postman Problem with Time Dependent Travel Times,F618
  20. Study on Optimizing Reverse Logistics Network in Automobile Manufacturing Enterprises,F253.9
  21. An Improved Genetic Algorithm and Its Applications for Solving Knapsack Problem,TP18

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory
© 2012 www.DissertationTopic.Net  Mobile