On the complexity of surrogate and group relaxation for integer linear programs
| Autor: | Adam N. Letchford, Trivikram Dokka, M. Hasan Mansoor |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
021103 operations research
Group (mathematics) Applied Mathematics 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research 01 natural sciences Industrial and Manufacturing Engineering Dual (category theory) Combinatorics 010104 statistics & probability Set packing Knapsack problem Relaxation (approximation) 0101 mathematics Integer programming Software Integer (computer science) Mathematics |
| Zdroj: | Dokka, T, Letchford, A & Mansoor, H 2021, ' On the complexity of surrogate and group relaxation for integer linear programs ', Operations Research Letters, vol. 49, no. 4, pp. 530-534 . https://doi.org/10.1016/j.orl.2021.05.011 |
| Popis: | Surrogate and group relaxation have been used to compute bounds for various integer linear programming problems. We prove that (a) when only inequalities are surrogated, the surrogate dual is NP -hard, but solvable in pseudo-polynomial time under certain conditions; (b) when equations are surrogated, the surrogate dual exhibits unusual complexity behaviour; (c) the group relaxation is NP -hard for the integer and 0-1 knapsack problems, and strongly NP -hard for the set packing problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|