Premium
Lifting and separation of robust cover inequalities
Author(s) -
Joung Seulgi,
Park Sungsoo
Publication year - 2018
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21829
Subject(s) - knapsack problem , cover (algebra) , mathematics , separation (statistics) , robustness (evolution) , algorithm , mathematical optimization , binary number , engineering , mechanical engineering , biochemistry , gene , statistics , chemistry , arithmetic
In this article we present a lifting algorithm and separation algorithms for robust cover inequalities of the binary robust knapsack problem using the Bertsimas and Sim model. First, we propose a polynomial time lifting algorithm for robust cover inequalities. Then the bounds on lifted coefficients are examined. We also propose three separation algorithms for robust cover inequalities and an exact separation algorithm for extended robust cover inequalities. Finally, the computational experiments exhibit the effect of proposed algorithms. The branch‐and‐cut algorithms with proposed lifting and separation algorithms are tested on the robust bandwidth packing problem and the robust knapsack problem.