|
|||||
|
|
The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs |
|
| Authors: | Giovanni Rinaldi Ulrich Voigt Gerhard J. Woeginger |
| Affiliation: | Istituto di Analisi dei Sistemi e Informatica, IASI-CNR, Viale Manzoni 30, I-00185 Roma, Italy, e-mail: rinaldi@iasi.rm.cnr.it, IT Institut für Mathematik, Universit?t Freiburg, D-79104 Freiburg im Breisgau, Germany, e-mail: uvo@mathematik.uni-freiburg.de, DE Department of Mathematics, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands, and Institut für Mathematik, Technische Universit?t Graz, Steyrergasse 30, A-8010 Graz, Austria, e-mail: g.j.woeginger@math.utwente.nl, NL |
| 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. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002 |
| Keywords: | : non-linear optimization – mixed integer program – integrality – computational complexity – NP-hard problem – golf problem |
| 本文献已被 SpringerLink 等数据库收录！ | |