Search

PASS Encrypt is a lattice-based public key encryption scheme introduced by Hoffstein and Silverman (Des Codes Cryptogr 77(2–3):541–552, 2015). The efficiency and algebraic properties of PASS Encrypt and of the underlying partial Vandermonde knapsack problem ( PV - Knap ) make them an attractive starting point for building efficient post-quantum cryptographic primitives. Recall that PV - Knap asks to recover a polynomial of small norm from a partial list of its Vandermonde transform. Unfortunately, the security foundations of PV - Knap -based encryption are not well understood, and in particular, no security proof for PASS Encrypt is known. In this work, we make progress in this direction. First, we present a modified version of PASS Encrypt with a security proof based on decision PV - Knap and a leaky variant of it, named the PASS problem. We next study an alternative approach to build encryption based on PV - Knap . To this end, we introduce the partial Vandermonde LWE problem ( PV - LWE ), which we show is computationally equivalent to PV - Knap . Following Regev's design for LWE -based encryption, we use PV - LWE to construct an efficient encryption scheme. Its security is based on PV - LWE and a hybrid variant of PV - Knap and Polynomial LWE . Finally, we give a refined analysis of the concrete security of both schemes against best known lattice attacks. [ABSTRACT FROM AUTHOR]

The Knapsack Sharing Problem (KSP) is the problem of assigning a subset of n items from m disjoint classes to a shared knapsack such that the total profit of the smallest class is maximized subject to the knapsack capacity constraint. The KSP problem generalizes the 0/1 Knapsack Problem (KP), and it has wide applications in finance and resource allocation domains. In this article, we describe a new Dichotomous-based exact algorithm, called Sharknap, to solve large knapsack sharing problems. Sharknap solves the KSP problem by decomposition and dichotomous reduction like all existing Dichotomous-based algorithms. The decomposition phase splits each KSP instance into a series of KP problems to be solved using an exact KP solver. The dichotomous reduction phase reduces the weight of each considered class. We introduce the concept of critical class to bound the number of calls to the KP solver and to speed up the search algorithm. Experimental results on standard benchmarks from the literature as well as on randomly generated instances show that Sharknap significantly outperforms all existing exact algorithms. Interestingly, the new algorithm is able to solve large instances with up to 100000 items and 1000 classes within less than one second in many times. [ABSTRACT FROM AUTHOR]

• MCKS instances are efficiently solved using Gurobi. • Gurobi generated guaranteed near-optimum by using a sequential strategy. • Gurobi results for the MCKS are proven competitive using statistics. • 31 MCKS instances solved by the IILP-H algorithm violate Gurobi upper bounds. An interesting extension of the classic Knapsack Problem (KP) is the Multiple-Choice Knapsack Problem with Setups (MCKS) which is focused on solving practical applications that involve both multiple periods and setups. Sophisticated solution methods for the MCKS that are presented in the operations research (OR) literature are not readily available for use by OR practitioners. Using MCKS test instances that appear in the literature, we demonstrate that the general-purpose integer programming software Gurobi sometimes used in an iterative manner can efficiently solve these MCKS instances using all default parameter values on a standard PC. It is shown both empirically and statistically that these Gurobi solutions are competitive with solution approaches from the literature. Hence, our approach using Gurobi is both easy for the OR practitioner to use and gives results competitive with the best specialized MCKS solution methods in the literature without the need to generate algorithm-specific code. Furthermore, this paper presents significant concerns regarding the solutions stated in the literature by the approximate solution method that reports the best results on 120 MCKS test instances. Specifically, 26% of this method's solutions violate Gurobi upper bounds and an additional 33% of its solutions, on average, exceed the known guaranteed optimums by a value of 12,510. [ABSTRACT FROM AUTHOR]

The 0–1, Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computation with the exact algorithm to solve the 0–1 MKP. It maintains a set of solutions and utilizes the information from the population to extract good partial assignments. To find high-quality solutions, an exact algorithm is applied to explore the promising search space specified by the good partial assignments. The new solutions are used to update the population. Thus, the good partial assignments evolve towards a better direction with the improvement of the population. Extensive experimentation with commonly used benchmark sets shows that our algorithm outperforms the state-of-the-art heuristic algorithms, TPTEA and DQPSO , as well as the commercial solver CPlex. It finds better solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances. • We propose an efficient and practical algorithm for solving the 0–1 Multidimensional Knapsack Problem in this paper. • The algorithm takes advantages of Evolutionary Computation and Large Neighborhood Search. • It works well in solving the large and hard 0–1 MKP instances. • We provide new lower bounds (best known results) for 10 large and hard instances from the commonly used benchmark set. [ABSTRACT FROM AUTHOR]

The Set-Union Knapsack Problem (SUKP) is a complex combinatorial optimisation problem with applications in resource allocation, portfolio selection, and logistics. This paper presents a parallel local search algorithm for solving SUKP on the Compute Unified Device Architecture (CUDA) platform in Graphics Processing Units (GPUs). The proposed method employs a compact algorithm that divides the search space into smaller regions. For diversity, each thread in a GPU block starts the search process from a different location in a region using a different initial solution. Each thread then searches the local optimum by utilising communication between individuals through a crossover operator exploiting the best solution within the GPU block. Through extensive experiments on a set of SUKP benchmark instances ranging in size from small to large, we demonstrate the effectiveness of the proposed algorithm in finding high-quality solutions within comparable time frames. Furthermore, a comparative performance analysis with the current state-of-the-art SUKP algorithms reveals the competitive advantage of the proposed method. The GPU-based parallel local search algorithm using uniform crossover is a valuable addition to the repertoire of algorithms addressing SUKP, highlighting its potential for practical applications in real-world decision-making scenarios. [ABSTRACT FROM AUTHOR]

We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0–1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments for 99% of the instances reported in the literature. On many of the harder instances, our algorithm is orders of magnitude faster, which enabled it to solve 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program solves a relaxation of the problem from bilevel to 2n-level where the items are processed in an online fashion. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems. [ABSTRACT FROM AUTHOR]

This study proposes an end-to-end multiobjective reinforcement learning (MORL) approach to solve the biobjective traveling thief problems (TTP). A TTP involves a thief visiting cities and selecting items to maximize profit while minimizing travel time within a knapsack's capacity. The study evaluates combinations of two architectures, namely the pointer network (PN) and attention mechanism (AM), with three MORL methods: deep reinforcement learning multiobjective algorithm (DRLMOA), multi-sample Pareto hypernetwork (PHN), and manifold-based policy search (MBPS). However, PN and AM cannot be directly used to predict two different sequences simultaneously: the city tour and the item selection. Therefore, a solution encoding and decoding scheme is proposed to solve TTP without substantially modifying PN and AM. The methods are trained on only small randomly generated problem instances based on Eil76 instances, and their performance is evaluated on various problem instances. The state-of-the-art non-dominated sorting-based customized random-key genetic algorithm (NDS-BRKGA) serves as the baseline. The experimental study demonstrates a competitive performance of the proposed methods compared to the baseline, particularly in instances with a high number of items. The proposed methods, especially PN-DRLMOA and AM-DRLMOA, also show promising generalization capabilities on different and larger graphs. Lastly, the proposed MORL methods significantly outperform NDS-BRKGA in terms of the solution generation running time. • A multiobjective RL approach is proposed for the biobjective traveling thief problem. • Combinations of three multiobjective RL methods and two architectures are proposed. • An analysis of the preference-based multiobjective RL methods is conducted. • The methods show promising performance and generalizability compared to NDS-BRKGA. • The proposed methods are compared based on solution quality and training time. [ABSTRACT FROM AUTHOR]

Portfolio optimization is one of the most important issues in financial markets. In this regard, the more realistic are assumptions and conditions of modelling to portfolio optimization into financial markets, the more reliable results will be obtained. This paper studies the knapsack-based portfolio optimization problem that involves discrete variables. This model has two very important features; achieving the optimal number of shares as an integer and with masterly efficiency in portfolio optimization for high priced stocks. These features have added some real aspects of financial markets to the model and distinguish them from other previous models. Our contribution is that we present an algorithm based on dynamic programming to solve the portfolio selection model based on the knapsack problem, which is in contrast to the existing literature. Then, to show the applicability and validity of the proposed dynamic programming algorithm, two case studies of the US stock exchange are analyzed. [ABSTRACT FROM AUTHOR]

We study the K -item knapsack problem (i.e. , 1.5-dimensional knapsack problem), a generalization of the famous 0–1 knapsack problem (i.e. , 1-dimensional knapsack problem) in which an upper bound K is imposed on the number of items selected. This problem is of fundamental importance and is known to have a broad range of applications in various fields. It is well known that, there is no fully polynomial time approximation scheme (FPTAS) for the d -dimensional knapsack problem when d ≥ 2 , unless P = NP. While the K -item knapsack problem is known to admit an FPTAS, the complexity of all existing FPTASs has a high dependency on the cardinality bound K and approximation error ɛ , which could result in inefficiencies especially when K and ɛ − 1 increase. The current best results are due to Mastrolilli and Hutter (2006), in which two schemes are presented exhibiting a space–time tradeoff-one scheme with time complexity O (n + K z 2 / ɛ 2) and space complexity O (n + z 3 / ɛ) , and another scheme that requires a run-time of O (n + (K z 2 + z 4) / ɛ 2) but only needs O (n + z 2 / ɛ) space, where z = min { K , 1 / ɛ }. In this paper we close the space–time tradeoff exhibited in Mastrolilli and Hutter (2006) by designing a new FPTAS with a running time of O ˜ (n + z 2 / ɛ 2) , while simultaneously reaching a space complexity 1 1 O ˜ notation hides terms poly-logarithmic in n and 1 / ɛ. of O (n + z 2 / ɛ). Our scheme provides O ˜ (K) and O (z) improvements on the state-of-the-art algorithms in time and space complexity respectively, and is the first scheme that achieves a running time that is independent of the cardinality bound K (up to logarithmic factors) under fixed ɛ. Another salient feature of our algorithm is that it is the first FPTAS that achieves better time and space complexity bounds than the very first standard FPTAS over all parameter regimes. [ABSTRACT FROM AUTHOR]

This work aims to improve the GPU performance for solving the 0/1 knapsack problem, which is a well-known combinatorial optimization problem found in many practical applications, including cryptography, financial decision, electronic design automation, computing resource management, etc. The knapsack problem is NP-hard, but it can be solved efficiently by dynamic programming (DP) algorithms in pseudo-polynomial runtime. The DP knapsack algorithm on GPUs has been presented. However, as the modern GPU architecture provides much higher computing throughput than its memory bandwidth, previous work is bounded by the data access time on GPU memory because its CGMA (Compute to Global Memory Access) ratio is 1, which means every computing operation involves one memory access on average. To address the problem, an innovative approach called Multi-Class 0/1 Knapsack Problem (MCKP), whose items can be classified into groups with equal values or weights is proposed in this paper. By reconstructing the DP equations for solving MCKP, it is able to explore data parallelism and reusability across threads. This made it possible to optimize the computation across iterations (i.e., items), and significantly improve the CGMA ratio by 5-fold after exploring the use of GPU shared memory and registers for reused data. We extensively analyze the performance of our approach on two modern GPU models, NVIDIA Tesla V100 and RTX 3070. Compared to the runtime of previous work, our approach achieves up to 8x and 18x speedup on V100 and RTX 3070 respectively, the latter one being a GPU with lower memory bandwidth. In addition, by comparing the two speedups, we found that we are able to achieve more efficient computing usage when the memory bandwidth is limited such as RTX 3070. [ABSTRACT FROM AUTHOR]

Fuzzy high average-utility itemset (FHAUI) mining problem considers the effect of the length of the itemsets on their calculated utilities, in addition to the number of occurrences of each item in each transaction and the unit profit of each item as the internal and external utility of that item, respectively. FHAUI mining avoids generating large fuzzy high utility itemsets which consist of fuzzy low utility items. The fuzzy theory has been combined with the high average-utility itemset mining problem in order to better understanding the users' results and provide more useful information, such as determining the overlapping range of the set of discovered items. In this paper, by extending MHAI method (Yun and Kim in Future Gener Comp Syst 68:346–36, 2017) for fuzzy itemset using the fuzzy approach of (Lan et al. in Appl Soft Comput 30:767–777, 2015), a method called HiFAM is presented for efficient exploration of FHAUIs. The algorithm introduces a fuzzy average-utility list (FAUL) structure, by extending HAI-list from Yun and Kim (Future Gener Comp Syst 68:346–36, 2017), to summarize required information of the dataset in a compact form to explore the FHAUIs without candidate generation. After creating the FAUL of the items (1-itemsets), there is no need to re-scan the database in the proposed algorithm, and all the FAULs of the (k + 1)-itemsets can be obtained from the combination of the FAULs of k-itemsets and (k − 1)-itemsets. The complete set of all FHAUIs can be extracted by HiFAM, through a depth first exploration process. A pruning technique is also used in the proposed method to prevent the exploration of unpromising itemsets; their exploration does not lead to discover FHAUIs. This pruning strategy effectively reduces the memory consumption and time complexity of the proposed method. Various experiments are conducted using real and synthetic datasets, the results of which show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variant of adaptive robust combinatorial optimization problems where the decision maker can prepare K solutions and choose the best among them upon knowledge of the true data realizations. We suppose that the uncertainty may affect the objective and the constraints through functions that are not necessarily linear. We propose a new exact algorithm for solving these problems when the feasible set of the nominal optimization problem does not contain too many good solutions. Our algorithm enumerates these good solutions, generates dynamically a set of scenarios from the uncertainty set, and assigns the solutions to the generated scenarios using a vertex p-center formulation, solved by a binary search algorithm. Our numerical results on adaptive shortest path and knapsack with conflicts problems show that our algorithm compares favorably with the methods proposed in the literature. We additionally propose a heuristic extension of our method to handle problems where it is prohibitive to enumerate all good solutions. This heuristic is shown to provide good solutions within a reasonable solution time limit on the adaptive knapsack with conflicts problem. Finally, we illustrate how our approach handles nonlinear functions on an all-or-nothing subset problem taken from the literature. Summary of Contribution: Our paper describes a new exact algorithm for solving adaptive robust combinatorial optimization problems when the feasible set of the nominal optimization problems does not contain too many good solutions. Its development relies on a progressive relaxation of the problem augmented with a row-and-column generation technique. Its efficient execution requires a reformulation of this progressive relaxation, coupled with dominance rules and a binary search algorithm. The proposed algorithm is amenable to exploiting the special structures of the problems considered as illustrated with various applications throughout the paper. A practical view is provided by the proposition of a heuristic variant. Our computational experiments show that our proposed exact solution method outperforms the existing methodologies and therefore pushes the computational envelope for the class of problems considered. [ABSTRACT FROM AUTHOR]

A generating function technique for solving integer programs via the evaluation of complex path integrals is discussed from a theoretical and computational perspective. Applying the method to knapsack feasibility problems, it is demonstrated how the presented numerical integration algorithm benefits from a preoptimized path of integration. After discussing the algorithmic setup in detail, a numerical study is implemented to evaluate the computational performance of the preoptimized integration method, and the algorithmic parameters are tuned to a set of knapsack instances. The goal is to highlight the method's computational advantage for hard knapsack instances. Summary of Contribution: A method for evaluating the feasibility of knapsack problems is discussed and connected to the existing theory on generating function techniques for computational integer optimization. Specifically, the number of solutions to knapsack instances is computed using numerical quadrature of complex path integrals. The choice of the path of integration is identified as an important degree of freedom, and it is shown that preoptimizing the path improves the computational performance for hard instances significantly. The scope of this work is to give a self-contained presentation of the mathematical theory, introduce and discuss path optimization as a presolving routine, and demonstrate the computational performance of the overall approach with the help of a detailed numerical study. The main goal is to highlight the computational advantage of the new algorithm for hard knapsack instances. [ABSTRACT FROM AUTHOR]

In order to use Harris hawks optimization ( HHO) to solve KPC, this paper proposed a new discrete Harris hawks optimization ( DisHHO ) algorithm. DisHHO encoded individual based on 0-1 vector and established the discrete evolution equations by bitwise operation. Furthermore, it used an adaptive mutation mechanism to improve the search performance. For verifying the performance of DisHHO in solving KPC, it was used to solve four kinds of large -scale KPC instances. The comparison with the existing binary HHO and state-of-the-art algorithms for solving KPC show that DisHHO not only has excellent average calculation results, but also has fast calculation speed. Hence, DisHHO is a new and efficient algorithm for solving KPC. [ABSTRACT FROM AUTHOR]

As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in cloud computing and introduced by Chen et al. [3] recently. A set of two-stage jobs are selected and scheduled on parallel two-stage flowshops to achieve the maximum total profit while maintaining the given makespan constraint. We give a positive answer to an open question about its approximability proposed by Chen et al. [3]. More specifically, based on guessing strategies and rounding techniques for linear programs, we present a polynomial time approximation scheme (PTAS) for the case when the number of flowshops is a fixed constant. As the case with two flowshops is already strongly NP-hard, our PTAS achieves the best possible approximation ratio. [ABSTRACT FROM AUTHOR]

In this paper, we consider the k -submodular secretary problem, in which the items or secretaries arrive one by one in a uniformly random order, and the goal is to select k disjoint sets of items, so as to maximize the expectation of a monotone non-negative k -submodular function. A decision for each item must be made immediately and irrevocably after its arrival: accept and assign it to one of the k dimensions, or reject it. We first show that, in the unconstrained setting, there is an offline algorithm that can be transformed to a k 2 k − 1 -competitive online algorithm, which is asymptotically the best possible. For the problem with cardinality constraints, we present online algorithms with provable performance guarantees for the total size constraint and individual size constraint settings that depend on the corresponding budget parameters. For the problem under a knapsack constraint, we provide a constant-competitive online algorithm. [ABSTRACT FROM AUTHOR]

• We study the catalytic computational model when the pure space is much smaller than logarithmic in catalytic space. • We showed that the Knapsack problem can be solved catalytically with much lesser pure space. • We introduced the catalytic regular class CR, where pure space used is a constant and showed its power and limitations. This paper explores the power of catalytic computation when the catalytic space (c (n) , the full memory whose content needs to be restored to the original by the end of computation) is much more than exponential in the pure space (s (n) , the empty memory which does not have any access/restoration constraints). We study the following three regimes of the relation between s (n) and c (n) and explore the class CSPACE (s (n) , c (n)) in each of them. • High-end regime - s (n) = O (c (n) ϵ) : We show an implementation of incremental dynamic program using catalytic machines, thus showing that Knapsack problem (with n items, sum of their costs as C and the capacity of the bag as K) can be solved in O (n log ⁡ n log ⁡ C + log ⁡ (n K C)) pure space and O (n 2 K C 3 log 2 ⁡ K log ⁡ n) catalytic space. Hence, catalytic algorithms can lead to a non-trivial saving in the pure space required for computation when K is Ω (n 2). • Low-end regime - s (n) = O (1) : We define the classes CR and CNR (nondeterministic variant of CR) where s (n) = O (1) and c (n) = poly (n). Exploring the connection between computational power of one counter machines (OC) and constant pure space catalytic Turing machines, we observe that OC ⊆ CR and show that CR ⊆ OC ⇒ CR ≠ CNR. We prove that L ⊈ CSPACE (O (1) , o (n)). We also study the effect of adding additional read-only tapes to the model and show that: For any k ∈ N , (k + 1) - CSPACE (O (1) , O (n c)) ⊆ CSPACE (k log ⁡ n , n c) ⊆ (4 k + 1) - CSPACE (O (1) , O (n c)). • Low-end non-constant regime - s (n) = o (log ⁡ log ⁡ n) : Let M be an oblivious catalytic Turing machine using s (n) pure space and c (n) catalytic space such that s (n) + log ⁡ c (n) = o (log ⁡ log ⁡ n) then L (M) is regular. This strengthens the classical theorem on s (n) = o (log ⁡ log ⁡ n) to the case of catalytic Turing machines. Our techniques include interesting generalizations of crossing sequence arguments and implementations of incremental dynamic programs using catalytic algorithms. These may be of independent interest. [ABSTRACT FROM AUTHOR]

• Research was motivated from recent research in cloud computing. • A new model for research on scheduling of multiple processors. • Computational complexity of the proposed scheduling problems. • Approximation algorithms for the proposed scheduling problems. • Relationship between the proposed scheduling problems and multiple knapsack packing. Recently, motivated by applications in cloud computing, scheduling multiple two-stage flowshops with the objective of minimizing the makespan has drawn increasing attention. Motivated by the same applications, the current paper studies the problem of scheduling multiple two-stage flowshops with a deadline, with the objective of maximizing the profit of the jobs that can be completed by the deadline. Algorithms and complexity of the problem are investigated. For the case where the number of two-stage flowshops is part of the input, we present an efficient approximation algorithm with a constant ratio. The approximation ratio is improved via a study of the relationship between the problem and the multiple knapsack problem, combined with the recent progresses in the research in approximation algorithms for the multiple knapsack problem. By integrating techniques in the study of the classical Knapsack problem and the classical Makespan problem on multiple processors, plus additional new techniques, a polynomial-time approximation algorithm with a further improved approximation ratio is developed for the case where the number of flowshops is a fixed constant. [ABSTRACT FROM AUTHOR]

In this article, we consider a network of agents that has to self-assign a set of tasks while respecting resource constraints. One possible formulation is the generalized assignment problem, where the goal is to find a maximum payoff while satisfying capability constraints. We propose a purely distributed branch-and-price algorithm to solve this problem in a cooperative fashion. Inspired by classical (centralized) branch-and-price schemes, in the proposed algorithm, each agent locally solves small linear programs, generates columns by solving simple knapsack problems, and communicates to its neighbors a fixed number of basic columns. We prove finite-time convergence of the algorithm to an optimal solution of the problem. Then, we apply the proposed scheme to a generalized assignment scenario, in which a team of robots has to serve a set of tasks. We implement the proposed algorithm in a Robot Operating System testbed and provide experiments for a team of heterogeneous robots solving the assignment problem. [ABSTRACT FROM AUTHOR]

Many systems have to be maintained while the underlying constraints, costs and/or profits change over time. Although the state of a system may evolve during time, a non-negligible transition cost is incurred for transitioning from one state to another. In order to model such situations, we look at a recently introduced multistage model where the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) that are both (i) near optimal for each time step and (ii) as stable as possible. We propose a PTAS for the Multistage Knapsack problem. This is the first approximation scheme for a combinatorial optimization problem in the considered multistage setting, and its existence contrasts with the inapproximability results for other combinatorial optimization problems that are even polynomial-time solvable in the static case. [ABSTRACT FROM AUTHOR]

The discounted {0-1} knapsack problem (D{0-1}KP) is a multi-constrained optimization and an extended form of the 0-1 knapsack problem. The DKP is composed of a set of item batches where each batch has three items and the objective is to maximize profit by selecting at most one item from each batch. Therefore, the D{0-1}KP is complex and has found many applications in real economic problems and other areas where the concept of promotional discounts exists. As DKP belongs to a binary class problem, so the novel binary particle swarm optimization variant with modifications is proposed in this paper. The acceleration coefficients are important parameters of the particle swarm optimization algorithm that keep the balance between exploration and exploitation. In conventional binary particle swarm optimization (BPSO), the acceleration coefficients of each particle remain the same in iteration, whereas in the proposed variant, fitness-based acceleration coefficient binary particle swarm optimization (FACBPSO), values of acceleration coefficients are based on the fitness of each particle. This modification enforces the least fit particles to move fast and best fit accordingly, which accelerates the convergence speed and reduces the computing time. Experiments were conducted on four instances of DKP having 10 datasets of each instance and the results of FACBPSO were compared with conventional BPSO and the new exact algorithm using a greedy repair strategy. The results demonstrate that the proposed algorithm outperforms PSO-GRDKP and the new exact algorithm in solving four instances of D{0-1}KP, with improved convergence speed and feasible solution time. [ABSTRACT FROM AUTHOR]

Vegetable retailing system in rural market is an interesting field of research. Vegetable retailing system refers to the supply or sell of vegetables to people or customers after collecting the vegetables directly from cultivators or farmers. In this article, we have proposed a special 0-1 Knapsack Problem (KP) for vegetable sellers in the rural market. The proposed Knapsack Problem is termed "special" because there is a limitation on the selection of objects. In the proposed 0-1 KP, a predetermined set of objects must be consumed or retailed among all available objects. This constraint has been considered by observing some practical phenomena in rural vegetable markets. We have noticed that some vegetables are used for retail in the daily market, those are essential in our everyday life. For example, we can mention green chilli, onions, etc. Sometimes the predetermined vegetables are not profitable but still retailed by the seller. The model has been solved by an Ant Colony Optimization (ACO) based approach in a fuzzy environment. The novelty of the proposed ACO is the random initialization of pheromones. We have considered the weight, profit, and total weight capacity of consumed vegetables as triangular fuzzy numbers in nature. We have applied two defuzzification techniques, namely Center of Area (COA) and Fuzzy Weighted Average (FWA), respectively, to defuzzify the objective of the proposed problem. We have solved a few benchmark instances from the library for performance testing of the ACO and then redefined the instances for our proposed model of the Knapsack Problem under fuzziness. Computational results with different input data sets are presented in the experimental section. [ABSTRACT FROM AUTHOR]

In a multi-tenant cloud, cloud vendors provide services (e.g., elastic load-balancing, virtual private networks) on service nodes for tenants. Thus, the mapping of tenants’ traffic and service nodes is an important issue in multi-tenant clouds. In practice, unreliability of service nodes and uncertainty/dynamics of tenants’ traffic are two critical challenges that affect the tenants’ QoS. However, previous works often ignore the impact of these two challenges, leading to poor system robustness when encountering system accidents. To bridge the gap, this paper studies the problem of robust service mapping in multi-tenant clouds (RSMP). Due to traffic dynamics, we take a two-step approach: service node assignment and tenant traffic scheduling. For service node assignment, we prove its NP-Hardness and analyze its problem difficulty. Then, we propose an efficient algorithm with bounded approximation factors based on randomized rounding and knapsack. For tenant traffic scheduling, we design an approximation algorithm based on fully polynomial time approximation scheme (FPTAS). The proposed algorithm achieves the approximation factor of 2+ $\epsilon $ , where $\epsilon $ is an arbitrarily small value. Both small-scale experimental results and large-scale simulation results show the superior performance of our proposed algorithms compared with other alternatives. [ABSTRACT FROM AUTHOR]

Knapsack problem with a single continuous variable (KPC) is a natural generalization of the standard 0-1 knapsack problem. In KPC, the capacity of the knapsack is not fixed, so it becomes more difficult to solve. In order to overcome the shortcoming that the performance of existing differential evolution (DE) algorithm is not good enough on highdimensional KPC instances, this paper proposes Lamarckian evolution-based DE (LEDE) algorithm to solve KPC. The improvement generated by the greedy repair and optimization operator is inherited to the offspring, which can speed up the convergence speed of DE algorithm and improve the precision of DE algorithm on high-dimensional KPC instances. At the same time, a profit-based greedy optimization strategy is introduced in the greedy repair and optimization operator to optimize the feasible solution generated by greedy repair strategy based on profit weight ratio, so as to help the algorithm jump out of local optimum. The LEDE algorithm is experimentally analyzed on 40 KPC instances. The experimental results show that the Lamarckian evolution and the profit-based greedy optimization strategy can improve the exploitation ability of LEDE algorithm, and LEDE algorithm is better than other intelligent optimization algorithms in terms of obtaining the best solution and the mean solution. [ABSTRACT FROM AUTHOR]

Many optimization algorithms have been applied to solve high-dimensional instances of the 0-1 knapsack problem. However, these algorithms often fall into a local optimization trap and thus fail to obtain the global optimal solutions. To circumvent this shortcoming, a hybrid harmony search algorithm with distribution estimation is proposed in this paper. A few important features of the proposed algorithm are as follows: (i) the idea of probability distribution estimation is employed to design the adaptive search strategy, (ii) a fixed improvisation process is presented to improve the algorithm searching ability, (iii) a new method of initialization is used to ensure that the initialization is feasible harmony and (iv) an improved remediation approach is proposed to effectively repair the infeasible solutions. To assess the effectiveness of the proposed algorithm, some experiments are carried out. The experimental results reveal that the proposed algorithm is a reliable and promising alternative for solving the 0-1 knapsack problem. [ABSTRACT FROM AUTHOR]

Human Learning Optimization (HLO) is a simple yet highly efficient metaheuristic developed based on a simplified human learning model. To further extend the research of HLO, the social reasoning learning operator (SRLO) is introduced. However, the learning ability of social imitating learning operator (SILO) and SRLO is constant in the process of iterations, which is not true in a real human population as humans often adopt dynamic learning strategies to solve the problem. Inspired by this fact, an improved adaptive human learning optimization algorithm with reasoning learning (AHLORL) is proposed to enhance the global search ability, in which an adaptive ps strategy is carefully designed to sufficiently motivate the roles of SILO and SRLO and dynamically adjust the learning efficiency of the algorithm at different stages of iterations. Then, a comprehensive parameter study is performed to explain why the proposed adaptive strategy can exploit the optimization ability of SILO and SRLO effectively. Finally, the AHLORL is applied to solve the CEC 15 benchmark functions as well as multidimensional knapsack problems (MKPs), and its performance is compared with the previous HLO variants as well as the other recent metaheuristics. The experimental results show that the proposed AHLORL outperforms the other algorithms in terms of search accuracy and scalability. [ABSTRACT FROM AUTHOR]

An important generalization of the classic 0-1 knapsack problem is the multi-demand multidimensional knapsack problem (MDMKP). In addition to being theoretically difficult to solve (it is NP-hard), it can be in practice difficult to solve because of its conflicting knapsack and demand constraints. Since there are significant large-scale applications of the MDMKP, approximate solution approaches are commonly used to solve these problems. However, using 1620 MDMKPs discussed in the literature, this article demonstrates which types of large MDMKPs can be solved efficiently by operations research practitioners using general purpose integer programming software on a standard personal computer within 0.1% of optimum. Statistical analyses are used to determine which problem parameters significantly impact solution time. Finally, based on these 1620 MDMKP instances, a classification tree is generated. This tree can be used to guide practitioners in solving MDMKPs that arise in business and industry. [ABSTRACT FROM AUTHOR]

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern-day applications can render existing algorithms prohibitively slow. Moreover, frequently those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a 5.83-approximation and runs in O(n log n) time, i.e., at least a factor n faster than other state-of-the-art algorithms. The versatility of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a (9 + ε)-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data. [ABSTRACT FROM AUTHOR]

We study two NP-complete graph partition problems, k-equipartition problems and graph partition problems with knapsack constraints (GPKC). We introduce tight SDP relaxations with nonnegativity constraints to get lower bounds, the SDP relaxations are solved by an extended alternating direction method of multipliers (ADMM). In this way, we obtain high quality lower bounds for k-equipartition on large instances up to n = 1000 vertices within as few as 5 min and for GPKC problems up to n = 500 vertices within as little as 1 h. On the other hand, interior point methods fail to solve instances from n = 300 due to memory requirements. We also design heuristics to generate upper bounds from the SDP solutions, giving us tighter upper bounds than other methods proposed in the literature with low computational expense. [ABSTRACT FROM AUTHOR]

This paper addresses a single item two-level supply chain inventory model considering deterioration during carrying of deteriorating item from a supplier's warehouse to a retailer's warehouse as well as deterioration in the retailer's warehouse. The model assumes preservation technology in the retailer's warehouse to prevent the rate of deterioration. An upper limit for the preservation technology investment has been set as a constraint to the model. The model maximizes the retailer's profit per unit time, simultaneously calculated optimal order quantity. A price dependent demand and storage-time dependent holding cost is considered to develop the model. Some theorems are proven to get optimal values of the total cost. A numerical problem is workout as per the developed algorithm and with the help of MATLAB software to study the applicability of our theoretical results. [ABSTRACT FROM AUTHOR]

We present the Positional Knapsack Problem (PKP), show that it is NP-hard and admits a Fully Polynomial-Time Approximation Scheme (FPTAS). This problem is a variant of the classical Binary Knapsack Problem (KP) in which the contribution of an item to the objective function varies according to the position in which it is added. The change in the valuation adds new properties to the problem that do not hold for KP as PKP is not a generalization of KP. Our FPTAS is based on a dynamic programming algorithm and uses a recursive rounding approach, which is necessary since the objective function depends on each item's value and position. [ABSTRACT FROM AUTHOR]

In the paper by Jovanovic et al. [[11]], the authors propose a hybrid ML and swarm intelligence approach to address credit card fraud detection. 10.3390/math10081232 11 Jovanovic D., Antonijevic M., Stankovic M., Zivkovic M., Tanaskovic M., Bacanin N. Tuning Machine Learning Models Using a Group Search Firefly Algorithm for Credit Card Fraud Detection. Swarm and evolutionary computation (SEC) [[1]] is a broad and growing area of modern computer sciences, dealing with nature-inspired systems that are capable of displaying intelligent behaviour, thus optimising a vast range of challenging real-world scenarios that cannot be addressed via the direct application of purely theoretical exact approaches (e.g., [[2]]). [Extracted from the article]

Human Learning Optimization (HLO) is an efficient metaheuristic algorithm in which three learning operators, i.e., the random learning operator, the individual learning operator, and the social learning operator, are developed to search for optima by mimicking the learning behaviors of humans. In fact, people not only learn from global optimization but also learn from the best solution of other individuals in the real life, and the operators of Differential Evolution are updated based on the optima of other individuals. Inspired by these facts, this paper proposes two novel differential human learning optimization algorithms (DEHLOs), into which the Differential Evolution strategy is introduced to enhance the optimization ability of the algorithm. And the two optimization algorithms, based on improving the HLO from individual and population, are named DEHLO1 and DEHLO2, respectively. The multidimensional knapsack problems are adopted as benchmark problems to validate the performance of DEHLOs, and the results are compared with the standard HLO and Modified Binary Differential Evolution (MBDE) as well as other state-of-the-art metaheuristics. The experimental results demonstrate that the developed DEHLOs significantly outperform other algorithms and the DEHLO2 achieves the best overall performance on various problems. [ABSTRACT FROM AUTHOR]

Summary: Knapsack is a combinatorial optimization problem that involves a variety of resource allocation challenges. It is defined as non‐deterministic polynomial time (NP) hard and has a wide range of applications. Knapsack problem (KP) has been studied in applied mathematics and computer science for decades. Many algorithms that can be classified as exact or approximate solutions have been proposed. Under the category of exact solutions, algorithms such as branch‐and‐bound and dynamic programming and the approaches obtained by combining these algorithms can be classified. Due to the fact that exact solutions require a long processing time, many approximate methods have been introduced for knapsack solution. In this research, deep Q‐learning using models containing fully connected layers, attention, and transformer as function estimators were used to provide the solution for KP. We observed that deep Q‐networks, which continued their training by observing the reward signals provided by the knapsack environment we developed, optimized the total reward gained over time. The results showed that our approaches give near‐optimum solutions and work about 40 times faster than an exact algorithm using dynamic programming. [ABSTRACT FROM AUTHOR]

We consider multi-objective optimization problems where the decision maker (DM) has equity concerns. We assume that the preference model of the DM satisfies properties related to inequity-aversion, hence we focus on finding nondominated solutions in line with the properties of inequity-averse preferences, namely the equitably nondominated solutions. We discuss two algorithms for finding good subsets of equitably nondominated solutions. The first approach is an extension of an interactive approach developed for finding the most preferred nondominated solution when the utility function is assumed to be quasiconcave. We find the most preferred equitably nondominated solution when the utility function is assumed to be symmetric quasiconcave. In the second approach we generate an evenly distributed subset of the set of equitably nondominated solutions to be considered further by the DM. We show the computational feasibility of the two algorithms on equitable multi-objective knapsack problem, in which projects in different categories are to be funded subject to a limited budget. We perform experiments to show and discuss the performances of the algorithms. [ABSTRACT FROM AUTHOR]

While the classical knapsack problem has been the object to be solved by optimization algorithm proposals for many years, another version of this problem, discounted {0-1} knapsack problem, is gaining a lot of attention recently. The original knapsack problem requires selecting specific items from an item set to maximize the total benefit while ensuring that the total weight does not exceed the knapsack capacity. Meanwhile, discounted {0-1} knapsack problem has more stringent requirements in which items are divided into groups, and only up to one item from a particular group can be selected. This constraint, which does not exist in the original knapsack problem, makes discounted {0-1} knapsack problem even more challenging. In this paper, we propose a new algorithm based on salp swarm algorithm in the form of four different variants to resolve the discounted {0-1} knapsack problem. In addition, we also make use of an effective data modeling mechanism and a greedy repair operator that helps overcome local optima when finding the global optimal solution. Experimental and statistical results show that our algorithm is superior to currently available algorithms in terms of solution quality, convergence, and other statistical criteria. [ABSTRACT FROM AUTHOR]

We present PyQUBO, an open-source Python library for constructing quadratic unconstrained binary optimizations (QUBOs) from the objective functions and the constraints of optimization problems. PyQUBO enables users to prepare QUBOs or Ising models for various combinatorial optimization problems with ease thanks to the abstraction of expressions and the extensibility of the program. QUBOs and Ising models formulated using PyQUBO are solvable by Ising machines, including quantum annealing machines. We introduce the features of PyQUBO with applications in the number partitioning problem, knapsack problem, graph coloring problem, and integer factorization using a binary multiplier. Moreover, we demonstrate how PyQUBO can be applied to production-scale problems through integration with quantum annealing machines. Through its flexibility and ease of use, PyQUBO has the potential to make quantum annealing a more practical tool among researchers. [ABSTRACT FROM AUTHOR]

High utility itemset (HUI) mining is a powerful data mining technique to discover profitable patterns. The utility of an item is computed by using two measures named quantity and per-unit profit. All existing HUI mining algorithms consider a single value of external utility (per unit profit) for the entire database. However, the per-unit profit of items might fluctuate over time in many applications. This research introduces three novel strategies to comprise the external utilities of items as input for the HUI mining algorithm. Traditional HUI mining algorithms have been developed for the standalone system and do not fit for big data processing due to the limited computing resources (CPU, memory). Big data are efficiently processed on distributed frameworks like Apache Hadoop, Spark, etc. This paper introduces a distributed HUI mining algorithm named Spark-based Top-k high utility itemset (k-SHUI) miner. We also propose a fair load distribution strategy to divide the search space equally among the cluster nodes. The k-SHUI produces top-k HUIs without the requirement of the minimum utility threshold. We conducted extensive experiments on six real-life datasets to compare the proposed algorithm's performance with the existing algorithm. The experimental results demonstrate that the proposed algorithm outperforms the existing algorithms. [ABSTRACT FROM AUTHOR]

Machine Learning (ML) has gained much importance in recent years as many of its effective applications are involved in different fields, healthcare, banking, trading, gaming, etc. Similarly, Combinatorial Optimisation (CO) keeps challenging researchers by new problems with more complex constraints. Merging both fields opens new horizons for development in many areas. This study investigates how effective is to solve CO problems by ML methods. The work considers the Multidimensional Knapsack Problem (MKP) as a study case, which is an np-hard CO problem well-known for its multiple applications. The proposed approach suggests to use solutions of small-size MKP to build models with different ML methods; then, to apply the obtained models on large-size MKP to predict their solutions. The features consist of scores calculated based on information about items while the labels consist of decision variables of optimal solutions calculated from applying CPLEX Solver on small-size MKP. Supervised ML methods build models that help to predict structures of large-size MKP solutions and build them accordingly. A comparison of five ML methods is conducted on standard data set. The experiments showed that the tested methods were able to reach encouraging results. In addition, the study proposes a Genetic Algorithm (GA) that exploits ML outputs essentially in initialisation operator and to repair unfeasible solutions. The algorithm denoted GaPR explores the ML solution neighbourhood as a way of intensification to approach optimal solutions. The carried out experiments indicated that the approach was effective and competitive. [ABSTRACT FROM AUTHOR]

This paper deals with knapsack problem in fuzzy nature, where both the objective function and constraints are considered to be fuzzy. Three different models for fuzzy knapsack problem are proposed including, expected value model, chance-constrained model, and dependent-chance model. Credibility ranking method is applied to convert the fuzzy models into a crisp equivalent linear one considering triangular and trapezoidal fuzzy numbers. The solution of the fuzzy problem is obtained with respect to different satisfaction degrees in the objective function and constraints. Several numerical examples are given to demonstrate different models and concepts. The proposed approaches are applied to model and to solve a fuzzy pre-disaster investment decision problem. [ABSTRACT FROM AUTHOR]

Ensemble-based methods are highly popular approaches that increase the accuracy of a decision by aggregating the opinions of individual voters. The common point is to maximize accuracy; however, a natural limitation occurs if incremental costs are also assigned to the individual voters. Consequently, we investigate creating ensembles under an additional constraint on the total cost of the members. This task can be formulated as a knapsack problem, where the energy is the ensemble accuracy formed by some aggregation rules. However, the generally applied aggregation rules lead to a nonseparable energy function, which takes the common solution tools—such as dynamic programming—out of action. We introduce a novel stochastic approach that considers the energy as the joint probability function of the member accuracies. This type of knowledge can be efficiently incorporated in a stochastic search process as a stopping rule, since we have the information on the expected accuracy or, alternatively, the probability of finding more accurate ensembles. Experimental analyses of the created ensembles of pattern classifiers and object detectors confirm the efficiency of our approach over other pruning ones. Moreover, we propose a novel stochastic search method that better fits the energy, which can be incorporated in other stochastic strategies as well. [ABSTRACT FROM AUTHOR]

The 0-1 knapsack problem (KP) is a classic NP-hard problem and could be handled by swarm intelligence algorithms. However, most of these algorithms might be trapped in the local optima as the scale increases. Hybrid rice optimization (HRO) is a novel swarm intelligence algorithm inspired by the breeding process of Chinese three-line hybrid rice, its population is classified into three types such as the maintainer, restorer and sterile line and several stages including hybridization, selfing and renewal are implemented. In this paper, a modified HRO algorithm is proposed for the complicated large-scale 0-1 KP. A dynamic step is introduced in the renewal stage to balance the exploration and exploitation phases. Moreover, HRO is combined with binary ant colony optimization (BACO) algorithm to compose the parallel model and serial model for enhancing the convergence speed and search efficiency. In the parallel model, HRO and BACO are independently implemented on two subpopulations and communicate during each iteration. In the serial model, BACO is embedded in HRO as an operator to update the maintainer line. The experimental results on 0-1 KPs of different scales and correlations demonstrate the outperformance of the parallel model and serial model. [ABSTRACT FROM AUTHOR]

A knapsack problem is to select a set of items that maximizes the total profit of selected items while keeping the total weight of the selected items no less than the capacity of the knapsack. As a generalized form with multiple knapsacks, the multi-knapsack problem (MKP) is to select a disjointed set of items for each knapsack. To solve MKP, we propose a deep reinforcement learning (DRL) based approach, which takes as input the available capacities of knapsacks, total profits and weights of selected items, and normalized profits and weights of unselected items and determines the next item to be mapped to the knapsack with the largest available capacity. To expedite the learning process, we adopt the Asynchronous Advantage Actor-Critic (A3C) for the policy model. The experimental results indicate that the proposed method outperforms the random and greedy methods and achieves comparable performance to an optimal policy in terms of the profit ratio of the selected items to the total profit sum, particularly when the profits and weights of items have a non-linear relationship such as quadratic forms. [ABSTRACT FROM AUTHOR]

Compared to fuzzy utility itemset mining (FUIM), temporal fuzzy utility itemset mining (TFUIM) has been proposed and paid attention to in recent years. It considers the characteristics of transaction time, sold quantities of items, unit profit, and transformed semantic terms as essential factors. In the past, a tree-structure method with two phases was previously presented to solve this problem. However, it spent much time because of the number of candidates generated. This paper thus proposes a one-phase tree-structure method to find the high temporal fuzzy utility itemsets in a temporal database. The tree was designed to maintain candidate 1-itemsets with their upper bound values meeting the defined threshold constraint. Besides, each node in this tree keeps the required data of a 1-itemset for mining. We also designed an algorithm to construct the tree and gave an example to illustrate the mining process in detail. Computational experiments were conducted to demonstrate the one-phase tree-structure method is better than the previous one regarding the execution time on three real datasets. [ABSTRACT FROM AUTHOR]

We present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. The follower must solve an optimization problem that has been previously perturbed by means of a series of attacking actions led by the attacker. These attacking actions aim at augmenting the cost of the decision variables of the follower's optimization problem. The objective, from the attacker's viewpoint, is that of choosing an attacking strategy that reduces as much as possible the quality of the optimal solution attainable by the follower. The progressive approximation mechanism consists of the iterative solution of an interdiction problem in which the attacker actions are restricted to a subset of the whole solution space and a pricing subproblem invoked with the objective of proving the optimality of the attacking strategy. This scheme is especially useful when the optimal solutions to the follower's subproblem intersect with the decision space of the attacker only in a small number of decision variables. In such cases, the progressive approximation method can solve interdiction games otherwise intractable for classical methods. We illustrate the efficiency of our approach on the shortest path, 0-1 knapsack and facility location interdiction games. Summary of Contribution: In this article, we present a progressive approximation algorithm for the exact solution of several classes of interdiction games in which two noncooperative players (namely an attacker and a follower) interact sequentially. We exploit the discrete nature of this interdiction game to design an effective algorithmic framework that improves the performance of general-purpose solvers. Our algorithm combines elements from mathematical programming and computer science, including a metaheuristic algorithm, a binary search procedure, a cutting-planes algorithm, and supervalid inequalities. Although we illustrate our results on three specific problems (shortest path, 0-1 knapsack, and facility location), our algorithmic framework can be extended to a broader class of interdiction problems. [ABSTRACT FROM AUTHOR]