Linear integer programming and the computation of the Sylvester denumerant

Computing the Sylvester denumerant is a difficult problem (NP–hard as of today, to be precise) which arises from a rather natural question in Combinatorial Number Theory. In this paper we explore a linear integer programming approach to it, based on previous work of the first and third author, and compare the practical results with the best methods currently available. The methods included allow us to compute examples of denumerants bigger than the ones treated hitherto in the literature.