The Experts below are selected from a list of 315 Experts worldwide ranked by ideXlab platform
David Pisinger - One of the best experts on this subject based on the ideXlab platform.
-
The Multiple-Choice Knapsack Problem
Knapsack Problems, 2020Co-Authors: Hans Kellerer, Ulrich Pferschy, David PisingerAbstract:The multiple-choice Knapsack Problem (MCKP) is a generalization of the ordinary Knapsack Problem, where the set of items is partitioned into classes. The binary choice of taking an item is replaced by the selection of exactly one item out of each class of items. In Section 7.1 we already noticed that a (BKP) can be formulated as a (MCKP), and indeed the (MCKP) model is one of the most flexible Knapsack models. (MCKP) is also denoted as Knapsack Problem with generalized upper bound constraints or for short Knapsack Problem with GUB.
-
The Bounded Knapsack Problem
Knapsack Problems, 2020Co-Authors: Hans Kellerer, Ulrich Pferschy, David PisingerAbstract:Right from the beginning of research on the Knapsack Problem in the early six-ties separate considerations were devoted to Problems where a number of identical copies of every item are given or even an unlimited amount of each item is available. The corresponding Problems are known as the bounded and unbounded Knapsack Problem, respectively. Since there exists a considerable amount of theoretical, algorithmic and computational results which apply for only one of these two Problems, we found it appropriate to deal with them in separate chapters. Hence, we restrict this chapter to the bounded case whereas the unbounded case will be treated in Chapter 8.
-
a minimal algorithm for the multiple choice Knapsack Problem
European Journal of Operational Research, 1995Co-Authors: David PisingerAbstract:Abstract The Multiple-Choice Knapsack Problem is defined as a 0–1 Knapsack Problem with the addition of disjoined multiple-choice constraints. As for other Knapsack Problems most of the computational effort in the solution of these Problems is used for sorting and reduction. But although O(n) algorithms which solve the linear Multiple-Choice Knapsack Problem without sorting have been known for more than a decade, such techniques have not been used in enumerative algorithms. In this paper we present a simple O(n) partitioning algorithm for deriving the optimal linear solution, and show how it may be incorporated in a dynamic programming algorithm such that a minimal number of classes are enumerated, sorted and reduced. Computational experiments indicate that this approach leads to a very efficient algorithm which outperforms any known algorithm for the Problem.
Petru Eles - One of the best experts on this subject based on the ideXlab platform.
-
A scalable GPU-based approach to accelerate the multiple-choice Knapsack Problem
2012 Design Automation & Test in Europe Conference & Exhibition (DATE), 2012Co-Authors: Bharath Suri, Unmesh D. Bordoloi, Petru ElesAbstract:Variants of the 0-1 Knapsack Problem manifest themselves at the core of several system-level optimization Problems. The running times of such system-level optimization techniques are adversely affected because the Knapsack Problem is NP-hard. In this paper, we propose a new GPU-based approach to accelerate the multiple-choice Knapsack Problem, which is a general version of the 0-1 Knapsack Problem. Apart from exploiting the parallelism offered by the GPUs, we also employ a variety of GPU-specific optimizations to further accelerate the running times of the Knapsack Problem. Moreover, our technique is scalable in the sense that even when running large instances of the multiple-choice Knapsack Problems, we can efficiently utilize the GPU compute resources and memory bandwidth to achieve significant speedups.
Ulrich Pferschy - One of the best experts on this subject based on the ideXlab platform.
-
The Multiple-Choice Knapsack Problem
Knapsack Problems, 2020Co-Authors: Hans Kellerer, Ulrich Pferschy, David PisingerAbstract:The multiple-choice Knapsack Problem (MCKP) is a generalization of the ordinary Knapsack Problem, where the set of items is partitioned into classes. The binary choice of taking an item is replaced by the selection of exactly one item out of each class of items. In Section 7.1 we already noticed that a (BKP) can be formulated as a (MCKP), and indeed the (MCKP) model is one of the most flexible Knapsack models. (MCKP) is also denoted as Knapsack Problem with generalized upper bound constraints or for short Knapsack Problem with GUB.
-
The Bounded Knapsack Problem
Knapsack Problems, 2020Co-Authors: Hans Kellerer, Ulrich Pferschy, David PisingerAbstract:Right from the beginning of research on the Knapsack Problem in the early six-ties separate considerations were devoted to Problems where a number of identical copies of every item are given or even an unlimited amount of each item is available. The corresponding Problems are known as the bounded and unbounded Knapsack Problem, respectively. Since there exists a considerable amount of theoretical, algorithmic and computational results which apply for only one of these two Problems, we found it appropriate to deal with them in separate chapters. Hence, we restrict this chapter to the bounded case whereas the unbounded case will be treated in Chapter 8.
-
The Product Knapsack Problem: Approximation and Complexity
arXiv: Optimization and Control, 2019Co-Authors: Ulrich Pferschy, Joachim Schauer, Clemens ThielenAbstract:We consider the product Knapsack Problem, which is the variant of the classical 0-1 Knapsack Problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We show that this recently introduced variant of the Knapsack Problem is weakly NP-hard and present a fully polynomial-time approximation scheme (FPTAS) for the Problem. Moreover, we analyze the approximation quality achieved by a natural extension of the classical greedy procedure to the product Knapsack Problem.
-
the multidimensional Knapsack Problem structure and algorithms
Informs Journal on Computing, 2010Co-Authors: Jakob Puchinger, Gunther R Raidl, Ulrich PferschyAbstract:We study the multidimensional Knapsack Problem, present some theoretical and empirical results about its structure, and evaluate different integer linear programming (ILP)-based, metaheuristic, and collaborative approaches for it. We start by considering the distances between optimal solutions to the LP relaxation and the original Problem and then introduce a new core concept for the multidimensional Knapsack Problem (MKP), which we study extensively. The empirical analysis is then used to develop new concepts for solving the MKP using ILP-based and memetic algorithms. Different collaborative combinations of the presented methods are discussed and evaluated. Further computational experiments with longer run times are also performed to compare the solutions of our approaches to the best-known solutions of another so-far leading approach for common MKP benchmark instances. The extensive computational experiments show the effectiveness of the proposed methods, which yield highly competitive results in significantly shorter run times than do previously described approaches.
-
the Knapsack Problem with conflict graphs
Journal of Graph Algorithms and Applications, 2009Co-Authors: Ulrich Pferschy, Joachim SchauerAbstract:We extend the classical 0-1 Knapsack Problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the Knapsack. These constraints are represented by edges of a conict graph whose vertices correspond to the items of the Knapsack Problem. Similar conditions were treated in the literature for bin packing and scheduling Problems. For the Knapsack Problem with conict graphs, exact and heuristic algorithms were proposed in the past. While the Problem is strongly NP-hard in general, we present pseudopolynomial algorithms for two special graph classes, namely graphs of bounded treewidth (including trees and series-parallel graphs) and chordal graphs. From these algorithms we can easily derive fully polynomial time approximation schemes (FPTAS).
Bala Shetty - One of the best experts on this subject based on the ideXlab platform.
-
the nonlinear Knapsack Problem algorithms and applications
European Journal of Operational Research, 2002Co-Authors: Kurt M Bretthauer, Bala ShettyAbstract:Abstract We present a survey of algorithms and applications for the nonlinear Knapsack Problem (or, the nonlinear resource allocation Problem). In its most general form, the nonlinear Knapsack Problem will be defined as a nonlinear optimization Problem with just one constraint, bounds on the variables, and, in some cases, a set of specially structured constraints such as generalized upper bounds (GUBs). This Problem is encountered either directly, or as a subProblem, in a variety of applications, including production planning, financial modeling, stratified sampling, and capacity planning in manufacturing, health care, and computer networks. By taking advantage of the special structure of the Problem, efficient solution methods can be developed. Problem classes addressed here include continuous and integer Problems, convex and nonconvex Problems, separable and nonseparable Problems, and Problems with additional specially structured constraints.
Clemens Thielen - One of the best experts on this subject based on the ideXlab platform.
-
The Product Knapsack Problem: Approximation and Complexity
arXiv: Optimization and Control, 2019Co-Authors: Ulrich Pferschy, Joachim Schauer, Clemens ThielenAbstract:We consider the product Knapsack Problem, which is the variant of the classical 0-1 Knapsack Problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We show that this recently introduced variant of the Knapsack Problem is weakly NP-hard and present a fully polynomial-time approximation scheme (FPTAS) for the Problem. Moreover, we analyze the approximation quality achieved by a natural extension of the classical greedy procedure to the product Knapsack Problem.
-
approximation schemes for the parametric Knapsack Problem
Information Processing Letters, 2017Co-Authors: Alberto Giudici, Stefan Ruzika, Pascal Halffmann, Clemens ThielenAbstract:Abstract We consider the (linear) parametric 0–1 Knapsack Problem in which the profits of the items are affine-linear functions of a real-valued parameter and the task is to compute a solution for all values of the parameter. For this Problem, it is known that the piecewise linear convex function mapping the parameter to the optimal objective value of the corresponding instance (called the optimal value function) can have exponentially many breakpoints (points of slope change), which implies that every optimal algorithm for the Problem must output a number of solutions that is exponential in the number of items. We provide the first (parametric) polynomial time approximation scheme (PTAS) for the parametric 0–1 Knapsack Problem. Moreover, we exploit the connection between the parametric Problem and the bicriteria Problem in order to show that the parametric 0–1 Knapsack Problem admits a parametric FPTAS when the parameter is restricted to the positive real line and the slopes and intercepts of the affine-linear profit functions of the items are nonnegative. The method used to obtain this result applies to many linear parametric optimization Problems and provides a general connection between bicriteria and linear parametric optimization Problems.
-
The online Knapsack Problem with incremental capacity
Mathematical Methods of Operations Research, 2015Co-Authors: Clemens Thielen, Morten Tiedemann, Stephan WestphalAbstract:Abstract We consider an online Knapsack Problem with incremental capacity. In each time period, a set of items, each with a specific weight and value, is revealed and, without knowledge of future items, it has to be decided which of these items to accept. Additionally, the Knapsack capacity is not fully available from the start but increases by a constant amount in each time period. The goal is to maximize the overall value of the accepted items. This setting extends the basic online Knapsack Problem by introducing a dynamic instead of a static Knapsack capacity and is applicable to classic Problems such as resource allocation or one-way trading. In contrast to the basic online Knapsack Problem, for which no competitive algorithms exist, the setting of incremental capacity facilitates the development of competitive algorithms for a bounded time horizon. We provide a competitive analysis of deterministic and randomized online algorithms for the online Knapsack Problem with incremental capacity and present lower bounds on the competitive ratio achievable by online algorithms for the Problem. Most of these lower bounds match the competitive ratios achieved by our online algorithms exactly or differ only by a constant factor.