Stability radius of a vector integer linear programming problem: case of a regular norm in the space of criteria
- PDF / 126,467 Bytes
- 8 Pages / 595.276 x 793.701 pts Page_size
- 54 Downloads / 181 Views
STABILITY RADIUS OF A VECTOR INTEGER LINEAR PROGRAMMING PROBLEM: CASE OF A REGULAR NORM IN THE SPACE OF CRITERIA V. A. Emelicheva† and K. G. Kuzmina‡
UDC 519.8
A multicriteria integer linear programming problem of finding a Pareto set is considered. The set of feasible solutions is supposed to be finite. The lower and upper achievable bounds for the radius of stability are obtained using a stability criterion and the Minkowski–Mahler inequality and assuming that the norm is arbitrary in the space of solutions and is monotone in the space of criteria. Bounds for the radius of stability in spaces with the Holder metric are given in corollaries. Keywords: vector integer linear programming problem, Pareto set, Slater set, stability, radius of stability, perturbing matrix, norm of vector, space of criteria, space of solutions. INTRODUCTION The initial result of the qualitative theory of stability of vector discrete optimization problems is the theorem established in [1–3] (see also [4–8]). This theorem states that the coincidence of the Pareto and Slater sets is necessary and sufficient for the stability, with respect to the functional, of a vector integer linear programming (ILP) problem with a finite set of feasible solutions, which consists in searching for Pareto optimal solutions. The paper [9] investigates quantitative characteristics of the stability of such a problem. For example, the lower and upper ahievable bounds of the stability radius of a vector ILP problem are obtained for the case where the same Chebyshev norm is specified in the spaces of solutions and criteria. Note that upper bound of the radius of stability proposed in [9], which is the norm of the matrix of coefficients of a vector criterion, is rather rough. We will establish a more exact upper bound of this radius by using the above-mentioned necessary and sufficient stability condition. Moreover, we will use the Minkowski–Mahler inequality to generalize the estimates obtained earlier to an arbitrary norm in the space of solutions and to a norm in the space of criteria that satisfies some weak conditions (such norms are, for example, all the Holder norms l p , 1£ p £ ¥). Note that the Minkowski–Mahler inequality was earlier applied in [10] to derive the lower and upper achievable estimates of the radius of strong stability (T1 -stability as termed in [5–8]), and also in [11] to derive a formula for the radius of stability of the efficient solution of a vector ILP problem. BASIC DEFINITIONS AND AUXILIARY STATEMENTS Let R m be the space of criteria, R n be the space of solutions, C be an n ´ m matrix with the columns C i = ( c i1 , c i 2 , K , c in )T Î R n , i Î N m = {1, 2, K , m}, x = ( x1 , x 2 , K , x n )T Î X Ì Z n , and
1< | X | < ¥. Let a linear vector
criterion C T x = ((C1 , x ), (C 2 , x ), K , (C m , x ))T ® min
xÎ X
be specified on the finite set of integer vectors (solutions) X , ( × , × ) being the scalar product of vectors. a
Belarusian State University, Minsk, Belarus, †[email protected] and [email protected]; ‡[email protected]
Data Loading...
