A Memetic Lagrangian Heuristic for the 0-1 Multidimensional Knapsack Problem
Discrete Dynamics in Nature and Society, 2013 We present a new evolutionary algorithm to solve the 0-1 multidimensional knapsack problem. We tackle the problem using duality concept, differently from traditional approaches. Our method is based on Lagrangian relaxation.
Yourim Yoon, Yong-Hyuk Kim
doaj +1 more source
Exact algorithms for the 0–1 Time-Bomb Knapsack Problem
Computers & Operations Research, 2022 We consider a stochastic version of the 0–1 Knapsack Problem in which, in addition to profit and weight, each item is associated with a probability of exploding and destroying all the contents of the knapsack. The objective is to maximise the expected profit of the selected items.
Monaci M., Pike-Burke C., Santini A.
openaire +4 more sources
Binary light spectrum optimizer for knapsack problems: An improved model
Alexandria Engineering Journal, 2023 This paper presents a binary variant of a novel physics-based meta-heuristic optimization algorithm, namely Light spectrum optimizer (LSO), for tackling both the 0–1 knapsack (KP01) and multidimensional knapsack problems (MKP).
Mohamed Abdel-Basset +5 more
doaj +1 more source
Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack [PDF]
, 2019 The area of parameterized approximation seeks to combine approximation and parameterized algorithms to obtain, e.g., (1+epsilon)-approximations in f(k,epsilon)n^O(1) time where k is some parameter of the input.
Grandoni, Fabrizio +2 more
core +2 more sources
A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem [PDF]
, 2008 Constraints exist in almost every optimization problem. Different constraint handling techniques have been incorporated with genetic algorithms (GAs), however most of current studies are based on computer experiments.
He, Jun, Yao, Xin, Zhou, Yuren
core +1 more source
Solving Multidimensional 0-1 Knapsack Problem with Time-Free Tissue P Systems
Journal of Applied Mathematics, 2014 Tissue P system is a class of parallel and distributed model; a feature of traditional tissue P system is that the execution time of certain biological processes is very sensitive to environmental factors that might be hard to control.
Xiangrong Liu +5 more
doaj +1 more source
Complexity, 2023 In this paper, a binary variant of a novel nature-inspired metaheuristic algorithm called the nutcracker optimization algorithm (NOA) is presented for binary optimization problems.
Mohamed Abdel-Basset +3 more
doaj +1 more source
Generalized Assignment via Submodular Optimization with Reserved Capacity [PDF]
, 2019 We study a variant of the generalized assignment problem (GAP) with group constraints. An instance of (Group GAP) is a set I of items, partitioned into L groups, and a set of m uniform (unit-sized) bins.
Kulik, Ariel +3 more
core +2 more sources
Enhanced Group Theory-Based Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [PDF]
Jisuanji kexue yu tansuoThe group theory-based optimization algorithm (GTOA) is a discrete evolutionary algorithm designed by group theory methods, which is very suitable for solving combinatorial optimization problems with integer vectors as feasible solutions.
ZHANG Hansong, HE Yichao, WANG Jinghong, SUN Fei, LI Mingliang
doaj +1 more source
An Adaptive Quantum-inspired Differential Evolution Algorithm for 0-1 Knapsack Problem
, 2010 Differential evolution (DE) is a population based evolutionary algorithm widely used for solving multidimensional global optimization problems over continuous spaces. However, the design of its operators makes it unsuitable for many real-life constrained
Hota, Ashish Ranjan, Pat, Ankit
core +1 more source