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\geq3$ there exist instances where every optimal solution takes non-integral values.
The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs
Rinaldi G;
2002
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\geq3$ there exist instances where every optimal solution takes non-integral values.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
