A scenario-cluster-based and enhanced progressive hedging algorithm for the two-stage stochastic quadratic knapsack problem
Abstract
This paper introduces the two-stage stochastic quadratic knapsack problem (TSSQKP) with uncertainty in profits and weights. To overcome the computational difficulties arising from the combined stochastic, binary, and quadratic structure, we propose a solution framework that integrates an adaptation of the progressive hedging algorithm with clustering-based scenario reduction. The enhanced progressive hedging algorithm (EPHA) incorporates a rounding procedure and a dynamic penalty update strategy driven by the detection of oscillation and stagnation patterns. In parallel, we propose a clustering framework based on opportunity-cost distances between scenarios, from which we derive the medoid lower bound (MLB), the cluster lower bound (CLB) and the cluster upper bound (CUB). To further improve computational efficiency, EPHA is also used to solve the cluster subproblems heuristically; in this case, the resulting upper bound is referred to as the estimated cluster upper bound (ECUB), and the corresponding gaps are interpreted as estimated optimality gaps. Computational experiments on 800 generated TSSQKP instances show that the proposed framework yields smaller gaps than CPLEX under comparable computational conditions. In the EPHA-based clustering framework, the average estimated gaps associated with the CLB, EPHA and MLB 1.65%, 1.88% and 2.41% respectively, compared with an average optimality gap of 35.86% for CPLEX. MLB is fastest to compute, with an average execution time of 420.88s, while EPHA provides a favourable compromise between solution quality and computational effort, reducing the average computational time associated with the cluster bounds by approximately 52.7%, while increasing the average estimated gap by only 0.23 percentage points.
Related
- Scentree: a framework for generating scenario trees for multistage stochastic programming
- Fused ultrametric Gromov-Wasserstein for Scenario Tree generation in Multistage Stochastic Programming
- Semidefinite Implementations of the Proximal Point Algorithm and Consequences for Progressive Decoupling in Optimization
- Regret-Based Scenario-Tree Construction for Multistage Stochastic Programs with Deterministic Constraints
- Optimization of Quadratic Sieve Algorithm Implementation for Large Integer Factorization
BibTeX
@misc{dije2026scenarioclusterbased,
title = {{A scenario-cluster-based and enhanced progressive hedging algorithm for the two-stage stochastic quadratic knapsack problem}},
author = {Ibrahim Dan Dije and Franklin Djeumou Fomeni and Leandro C. Coelho and Janosch Ortmann},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23176},
eprint = {2609.23176},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23176},
}
RIS
TY - UNPB
TI - A scenario-cluster-based and enhanced progressive hedging algorithm for the two-stage stochastic quadratic knapsack problem
AU - Ibrahim Dan Dije
AU - Franklin Djeumou Fomeni
AU - Leandro C. Coelho
AU - Janosch Ortmann
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.23176
UR - https://arxiv.org/abs/2609.23176
AB - This paper introduces the two-stage stochastic quadratic knapsack problem (TSSQKP) with uncertainty in profits and weights. To overcome the computational difficulties arising from the combined stochastic, binary, and quadratic structure, we propose a solution framework that integrates an adaptation of the progressive hedging algorithm with clustering-based scenario reduction. The enhanced progressive hedging algorithm (EPHA) incorporates a rounding procedure and a dynamic penalty update strategy driven by the detection of oscillation and stagnation patterns. In parallel, we propose a clustering framework based on opportunity-cost distances between scenarios, from which we derive the medoid lower bound (MLB), the cluster lower bound (CLB) and the cluster upper bound (CUB). To further improve computational efficiency, EPHA is also used to solve the cluster subproblems heuristically; in this case, the resulting upper bound is referred to as the estimated cluster upper bound (ECUB), and the corresponding gaps are interpreted as estimated optimality gaps. Computational experiments on 800 generated TSSQKP instances show that the proposed framework yields smaller gaps than CPLEX under comparable computational conditions. In the EPHA-based clustering framework, the average estimated gaps associated with the CLB, EPHA and MLB 1.65%, 1.88% and 2.41% respectively, compared with an average optimality gap of 35.86% for CPLEX. MLB is fastest to compute, with an average execution time of 420.88s, while EPHA provides a favourable compromise between solution quality and computational effort, reducing the average computational time associated with the cluster bounds by approximately 52.7%, while increasing the average estimated gap by only 0.23 percentage points.
ER -