The mathematics of playing golf, or: A new class of difficult non-linear mixed integer programs

0.00 Avg rating—0 Votes

Article ID:	iaor20032534
Country:	Germany
Volume:	93
Issue:	1
Start Page Number:	77
End Page Number:	86
Publication Date:	Jan 2002
Journal:	Mathematical Programming
Authors:	Rinaldi G., Woeginger G.J., Voigt U.
Keywords:	programming: integer, sports

Abstract:

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k = 1 and k = 2, every optimal solution is integral. In contrast to this, for every k ≥ 3 there exist instances where every optimal solution takes non-integral values.

Reviews

Required fields are marked *. Your email address will not be published.