Evolutionary Algorithm for Chance Constrained Quadratic Multiple Knapsack Problem

• URL: http://arxiv.org/abs/2511.02500v1
• Date: Tue, 04 Nov 2025 11:39:33 GMT
• Title: Evolutionary Algorithm for Chance Constrained Quadratic Multiple Knapsack Problem
• Authors: Kokila Kasuni Perera, Aneta Neumann,
• Abstract summary: Quadratic multiple knapsack problem (QMKP) is an optimisation problem characterised by multiple weight capacity constraints.<n>We study a variant of this problem where profits are considered as random variables.<n>We propose a hybrid approach for this problem, which combines an evolutionary algorithm (EA) with a local optimisation strategy inspired by multi-factorial optimisation (MFO)
• Score: 3.6439154309310013
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quadratic multiple knapsack problem (QMKP) is a combinatorial optimisation problem characterised by multiple weight capacity constraints and a profit function that combines linear and quadratic profits. We study a stochastic variant of this problem where profits are considered as random variables. This problem reflects complex resource allocation problems in real-world scenarios where randomness is inherent. We model this problem using chance constraints to capture the stochastic profits. We propose a hybrid approach for this problem, which combines an evolutionary algorithm (EA) with a local optimisation strategy inspired by multi-factorial optimisation (MFO). EAs are used for global search due to their effectiveness in handling large, complex solution spaces. In the hybrid approach, EA periodically passes interim solutions to the local optimiser for refinement. The local optimiser applies MFO principles, which are typically used in multi-tasking problems. The local optimiser models the local problem as a multi-tasking problem by constructing disjoint search spaces for each knapsack based on an input solution. For each item, its assignment across all knapsacks is considered to determine the preferred knapsack. Items are then divided into disjoint groups corresponding to each knapsack, allowing each knapsack to be treated as a separate optimisation task. This structure enables effective application of MFO-based local refinements. We consider two EAs for the problem, (1+1) EA and ($\mu+\lambda$) EA. We conduct experiments to explore the effectiveness of these EAs on their own and also with the proposed local optimiser. Experimental results suggest that hybrid approaches, particularly those incorporating MFO, perform well on instances where chance constraints and capacity constraints are tight.

Related papers

• Random-Key Metaheuristic and Linearization for the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem [0.0]
  This paper addresses the Quadratic Multiple Constraints Variable-Sized Bin Packing Problem (QMC-VSBPP)<n>The problem generalizes the classical bin packing by incorporating multiple capacity dimensions, heterogeneous bin types, and quadratic interaction costs between items.<n>We propose two complementary methods that advance the current state-of-the-art.
  arXiv  Detail & Related papers  (2025-11-15T22:05:53Z)
• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  This paper introduces a versatile and efficient local search method tailored for optimization problems.<n>Using the random-key concept, RKO encodes solutions as vectors of random keys that are subsequently decoded into feasible solutions.<n>The RKO framework is able to combine a plethora of classic metaheuristics, each capable of operating independently or in parallel, with solution sharing facilitated through an elite solution pool.
  arXiv  Detail & Related papers  (2024-11-06T22:23:29Z)
• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets [86.43523688236077]
  Combinatorial optimization (CO) problems are often NP-hard and out of reach for exact algorithms. GFlowNets have emerged as a powerful machinery to efficiently sample from composite unnormalized densities sequentially. In this paper, we design Markov decision processes (MDPs) for different problems and propose to train conditional GFlowNets to sample from the solution space.
  arXiv  Detail & Related papers  (2023-05-26T15:13:09Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  We study the scenario of components that are independent and normally distributed. We introduce a multi-objective formulation of the problem which trades off the expected cost and its variance. We prove that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
  arXiv  Detail & Related papers  (2021-09-13T09:24:23Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Runtime Analysis of RLS and the (1+1) EA for the Chance-constrained Knapsack Problem with Correlated Uniform Weights [15.402666674186936]
  We perform runtime analysis of a randomized search algorithm (RSA) and a basic evolutionary algorithm (EA) for the chance-constrained knapsack problem with correlated uniform weights. We show how the weight correlations and the different types of profit profiles influence the runtime behavior of both algorithms in the chance-constrained setting.
  arXiv  Detail & Related papers  (2021-02-10T23:40:01Z)
• Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes [43.19936635161588]
  We present a method for Bayesian optimization in a space which can operate well in a large space. Our algorithm shows satisfactory performance compared to existing methods.
  arXiv  Detail & Related papers  (2020-11-26T02:22:41Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
  arXiv  Detail & Related papers  (2020-06-15T19:40:24Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  We investigate multi-armed bandit with semi-bandit feedback (CMAB) We analyze variants of the Combinatorial Thompson Sampling policy (CTS) This last result gives us an alternative to the Efficient Sampling for Combinatorial Bandit policy (ESCB)
  arXiv  Detail & Related papers  (2020-06-11T17:12:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.