New Approaches to Solving Discrete Programming Problems on the Basis of Lexicographic Search
- PDF / 156,377 Bytes
- 10 Pages / 594 x 792 pts Page_size
- 63 Downloads / 192 Views
NEW APPROACHES TO SOLVING DISCRETE PROGRAMMING PROBLEMS ON THE BASIS OF LEXICOGRAPHIC SEARCH
UDC 519.854
S. V. Chupov
Abstract. New approaches are proposed to the solution of discrete programming problems on the basis of searching for lexicographic vector ordering for which the optimal solution to a problem coincides with the lexicographic extremum of the set of feasible solutions of the problem or is located rather close to it in the lexicographic sense. A generalized scheme of this lexicographic search and possibilities of its modification are described. Considerable advantages of this approach over the standard lexicographic search algorithm in efficiency are illustrated. Keywords: lexicographic order, lexicographic maximum, discrete programming problem, lexicographic search algorithm. INTRODUCTION Practical optimization problems require efficient algorithms for finding their solutions. Under present-day conditions, in connection with fast development of computer aids and various technologies, in particular, technologies of parallel computations, a demand arises for the development of new algorithms and methods allowing one to obtain optimal (or close to optimal) solutions within a reasonable time. This is especially topical because of the considerable increase in dimensions of real-world applied problems. In this work, such methods and algorithms are used with a view to increasing the efficiency of the lexicographic search algorithm for the solution of discrete optimization problems [1, 2]. PROBLEM STATEMENT AND BASIC DEFINITIONS Let us consider the following discrete programming problem: maximize under the conditions
x 0 = f 0 (x )
(1)
f (x ) £ b,
(2)
x ÎD,
(3)
where f : R n ® R m , b Î R m , D = D1 ´ D 2 ´ K ´ D n is a discrete set, and D j Ì [ a j , b j ] Ì R , j = 1, 2, K , n , are discrete sets. If f 0 ( x ) and the vector function f ( x ) are linear and each of sets D j , j = 1, 2, K , n , is a subset of integers, then problem (1)–(3) is a linear integer programming problem. We denote the solution set satisfying conditions (2) and (3) by X D . Assume that each variable of the problem is bounded both from below and from above, i.e., the set X D is bounded. We define the lexicographic ordering of vectors as follows: a vector x Î R n is Uzhhorod National University, Uzhhorod, Ukraine, [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 4, July–August 2016, pp. 43–54. Original article submitted November 10, 2015. 536
1060-0396/16/5204-0536 ©2016 Springer Science+Business Media New York
lexicographically positive, x > L 0 (> L is the sign of the relation “lexicographically larger”) if the first nonzero coordinate of this vector is positive; a vector x Î R n is lexicographically larger than a vector y Î R n , x > L y, if the vector ( x - y) is lexicographically positive, x - y > L 0 . The equality of vectors is ordinarily defined. In this ordering, any two vectors of one dimension are comparable among themselves. Based on the lexicographic ordering of vectors, the concept o
Data Loading...
