M/611

We consider nonlinear integer optimization problems. In order to solve such a problem, we use the fact, that continuous nonlinear optimization problems are often easier to solve than their integer counterparts. Assume that we can solve a continuous nonlinear problem in polynomial time and we know that an optimal integer point can be found by just rounding (up or down) the components of an optimal solution of the continuous problem, then we can (in fixed dimension) also solve the IP in polynomial time. To check whether we get an optimal soluTion to the IP by rounding a continuous solution (we call this the rounding property) we use a geometric approach: we investigate the geometric shape of the level sets. E.g. if the level sets are balls around the continuous solution the problem has the rounding property. We extend this by identifying geometric properties of the level sets that also lead to the rounding property: First, the rounding property is still true, if we don`t take the standard Euclidean-norm-ball, but an arbitrary p-norm ball. Second, we will show that the rounding property holds if the level set is included between two p-norm-balls if the difference of their radii is small enough. We call this type of sets p-quasiround. Four our third generalization we investigate rectangular-distance-star-shaped sets and show that the rounding property also holds in this case. Furthermore, we will discuss a sharper property which makes sure that we can round the continuous optimum to the closest integer point. If it holds then we can solve the integer version of a continuous optimization problem in the same time as the continuous problem (in any dimension).

Ruth Hübner

Universität Göttingen