Analysis of algorithms for a class of continuous partition problems
type: Item
instance of: scholarly article
title: Analysis of algorithms for a class of continuous partition problems
zbMATH Open document ID: 0911.90241
DOI: 10.1007/BF02366365
author: E. M. Kiseleva
author: N. Z. Shor
published in: Cybernetics and Systems Analysis
publication date: 1995-05-17T00:00:00Z
review text: We consider a class of continuous problems of optimal partition of sets in the \(n\)-dimensional Euclidean space into nonintersecting subsets. Continuous optimal set partition problems arise in connection with some covering problems, global optimization problems seeking the attraction domains of local extrema, problems that find the nodes of optimal quadrature formulas for evaluation of integrals, computation of decision rules in nonlinear integer stochastic programming problems, and problems of statistical decision theory in which the criterion space is partitioned into disjoint classes. Moreover, a large body of important applied optimization problems are reducible to continuous optimal partition problems. These include, for instance, multicommodity plant location problems required to satisfy a continuously distributed demand, regional service planning problems, oil field outfitting problems, etc. Algorithm 1 proposed below solves continuous problems of optimal partition of sets in the \(n\)-dimensional Euclidean space \(E_n\) into nonintersecting subsets with determination of the center coordinates of the subsets. These are infinite-dimensional integer programming problems. The algorithm reduces the infinite-dimensional optimization problem to a finite-dimensional problem with a nonsmooth objective function, which is then solved by one of the modern methods of nondifferentiable optimization -- the \(r\)-algorithm. For the given class of partition problems, algorithm 1 generates a sequence that in general converges to local minima. We experimentally explore the efficiency of the algorithm and its ability to find the global minimum for the given class of partition problems, which in general are multiextremum optimization problems. Computational results are reported for some model of continuous optimal partition problems.
Mathematics Subject Classification ID: 90B85
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 746019
zbMATH Keywords: continuous optimal set partition
zbMATH Keywords: covering problems
zbMATH Keywords: infinite-dimensional integer programming
zbMATH Keywords: nonsmooth objective function
zbMATH Keywords: \(r\)-algorithm
MaRDI profile type: Publication
cites work: Q3036155
cites work: Q5187067
cites work: Q4205227
cites work: Q4040646
cites work: Q3197862
cites work: The Optimal Arrangement of Producers
cites work: Q4692345
cites work: Q3908420
full work available at URL: https://doi.org/10.1007/bf02366365
OpenAlex ID: W1970766790
description: scientific article; zbMATH DE number 746019