Search Results - subject:"knapsack problem"

An exact algorithm for the multiple-choice multidimensional knapsack problem.

Hifi, Mhand; Sadfi, Slim; Sbihi, Abdelkader - Maison des Sciences Économiques, Université Paris 1 … - 2004

In this paper, we propose an optimal algorithm for the Multiple-choice Multidimensional Knapsack Problem MMKP. The main …

Persistent link: https://www.econbiz.de/10005510637

The average behaviour of greedy algorithms for the knapsack problem: General distributions

Diubin, Gennady; Korbut, Alexander - In: Mathematical Methods of Operations Research 57 (2003) 3, pp. 449-479

coefficients of the objective function and the constraint of the knapsack problem are independent identically distributed random …

Persistent link: https://www.econbiz.de/10010999610

The average behaviour of greedy algorithms for the knapsack problem: General distributions

Diubin, Gennady; Korbut, Alexander - In: Computational Statistics 57 (2003) 3, pp. 449-479

coefficients of the objective function and the constraint of the knapsack problem are independent identically distributed random …

Persistent link: https://www.econbiz.de/10010759207

Approximating Multiobjective Knapsack Problems

Erlebach, Thomas; Kellerer, Hans; Pferschy, Ulrich - In: Management Science 48 (2002) 12, pp. 1603-1612

-offs between the different objectives. The multiobjective knapsack problem is a generalization of the classical knapsack problem in …-dimensional knapsack problem, a practical fully polynomial-time approximation scheme (FPTAS) is derived. It is based on a new approach to … the single-objective knapsack problem using a partition of the profit space into intervals of exponentially increasing …

Persistent link: https://www.econbiz.de/10009209075

The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance

Hill, Raymond R.; Reilly, Charles H. - In: Management Science 46 (2000) 2, pp. 302-317

This paper presents the results of an empirical study of the effects of coefficient correlation structure and constraint slackness settings on the performance of solution procedures on synthetic two-dimensional knapsack problems (2KP). The population correlation structure among 2KP coefficients,...

Persistent link: https://www.econbiz.de/10009191653

Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem

Martello, Silvano; Pisinger, David; Toth, Paolo - In: Management Science 45 (1999) 3, pp. 414-424

Two new algorithms recently proved to outperform all previous methods for the exact solution of the 0-1 Knapsack … Problem. This paper presents a combination of such approaches, where, in addition, valid inequalities are generated and …

Persistent link: https://www.econbiz.de/10009198165

Test sets of integer programs

Weismantel, Robert - In: Mathematical Methods of Operations Research 47 (1998) 1, pp. 1-37

relations between them. We also illustrate on various examples such as the minimum cost flow problem, the knapsack problem and … problem by computing the Graver test set and show that, in the special case of an integer knapsack problem with 3 coefficients …

Persistent link: https://www.econbiz.de/10010999564

Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty

Laguna, Manuel - In: Management Science 44 (1998) 11-Part-2, pp. 101-101

The problem of expanding the capacity of a single facility in telecommunications network planning is addressed. This problem can be formulated as a time-dependent knapsack, when relevant information is assumed to be known. We introduce the use of scenarios to model uncertainty in key data. The...

Persistent link: https://www.econbiz.de/10009189501

Test sets of integer programs

Weismantel, Robert - In: Computational Statistics 47 (1998) 1, pp. 1-37

Persistent link: https://www.econbiz.de/10010759162

A new algorithm for the Integer Knapsack Problem and its parallelization

Almeida, F.; García, F.; Morales, D.; Roda, J.; … - In: TOP: An Official Journal of the Spanish Society of … 3 (1995) 2, pp. 221-234

Persistent link: https://www.econbiz.de/10005371478