Relaxation of 3-partition instances
Authors:
- Joosten, Sebastiaan J. C.
- Zantema, Hans
Abstract:
The 3-partition problem admits a straightforward formulation as a 0-1 Integer Linear Program (ILP). We investigate problem instances for which the half-integer relaxation of the ILP is feasible, while the ILP is not. We prove that this only occurs on a set of at least 18 elements, and in case of 18 elements such an instance always contains an element of weight ≥ 10. These bounds are sharp: we give all 14 instances consisting of 18 elements all having weight ≤ 10. Our approach is based on analyzing an underlying graph structure.
BibTeX entry:
@article{Joosten13b,
abstract = {The 3-partition problem admits a straightforward formulation as a 0-1 Integer Linear Program (ILP). We investigate problem instances for which the half-integer relaxation of the ILP is feasible, while the ILP is not. We prove that this only occurs on a set of at least 18 elements, and in case of 18 elements such an instance always contains an element of weight ≥ 10. These bounds are sharp: we give all 14 instances consisting of 18 elements all having weight ≤ 10. Our approach is based on analyzing an underlying graph structure.},
author = {Joosten, Sebastiaan Jozef Christiaan and Zantema, Hans},
day = {21},
month = {May},
pdf = {CTW2013Relaxation},
publisher = {Enschede: University of Twente},
title = {Relaxation of 3-partition instances},
year = {2013}
}