# 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}
}
```