Search

• The 0-1 knapsack problem (KP01) is one of the classic variants of knapsack problems in which the aim is to select the items with the total profit to be in the knapsack. • In this paper, a comprehensive survey on the recent advances in 0-1 knapsack problem is presented. • Literature survey reveals some interesting challenges and future research directions. 0-1 knapsack problem (KP01) is one of the classic variants of knapsack problems in which the aim is to select the items with the total profit to be in the knapsack. In contrast, the constraint of the maximum capacity of the knapsack is satisfied. KP01 has many applications in real-world complex problems such as resource distribution, portfolio optimization, etc. This study reviews the basic theory and main algorithms of 0-1 knapsack, proposes many different types of nature-inspired metaheuristic algorithms, and divides existing 0-1 knapsack problems into 6 types according to the different coding methods of the algorithms, for a comprehensive overview of it. In this paper, a comprehensive survey on the recent advances in 0-1 knapsack problem is presented. Literature survey reveals some interesting challenges and future research directions. [ABSTRACT FROM AUTHOR]

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic 0.283 − o (1) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio. For the linear packing constraints with large widths, we provide a deterministic 1 / 6 − ϵ approximation algorithm. To the best of our knowledge, there is currently no deterministic approximation algorithm for the constraints. [ABSTRACT FROM AUTHOR]

We consider robust combinatorial optimization problems with cost uncertainty where the decision maker can prepare K solutions beforehand and chooses the best of them once the true cost is revealed. Also known as min–max–min robustness (a special case of K -adaptability), it is a viable alternative to otherwise intractable two-stage problems. The uncertainty set assumed in this paper considers that in any scenario, at most Γ of the components of the cost vectors will be higher than expected, which corresponds to the extreme points of the budgeted uncertainty set. While the classical min–max problem with budgeted uncertainty is essentially as easy as the underlying deterministic problem, it turns out that the min–max–min problem is NP - hard for many easy combinatorial optimization problems, and not approximable in general. We thus present an integer programming formulation for solving the problem through a row-and-column generation algorithm. While exact, this algorithm can only cope with small problems, so we present two additional heuristics leveraging the structure of budgeted uncertainty. We compare our row-and-column generation algorithm and our heuristics on min-knapsack and shortest path instances previously used in the scientific literature and find that the heuristics obtain good quality solutions in short computational times. [ABSTRACT FROM AUTHOR]