Analysis of algorithms for a class of continuous partition problems

DOI10.1007/BF02366365MaRDI QIDQ1842452zbMATH OpenOpenAlexFDO

Authors E. M. Kiseleva, N. Z. Shor

Publication date 17 May 1995

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02366365

zbMATH Keywords

\(r\)-algorithmcontinuous optimal set partitioncovering problemsinfinite-dimensional integer programmingnonsmooth objective function

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Continuous location (90B85) Integer programming (90C10)

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.

Recommendations

• scientific article; zbMATH DE number 4125186
• Solving a continuous nonlinear problem of optimal set partition with arrangement of subset centers in the case of a convex objective functional
• Optimality conditions and solution of a class of multicriteria continuous set partitioning problems
• An algorithm of solution of a multiproduct problem of optimal partitioning with constraints
• Solving a two-stage continuous-discrete problem of optimal partition-allocation with a given position of the centers of subsets

Cites work

• scientific article; zbMATH DE number 3830713 (Why is no real title available?)
• scientific article; zbMATH DE number 4173025 (Why is no real title available?)
• scientific article; zbMATH DE number 3718485 (Why is no real title available?)
• scientific article; zbMATH DE number 193848 (Why is no real title available?)
• scientific article; zbMATH DE number 4125186 (Why is no real title available?)
• scientific article; zbMATH DE number 194389 (Why is no real title available?)
• scientific article; zbMATH DE number 3894826 (Why is no real title available?)
• The Optimal Arrangement of Producers

Cited in

(16)

• Solution of continuous problems of optimal covering with spheres using optimal set-partition theory
• Analyzing a class of distributive partitioning sort algorithms
• Optimality conditions and solution of a class of multicriteria continuous set partitioning problems
• Application of the theory of optimal set partitioning for constructing fuzzy Voronoi diagrams
• Solving a two-stage continuous-discrete problem of optimal partition-allocation with a given position of the centers of subsets
• An algorithm of solution of a multiproduct problem of optimal partitioning with constraints
• Worst-case analysis of the differencing method for the partition problem
• Stochastic analysis of partitioning algorithms for matching problems
• scientific article; zbMATH DE number 1884455 (Why is no real title available?)
• scientific article; zbMATH DE number 3895078 (Why is no real title available?)
• Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals
• The features of solving of the set partitioning problems with moving boundaries between subsets
• A continuous problem of optimal partition with a nondifferentiable functional
• An analysis of the LPT algorithm for the max-min and the min-ratio partition problems
• Solving the dynamic optimal set partitioning problem with arrangement of centers of subsets
• Solving a continuous nonlinear problem of optimal set partition with arrangement of subset centers in the case of a convex objective functional

This page was built for publication: Analysis of algorithms for a class of continuous partition problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1842452)