OPUS 4 | Search

Inclusion-maximal integral point sets over finite fields (2007)

Michael Kiermaier Sascha Kurz

We consider integral point sets in affine planes over finite fields. Here an integral point set is a set of points in $GF(q)^2$ where the formally defined Euclidean distance of every pair of points is an element of $GF(q)$. From another point of view we consider point sets over $GF(q)^2$ with few and prescribed directions. So this is related to Redeis work. Another motivation comes from the field of ordinary integral point sets in Euclidean spaces. In this article we study the spectrum of integral point sets over $GF(q)^2$ which are maximal with respect to inclusion. We give some theoretical results, constructions, conjectures, and some numerical data.

Lotsize optimization leading to a p-median problem with cardinalities (2007)

Constantin Gaul Sascha Kurz Jörg Rambau

We consider the problem of approximating the branch and size dependent demand of a fashion discounter with many branches by a distributing process being based on the branch delivery restricted to integral multiples of lots from a small set of available lot-types. We propose a formalized model which arises from a practical cooperation with an industry partner. Besides an integer linear programming formulation and a primal heuristic for this problem we also consider a more abstract version which we relate to several other classical optimization problems like the p-median problem, the facility location problem or the matching problem.

The Top-Dog Index: A New Measurement for the Demand Consistency of the Size Distribution in Pre-Pack Orders for a Fashion Discounter with Many Small Branches (2008)

Sascha Kurz Jörg Rambau Jörg Schlüchtermann Rainer Wolf

We propose the new Top-Dog-Index, a measure for the branch-dependent historic deviation of the supply data of apparel sizes from the sales data of a fashion discounter. A common approach is to estimate demand for sizes directly from the sales data. This approach may yield information for the demand for sizes if aggregated over all branches and products. However, as we will show in a real-world business case, this direct approach is in general not capable to provide information about each branchs individual demand for sizes: the supply per branch is so small that either the number of sales is statistically too small for a good estimate (early measurement) or there will be too much unsatisfied demand neglected in the sales data (late measurement). Moreover, in our real-world data we could not verify any of the demand distribution assumptions suggested in the literature. Our approach cannot estimate the demand for sizes directly. It can, however, individually measure for each branch the scarcest and the amplest sizes, aggregated over all products. This measurement can iteratively be used to adapt the size distributions in the pre-pack orders for the future. A real-world blind study shows the potential of this distribution free heuristic optimization approach: The gross yield measured in percent of gross value was almost one percentage point higher in the test-group branches than in the control-group branches.

On the minimum diameter of plane integral point sets (2007)

Sascha Kurz Alfred Wassermann

Since ancient times mathematicians consider geometrical objects with integral side lengths. We consider plane integral point sets P, which are sets of n points in the plane with pairwise integral distances where not all the points are collinear. The largest occurring distance is called its diameter. Naturally the question about the minimum possible diameter d(2,n) of a plane integral point set consisting of n points arises. We give some new exact values and describe state-of-the-art algorithms to obtain them. It turns out that plane integral point sets with minimum diameter consist very likely of subsets with many collinear points. For this special kind of point sets we prove a lower bound for d(2,n) achieving the known upper bound n^{c_2loglog n} up to a constant in the exponent.

There are integral heptagons, no three points on a line, no four on a circle (2007)

Tobias Kreisel Sasch Kurz

We give two configurations of seven points in the plane, no three points in a line, no four points on a circle with pairwise integral distances. This answers a famous question of Paul Erdös.

Integral point sets over Z_n^m (2007)

Axel Kohnert Sascha Kurz

There are many papers studying properties of point sets in the Euclidean space or on integer grids, with pairwise integral or rational distances. In this article we consider the distances or coordinates of the point sets which instead of being integers are elements of Z_n, and study the properties of the resulting combinatorial structures.

Bounds for the minimum oriented diameter (2008)

Sascha Kurz Martin Lätsch

We consider the problem of finding an orientation with minimum diameter of a connected bridgeless graph. Fomin et. al. discovered a relation between the minimum oriented diameter an the size of a minimal dominating set. We improve their upper bound.

How to avoid collisions in scheduling industrial robots? (2010)

Jörg Rambau Cornelius Schwarz

In modern production facilities industrial robots play an important role. When two ore more of them are moving in the same area, care must be taken to avoid collisions between them. Due to expensive equipment costs our approach to handle this is very conservative: Each critical area is modeled as a shared resource where only one robot is allowed to use it at a time. We studied collision avoidance in the context of arc welding robots in car manufacture industry. Here another shared resource comes into place. When using laser welding technology every robot needs to be connected to a laser source supplying it with the necessary energy. Each laser source can be connected to up to six robots but serve only one at a time. An instance of the problem consists of a set of robots, a set of welding task, a number of laser sources, a distance table, collision information and a production cycle time. The goal is to design robot tours covering all task and schedule them resource conflict free such that the makespan does not exceed the cycle time. We propose a general model for integrated routing and scheduling including collision avoidance as well as a branch-and-bound algorithm for it. Computational results on data generated with the robot simulation software KuKa Sim Pro are also provided showing that our algorithm outperforms standard mixed-integer models for our application.

A generalized job-shop problem with more than one resource demand per task (2011)

Joachim Schauer Cornelius Schwarz

We study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. On the positive side, we present a polynomial algorithm for the two robot case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of robots. This gives a sharp boundary of the complexity status for a constant number of robots.

Local Approximation of Discounted Markov Decision Problems by Mathematical Programming Methods (2011)

Stefan Heinz Jörg Rambau Andreas Tuchscherer

We develop a method to approximate the value vector of discounted Markov decision problems (MDP) with guaranteed error bounds. It is based on the linear programming characterization of the optimal expected cost. The new idea is to use column generation to dynamically generate only such states that are most relevant for the bounds by incorporating the reduced cost information. The number of states that is sufficient in general and necessary in the worst case to prove such bounds is independent of the cardinality of the state space. Still, in many instances, the column generation algorithm can prove bounds using much fewer states. In this paper, we explain the foundations of the method. Moreover, the method is used to improve the well-known nearest-neighbor policy for the elevator control problem.

Preprint

Refine

Author

Year of publication

Document Type

Language

Keywords

Institute

26 search hits