Stability of a combinatorial vector partition problem
- PDF / 72,353 Bytes
- 4 Pages / 595 x 842 pts (A4) Page_size
- 92 Downloads / 221 Views
BRIEF COMMUNICATIONS STABILITY OF A COMBINATORIAL VECTOR PARTITION PROBLEM
UDC 519.8
V. A. Emelichev and E. E. Gurevskii
The vector variant of the partition problem is considered. It is shown that the coincidence of the Pareto and Slater sets is the necessary and sufficient condition of stability of the problem with respect to its functional. Keywords: multicriteriality, partition problem, stability.
As is well known [1] (see also [2–4]), the coincidence of Pareto and Slater sets is the necessary and sufficient condition of stability (with respect to the functional) of a vector (multicriteria) problem of integer linear programming with a finite set of feasible solutions. In this paper, we prove that the coincidence of these sets is also the criterion of stability of the vector variant of the classical partition problem that is as follows: divide a set of several numbers into two subsets so that the sums of elements in the subsets are minimal. In the case when the elements of a set are positive, this problem is equivalent to the scheduling-theory problem that consists of the distribution of independent tasks between two identical processors so that the moment of time at which the last fulfilled task comes to an end is minimal [5]. In scheduling theory, this problem is denoted by P | × |C max . By an m-criterion (vector) partition problem Z m (C ):min{ f ( x, C ): x Î Q n } , where f ( x, C ) = (|C1 x| , |C 2 x| , K , |C m x| ) , we understand the problem of searching for the set of efficient solutions (the Pareto set) P m (C ) = {x Î Q n : p ( x, C ) = Æ}. Here, p ( x, C ) = {x ¢ Î X : f ( x, C ) ³ f ( x ¢ , C ) & f ( x, C ) ¹ f ( x ¢ , C )}, C i is the ith row of a matrix C = [ c ij ] m ´ n Î R m ´ n , m ³ 1, n ³ 2 , i Î N m = {1, 2, . . . , m}, x = ( x1 , x 2 , . . . , x n )T Î Q n , and Q = {- 1, 1}. By virtue of the finiteness of Q n , the set P m (C ) is nonempty for any matrix C Î R m ´ n . It is obvious that, when x 0 Î P m (C ) , the solution - x 0 is also efficient in view of the equality f ( x 0 , C ) = f ( - x 0 , C ). Therefore, the Pareto set of the problem Z m (C ) always consists of an even number of solutions. Let us investigate the stability of the Pareto set P m (C ) with respect to perturbations of the parameters of the vector function f ( x, C ) by addition of perturbation matrices to the matrix C. To this end, we specify a metric l¥ in a space R k of arbitrary dimension k Î N, i.e., the norm of a vector z = ( z1 , z 2 , ... , z k ) Î R k is understood to be the following number: | | z | |¥ = max | z j | jÎNk
and the norm of a matrix is understood to be the norm of the vector composed of its elements. We also use the Belarus State University, Minsk, Belarus, [email protected] and [email protected]; [email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 177–181, May–June 2007. Original article submitted May 29, 2006.
462
1060-0396/07/4303-0462
©
2007 Springer Science+Business Media, Inc.
following denotation for any t Î R:
ì 1 if t ³ 0, sg t = í î - 1 if t < 0 . F
Data Loading...
