1615. On the Rank-1 Chvátal-Gomory inequalities for the knapsack problem with generalized upper bounds
Invited abstract in session TC-20: Exact algorithms for combinatorial optimization, stream Combinatorial Optimization.
Tuesday, 12:30-14:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Junyoung Kim
|
| Business Administration, Myongji University | |
| 2. | Kyungsik Lee
|
| Industrial Engineering, Seoul National University |
Abstract
In this talk, we examine rank-1 Chvátal-Gomory (CG) inequalities for the knapsack problem with generalized upper bounds (GKP). We first analyze the properties of non-dominated rank-1 CG cuts for the GKP. Based on these results, we propose efficient exact and heuristic algorithms for the separation problem, along with an analysis of their computational complexity. We then conducted computational tests on benchmark instances for the multi-dimensional multiple-choice knapsack problem. The results demonstrate that the proposed algorithms generate the CG inequalities that are more effective in strengthening the linear programming relaxations than existing valid inequalities for the GKP, within a short computation time.
Keywords
- Mathematical Programming
- Combinatorial Optimization
- Programming, Integer
Status: accepted
Back to the list of papers