Revisiting surrogate relaxation for the multidimensional knapsack problem |
| |
Institution: | 1. Management Section, Queen''s Management School, Riddel Hall, 185 Stranmillis Road, Belfast BT9 5EE, Northern Ireland, UK;2. Department of Management Science, Lancaster University, Lancaster LA1 4YX, UK |
| |
Abstract: | The multidimensional knapsack problem (MKP) is a classic problem in combinatorial optimisation. Several authors have proposed to use surrogate relaxation to compute upper bounds for the MKP. In their papers, the surrogate dual is solved heuristically. We show that, using a modern dual simplex solver as a subroutine, one can solve the surrogate dual exactly in reasonable computing times. On the other hand, the resulting upper bound tends to be strong only for relatively small MKP instances. |
| |
Keywords: | Knapsack problems Integer programming Surrogate relaxation |
本文献已被 ScienceDirect 等数据库收录! |
|