Properties of Combinatorial Optimization Problems Over Polyhedral-Spherical Sets
- PDF / 151,850 Bytes
- 11 Pages / 594 x 792 pts Page_size
- 76 Downloads / 219 Views
PROPERTIES OF COMBINATORIAL OPTIMIZATION PROBLEMS OVER POLYHEDRAL-SPHERICAL SETS S. V. Yakovlev1 and O. S. Pichugina2
UDC 519.85
Abstract. The class of combinatorial optimization problems over polyhedral-spherical sets is considered. The results of theory of convex extensions are generalized to certain classes of functions defined on sphere-located and vertex-located sets. The original problem is equivalently formulated as a mathematical programming problem with convex both objective function and functional constraints. A numerical illustration and possible applications of the results to solving combinatorial optimization problems are given. Keywords: combinatorial optimization, polyhedral-spherical set, continuous representation, convex extension. INTRODUCTION Combinatorial optimization problems are of permanent interest for researchers [1–6]. This class includes problems of Euclidean combinatorial optimization [7, 8] where combinatorial objects are mapped into arithmetic Euclidean space. The most important feature of discrete optimization problems is that the domain of feasible solutions is a finite set coinciding with the set of vertices of its convex hull. The studies [9–12] lay the foundation for the theory of convex extensions for functions defined at vertices of convex polyhedra. Analyses of special classes of Euclidean combinatorial sets and functions defined on these sets are described, in particular, in [13–20]. The current state of the theory of convex extensions and continuous functional representations for Euclidean combinatorial sets is presented in [21–33]. In the present paper, we will develop the main provisions of this theory in solving optimization problems on the set of Euclidean combinatorial objects. PROBLEM STATEMENT Let us consider a combinatorial optimization problem with the use of the concept of a combinatorial object introduced in [34–37]. Let J n = {1, 2, ..., n}, Z be a no more than countable space of isolated points, which we will call generating, and Z be basic set generated by it. By a combinatorial object we understand a triad ( y, Z , W ) , where y : J n ® Z is a homomorphism that satisfies some system of constraints W . The set J n is called numbering. Such definition of a combinatorial object is based on the concept of combinatorial configuration, introduced by C. Berge [38] as mapping of numbering set into some finite abstract strictly ordered set. Note that the requirements of finiteness and strict ordering are caused first of all by problems that arise in enumeration and construction of various classes of combinatorial configurations [38–41]. In the definition of a combinatorial object, these conditions are weakened without loss of the essence of the concept of configuration. 1
M. E. Zhukovsky National Aerospace University “Kharkiv Aviation Institute,” Kharkiv, Ukraine, [email protected]. 2Kharkiv National University of Radio Electronics, Kharkiv, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 1, January–February, 2018, pp. 111–123. Orig
Data Loading...
