Journées de l'optimisation 2007 Optimizations days

Consider a convex polygon $V_n$ with $n$ sides, perimeter $P_n$, diameter $D_n$, area $A_n$, sum of distances between vertices $S_n$ and width $W_n$. Minimizing or maximizing any of these quantities while fixing another defines ten pairs of extremal polygon problems (one of which usually has a trivial solution or no solution at all). We survey research on these problems, which uses geometrical reasoning increasingly complemented by global optimization methods. Numerous open problems are mentioned, as well as series of test problems for global optimization and nonlinear programming codes.

We consider the problem of finding for all $n$ which convex polygon with $n$ vertices and unit diameter has the largest sum of distances between pairs of vertices. This problem was introduced by Fejes \textsc{T\'oth} and studied by Friedrich \textsc{Pillichshammer} for $n$ lower or equal to 5. Combining geometric reasoning with two algorithms for non convex quadratic programming, we solve the case $n$=6 and provide lower bounds on the objective for all $n$.

An approach that systematically changes formulations for solving circle packing problem (CPP) we have recently suggested in 2004. There we show that stationary point of non-linear programming formulation of CPP in Cartesian coordinates is not necessarily so in polar coordinate system. The method "Reformulation descent" (RD) that alternates between these two formulations until the final solution is stationary with respect to both is suggested. In this paper we extend the RD idea. Several formulations instead of only two are used. The distance between two formulations is defined as the number of centers whose coordinates are expressed in different systems in each formulation. Therefore, the search is performed through the formulation space as well. Results with up to 100 circles compare favorable with RD method.

The value $\frac{1}{2n} \cot\left( \frac{\pi}{2n}\right)$ is shown to be an upper bound on the width of any $n$-sided polygon with unit perimeter. This bound is reached when $n$ is not a power of 2, and the corresponding optimal solutions are the regular polygons when $n$ is odd, and clipped regular Reuleaux polygons when $n$ is even but not a power of 2. Using a global optimization algorithm, we solve the problem for $n=4$. The optimal width for the quadrilateral is shown to be $\frac 14 \sqrt{ 3( 2\sqrt 3 -3 )} \approx 0.2949899\ldots$ We propose two mathematical programs to determine the maximal width when $n=2^s$ with $s\geq 3$ and provide approximate, but near-optimal, solutions obtained by various heuristics and local optimization for $n=8,16$ and $32$.