Dynamic programming and strong bounds for the 0-1 Knapsack problem
Article Abstract:
A study was conducted to analyze the use of two novel algorithms to determine an exact solution to the 0-1 Knapsack problem. Valid inequalities were produced and new upper bounds determined from the surrogate relaxation of cardinality constraints were introduced. Items were assumed to be ordered by non-increasing profit-to-weight ratios, willing the knapsack until the first item that does not fit was found. The break item was determined through partial sorting in time. Results indicated that the algorithm can promote solutions to all classical test instances supporting up to 10,000 variables in less than 0.2 seconds on an Hewlett-Packard 9000-735/99 computer system. In addition, the algorithm returns partially sorted intervals which can be utilized to expand the core without complete sorting.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1999
User Contributions:
Comment about this article or add new information about this topic:
Heuristic algorithms for the multiple depot vehicle scheduling problem
Article Abstract:
The minimization of operational costs in the Multiple Depot Vehicle Scheduling Problem is examined. The problem involves the assignment of time-tabled trips to vehicles at various depots such that the number of vehicles used is minimized. A new polynomial-time heuristic algorithm is proposed based on the exploitation of the problem's structural properties, and several refining procedures are constructed. Test problems involving a maximum of 1,000 trips and ten depots yield solutions that are tight approximations within short computing times, demonstrating the procedure's efficiency relativeto other heuristics. The results have important implications for the managementof transportation facilities.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1993
User Contributions:
Comment about this article or add new information about this topic:
A new algorithm for the 0-1 knapsack problem
Article Abstract:
A new algorithm is presented for the best solution to the '0-1 knapsack' problem, which is especially effective for big-size problems. The algorithm stems from determination of an appropriate, tiny group of items and solving the related core problem. An heuristic solution for the original problem can then be shown to be best, with high probability. The algorithm includes a new way of computing the upper bounds and efficient ways of reducing procedures. Related Fortran code is available.
Publication Name: Management Science
Subject: Business, general
ISSN: 0025-1909
Year: 1988
User Contributions:
Comment about this article or add new information about this topic:
- Abstracts: An integer programming approach to the bandwidth packing problem. Heuristics based on spacefilling curves for combinatorial problems in Euclidean space
- Abstracts: Ethics programs: make them real. Career planning for the '90s
- Abstracts: Economics language and assumptions: How theories can become self-fulfilling. Determinants of work force reduction strategies in declining organizations
- Abstracts: Two-stage perishable inventory models. Repetitive testing strategies when the testing process is imperfect. Optimal order of servers for tandem queues in light traffic
- Abstracts: Dispersive equity and social risk. Foundations of decision analysis: along the way. An experiment in approval voting