Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911792778706944 |
|---|---|
| author | Kim, Junyoung Lee, Kyungsik |
| author_facet | Kim, Junyoung Lee, Kyungsik |
| contents | We consider the chance-constrained binary knapsack problem (CKP), where the item weights are independent and normally distributed. We introduce a continuous relaxation for the CKP, represented as a non-convex optimization problem, which we call the non-convex relaxation. A comparative study shows that the non-convex relaxation provides an upper bound for the CKP, at least as tight as those obtained from other continuous relaxations for the CKP. Furthermore, the quality of the obtained upper bound is guaranteed to be at most twice the optimal objective value of the CKP. Despite its non-convex nature, we show that the non-convex relaxation can be solved in polynomial time. Subsequently, we proposed a polynomial-time 1/2-approximation algorithm for the CKP based on this relaxation, providing a lower bound for the CKP. Computational test results demonstrate that the non-convex relaxation and the proposed approximation algorithm yields tight lower and upper bounds for the CKP within a short computation time, ensuring the quality of the obtained bounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_06686 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem Kim, Junyoung Lee, Kyungsik Optimization and Control Discrete Mathematics Combinatorics 90C15, 90C27, 90C59 We consider the chance-constrained binary knapsack problem (CKP), where the item weights are independent and normally distributed. We introduce a continuous relaxation for the CKP, represented as a non-convex optimization problem, which we call the non-convex relaxation. A comparative study shows that the non-convex relaxation provides an upper bound for the CKP, at least as tight as those obtained from other continuous relaxations for the CKP. Furthermore, the quality of the obtained upper bound is guaranteed to be at most twice the optimal objective value of the CKP. Despite its non-convex nature, we show that the non-convex relaxation can be solved in polynomial time. Subsequently, we proposed a polynomial-time 1/2-approximation algorithm for the CKP based on this relaxation, providing a lower bound for the CKP. Computational test results demonstrate that the non-convex relaxation and the proposed approximation algorithm yields tight lower and upper bounds for the CKP within a short computation time, ensuring the quality of the obtained bounds. |
| title | Non-convex relaxation and 1/2-approximation algorithm for the chance-constrained binary knapsack problem |
| topic | Optimization and Control Discrete Mathematics Combinatorics 90C15, 90C27, 90C59 |
| url | https://arxiv.org/abs/2403.06686 |