Interval-parameter optimization problems on graphs
- PDF / 157,991 Bytes
- 10 Pages / 595.276 x 793.701 pts Page_size
- 19 Downloads / 221 Views
CYBERNETICS INTERVAL-PARAMETER OPTIMIZATION PROBLEMS ON GRAPHS V. A. Perepelitsa,a† I. V. Kozin,a‡ and N. K. Maksishkoa††
UDC 519.86
Well-known optimization problems on graphs are considered under uncertainty when parameter domains are specified in the form of intervals. Exponential estimates of computational complexity of problems being studied and also problems that are polynomial in the classical formulation are substantiated. Polynomially solvable subclasses are found, and sufficient conditions of statistical efficiency of a proposed approximate algorithm are constructively substantiated. Keywords: interval optimization on graphs, computational complexity, polynomially solvable problems, statistically efficient algorithms. 1. DEFINITION OF A DISCRETE INTERVAL-PARAMETER OPTIMIZATION PROBLEM An optimization problem is usually specified as a computational problem in which a set of alternatives X = {x}and an objective function (OF) F ( x ) : X ® R are given and it is required to find an alternative x 0 Î X for which this OF assumes an extreme value F ( x 0 ) = extr F ( X ), extr Î {min, max}. For optimization problems, alternatives x Î X , x 0 , and X = {x} are xÎ X
usually called feasible solutions, an optimum (an optimal solution), and an acceptable solutions set (ASS), respectively. If the set X is discrete, then the corresponding optimization problem is called a discrete optimization problem. In actual practice, the result of a choice depends not only on an alternative x but also on definite parameters b1 , K , bL . If a vector b = ( b1 , K , bL ) Î R L , then the OF F ( x ) is an objective function F ( x, b ): X ´ R L ® R . In optimization, the exact values of all parameters bi , i = 1, L , are traditionally assumed to be known. In this case, the concept of an “optimum” is consistently explicitly defined as follows: a feasible solution x 0 is optimal if it minimizes (or maximizes) the objective function on X , F ( x 0 , b ) = min F ( x, b ) or F ( x 0, b ) = max F ( x, b ) . xÎ X
xÎ X
However, in many real-life situations, exact values of the parameters of the problem being considered are unknown. This can be explained as follows: first, such parameters are results of measurements, and these measurements are inexact in principle, and second, these parameters vary with time. In such situations, instead of the exact value of a parameter bi , only an interval B i = [ b i , bi ] of its possible values bi Î B i is known. As a result, it is only known that the parametric vector b belongs to the corresponding L-dimensional parallelepiped b Î B = ( B i , K , B L ) . In such situations, it is not clear how to formulate the corresponding optimization problem. A possible approach is as follows: since the exact value of bi for each feasible solution x is unknown, the exact value of the objective function F ( x, b ) is also unknown; hence, only the domain of possible values of this OF is known, F ( x , B ) = {F ( x, b ) : b Î B}. From the viewpoint of calculus of segments, this domain is an interval extension [1] of t
Data Loading...
