Optimization Problems with Interval Uncertainty: Branch and Bound Method
- PDF / 132,075 Bytes
- 11 Pages / 594 x 792 pts Page_size
- 63 Downloads / 231 Views
SYSTEMS ANALYSIS OPTIMIZATION PROBLEMS WITH INTERVAL UNCERTAINTY: BRANCH AND BOUND METHOD I. V Sergienko,a Ol. O. Iemets,b† Ol. O. Yemetsb‡
UDC 519.85
Abstract. An order on a set of centered intervals is introduced and is proved to be linear. An optimization problem is formulated over a set of centered intervals. The branch and bound method is proposed and substantiated to solve this problem. A number of theorems that substantiate estimates in the branch and bound method are proved. Keywords: optimization, interval uncertainty, branch and bound method. INTRODUCTION The need in practical results necessitates investigation into not clearly understood optimization problems of various classes with definite data (for example, see [1–3] for combinatorial optimization). For such problems, it is expedient to develop methods that take into account their specific features. Therefore, considering such problems and methods of their analysis for different forms of uncertainty, including interval one [4–11], is important. In the present paper, we will justify the general approach, within the framework of the branch and bound method (BBM), to the minimization problem in interval formulation. 1. NECESSARY CONCEPTS AND PROBLEM STATEMENT Let functional F ( x ) be defined on a set of centered intervals X ( x Î X ) [5, 6]); F ( x ) Î X , i.e., the value it takes is also an element of the set of centered intervals; D Ì X be feasible set of centered intervals. The studies [4–6] introduce arithmetic operations on intervals and elementary functions on X Ì R 1 . Let us consider how a linear order can be established on the set A = {a1 , K , a k } of centered intervals a i = ( a i , s i ), i Î J k = {1, 2,... , k }. Introduce characteristic comparators for the centered intervals denoted as a = ( a, s ) and understand them as an interval of the numerical axis R 1 , a = ( a - s , a + s ) Ì R 1 , where s ³ 0, a, s Î R 1 . Introduce characteristic comparators (in what follows, comparators) H1 , H 2 , and H 3 , which associate centered interval ( a, s ) with a real number according to the following rules: (i) H1 ( a, s ) = a 2 + s 2 sign ( a ) ; hereinafter, ì 1, a > 0; ï sign ( a ) = í 0, a = 0; ï -1, a < 0; î
a
V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine, aik@publiñ.icyb.kiev.ua. bPoltava University of Economics and Trade, Poltava, Ukraine, †[email protected]; ‡ [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, September–October, 2013, pp. 38–50. Original article submitted November 23, 2012. 1060-0396/13/4905-0673
©
2013 Springer Science+Business Media New York
673
ì a + s , a > 0, (ii) H 2 ( a, s ) = ( | a | + s ) × sign ( a ) = í î a - s , a < 0, if H1 ( a, s ) = H1 ( b, d ) ; similarly, H 2 is calculated for ( b, d ); (iii) if H t ( a i ) = H t ( a j ) , t = 1, 2, then a i ¹ 0, H 3 ( a i ) = a i , i Î J k . If a i = 0, then H 3 ( a i ) = s i . Denote by H = á H1 , H 2 , H 3 ñ the comparator of centered intervals, which is a sequential (if necessary) applicat
Data Loading...
