A scenario-cluster-based and enhanced progressive hedging algorithm for the two-stage stochastic quadratic knapsack problem

Ibrahim Dan Dije, Franklin Djeumou Fomeni, Leandro C. Coelho, Janosch Ortmann

arXivarxiv/2609.23176Sep 19, 2026math.OCscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.23176
curl -X POST /api/v1/records/arxiv/2609.23176/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.23176/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'