Cutting circles and polygons from area-minimizing rectangles

A set of circles, rectangles, and convex polygons are to be cut from rectangular design plates to be produced, or from a set of stocked rectangles of known geometric dimensions. The objective is to minimize the area of the design rectangles. The design plates are subject to lower and upper bounds of their widths and lengths. The objects are free of any orientation restrictions. If all nested objects fit into one design or stocked plate the problem is formulated and solved as a nonconvex nonlinear programming problem. If the number of objects cannot be cut from a single plate, additional integer variables are needed to represent the allocation problem leading to a nonconvex mixed integer nonlinear optimization problem. This is the first time that circles and arbitrary convex polygons are treated simultaneously in this context. We present exact mathematical programming solutions to both the design and allocation problem. For small number of objects to be cut we compute globally optimal solutions. One key idea in the developed NLP and MINLP models is to use separating hyperplanes to ensure that rectangles and polygons do not overlap with each other or with the circles. Another important idea used when dealing with several resource rectangles is to develop a model formulation which connects the binary variables only to the variables representing the center of the circles or the vertices of the polytopes but not to the non-overlap or shape constraints. We support the solution process by symmetry breaking constraints. In addition we compute lower bounds, which are constructed by a relaxed model in which each polygon is replaced by the largest circle fitting into that polygon. We have successfully applied several solution techniques to solve this problem among them the Branch&Reduce Optimization Navigator (BARON) and the LindoGlobal solver called from GAMS, and, as described in Rebennack et al. [21], a column enumeration approach in which the columns represent the assignments. Good feasible solutions are computed within seconds or minutes usually during preprocessing. In most cases they turn out to be globally optimal. For up to 10 circles, we prove global optimality up to a gap of the order of 10^?8 in short time. Cases with a modest number of objects, for instance, 6 circles and 3 rectangles, are also solved in short time to global optimality. For test instances involving non-rectangular polygons it is difficult to obtain small gaps. In such cases we are content to obtain gaps of the order of 10%.     

Sporadic Reinhardt Polygons

Let $n$ be a positive integer, not a power of two. A Reinhardt polygon is a convex $n$ -gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. For almost all $n$ , there are many Reinhardt polygons with $n$ sides, and many of them exhibit a particular periodic structure. While these periodic polygons are well understood, for certain values of $n$ , additional Reinhardt polygons exist, which do not possess this structured form. We call these polygons sporadic. We completely characterize the integers $n$ for which sporadic Reinhardt polygons exist, showing that these polygons occur precisely when $n=pqr$ with $p$ and $q$ distinct odd primes and $r\ge 2$ . We also prove that a positive proportion of the Reinhardt polygons with $n$ sides is sporadic for almost all integers $n$ , and we investigate the precise number of sporadic Reinhardt polygons that are produced for several values of $n$ by a construction that we introduce.     

On convex relaxations for quadratically constrained quadratic programming

We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let $\mathcal{F }$ denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on $\mathcal{F }$ is dominated by an alternative methodology based on convexifying the range of the quadratic form $\genfrac(){0.0pt}{}{1}{x}\genfrac(){0.0pt}{}{1}{x}^T$ for $x\in \mathcal{F }$ . We next show that the use of ?? $\alpha $ BB?? underestimators as computable estimates of convex lower envelopes is dominated by a relaxation of the convex hull of the quadratic form that imposes semidefiniteness and linear constraints on diagonal terms. Finally, we show that the use of a large class of D.C. (??difference of convex??) underestimators is dominated by a relaxation that combines semidefiniteness with RLT constraints.     

On efficiency and mixed duality for a new class of nonconvex multiobjective variational control problems

In this paper, we extend the notions of \((\Phi ,\rho )\) -invexity and generalized \((\Phi ,\rho )\) -invexity to the continuous case and we use these concepts to establish sufficient optimality conditions for the considered class of nonconvex multiobjective variational control problems. Further, multiobjective variational control mixed dual problem is given for the considered multiobjective variational control problem and several mixed duality results are established under \((\Phi ,\rho )\) -invexity.     

Asymptotics of random lozenge tilings via Gelfand–Tsetlin schemes

A Gelfand–Tsetlin scheme of depth \(N\) is a triangular array with \(m\) integers at level \(m\) , \(m=1,\ldots ,N\) , subject to certain interlacing constraints. We study the ensemble of uniformly random Gelfand–Tsetlin schemes with arbitrary fixed \(N\) th row. We obtain an explicit double contour integral expression for the determinantal correlation kernel of this ensemble (and also of its \(q\) -deformation). This provides new tools for asymptotic analysis of uniformly random lozenge tilings of polygons on the triangular lattice; or, equivalently, of random stepped surfaces. We work with a class of polygons which allows arbitrarily large number of sides. We show that the local limit behavior of random tilings (as all dimensions of the polygon grow) is directed by ergodic translation invariant Gibbs measures. The slopes of these measures coincide with the ones of tangent planes to the corresponding limit shapes described by Kenyon and Okounkov (Acta Math 199(2):263–302, 2007). We also prove that at the edge of the limit shape, the asymptotic behavior of random tilings is given by the Airy process. In particular, our results cover the most investigated case of random boxed plane partitions (when the polygon is a hexagon).     

On the set-semidefinite representation of nonconvex quadratic programs over arbitrary feasible sets

In the paper we prove that any nonconvex quadratic problem over some set ${K\subset \mathbb {R}^n}$ with additional linear and binary constraints can be rewritten as a linear problem over the cone, dual to the cone of K-semidefinite matrices. We show that when K is defined by one quadratic constraint or by one concave quadratic constraint and one linear inequality, then the resulting K-semidefinite problem is actually a semidefinite programming problem. This generalizes results obtained by Sturm and Zhang (Math Oper Res 28:246–267, 2003). Our result also generalizes the well-known completely positive representation result from Burer (Math Program 120:479–495, 2009), which is actually a special instance of our result with ${K=\mathbb{R}^n_{+}}$ .     

How large dimension guarantees a given angle?

We study the following two problems: (1) Given $n\ge 2$ and $0\le \alpha \le 180^\circ $ , how large Hausdorff dimension can a compact set $A\subset \mathbb{R }^n$ have if $A$ does not contain three points that form an angle $\alpha $ ? (2) Given $\alpha $ and $\delta $ , how large Hausdorff dimension can a subset $A$ of a Euclidean space have if $A$ does not contain three points that form an angle in the $\delta $ -neighborhood of $\alpha $ ? An interesting phenomenon is that different angles show different behaviour in the above problems. Apart from the clearly special extreme angles $0$ and $180^\circ $ , the angles $60^\circ , 90^\circ $ and $120^\circ $ also play special role in problem (2): the maximal dimension is smaller for these angles than for the other angles. In problem (1) the angle $90^\circ $ seems to behave differently from other angles.     

Homomorphisms with respect to a function

Let X be a realcompact space and ${H:C(X)\rightarrow\mathbb{R}}$ be an identity and order preserving group homomorphism. It is shown that H is an evaluation at some point of X if and only if there is ${\varphi\in C(\mathbb{R})}$ with ${\varphi(r)>\varphi(0)}$ for all ${r\in\mathbb{R}-\{0\}}$ for which ${H\circ\varphi=\varphi\circ H}$ . This extends (and unifies) classical results by Hewitt and Shirota.     

Upper bounding in inner regions for global optimization under inequality constraints

In deterministic continuous constrained global optimization, upper bounding the objective function generally resorts to local minimization at several nodes/iterations of the branch and bound. We propose in this paper an alternative approach when the constraints are inequalities and the feasible space has a non-null volume. First, we extract an inner region, i.e., an entirely feasible convex polyhedron or box in which all points satisfy the constraints. Second, we select a point inside the extracted inner region and update the upper bound with its cost. We describe in this paper two original inner region extraction algorithms implemented in our interval B&B called IbexOpt (AAAI, pp 99–104, 2011). They apply to nonconvex constraints involving mathematical operators like , \( +\; \bullet ,\; /,\; power,\; sqrt,\; exp,\; log,\; sin\) . This upper bounding shows very good performance obtained on medium-sized systems proposed in the COCONUT suite.     

Elastic Splines I: Existence

Given interpolation points \(P_1,P_2,\ldots ,P_m\) in the plane, it is known that there does not exist an interpolating curve with minimal bending energy unless the given points lie sequentially along a line. We say that an interpolating curve is admissible if each piece, connecting two consecutive points \(P_i\) and \(P_{i+1}\) , is an s-curve, where an s-curve is a planar curve which first turns monotonically at most \(180^\circ \) in one direction and then turns monotonically at most \(180^\circ \) in the opposite direction. Our main result is that among all admissible interpolating curves there exists a curve with minimal bending energy. We also prove, in a very constructive manner, the existence of an s-curve, with minimal bending energy, that connects two given unit tangent vectors.     

A quasiconformal analog of Carathéodory’s criterion for the Möbius property of mappings

In 1937, Carathéodory proved that every injective mapping f: G → f(G) ? $\bar C$ of a domain G ? $\bar C$ , taking circles to circles, is Möbius. The present article shows that if each injective mapping takes circles onto k-quasicircles then it is K-quasiconformal with $K \leqslant k + \sqrt {k^2 - 1} $ .     

Symmetric 2-Structures,a Classification

We classify symmetric 2-structures ${(P, \mathfrak{G}_1, \mathfrak{G}_2, \mathfrak{K})}$ , i.e. chain structures which correspond to sharply 2-transitive permutation sets (E, Σ) satisfying the condition: “ ${(*) \, \, \forall \sigma, \tau \in \Sigma : \sigma \circ \tau^{-1} \circ \sigma \in \Sigma}$ ”. To every chain ${K \in \mathfrak{K}}$ one can associate a reflection ${\widetilde{K}}$ in K. Then (*) is equivalent to “ ${(**) \, \, \forall K \in \mathfrak{K} : \widetilde{K}(\mathfrak{K}) = \mathfrak{K}}$ ” and one can define an orthogonality “ ${\perp}$ ” for chains ${K, L \in \mathfrak{K}}$ by “ ${K \perp L \Leftrightarrow K \neq L \wedge \widetilde{K}(L) = L}$ ”. The classification is based on the cardinality of the set of chains which are orthogonal to a chain K and passing through a point p of K. For one of these classes (called point symmetric 2-structures) we proof that in each point there is a reflection and that the set of point reflections forms a regular involutory permutation set.     

On a measure of asymmetry for Reuleaux polygons

In a previous paper, we showed that for regular Reuleaux polygons R _n the equality ${{\rm as}_\infty(R_n) = 1/(2\cos \frac\pi{2n} -1)}$ holds, where ${{\rm as}_\infty(\cdot)}$ denotes the Minkowski measure of asymmetry for convex bodies, and ${{\rm as}_\infty(K)\leq \frac 12(\sqrt{3}+1)}$ for all convex domains K of constant width, with equality holds iff K is a Reuleaux triangle. In this paper, we investigate the Minkowski measures of asymmetry among all Reuleaux polygons of order n and show that regular Reuleaux polygons of order n (n ?? 3 and odd) have the minimal Minkowski measure of asymmetry.     

Ergodic dynamical systems over the cartesian power of the ring of p-adic integers

For any 1-lipschitz ergodic map F: ? _p ^k ? ? _p ^k , k >1 ∈ ?, there are 1-lipschitz ergodic map G: ? _p ? ? _p and two bijections H _k , T _{k, P} that $G = H_k \circ T_{k,P} \circ F \circ H_k^{ - 1} andF = H_k^{ - 1} \circ T_{k,P - 1} \circ G \circ H_k $ .     

Fibered incidence groups which are not kinematic

An incidence space \((\beta ,\mathfrak{L})\) which is obtained from an affine space \((\beta _a ,\mathfrak{L}_a )\) by omitting a hyperplane is calledstripe space. If \((\beta _a ,\mathfrak{L}_a )\) is desarguesian, then \(\beta \) can be provided with a group operation “ ○ ” such that \((\beta ,\mathfrak{L}, \circ )\) becomes a kinematic space calledstripe group. It will be shown that there are stripe groups \((\beta ,\mathfrak{L}, \circ )\) where the incidence structure \(\mathfrak{L}\) can be replaced by another incidence structure ? such that \((\beta ,\Re , \circ )\) is afibered incidence group which is not kinematic. An application on translation planes concerning the group of affinities is also given.     

Geodesics on the Moduli Space of Oriented Circles in \mathbb{S}^{3}

Let ${\mathbb{Q}^3}$ be the moduli space of oriented circles in the three dimensional unit sphere ${\mathbb{S}^3}$ . Given a natural complex structure such space becomes a three dimensional complex manifold, with a M?bius invariant Hermitian metric h of type (2, 1). Up to M?bius transformations, all geodesics with respect to the Lorentz metric g = Re(h) on ${\mathbb{Q}^3}$ are determined to form a one-parameter family of circles on a helicoid in a space form ${\mathbb{R}^3, \mathbb{H}^3}$ or ${\mathbb{S}^{3}}$ , resp. We show also that any two oriented circles in ${\mathbb{S}^3}$ are connected by countably infinitely many geodesics in ${\mathbb{Q}^3}$ .     

Bounds for codes and designs in complex subspaces

We introduce the concepts of complex Grassmannian codes and designs. Let $\mathcal{G}_{m,n}$ denote the set of m-dimensional subspaces of ? ⁿ : then a code is a finite subset of $\mathcal{G}_{m,n}$ in which few distances occur, while a design is a finite subset of $\mathcal{G}_{m,n}$ that polynomially approximates the entire set. Using Delsarte’s linear programming techniques, we find upper bounds for the size of a code and lower bounds for the size of a design, and we show that association schemes can occur when the bounds are tight. These results are motivated by the bounds for real subspaces recently found by Bachoc, Bannai, Coulangeon and Nebe, and the bounds generalize those of Delsarte, Goethals and Seidel for codes and designs on the complex unit sphere.