Solution Branching in Partitioning Problems

Project Description

A given amount of stock is to be distributed onto a homogeneous group of consumers. Each of the consumers rates their benefit with the same profit function. We ask for the optimal total profit and the structure of the best distribution. In 1920, the economist DALTON formulated principles on the distribution of incomes. He has proposed convex criterions to mesure its quality, so that the uniformal distribution is the best one. We consider non-convex rating criterions and study the following parametric problem:

The goal function is symmetric w.r.t. permutations of the variables, the symmetric partition (uniformal distribution) is a stationary solution of this problem. We investigate the structure of the global minimum in dependence on the linking parameter c for strictly convex-concave functions f. Under some additional conditions on f, a branching between symmetric and non-symmetric sructures can be described. Certain convexity defect mesures contribute to an explanation of this phenomenon.

Following examples belong to this class of problems:

• Let be given m-tupels of convex figures, where each of them is inscribed in a circle. The minimal total area is to determine while fixing the total perimeter length.
• Let be given m-tupels of spherical caps with the same radius. The minmal total surface area is to determine while fixing the total volume.

The below represented figure demonstrates solution structures for the first example. Optimal triple are vertically illustreted.

 
Figure: Triple of circular inpolyeders