Relaxation of 3-partition instances
Sjc Sebastiaan Joosten, Hans Zantema · TU/e Research Portal · 2013
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.