For formulating Quadratic Knapsack Problems (QKPs) into the form of Quadratic Unconstrained Binary Optimization (QUBO), it is necessary to introduce an integer variable, which converts and incorporates the knapsack capacity constraint into the overall energy function. In QUBO, this integer variable is encoded with auxiliary binary variables, and the encoding method used for it affects the behavior of Simulated Annealing (SA) significantly. For improving the efficiency of SA for QKP instances, this paper first visualized and analyzed their annealing processes encoded by conventional binary and unary encoding methods. Based on this analysis, we proposed a novel hybrid encoding (HE), getting the best of both worlds. The proposed HE obtained feasible solutions in the evaluation, outperforming the others in small- and medium-scale models.

In the online removable knapsack problem, a sequence of items, each labeled with its value and its size, is given one by one. At each arrival of an item, a player has to decide whether to put it into a knapsack or to discard it. The player is also allowed to discard some of the items that are already in the knapsack. The objective is to maximize the total value of the knapsack. Iwama and Taketomi gave an optimal algorithm for the case where the value of each item is equal to its size. In this paper we consider a case with an additional constraint that the capacity of the knapsack is a positive integer N and that the sizes of items are all integral. For each positive integer N, we design an algorithm and prove its optimality. It is revealed that the competitive ratio is not monotonic with respect to N.

The binary quadratic knapsack problem (QKP) aims at optimizing a quadratic cost function within a single knapsack. Its applications and difficulty make it appealing for various industrial fields. In this paper we present an efficient strategy to solve the problem by modeling it as an Ising spin model using an Ising machine to search for its ground state which translates to the optimal solution of the problem. Secondly, in order to facilitate the search, we propose a novel technique to visualize the landscape of the search and demonstrate how difficult it is to solve QKP on an Ising machine. Finally, we propose two software solution improvement algorithms to efficiently solve QKP on an Ising machine.

Finding Pareto-optimal solutions is a basic approach in multi-objective combinatorial optimization. In this paper, we focus on the 0-1 multi-objective knapsack problem, and present an algorithm to enumerate all its Pareto-optimal solutions, which improves upon the method proposed by Bazgan et al. Our algorithm is based on dynamic programming techniques using an efficient data structure called zero-suppressed binary decision diagram (ZDD), which handles a set of combinations compactly. In our algorithm, we utilize ZDDs for storing all the feasible solutions compactly, and pruning inessential partial solutions as quickly as possible. As an output of the algorithm, we can obtain a useful ZDD indexing all the Pareto-optimal solutions. The results of our experiments show that our algorithm is faster than the previous method for various types of three- and four-objective instances, which are difficult problems to solve.

A new artificial fish swarm algorithm (AFSA) for solving the multiple knapsack problem (MKP) is introduced in this paper. In the proposed AFSA, artificial fish (AF) individuals are only allowed to search the region near constraint boundaries of the problem to be solved. For this purpose, several behaviors to be performed by AF individuals, including escaping behavior, randomly moving behavior, preying behavior and following behavior, were specially designed. Exhaustive experiments were implemented in order to investigate the proposed AFSA's performance. The results demonstrated the proposed AFSA has the ability of finding high-quality solutions with very fast speed, as compared with some other versions of AFSA based on different constraint-handling methods. This study is also meaningful for solving other constrained problems.

In this letter, we propose an improvement on a knapsack probabilistic encryption scheme [B. Wang, Q. Wu, Y. Hu, Information Sciences 177 (2007)], which was shown vulnerable to attacks due to Youssef [A.M. Youssef, Information Sciences 179 (2009)] and Lee [M.S. Lee, Information Sciences 222 (2013)], respectively. The modified encryption scheme is secure against Youssef's and Lee's attacks only at the costs of slightly compromising the efficiency of the original proposal.

The subset sum problem, which is often called as the knapsack problem, is known as an NP-hard problem, and there are several cryptosystems based on the problem. Assuming an oracle for shortest vector problem of lattice, the low-density attack algorithm by Lagarias and Odlyzko and its variants solve the subset sum problem efficiently, when the “density” of the given problem is smaller than some threshold. When we define the density in the context of knapsack-type cryptosystems, weights are usually assumed to be chosen uniformly at random from the same interval. In this paper, we focus on general subset sum problems, where this assumption may not hold. We assume that weights are chosen from different intervals, and make analysis of the effect on the success probability of above algorithms both theoretically and experimentally. Possible application of our result in the context of knapsack cryptosystems is the security analysis when we reduce the data size of public keys.

In this paper, we propose a hybrid fine-tuned multi-objective memetic algorithm hybridizing different solution fitness evaluation methods for global exploitation and exploration. To search across all regions in objective space, the algorithm uses a widely diversified set of weights at each generation, and employs a simulated annealing to optimize each utility function. For broader exploration, a grid-based technique is adopted to discover the missing nondominated regions on existing tradeoff surface, and a Pareto-based local perturbation is performed to reproduce incrementing solutions trying to fill up the discontinuous areas. Additional advanced feature is that the procedure is made dynamic and adaptive to the online optimization conditions based on a function of improvement ratio to obtain better stability and convergence of the algorithm. Effectiveness of our approach is shown by applying it to multi-objective 0/1 knapsack problem (MOKP).

This paper develops an algorithm based on the Modular Approach to solve singly constrained separable discrete optimization problems (Nonlinear Knapsack Problems). The Modular Approach uses fathoming and integration techniques repeatedly. The fathoming reduces the decision space of variables. The integration reduces the number of variables in the problem by combining several variables into one variable. Computational experiments for "hard" test problems with up to 1000 variables are provided. Each variable has up to 1000 integer values.

We discuss the security of the improved knapsack cryptosystem that Kobayashi and Kimura have proposed. Two attacking methods for their cryptosystem are proposed; one is the method for obtaining secret keys from public keys by using the continued fraction, and the other is for decrypting the ciphertext without knowing secret keys. We show that their cryptosystem is not secure against these attacks.

In this paper we present an algorithm to solve an as-yet untreated knapsack problem, the Multidimensional Multiple-choice Knapsack Problem (MMKP). Since our specific application occurs in the real-time domain, a solution for the MMKP with a small upper bound on the runtime is desirable. Thus, the Lagrange multiplier method is chosen, and a heuristic with a worst-case runtime behavior better than O(n2m) is developed, n being the number of elements and m the number of dimensions. Extensive testing against an exact algorithm based on partial enumeration is used to establish the accuracy and efficiency of the heuristic.

We propose an asymmetric neural network which can solve inequality-constrained combinatorial optimization problems that are difficult to solve using symmetric neural networks. In this article, a knapsack problem that is one of such the problem is solved using the proposed network. Additionally, we study condition for obtaining a valid solution. In computer simulations, we show that the condition is correct and that the proposed network produces better solutions than the simple greedy algorithm.