QUADRATIC PROGRAMMING: QUANTITATIVE AND POLYNOMIAL RUNNING ANALYSIS TIME ALGORITHMS By JADRANKA SKORIN-KAPOV B. Sc. The University of Zagreb, Yugoslavia, 1977 M . Sc. The University of Zagreb, Yugoslavia, 1983 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F T H E REQUIREMENTS FOR T H E D E G R E E OF D O C T O R O F PHILOSOPHY in T H E F A C U L T Y O F G R A D U A T E STUDIES (Department of Commerce and Business Administration) We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F BRITISH C O L U M B I A August © 1987 Jadranka Skorin-Kapov , 1987 In p r e s e n t i n g t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of requirements f o r an advanced degree at the the University o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make it f r e e l y a v a i l a b l e f o r reference and study. I further agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying o f t h i s t h e s i s f o r s c h o l a r l y purposes may department or by h i s or her be granted by the head of representatives. my It i s understood t h a t copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed without my permission. Department of The U n i v e r s i t y of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date DE-6 (3/81) written Abstract Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {c x-\x Dx T with D : Ax <b T ,x>0} being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of entries of the matrices A and c and b but depends on the size of the D . Another part of the thesis is concerned with proximity and sensitivity of integer and mixed-integer quadratic programs. We have shown that for any optimal solution z for a given separable quadratic integer programming problem there exist an op- timal solution where n x for its continuous relaxation such that is the number of variables and determinant of the integer constraint matrix any feasible solution z A(A) nA(A) is the largest absolute sub- A . We have further shown that for , which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution function value and with \\z — X^QQ < \\z — 2||oo < nA(A). z having greater objective Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming problem with right hand side vectors linearly on b and b', respectively, depends ||6 — 6'||i. The extension to the mixed-integer nonseparable quadratic ii case is also given. Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say x i n+ . We determined a lower bound on the added objective function coefficients for which the new integer variable z -|_i remains n at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixed-integer case as well as to the case when integer variables are not resticted to be 0 or 1 . The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided. Finally, we have shown how to replace the objective function of a quadratic program with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovasz (1982). in T a b l e o f C o n t e n t s Abstract ii L i s t of F i g u r e s vi List of Tables vii Acknowledgement viii I. Introduction 1 1.1. Preliminary Definitions from Linear Algebra and Convexity Theory . . 2 1.2. Duality in Convex Nonlinear Programming 1.3. Integer Quadratic Programming 11 1.4. Some Transformations of Quadratic Programs 12 1.5. A Review of Polynomial Algorithms for Quadratic Programs 1.6. Basis Reduction Algorithm and Application to the Simultaneous Diophantine Approximation Problem 19 Towards a Strongly P o l y n o m i a l A l g o r i t h m for Strictly Convex Quadratic Programs 23 II. 8 . . . . 14 2.1. Setup of the Problem 24 2.2. The Quadratic Programming Algorithm 27 2.3. Extension to the Inequality Constrained Case III. P r o x i m i t y a n d Sensitivity Results for Q u a d r a t i c Integer Programming iv • . 37 41 3.1. Proximity Results for Separable Quadratic Integer Programming 3.2. Sensitivity for Quadratic Integer Programming : The Right Hand Side Case 49 Extension to Nonseparable Quadratic Mixed-Integer Programming 53 Nonlinear Integer Programs: Sensitivity Analysis for Branch and Bound 57 3.3. IV. . . 42 4.1. The Pure Nonlinear 0-1 Program 58 4.2. The Mixed-Integer Case 62 4.3. The Quadratic 0-1 Problem: A n Example 63 V. Simultaneous Approximation in Quadratic 0-1 Programming . 70 5.1. Setup of the Problem 72 5.2. Simultaneous Approximation of Objective Function Coefficients . . . 74 VI. Areas for Further Research 79 Bibliography 81 V L i s t Figure 4.1 o f F i g u r e s Branch and Bound Tree for Example 4 L i s t Table 4.1 of T a b l e s Sensitivity Analysis Sample for Example 4.1 vii 69 Acknowledgement I would like to express my sincere appreciation to the University of British Columbia and especially to the Faculty of Commerce and Business Administration for providing me with a financial support through : Dean Earle D. McPhee Memorial Fellowship in Commerce and Business Administration, University of British Columbia Summer Graduate Fellowship, University of British Columbia Graduate Fellowship and Graduate Travel Grant. My sincere thanks go to the Division of Management Science for giving me the opportunity to be one of their Ph.D. Students. I am deeply indebted to Professor Frieda Granot, my supervisor, for her guidance, many valuable comments and suggestions and for her friendliness and financial support. Furthermore, I would like to thank other members of my dissertation committee Dr Richard Anstee, Dr Daniel Granot and Dr Maurice Queyranne for their helpful suggestions. Finally, special thanks to my husband Darko for " sailing in the same boat " , and to our two little beauties Lea and Nina for sharing their mama with many hours of overtime work. V U l To the memory of my mother, Fumica Boljuncic, and to my father, Ivan Boljuntic . Chapter I INTRODUCTION Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. Moreover, some algorithms for solving large scale mathematical programming problems minimize a quadratic function over a polyhedral set as a subroutine, e.g. Held at al. [27] , Kennington and Shalaby [29] . Several methods that are based on solving a quadratic programming subproblem to determine a direction of search were also suggested for optimization problems with nonlinear constraints, e.g. Biggs [5] , Garcia and Mangasarian [20] and Gill at al. [21]. The existence of efficient quadratic programming algorithms and the fact that nonlinear functions can be sometimes accurately approximated by quadratic functions led to the development of approximation methods that make use of quadratic subproblems, e.g. Fletcher [18]. The above mentioned are just some of the reasons why the quadratic programming arose as a very important part of the rich theory of Mathematical Programming. We start by presenting in Section 1.1. some preliminary definitions from linear algebra and convexity theory to be used in this thesis. Many of the results in this thesis make use of duality. We will review the convex nonlinear programming problem and its dual as stated by Wolfe[49] and, as a special case in Section 1.2., a convex quadratic programming problem and its dual as stated by Dorn [13]. In Section 1.3. l we introduce integer quadratic programming problems. In Section 1.4. some transformations of quadratic programs which will be used in subsequent Chapters are summarized. We do not attempt to survey the algorithms suggested for optimiz- ing a convex quadratic function, rather we restrict our attention to polynomially bounded algorithms and review them in Section 1.5. A n introduction to lattices and the transformation of simultaneous Diophantine approximation problem to a short lattice vector problem will be given in Section 1.6. 1.1. PRELIMINARY DEFINITIONS F R O M LINEAR CONVEXITY ALGEBRA AND THEORY In this Section we first review some well known definitions and results the details on which can be found in any text-book of linear algebra. We are considering in this thesis the vector space R n ordered tuples of real numbers denoted as . The elements of R n are and refered to as vectors. The elements of R are called scalars and will be denoted by lowercase Greek letters a, /?, 7, etc. The function N(x) : R 1) N[x) > 0 for all x e R n n —•> R is called a norm if 2) N(ax) = \a\N{x) for all 3) N(x + y)< N{x) + N{y) if and only if , N{x) = 0 xeR for all n x= 0 ; , a eR; x , yeR n . We will use the standard notation || x || to denote the norm of a vector x . For 1 < p < oo the p-norm will be given by n xeR •n 2 (1.1) In this thesis we will make use of - ]Cr=i \ i\ t x IMh = \ i\ )^ X 2 n ^i-norm , e t n ^2-norm , e and |x||oo = max {|xj| : i = l,...n} the /oo-norm . These three norms are equivalent in the sense that for any x e R n , IMIoo < \\ h < Vn\\ \\<x> (1-2) IMloo < ll^lll < ^Iklloo (1-3) x x N | < ll^lli < V^Nh- (1-4) 2 For a scalar a, \a] (resp., [aj ) will denote the smallest (resp., greatest) integer not smaller (resp., not greater) than a . The of constraint sets of optimization problems to be treated in this thesis are sets linear equalities and (or) inequalities which are usually stated in matrix form, therefore the second algebraic object of our interest are real matrices. Unless otherwise stated, in our thesis vectors are considered as column vectors, i.e. x e R n is an n x 1 matrix. Transposition applied to a vector x (resp., matrix A ) will have the usual notation x For 1) T (resp., A ). our purposes , some special square matrices deserve to be mentioned here. Identity m a t r i x / : / = (<5iy)"y Nonsingular matrix matrix B such that , =1 2) D i a g o n a l m a t r i x D : 3) T D = (dtj)"y A : A S- = l} , =1 J 1 for i = j \ 0 for i ^ j . dij = 0 for i ^ j. is nonsingular if and only if there exist a AB = BA = I . refered to as the inverse of A . 3 B is usually denoted as A -1 and is 4) Symmetric matrix A : A is symmetric if and only if A = A T . 5) Positive Semidefinite matrix A : A is positive semidefinite if and only if x Ax T > 0 Vx eR . A is n positive definite if in addition x Ax = 0 implies T x= 0 . 6) Idempotent matrix P : P is idempotent if and only if P = P . 2 The vectors a^, ...,x are said to be r linearly independent if and only if their linear combination vanishes in a trivial way only , i.e. OL\X\ + ... + a x r r = 0 implies ai = ... = a — 0 . Otherwise, the vectors are said to be T dent and each vector x; with linearly depen- ^ 0 can be expressed as a linear combination of the remaining vectors. row ( resp., column ) rank of an n x n matrix A is the number of its A linearly independent rows ( resp., columns ). The row and column rank of a given matrix always coincide and will be denoted by r(A) to be refered to as the rank of the matrix. A nonsingular n x n matrix A has a full rank , i.e. r[A) = n . determinant is a function that assigns to each n x n matrix A with columns A A\,...,A n a scalar value denoted by det A that hasthe following properties: For each scalar a and each i = 1) det(Ai,...,aAi,...,A ) n l,...,n = adet(Ai,Ai,A ) n 2) det(Ai,.., A{,.., Aj,.., A ) n , = det(Ax,..,Ai + aAj,.., Aj,.., A ) for each j ^ i , n 3) det(I) = 1 . As a consequence, it can be observed that det A for a singular matrix A is equal to zero. For a nonsingular matrix with all entries integral , det A is not less than one. 4 For n > 3 , determinants are very inefficient as a computational tool, but they are useful to obtain some theoretical results. For example, if A is an n x n nonsingular matrix then the cofactor of any element a cofa = {-l) detA , rs (1.5) r+s rs where A of A is defined as rs rs is the (n — 1) x (n — 1) matrix obtained from A by deleting row r and column s. The inverse matrix A~ can then be stated as 1 A - 1 = —^—cornA de*A v (1.6) ' where com A is the transpose of the matrix of cofactors of A . The unique solution x T — (x l5 ...,x ) to a linear system Ax — b where b is an nxl n detAi X i = -teZ vector is given by . ' t= 1 . '-' n ( L 7 . ) where A{ is the n x n matrix obtained by replacing the i-th column of A by the vector 6 (Cramer's rule ). A n upper bound on the value of detA is given by the following inequality \detA\ < ||oi||2---||°n||2where a\,...,a n (1-8) are columns of A (Hadamard's inequality). Combining (1.2) with (1.8) implies that if A = (aiy) with \a.ij\ < a for all i , j , then \detA\ < a ni. n For an m x n matrix A we will denote by A ( A ) = max { \detH\ : all square submatrices H of A}. 5 The scalar A(A) , where is the constraint matrix of a quadratic optimization A problem, will play an important role in many results of this thesis. For an m x n matrix A , the matrix norms to be considered in this thesis are m \\A\\i = max > |a -y| , 1 <j<n i= l n ||A||oo = max \ \a.ij\ . Ki<m ~ ~ j=l (1-9) t (1-1°) The matrix norms are consistent with the vector norms in the sense that ||-As||i < ||A||i||x||i H-^xlloo < , II^Hooll^lloo Next, we will review some definitions from convexity theory (see for example Stoer and Witzgall [44]). A function / : R i) —> R U {+oo, —oo} is convex if {x : f{x) = -oo} = 0 , ii) {x : f{x) < iii) n ^ 0, +00} f{Xx + (1 - A)y) < A/(x) + (1 - X)f[y) EXAMPLE for 0 < A < 1 and x, y e R . n A quadratic function f(x) = c x + ^x Dx T T with D positive semidefinite is a convex function. This since {x-y) D{x-y) >0 T x, y and therefore x Dx T + y Dy > 2x Dy T T symmetric which in turn implies /(Ax + ( l - A ) y ) = c (Ax + (1 - A)y) + f (Ax + (1 - A)y) 7J(Ax + (l - A)y) T T = A c x + (1 - A)c y + \\ x Dx r T 2 T + 1(1 - \) y Dy 2 6 T + A(l - \)x T Dy for all < Xc x + (1 - \)c y T T + \X x Dx 2 + \(l - T + |A(1 - X)x Dx + \X(l - T T = Xc x + (1 - X)c y + \Xx Dx T 2 X)y Dy T T X) y Dy + |(1 - T X)y Dy T = Xf(x) + (1 - X)f(y) . If D is positive definite, then f[x) = c x-\-\x Dx is a strictly convex function. T T With regard to the optimization of a convex function, recall that every local minimum is a global one and that a strictly convex function has a unique minimum. If / convex, then — / A set is is concave. S C R n is said to be a if it contains all convex set combinations of its elements, i.e. for any x , x 1 2 , x s e S , Yli=i i w x% convex e & f° r a u Wi > 0 , V i and X2i=i i ~ 1 • w If Yli-i S contains all nonnegative linear combinations of its elements , i.e. W{X , tu,: > 0 for all i , then it is called a l convex cone . The solution set P of a finite system of linear inequalities Ax < set refered to as a is a convex polyhedron . A cone which is a polyhedron is called a polyhedral cone and it is the solution set of some homogeneous system of linear inequalities Ax < 0 . In Chapter III we will use the following theorem due to Minkowski (which is a special case of Caratheodory's theorem see e.g. [44], page 55): THEOREM PROOF 1.1.1 Every polyhedral cone has a finite set of generators. See Stoerand Witzgall [44], Theorem 2.8.6., page 55. • 7 1.2. D U A L I T Y IN C O N V E X N O N L I N E A R PROGRAMMING Although our thesis is concerned mainly with quadratic programming, the results presented in Chapter IV were shown to be valid for a broader class of problems, namely for convex nonlinear programs in which some variables are restricted to be integral. In this Section we will review a duality for convex nonlinear problems as introduced by Wolfe [49] and will then state a duality theorem of Dorn [13] for a special case of quadratic convex programming problems. Consider the following nonlinear programming problem min {f{x) where x is an n x 1 vector, : gi(x) > 6,-, i = 1 , m / is (resp., } (l-ll) gi ,i = l , . . . , m differentiable convex (resp., concave) functions on R n are) real valued, . Denote by S a set of feasible solutions to (l.11). In the sequel we assume that on the boundary of the constraint set no singularities will occur, i.e. that some constraint qualification is satisfied. (For detailed discussion on constraint qualifications see e.g. [3] or [36].) For example, we can assume Abadie's constraint qualification (see [4]) of the following form to be valid. Let x e S , then every z satisfying Vg (x) z T l > 0 for all i such that gi{x) = b{ has to be an element of a cone of tangents T = { z :z = lim X (x n n - x), x n e S, X > 0 n n—>oo for all n, lim x n = x }. n—>oo If the constraints are all linear, this constraint qualification is automatically satisfied. (See Bazaraa [4], Lemma 5.1.4., page 164.) The Karush-Kuhn-Tucker necessary optimality conditions (which are also sufficient optimality conditions under suitable convexity assumptions) are as follows. 8 If x is an optimal solution to problem (1.11) under some constraint qualification condition, then there exists a vector u > 0 such that V/(x) = u Vg(x) T and u {g{x) - b) = 0 . T For problem (1.11) Wolfe's dual [49] is given by max b u + f(x) — u g(x) T s.t. T u Vg(x) = V / ( x ) (1.12) T u > 0 where b = (b T u 6 ) m and ff(x) = (gi{x), ...,g (x)). T m If all the constraints are linear, then the objective function of (1.12) can be equivalently written as b u + f(x) — x V f(x) . T T Consider now the convex quadratic programming problem min {c x + \^x Dx : Ax > b,x > 0} T where D (1-13) T is a symmetric positive semidefinite n x n matrix , c and x are re x 1 vectors , b is an m x 1 vector and A is an m x re matrix. Positive semidefiniteness of the matrix D implies convexity of the objective function. As stated by Dorn [13] a dual of problem (1.13) can be written as max {b u - ~x Dx T T : A u - Dx < c,u > 0} . T (1.14) The Karush-Kuhn-Tucker optimality conditions for a pair of problems (1.13) and 9 (1.14) are the primal and dual feasibility conditions Ax > b (1.15) x>0 Au — Dx < c T u > 0 , and the complementary slackness conditions x (c - A u + Dx) = 0 T (1.16) T u {Ax - b) = 0 . T The existence theorem for quadratic programming states that the feasibility of both the primal and dual programs implies the existence of optimal solutions for each of them . The following theorem is taken from Dorn [13]. THEOREM (u ,x ) 0 ii) 0 1.2.1 i) If x = x is a solution to (1.13) , then a solution [u,x) = exists to problem (1-14) such that Dx = Dx . 0 Conversely , if a solution {u,x) = (uo,Xo) to problem (1.14) exists, then a solution x which satisfies Dx = DXQ exists to problem (1.13). In either case the objective function values for (1.13) and (1.14) are equal. PROOF See Dorn [13], page 156. • Also, if one of the problems (1.13) or (1-14) is feasible while the other is not, then on its constraint set the objective function of the feasible program is unbounded in 10 the direction of extremization (see [13] ). The Fundamental Theorem of linear programming states that if a linear program has an optimal solution, then it has one which is a basic solution of a linear system of constraints. For a quadratic programming problem this is, however, not the case. An optimal solution for a quadratic programming problem may occur everywhere in the feasible region, in the interior as well as on the boundary. Consideration of nonbasic solutions makes quadratic programming more difficult than the linear one. However, if a quadratic program has an optimal pair (x , u ) T T of primal and dual solutions satisfying (1.15) and (1.16)), then it has one which is a basic solution for the system of linear equalities and inequalities (1.15) or, equivalently, a solution that is a vertex of a polyhedron defined by (1.15). Combined with Cramer's rule (see (1.7)) this fact gives us a way to bound the values of the primal and dual variables. This will be discussed in more detail in Section 1.5. 1.3. INTEGER QUADRATIC PROGRAMMING Many real world problems require a mathematical programming formulation in which all or some of the variables are restricted to be integral. Moreover, a quadratic objective function enables one to take into account the interactions between variables. The applications in, for example, finance [34], capital budgeting [31] or scheduling [40] have natural representations as 0—1 quadratic programming (i.e. integer quadratic programming in which the variables are restricted to be zero or one). In this thesis we will consider a general mixed-integer quadratic programming problem and will discuss some sensitivity aspects of it (see Chapter III and IV) as well as a transformation of the objective function coefficients in Chapter V . 11 1.4. SOME TRANSFORMATIONS OF QUADRATIC In some cases the form of the objective function PROGRAMS c x + x Dx T of a quadratic programming problem is not suitable for our purposes. In this event some transformations are performed to obtain an equivalent quadratic programming problem of suitable form. In this section we will list the transformations of the objective function to be used in subsequent chapters. Consider, for example, the quadratic cost matrix D . Without loss of generality one can assume that D is symmetric since, if not, D = ^(D + D ) T replacing D x Dx T by D is symmetric and in a quadratic programming problem of the form min {c x + T : Ax > b, x > 0} will not change the objective function value. Suppose, next, that we have a quadratic 0 — 1 minimization problem of the form min f(x)=c x + T x Dx T s.t Ax > b (1.17) 0 < x< 1 x integer If we want to solve this problem by implicit enumeration where at each node the continuous relaxation of a corresponding integer subproblem is solved, then we would like to ensure the convexity of the objective function (in order to avoid local minimum points). If D is not positive semidefinite, it is shown in [25] that problem (1.17) can be replaced by an equivalent problem in which the objective function is given by f'(x) = {c -Xe )x T where e T = (l,...,l) and T + x {D + XI)x T A is a positive scalar such that 12 (1.18) D + XI is positive semidefinite. This is due to the fact that x = x for any vector x of zeros and 2 ones. It is often desirable to have a homogeneous quadratic form in the objective function of a quadratic programming problem. This can be achieved by adding a new variable and a new constraint. For example, for problem (1.13) an equivalent homogeneous problem is min \{x M(° )C ) C T T Q s.t. a Ax > 0 (1.19) a = 1 x > 0. Note that if D is positive definite adding a constant to the objective ~c D~ c T 1 function results with a convex quadratic program since the matrix is positive definite ( observe that ac D- ) 'D{x 7 l T (XT,OJ)(^ T C D- c)i.'a) 1 c a n ^ e w r n Tr)-i ) c c ^ e n as (x + + ac 'D~ ) ). 1 l An alternative way to homogenize the objective function of a strictly convex quadratic programming problems is to leave the matrix D unchanged, but to change the right hand side vector. This by replacing the vector x in (1.13) by z — D~ c . l The resulting problem is ~-c D~ c 2 T 1 + min s.t. -z Dz T 2 Az >b + AD'h Iz- Ix = D' c l x > 0. 13 (1.20) We will employ this transformation in Chapter II. Due to the fact that a positive semidefinite matrix can be diagonalized, we shall see in Chapter III how a convex quadratic programming problem can be replaced by an equivalent separable convex quadratic programming problem. Without loss of generality assume that a positive semidefinite matrix C is of the form ( Q ° ) where A = (<x-y) is positive definite (this can be done by a change t of coordinates). Using the diagonalization for positive definite matrices proposed in [48], we obtain (1.21) A = LDL T where D is a positive diagonal matrix and L is lower triangular with ones on the diagonal. The entries in D and L are determined using the following equations (which are modifications of the equations from Cholesky's decomposition) j J Z Likdktjk = a,ij k=l giving j'-i tijdj = o-y - ^ t d lj k=l t ik k , j = 1 , i - l k x , (1-22) i— 1 UkdkUk = an giving d, = a i{ - ^ l d l . i k k i k (1.23) fc=l k=l From (1.21) if follows that C can be written as ( Q ) D ( L , 0 ) . Observe that no T T square roots appear in the process of diagonalization. 1.5. A REVIEW OF POLYNOMIAL ALGORITHMS FOR QUADRATIC PROGRAMS Let us start this Section with some preliminary definitions (see for example [43] or [45]). 14 1) The dimension of the input is the number of data in the input of a given optimization problem. (Therefore, each number adds one to the dimension of the input). 2) The size of a n u m b e r is the length of its binary description (i.e. the number of bits needed to record a given number in a binary format). For a rational number ^ its size s(^) is given by *{-) Q = \ °92(P l A size of a rational vector given by 3) The s(r) =n + Y!i=i r s T + 1)1 + \ °92{q l = (r ...,r ) { i) r l 5 n (resp., s(A) elementary arithmetic operations + l)] + 1 . (resp., matrix = mn + £ i y (1.24) = A s(a ) {j {o-ij)j =1 j-y ) is ). are additions, comparisons, mul- tiplications and divisions. 4) A n algorithm's r u n n i n g time is the number of arithmetic operations per- formed in it. 5) A n algorithm is polynomial if it has running time polynomial in the dimen- sion and in the size of the input and, when applied to rational input, the size of the numbers occuring in it is polynomially bounded by the dimension of the problem and the size of the input numbers. 6) A n algorithm is strongly p o l y n o m i a l if it has running time polynomial in the dimension of the input and, when applied to rational input, the size of the numbers occuring in it is polynomially bounded by the dimension of the problem and the size of the input numbers. Note that the merit of a strongly polynomial algorithm lays in the fact that its running time is independent of the size of the input data. 15 In 1979 HaCijan [24] proved that a linear programming problem is polynomially solvable. In his result the size of the input was a very important constant. For the sake of completeness, let us state some well known results with respect to the size of the input. THEOREM 1.5.1 Let A be a square rational matrix of size a . Then the size of det(A) is less then 2cr . PROOF See Schrijver [43], Theorem 3.2., page 29. • Consider a polyhedron P — {Ax < b} and assume that A and b are integral. Denote by L the size of the input for P . LEMMA x° 1.5.2 If the system Ax < b is consistent, then there exists a solution in the Euclidean ball S = {x : \\x\\ < 2 PROOF L } . See Hacijan [24], Lemma 1. • As a consequence of Hacijan's result, in the same year Kozlov, Tarasov and Hacijan [30] gave a polynomial algorithm for quadratic programs with n variables and m constraints of the form min f(x) = d x + -x Cx T T (1.25) s.t. Ax < b where C is an integral symmetric positive semidefinite matrix and all other input 16 data are integrals as well. The size of the input was defined as YI °92(\cij\ + 1) + Y M\ j\ L= l lo m,n + + 1) d m Y 0 2 ( h y | + 1) + Y^ °92{\k \ + 1) + log mn ij = l i=l / o l 2 + 1. (1.26) Now, if problem (1.25) has a solution, it has a pair of optimal primal and dual variables (x ,y ) T T which is a vertex of the polyhedron P' defined by Ax < b Ay -Dx T (1.27) = d y >0. Observe that the length L' of the input data for P' is not greater than 2L . Using Lemma 1.5.2, one can then give an upper bound to the components of Namely, any component of integers such that will have the form (x ,y ) T \t\ , \s\ < T 2L ^) L \d I x+ T T T where t and s . are . Since the objective function is quadratic, the 2 smallest rational number will be | (x ,y ) ~ 2 2^ -x Dx\ T 2 a n c l <- * n 2 5L e n c e . After checking the compatibility of a system of linear equalities and inequalities (1.27), Kozlov at al. found the exact value /o = | of the objective function. This was done by checking the compatibility of 13L + 2 systems P^ of the form Ax < b f[x) < . where tk and Sk are integers such that \tk\ < 2 17 1 3 L + 2 and \sk\ < 2 8 i + 2 . Having the objective function value of (1.25), an exact optimal point was obtained. Helgason, Kennington and Lall [28] gave a polynomially bounded algorithm for a class of singly constrained quadratic programming problems of the form — ax min -x Dx 2 n T s.t. where D T YZ J j=i 0<x<b X = l - ) 1 c is a positive diagonal matrix and is a nonnegative vector. b 2 8 This very specific problem arised in a decomposition procedure to solve multicommodity network flow problems using subgradient optimization. The structure of the objective function and constraints enables one to explicitly represent the primal and dual variables as a function of a single dual variable constraint ]Cy=i j x = c )• A The optimal value of binary search on the interval with (the one associated with the A can be found by using a 2n points. According to definition, since the number of elementary arithmetic operations is polynomially bounded by the number of variables, Helgason at al.'s algorithm for solving the restrictive class of problems (1.28) is strongly polynomial. A more general class of problems was studied by Minoux [39]. He devised a polynomial algorithm for minimum quadratic cost flow problems of the form min ^2 ^u{<Pu - <Pu) utU s.t. A<p = 0 2 b < fu < c u u (1.29) , VueU where U is the set of arcs and A is the node-arc incidence matrix of a given graph, 18 b u (resp., c ) is the integer lower (resp., upper) bound on the flow value <p on u u arc u , <p are integer constants and OJ are positive numbers for each u . u U Minoux's algorithm consists of solving a number of successive approximations of the initial problem, obtained by replacing the quadratic cost function with a piecewise linear convex cost function, using the out-of-kilter algorithm. The approximations are iteratively refined until a point, sufficiently close to the optimal solution of the initial problem, is obtained. Using the fact that for convex quadratic programs with nonempty feasible sets there exist an optimal point which is a basic solution of the polyhedron defined by the primal and dual constraints, the minimal distance between two basic solutions defines the sufficient approximation to locate the optimal solution. Since the number of approximations is polynomially bounded by the input size and the out-of-kilter is a polynomial time algorithm, the polynomial bound on the running time of Minoux's algorithm follows. A drawbeck of Kozlov at al. and Minoux's algorithms is that their running time depends on the input size. It is still an open question whether there exist an algorithm for solving convex quadratic programming in strongly polynomial time. In Chapter II we will present an algorithm for strictly convex quadratic programming problems which runs in time independent of the size of the linear cost coefficients and the right hand side vector. 1.6. B A S I S R E D U C T I O N A L G O R I T H M A N D A P P L I C A T I O N T O T H E SIMULTANEOUS DIOPHANTINE APPROXIMATION PROBLEM We start this Section by introducing a lattice and a problem of finding a short vector in it. We then state the simultaneous Diophantine approximation problem and show how it can be transformed into a short lattice vector problem. More detailed 19 discussion can be found in e.g. Lovasz [35] or Schrijver [43]. Let points basis di,...,a n be linearly independent real vectors in x = Z\a,\ + ... + z a n with integral n zi,...,z n R n . The set of all is called a l a t t i c e with A = (ai,...,a ) and denoted by A(A) . A lattice is an additive group and n its importance follows from the fact that it is the most general group of vectors in an n—dimensional space which contains n linearly independent vectors and which further satisfies the property that there is some sphere around the origin which contains no other vector of the group except the origin. The basis is not uniquely determined by the lattice. For example, we can define n a' = y2 ij j j=i J v > i = l,...,n a i where Vij are any integers with det(vij) =_ 1 . Then each a X2y=i ij 'j w (1.30) t can be written as with integral tu,-y . Substituting this expression into (1.30) and using a the linear independence of a; , it follows that Y^WMi 1 = {l if i = I , otherwise . Hence, det(wij)det(vij) = 1 implying det(u>ij) = det(vij) =t. 1 • It follows then that det(ai,-...,a ) =1 det{a\,...,a' ) . (See for example Cassels [7]). We can, therefore, n n define the d e t e r m i n a n t o f a l a t t i c e , detA = |det(A)| where A = (ai,...,a ) n is any basis of the lattice. Geometrically, detA denotes the volume of a parallelopiped whose vertices are lattice points and which contains no other lattice point. An upper bound of detA is given by Hadamard's inequality detA < 1 1 «x 1 i 2 '" [| 112 - A lower bound of detA is due to Hermite (1850) and is given as follows. 20 Every n—dimensional lattice A has a basis ( 6 1 , . . . , b ) n IM| ---||M2 < 2 where c n c such that ndetk (1.31) is a constant depending only on n . This result led to the question of finding such a basis. As stated by Minkowski, the solution to the above problem always exists provided c n > (f^) 2 • To find a basis in the lattice for which the product of the euclidean norms of its vectors is n(n— 1 ) minimal is NP—hard. However, for a weaker bound, taking c gave a polynomial algorithm to find a basis satisfying (1.31). n 4 = 2 , Lovasz (See Lenstra at al. [33]). A related problem is the following (Short Lattice Vector Problem) : Given an n—dimensional lattice A and a number A , find a vector b e A , b 7^ 0 such that H&H2 < A. A classical result of Minkowski implies that for A > 2^J-^- y/detk such a vector e always exists, but no polynomial algorithm to find it is known to date. The shortest vector in the reduced basis obtained by Lovasz's basis reduction algorithm has a length at most 2~*~~ \fdetk . This is not the shortest vector in the lattice, however it is very useful in some applications. Consider, for example, the Simultaneous Diophantine Approximation Problem (see e.g. Lovasz [35]) : Given c c i , . . . , a e Q , 0 < e < 1 and Q > 0 find integers n pi,..,p n and q such that 0 < q < Q , | a » - - | < - ^ 21 , t= l,...,n. (1.32) A classical result due to Dirichlet (1842) is the proof of the existence of integers q and i = 1, ...n such that (1.32) is satisfied, whenever Q > s~ algorithm to find these integers is known (except for the case n . No polynomial n = 1 when the method of continued fractions can be applied). However, a weaker approximation IC / " > > (for Q > 2 n.(re+1 ) _ 4 e n ) can be found by transforming this problem into a short lattice vector problem and using Lovasz's basis reduction algorithm as follows [35] : Consider the lattice A(A) generated by the columns of the (n + 1) x (n + 1) nonsingular matrix 0 / l ai\ 0 1 oc Vo Q n Any vector b eA(A) has the form b = (px + p T where p T = (p . . . , p l5 n + 1 ) e n + 1 o : i , ...,p + p n n + ia ,p n n + 1 -|) , . Suppose that 6 ^ 0 but ||6|| < e . This implies 2 Pn+\ 7^ 0 . Without loss of generality assume p + i < 0 and denote q = —p i . It n n+ follows then that \bi\ = \pi — qoti\ < E , E >n+l | q< (1.33) i = l,...,n (1.34) or q < 0. E The shortest vector in the reduced basis of a lattice A(/l) obtained by Lovasz's algorithm satisfies ||6|| < 2* " < / + de<A 2 E and hence ||&||oo < (^) = * ( f ) ' 2 4 l • F o r 0- = Z^^e < ||^||2 < £ • We .shall make use of Lovasz's basis reduction algorithm in Chapter 5 in order to find simultaneous approximations of the objective function coefficients of a given quadratic integer programming problem. 22 Chapter II TOWARDS A STRONGLY POLYNOMIAL ALGORITHM FOR STRICTLY CONVEX QUADRATIC PROGRAMS In [45] Tardos was the first to present a polynomial algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. The aim of this Chapter is to extend Tardos' results to convex quadratic programming problems of the form max{c i - ~x Dx : Ax < b, x > 0} with D being T r a positive definite matrix. We assume, without loss of generality, that A and D are integral. We develop a polynomially bounded algorithm for solving the strictly convex quadratic problem where the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D. If in particular the size of the entries in A and D is polynomially bounded in the dimension of the input, the algorithm is strongly polynomial, e.g., when the quadratic term corresponds to a least squares and A is a node arc incidence matrix of a directed graph. Following Tardos [45] the algorithm presented here finds optimal primal and dual solutions to the quadratic programming problem (if they exist) by solving a sequence of simple quadratic programming problems using the polynomial algorithm 23 for solving quadratic programming problems given in [30] and by checking feasibility of a linear system in time independent of the right hand side using Tardos' feasibility algorithm [45]. 2.1. SETUP OF THE PROBLEM For simplicity of exposition we will first consider the quadratic programming problem of the form max { c x — -x Dx T : Ax = fe, x > 0 } T (2.1) where A is an integral m x n matrix with rank (yl) = ra; D is an integral n x n symmetric positive definite matrix; c and x are n-vectors and fe is an m-vector. The validity of the algorithm for quadratic programming problems with inequality constraints will be discussed in Section 2.3. Using the fact that D is nonsingular we can substitute z ~ x — D~ c l in (2.1) resulting with the following equivalent problem ^c D- c T l + max {~z Dz T : Az = b - AD~ c x Recall that positive definiteness of D , lz- Ix= -D~ c x , x > 0}. (2.2) implies that the objective function of (2.1) is strictly concave which in turn implies the uniqueness of the optimal solution of (2.1) (if one exists). Moreover, if the set {x : Ax —fe,x > 0} is not empty, (2.1) will be bounded. The uniqueness of the optimal value of x implies also the uniqueness of 24 the optimal value of z; however observe that z is not restricted to be non-negative any longer. Using now Dorn's duality [13], we can state a dual of the maximization problem given in (2.2) as min {y {b - AD~ c) T - v D~ c l T Substituting v = — Dz — A y T min {y {b T min {y b T - AD~ c) l - y AD~ c T l 1 + -z Dz 2 + Iv + Dz = 0, t; < 0}. :Ay T T (2.3) results with (see Section 1.4) + [y A + z D)D' c T T + y AD~ c T + -z Dz 2 1 + z c + -z Dz 2 l :Ay T T T T :Ay T + Dz>d} = + Dz > 0}. Finally, after adding slack variables 5 , we get a dual of (2.2) of the form -c D~ c 2 T 1 + min {c z T + b y + -z Dz 2 T It is easy to see that replacing z :Ay T T by x — D~ c l + Dz - Is = 0, 5 > 0}. (2.4) will give us the following dual of (2.1) min {b y + ^x Dx T T :Ay T + Dx - Is = c, s > 0}. (2.5) It is important to note that the same slack variables appear both in (2.4) and (2.5). Since the algorithm to be described in the following is significantly simpler when applied to problems with zero right hand side, we will always use the above transformation to replace a pair of primal and dual problems of the form (2.1) and (2.5) by an equivalent pair of the form (2.2) and (2.4). Recall that the Karush-Kuhn-Tucker optimality conditions for a pair of problems (2.1) and (2.5) will have the form 25 (2.6) x,s > 0 and x s = 0 . At each iteration of the algorithm to follow we will detect at least one new slack variable which is equal to zero in all optimal pairs of primal and dual solutions for the pair of problems (2.1) and (2.5). Or equivalently, at each iteration we will detect at least one new dual constraint which is tight at optimality. After each iteration we will add constraints of the form Si = 0 , i E I (where J is the set of slack variables detected to be zero at the current iteration) to the linear system given in (2.6) and perform Tardos' feasibility algorithm which will give us a feasible solution (x ,y ,s ). T T T We will check if x s = 0. If so, the algorithm will terminate since T an optimal pair of primal and dual solutions was determined. If on the other hand xs 0, we will perform another iteration of our algorithm. In at most n iterations T we will find a pair of optimal primal and dual solutions. As stated above the algorithm will be applied to a minimization problem of the form mm {c z + b y + ~z Dz T T : Dz + A y - Is = 0, s > 0}. T (2.7) T Before stating the algorithm we will give two preliminary lemmas. The first one is a direct generalization of Lemma 0.1 in [45], while the second is a special case of Lemma 2, p. 707 in [15]. LEMMA P (D,A , T T PROOF 2.1.1 Replacing ( c , 6 , 0 ) in (2.7) by {c' ,b ,a' ) T T r T ,T = (c ,b ,0 ) T T T T I) forsome n-vector p will not change the set of optimal solutions. If (z ,y ,s ) T T T solves (2.7), then it also solves the problem obtained from (2.7) by replacing the linear cost coefficient 26 ( c , 6 , 0 ) by (c' , b' , a' ) and T T T T T T vice versa. This since z (c J ,b ,a -±z Dz + = T ( \z Dz-(e y,0 ) T T -p (D,A ,-I) T T y T -p 0 T z^ y =o which is a constant. • LEMMA If (z ,y ,s ) 2.1.2 T T quadratic problem in which solve (2.7), then T (c ,b ,0 ) T T T (az , ay , as ) T T solves the T in (2.7) is replaced by a[c ,b ,0 ) T T for T any scalar a > 0. PROOF Let (z ,y ,s ) T T ab (ay) + \{az) D(az) T solve (2.7). Then for any scalar a > 0 , ac (az) + T T = o?{c z + b y + ~z Dz) T T solves (2.7) in which (c , b ,0 ) T T T T T and, therefore, was replaced by a(c ,b ,0 ) T T T Q:(2 ,y ,5 ) T T R . • We are now ready to describe the polynomial quadratic programming algorithm whose number of arithmetic steps is independent of the size of the numbers in the vectors c and b . 2.2. T H EQUADRATIC P R O G R A M M I N G ALGORITHM The Q U A D R A T I C P R O G R A M M I N G A L G O R I T H M (QPA) described below is a direct generalization to a class of strictly convex quadratic programming problems of Tardos' linear programming algorithm. It uses as input a strictly convex quadratic 27 program (2.1), Tardos' feasibility algorithm, which is a polynomial algorithm to check the feasibility of a system of linear inequalities in time independent of the right hand side and if feasible it generates a basic solution, and a polynomial algorithm for solving convex quadratic programming problems, e.g., Kozlov et al.'s algorithm. The output from Q P A is a pair of optimal primal and dual solutions for (2.1). T H E QUADRATIC PROGRAMMING ALGORITHM S T E P 1. Use Tardos' feasibility algorithm to check whether {Ax = b, is feasible. x > 0} If not, terminate since (2.1) is infeasible. If feasible, then the positive defmiteness of D guarantees boundedness which in turn implies that the dual constraint set is feasible. Set K = 0. S T E P 2. Let D°x + A y oT Is = c together with - E°s = c° denote the equality system Dx + S{ = 0 for i € K and let P° = {(x ,y ,s ) T T T A yT : Ax = b, Dx + A y — Is = c, S{ = 0 for i G K , x > 0, s > 0} . Use Tardos' feasibility T algorithm to find a point say (x ,y ,s ) T T (x ,y ,s ) T T in P°. If x s T as an optimal solution to (2.1) and (2.5). T S T E P 3. Find the projection space of (D°, A , {c' ,b' ,a' ) T T of T (c ,b ,0 ) T using Gaussian elimination. Recall that for a matrix projection onto its null space P = I — G (GG )~ G. T T 1 {x : Gx = 0} onto the null is determined by the idempotent I.e., for some vector T Px = x - G (GG )~ Gx T T G with full row rank, the i its projection onto the null space of G is Px (G(Px) = G(x - G (GG )~ Gx) T T — E°). Since the rows are linearly independent, this can be done oT matrix — 0 terminate with T = x- Gp 1 T T = Gx - Gx = 0) where 1 and p = (GG )~~ Gx. T Applying this to our 1 case we obtain (c> ,b' ,a' ) T T T = (c ,6 ,0 ) T T T 28 p (D°,A° ,-E°). T T If (c' , b' , a' ) = 0 then solve the problem min{±z Dz T T > 0} s T : D°z + A° y T T by Kozlov et al.'s algorithm to obtain an optimal solution -E°s = 0, (x = z T T + c D- ,y ,s ). T 1 T T S T E P 4. Let _ (3ra + m)(2n + m)A 11(^,6^,^^)1100 tt= where A is a maximum absolute sub determinant of (D, A , — I) , T i = l,. 6i = Ml t = l , . .., m i = l , . ..,n S T E P 5. Use Kozlov et al.'s algorithm to find an optimal solution (v ,z ) T max {-^z Dz :D v T = 6, - £ - Dz = c, oT o r to T w < a} which is a dual of min {c z + b y + a s + -z Dz T T T T 2 : D°z + A y oT - E°s = 0, 5 > 0}. (2.8) Let I = {i: (-E° v)i < aa'i - (2n + m)A}. T Add the set I to K and go to Step 2. The following lemmas which are extensions of corresponding lemmas in [45] will be used in order to verify the validity of Q P A . LEMMA where 2.2.1 Let (z ,y ,s ) T T {c ~b ,a ) = \(c ,b ,a )] T T T T T T T be an optimal solution to the problem (2.8) of some vector 29 {c ,b ,a ) T T T e R n + m + n , D is an integral nx n positive definite matrix and D°,A° of appropriate dimensions. Let (v ,z ) T and E° are integral matrices be an optimal dual solution for (2.8). Then T for any optimal solution (z , y , s ) to T T T min {c z + b y + a s + -z Dz T T T : D°z + A y T - E°s = 0, oT 2 s > 0} (2.9) (i.e., "unrounded" problem), we have, {-E° v)i <ai- T PROOF (2n + m)A implies s = 0. (2.10) l The dual of (2.8) has the following set of constraints D v oT - Dz = c < c + e A°v = b < 6 + e —E° v < a < a+ e T where e is a vector of ones of appropriate dimension. Moreover, since an optimal dual solution for (2.8) and (z ,y ,s ) T T T T is an optimal primal solution, we T have from complementary slackness that s (a + E° v) T (v ,z ) T = 0 . Coupling with the fact that a < a we obtain (—E v)i < di <a,i implies S{ = 0. (2-H) oT Now, suppose that (z , y , s ) T T problem (2.9). Since (z ,y ,s ) T c {z -z)+ T Substituting T T is an optimal solution to the "unrounded" T is a feasible solution for (2.9) we have b (y -y) + a (s - s) + \z Dz T T T - \z Dz T < 0. (2.12) u = z — z, u = y — y, u = s — s in (2.12) and rearranging terms 1 2 30 results with cu + bu T Since \u Du T + au l T + z Du < 0. + -u Du 2 2 T (2.13) T > 0 for each u, we obtain from (2.13) that T cu + bu T T + au l T 2 < 0. + z Du T (2.14) We will prove the validity of (2.10) by contradiction. Suppose that (2.10) is not valid, i.e., there exists an index i for which ( — E v ) i < a; — (2n + m)A and oT Now since by the optimality condition s = 0 we have that > 0. u\ > 0. Moreover, t u | > 0 for all j with sy = 0. If for some j , u < 0, then sy > 0 which on the other 2 hand implies (see (2.11)) that (-£'° C;)y > ay or -ay - (E v)j > 0. Now observe that the vector (u ,u ,u ) - E°u r T 1T oT satisfies the system D°u + A u 2T oT there also exists an integral basic solution to D °u + A u oT l - E°u l = 0. Thus 2 = 0, u > 0 and 2 2 u | > 0 for j with sy = 0 that satisfies (2.14). Denote this solution (u , u , T which by Cramer's rule satisfies constraints D v || (u ,u ,u ) T variables z and y we have c < D° v in turn implies || —c + D° v — T 2T \< 1. Combining the above facts and the conditions T 0 < -c u - b u 1 - au = {-c - z D)u - Pu T T T T T T k=1 T T T -a u 1 T T T - 6 u - - z Du = (-c - z D)u 2 - z D + v D°)u <T, \(-c -z D n d for j with we obtain from (2.14) that (u , u , u ) T a n 5 u | < 0 also | (—a — v E°)j = (-c ||oo< A . Note that for the dual 2T — Dz ||oo< 1? II b + A°v ||oo< 1 T 1T 2T — Dz < c + e and b < A°v < b + e which T T u ) — Dz = c and A°v = b corresponding to unconstrained primal oT on 1T 1T + + v {D°u 2 + A^u T + {-b + v A )u T T oT v D°) \\u \ T k 31 k T T l 1 au) J T 2 - E°u ) 2 + {-a T v E°)u T 2 T + (-a V ? <ELi K T - C £ r +vA 11 «i I + E!U** I (-« - * E°h + EZL, I M T oT T h + Efc=i,fc#t I "fc l< ^ + n m I +E L i I «l I "(2» + m)A - (2n + m)A + (n - l ) A = A 11 ul | T - A which is a contradiction. • Before stating the following lemma (which will ensure the finiteness of the algorithm), we will briefly explain the ideas used in the proof. Consider a full row rank matrix H of the form ( j H same dimension as the columns of H . Let us partition x ^) and a vector x of the H T — (xj, x^) corresponding to the partition of H to H\ and H - Then the projection ( x j , x ) T the null space of H of x T 2 is given by (0 ,x ' )- This since Hix[ + i f x r r 2 2 2 onto T 2 = 0, x\ = 0 has to be valid. In our case this tells us that wherever Sk — 0 is a row of D°z + A y oT for k G {l,...,n}, the component a' k — E°s — 0 of the projection a' determined in Step 3 of the algorithm is equal to zero. Next, if we have a vector x = Gu projection to the null space of Gu T - G (GG )~ GG u T T 1 T for some full row rank matrix T G is zero since = Gu - Gu T T Px = (7 — G (GG )~ G)x T T 1 G its = = 0. If we have a vector y which is a projection of some vector w (i.e., y — Pw) onto the null space of G , then the projection of y onto the null space of G is the same vector y. This since the projection matrix P = I — G (GG )~ G T (i.e., P • P = P ) and therefore Py = P{Pw) = Pw = y. 32 T 1 is idempotent Now, combining the above facts it is easy to see that for a vector d = c' + A v T where c' is a projection of some vector , c onto the null space of a full row rank matrix A, Pd = c'. LEMMA i 2.2.2 such that The set I found in Step 5 of QPA contains at least one index S{ = 0 is not a row of latter system is equivalent to z = x- D°z + A° y T — E°s = 0. (Recall that the — E°s — c° under the transformation D°x + A° y T D~ c.) l PROOF The proof will follow by constructing a vector d and looking at its max-norm. We will use the notation from Step 4 and Step 5 of Q P A and distinguish between the two cases. C A S E 1. d If z is not a zero vector, then define the (Sn + ra) vector d as follows = -OLC\ + v D° - zD T { ir d +j = -a&J + v A° , T j = T n d = n+m+k i 2n+m+£ l i0 y —aa' — v E oT k k (Dz)t — \\Dz\laa ' Since v,z 1 , m if s = 0 is a row of D°z + A y otherwise for k = 1, ...,n. T k i = 1, ...,n T Q - E°s = 0, , n. £ — 1, are dual variables for the "rounded" problem (2.8) we know that the following is valid: ac' <D° v T ab' <A°v -E° v T Therefore 0 < -ac' + D v oT - Dz = c= \ac'] < ac' + 1 = b= \ab'] < ab' + 1 <a = [ao'] < aa' + 1. - Dz < 1, 0 < -ab' + A°v < 1 and -aa' - E v oT 33 < 1. —^ For the last n components of d we know that — 1 < Now since all the components of ^ l>-->= n d are bounded by 1 from above and, with the exception of components d +i,d .+ 2n n+m ^ OT all others are bounded from below by m — 1, the validity of the Lemma will follow if we can show that Hoo^ || d (2n + m ) A . To that end note that d can be written as -c' ^ d — ( D° -b' -a' a A 0 -E° 0T ) ( v ) T i o ; It is easy to see that the projection of d onto the null space of 0 -E° H is ~ 0 0 [-D \D given by the vector d = a ( - c , -b' , -a' , - \\ Dz ||oo c' ) (i.e. / T T T H • d = 0). T Note also that || (c' ,b' ,a' ) \\oo<\\ {c' ,b' ,a' ,\\ Dz ||oo c' ) ||oo and that for T any n-vector x , || x T T ||oo> ^ || i Next, since —a(c' ,b' ,a' , T T T T dh>a\\ H2 and T || x || >|| x 2 T T Hoc are valid. \\ Dz ||oo c' ) is a projection of d, T (c' ,b' \a' ',|| Dz T T T c' ) || . T 2 Therefore, d ||„o>(3n + m) d II,> > (2n + m ) A (3n + m) (2n + m)A (3n + m)) || ( c ' ^ , ^ , a ^ ) ( ^,fe^,a^,|| C 34 l l o o Q || (c' ,6'V \|| Dz ||ooc")|| r 1^ || 2 3 2 > (2n + m ) A . C A S E 2. It z is a zero vector, then define the (2n + m) vector d as follows d = -ac' + t i n+j i v D°, i= 1 , n T = -ab'j. + l,...,m v A° , T T if s = 0 is a row of D°z + A otherwise for k = 1,.... n . y - E°s = 0, oi k + m+k <, _ - a f l , f c _ _ T £ o or, written in matrix form d = a ^ -c' ^ -b' + [ L>° A -E° ] oT v. —a The proof now follows along the same lines as for C A S E 1. • LEMMA 2.2.3 satisfies = 0 for i G /. PROOF Every optimal pair of primal and dual variables By Lemma 2.1.1 replacing change the set of optimal solutions D°z + A° y T (c ,6 ,0 ) T (z ,y ,s ) T T T T T by (c' , b' , a' ) T T T T T will not for min{c z + b y + ^z Dz : T T T - E°s = 0°, s > 0}. By Lemma 2.1.2 multiplying the linear part of the objective function by a positive scalar solutions T (x ,y ,s ) (az , cty , as ) T T T a, one obtains that the set of optimal and the set of variables that are equal to zero in all optimal solutions is unchanged. Finally, Lemma 2.2.1 holds with c replaced by etc' , b replaced by ab' , and a replaced by aa' . • LEMMA 2.2.4 After at most n iterations of QPA one gets a pair of optimal primal and dual solutions for problem (2.1). 35 PROOF By Lemma 2.2.3 adding constraints S; = 0,i G / where / determined in Step 5 of QPA does not affect the set of optimal solutions (x , T Recall that the set of optimal solutions form a face of a polyhedron Dx + A y T — Is = c, x > 0, s > 0} for which x s T was y ,s ). T T {Ax = 6, = 0. By Lemma 2.2.2 no more than n iterations of QPA are possible. (In the worst case, where all X{ > 0 and Tardos' feasibility algorithm in every iteration "missed" the desired face, i.e., face with x s T — 0, and where / is a singleton in every iteration, one will have exactly n iterations.) • Let us now calculate the complexity of QPA. Denote by T(A) the complexity of Tardos' feasiblity algorithm when applied to the system {Ax = 6, x > 0}, and by T(A,D) its complexity when applied to the system {Ax = b, Dx + A y x > 0, s > 0, T Si: = 0 for i G K}. Denote by K(A,D) — Is = c, the complexity of Kozlov et al.'s algorithm. Note that we will apply Kozlov et al.'s algorithm only to quadratic programs for which the linear part of the objective function is integral and polynomially bounded by the matrices A and D and with right hand side vector which is zero. THEOREM 2.2.5 The Q U A D R A T I C P R O G R A M M I N G A L G O R I T H M has running time polynomial in the size of the matrices A and D and independent of the sizes of the vectors c and b . It runs in 0(n(2n + m ) + n(2n + m)log(2n + m)(3n + m) A + T(A) + nT(A, D) + nK(A, 3 PROOF D)). Step 1 takes T(A) time (i.e., time of Tardos' feasibility algorithm when 36 applied to a linear system with constraint matrix A). Consequently Step 2 takes T(A,D) plus at most 2n comparisons to verify x s = 0. The Gaussian elimination T in Step 3 takes 0((2n + rn) ) time (see Edmonds [16]). Step 4 takes 0((2n + 3 m)log(2n + ra)(3n + m)A) comparisons to find (c ,b ,a ) T T T since || ( c , b , a ) T T T = (2n -f- m)(3n + m)A and one can use binary search to obtain (c ,b ,a ). T 5 takes K(A,D) time. Finally, we need at most T T Step n iterations and therefore the claimed complexity follows. • Recall (see Section 1.5) that an algorithm is termed strongly polynomial if all its operations consist of additions, comparisons, multiplications and divisions and if the number of such steps is polynomially bounded in the dimension of the input, where the dimension of the input is the number of data in the input. Further, when the algorithm is applied to rational input, then the size of the numbers occurring during the algorithm is polynomially bounded in the dimension of the input and the size of the input numbers. Thus the polynomial algorithm described in this paper becomes strongly polynomial if the size of the entries in A and D are polynomially bounded in the dimension of the data. This clearly provides a strongly polynomial algorithm for, e.g., problems where one minimizes the norm over flow (transportation) type constraints [1,12]. 2.3. EXTENSION TO THE INEQUALITY CONSTRAINED CASE The Algorithm can be generalized in a straightforward way to work on strictly convex quadratic programs with inequality constraints. To show this consider the 37 quadratic programming problem of the form. max {c x - -x Dx T : Ax < b, x > 0} T (2.15) with the same assumptions on the dimension of the problem and the input data as for problem (2.1). Observe that the only difference between problems (2.15) and (2.1) is the existence of inequality instead of equality constraints. The dual of (2.15) has the form min {b y + -x Dx 2 T Using the fact that z = x — D~ c l T D : A y - Dx > c, y > 0} . (2.16) T is positive definite and applying the transformation we obtain the equivalent pair of primal and dual problems -c D~ c 2 T 1 + max{--z Dz 2 : Az + Iw = b - T 1 AD~ c, 1 Iz - Ix = - L > c , £ > 0,w > 0} - 1 (2.17) and -c D~ c 2 T + min{c z + b y + -z Dz 2 1 T T : A y + Dz - Is = 0, y > 0, s > 0} . T T Note that an optimal solution (z ,y , T x = z + D~ c 1 for (2.15) and (x ,y ) T T T s) T (2.18) for (2.18) provides an optimal solution an optimal solution for (2.16). The Karush-Kuhn-Tucker optimality conditions for the pair of primal-dual problems (2.15), (2.16) will have the form 38 0 A (A {D I 0 T 0 ) -I ) y y w w (b) (c ) ~ (2.19) s x,y,w,s>0 and x s — 0, y w = 0. In this case, at each iteration the algorithm will detect at least one new variable y or s which has to equal zero in all optimal pairs of primal and dual solutions for (2.15) and (2.16). After each iteration one will perform Tardos' feasibility algorithm to detect a basic point from the linear system (2.19). The conditions and yw xs T = 0 = 0 will then be checked. If satisfied the algorithm will terminate since an T optimal pair of primal and dual solutions were found. Otherwise, another integration of Q P A will be performed. Instead of problem (2.7) (in the equality case), we will work with the problem of the form min {c z + b y + -z Dz T T : Dz + A y T - Is = 0, y > 0, s > 0}. T (2.20) The algorithm will have the same form, except that now S T E P 1 will read "Set Ki = <f> and K 2 = <p , in S T E P 2 the system {D°x + A y n oT 0} will be equivalent to the system {Dx + A y T i £ Ki and yj = 0 for j £ K }, 2 - E°s = c ° , y > 0, s > — Is = c, y > 0, s > 0, s = 0 for t and the polyhedron P° will be ( x \ "• = {(*'.» . T 5 «'.'')= > 0, Si = 0 for [ A D i £ Ki, °T A I yj = 0 _° ) 7 for y w s x > 0, y > 0, w > 0, j £ if }2 S T E P 5 will now read: "Use Kozlov et al.'s algorithm to find an optimal solution 39 {v ,z ) T T to max {--z Dz T 2 : D v - Dz = c,A°v < b,-E v oT oT < a} which is the dual of min {c z + b y + a s + -z Dz T T T : D°z + A y T 0T - E°s = 0, y > 0, s > 0} . 2 Let I = {i: {-E v) < aa'i - {2n + m)A}, 0T l and J = {j: [A°v) l < ab'j - (2n + m)A}. Add the set I to K\ , the set J to K 2 and go to Step 2." The complexity of the algorithm will be affected in the sense that at most (n+ra) iterations are now possible. 40 Chapter III PROXIMITY A N D SENSITIVITY RESULTS FOR QUADRATIC INTEGER PROGRAMMING In a recent paper, Cook et al. [8], obtained many proximity results for integer linear programming problems with a fixed constraint matrix and varying objective function and right-hand side vectors. In this Chapter we will extend their main proximity results to quadratic integer programming problems of the form max c x + T x Dx T s.t. Ax < b (3.1) x integer where c and x are n-vectors, b is an ra-vector, A is an integral m x n matrix and D is a negative semidefinite n x n matrix. In the sequel we will assume that the set {x : Ax < b,x integer} is non-empty, that max{c x + x Dx r T : Ax < b} exists, and that D is rational. As stated before, for any matrix A let A (A) denote the maximum of the absolute values of the determinants of the square submatrices of A . For simplicity of exposition we first consider problem (3.1) with diagonal matrix D , i.e. the separable case. We start by showing in Theorem 3.1.1 that, in this case, for any optimal solution z for (3.1) there exists an optimal solution 41 x* for its continuous relaxation such that || z — x* ||oo < nA(A) . Also, if z is a feasible solution to (3.1) which is not optimal then we show in Theorem 3.1.3 that there exists another feasible solution z to (3.1) having greater objective function value and with II z ~ z \\oo < nA(A) . With some additional assumptions we show in Theorem 3.2.2 that if z and and z! are optimal solutions for (3.1) with right hand side vectors 6 b' respectively then || z — z' ||oo < a \\ b — b' \\i +/3 parameters which depend only on A, D where a and /3 are and n . Finally, we show how to extend the above results to mixed-integer quadratic programs. 3.1. P R O X I M I T Y RESULTS FORSEPARABLE INTEGER QUADRATIC PROGRAMMING Theorem 3.1.1, to follow, provides an upper bound on the distance between a pair of optimal solutions for problem (3.1) and its continuous relaxation respectively. The bound obtained depends only on the number of variables n and the largest absolute subdeterminant of the matrix A , and is independent of the vectors 6, c and the matrix D . T H E O R E M 3.1.1 Let A be an integral m x n matrix, D a diagonal negative semidefinite n x n matrix, b an m-vector and c an n-vector such that the set {x : Ax < b , x integer} is non-empty and m a x { c i + x Dx r T : Ax < b} exists. Then (i) For each optimal solution x for m a x { c i + x Dx T optimal solution z* for max{c x + x Dx T T : Ax < 6} there exists an : Ax < 6,x integer} with T ||2*—x||oo < nA(A) , and (ii) For each optimal solution z for max{c x + x Dx T 42 T : Ax < b, x integer} there exists an optimal solution x* for m&x{c x-\-x Dx T : Ax < 6} with ||x* — z \\oo T < nA(A) . PROOF Let z and x be optimal solutions for problems (3.1) and its continuous relaxation respectively. Further assume without loss of generality that the first £ components of x — z are nonpositive and the last n — I components are positive. Partition the rows of the matrix A into submatrices A\ and A 2 A\z and A x < Az 2 A\x > 0, A x 2 2 < 0,x l is nonempty since generate such that A\x > . Consider the cone C = {x = (x\,..., xg, X£+i,..., x ) : = (x ...,X£) < 0,x = (x£ n 2 l5 x — z G C . Let G + 1 , . . . ,x ) n > 0} . Clearly, C be a finite set of integral vectors which C . By Cramer's rule for each g G G , || a ||oo < A(yl') = A ( A ) , where A' = ^ - / f o j and 7x (resp., I ) is an I x £ (resp., (n — £) x (n — £) ) identity 2 matrix. Now, since x — z G C there exists a finite set {g\,... ,gt} C G and scalars > 0, i = 1 , . . . , t such that x — z = Yll=i i9i • a In order to prove part (i) we will define the vector z* = z + 5Zi=i L^t'Jfft • ^ e will show first that z* is feasible and optimal for (3.1). Coupling with the fact that z* = x — Yli=i{ i a ~~ [ i\)di we will obtain that || z* - x \\oo< tA(A) < nA(A) . The a proof of the feasibility of z* is identical to the proof given in Cook et al., but we will state it for the sake of completeness. Observe that z* is integral and satisfies Aiz* = Ai{xand therefore Ei=i(«i - l i\9i)) a , A z* = A {z + Y?i=A il9i) < a 2 2 < A 2* Az* < b . To prove optimality, recall (see e.g. Dorn [13]) that the dual of the continuous relaxation of (3.1) is given by min{u 6 - x Dx r T : u A - 2x D = c ,u> T T T 0} (3.2) with complementary slackness conditions u (b— Ax) = 0 . Now, if we partition b T to (bi,b ) 2 corresponding to the partition of A to (Ai,A ) 2 43 T we have A x < A z < 2 2 &2 , and thus it follows from the above condition that for a vector u T optimal dual variables for (3.2) we have u = 0 and u Ai + 2x D —c 7 2 T = (uf, u ) T T of . Also, since for every y £ C , vliy > 0 we have c y + 2x 7Jy > 0. T (3.3) r Finally, using (3.3) and the fact that Ei=i [ i\9i £ C* we obtain a t t c z* + z* Dz* = c (z + Yi ^9i) T T T i=i + z Dz a T l t = c z + z Dz + c {Y[oc \gi) i=i t t T +2x D{J2l<Xi\9i) T T t i=l t=i t t i=l t=l t= 1 t QTQa.-J -2a -)ffi) ^£l- «J^)i=l i=l T It remains to show that t r > c z + z Dz+ T l i=i t T + 2z £(]T[a Jff ) T a t (Ei=i(l_ iJ a — 2a: )<7 ) .D(E* T t t [ i\9i] a =1 > 0 . To that end recall that gi £ C and hence can be partitioned into (<?/,<7j) where g] contains 2 the first £ components and g 2 the last n — £ components of gi . Clearly, 9i < 0 <7j > 0 . Diagonality and negative semidefiniteness of D implies 2 5 gjDgj < 0 Coupled with the fact that for all i,j = [a J — OL < 0 and [a,-J > 0 for all i we obtain t X ( E U ( M - 2a0ft) D(E!=iL«iJft) = E S = i ( W - 2 a ) [ « j f / J T t I 5 + E-=i Ej>,-(([a.-J - 2a,-) Lay J + ([a J - 2ay)[a -J)^I> > 0 . y 44 t W ffl Thus, c z* + z* Dz* > c z + z Dz T 7 T and part (i) is valid. Also, the optimality of T z and z* implies (3.4) In order to prove (ii) define first the vector (3.5) x = which will be shown to be feasible and optimal for the continuous relaxation of (3.1). The feasibility of x* can be shown in a similar manner to the way it was done for z*. To show optimality observe that c x* + x* Dx* = c x - c (Y2leti\gi) T T T + x Dx T T - 2x t'=i t D(^2[ai\ ) T gi i = i t + (£L«.:I*) 0(£L«.-J*) t i = l i = l t = c x + x Dx T T - ( c r t ( E | a i J g t ) + (21 + ^[ctilgif i=i t + 2 ( ^ ( [ a t i=i D(Y,[<*i\gi)) i = i t t J - a )»i) -D(X]L »-J^) = T a i ° T * + i=i t i = i t + 2(^2{[a \-a )g ) D(^2[a \g ) > cx + T i i i i T i x Dx, T i = i where the equalities follow from (3.5) and (3.4) and the last inequality follows from the fact that (£(La,-J -ai) ) D(J2l"i\9i) T gi Finally, from (3.5) || x*- z ||oo< tA(A) < > 0. nA(A). • 45 Using the example provided by L . Lovasz for the linear case (see Schrijver [43], page 241) it can be verified that the bound is tight. Observe that if lower and upper bounds on the variables X{ are known one can naturally improve the bound on the difference between an integral and continuous optimal solution. Indeed, if P = {x : Ax < b, ti < Xi < Ui} then denote by B = min { nA(A), max {| Uj — ti |: i — l,...,n} } . Clearly B is a valid bound. Trivially, in the case of a 0 —1 quadratic programming problem we have B = 1 . As a consequence of Theorem 3.1.1 we obtain Corollary 3.1.2 which provides a bound on the difference between the optimal objective function value of (3.1) and its continuous relaxation. C O R O L L A R Y 3.1.2 vector. Let Let A be an integral b an m- P = {x : Ax < b} be a nonempty bounded polyhedron having an integral point. Then, , max{c x + x Dx T < nA(4)(|| c PROOF m x n matrix and T : Ax < 6} — max{c x + x Dx T T : Ax < b, x integer} ||i + 2 n A ( A | 6) || Z? ||oo). Denote by z (resp., QI ) an optimal solution (resp., the optimal ob- jective function value) for max{c x + x Dx T : Ax < b, x integer} and by x (resp., T QC ) an optimal solution (resp., the optimal objective function value) for its continuous relaxation with || x — z | | o o < nA(A) which clearly exists by Theorem 3.1.1. Then, QC -QI = c x + x Dx T T - c z - z Dz = c (x - z) + (x + z) D(x T <\\ C ]ji|| X - Z || oo + <|| C || i | | X - Z || oo + T T T - z) || X + Z || i | | D(x - 2) || X + Z || i | | D 46 || oo ||oo || Z - Z ||oo where n || x II x || D = max{|d\i| : i = ||oo and for . Now since for a vector a pair of vectors x, y ||oo<|| % ||oo + || \\ x + y + z ||i< n(\\ x Hoc + || z ||oo) < n(A(A x , || x \\i< V ||oo , we have \fe)+ A(A | fe)) by the boundedness of the polyhedrons. Therefore, lu | (| c Id +2nA(A |fe)|| D IU) QC-QI<\\x-z < nA(A)(\\ c Id +2nA(A |fe)|| D W^) . • Theorem 3.1.3, which follows, will show that for any integral solution z of Ax <fewhich is not optimal for (3.1), there exists an integral solution z of Ax < b which has greater objective function value and with || z — z ||oo< nA(A) . THEOREM For each integral solution 3.1.3 z of Ax < b , either z is an optimal solution for (3.1) with a diagonal matrix D or there exists an integral solution z of Ax < b with || z — z PROOF < nA(A) and c z + z Dz T T > c z + z Dz T T . Let z be an integral solution of Ax < b which is not optimal for (3.1) with a diagonal matrix D . Then there exists an integral solution z* of Ax < fe with c z* + z* Dz* T T > c z'+ z Dz T T . As in the proof of Theorem 3.1.1, without loss of generality, assume that the first and that the last submatrices A x n — £ components are positive. Partition the rows of A into and A 2 such that A\z* > A\z ,A z* < A z and consider the cone C = {x = (xi,... ,X£,xe ,... +1 x 2 I components of z* — z are nonpositive 2 2 ,x ) : Aix > 0 , A x < 0 , x = ( x . . . ,xt) < 0 , l n 2 l s = (x^+i,... ,x ) > 0} . Since z* — z G C , we can write z* — z = n where a > 0 for i'. = 1,..., t and {g ,...,g } t t C . By Cramer's rule || gi ||oo < A(A) z + 0{ = z* — 5Zj = i , jSj — i i ~ l)°i a J ? i a t YA=I a i9i is a subset of integral generators of for every i . If oti > 1 for some i , then is 47 a n integer feasible solution of Ax < b . Now, if in addition c gi + (2z + gi) Dgi > 0 , then c (z + gi) + (z + gi) D(z + gi) T > c z + z Dz T and by choosing I = z + T T T T we are done. Thus, let us assume that for all i for which ai > 1 we have c + (2z + T gi ) D T g i g i < 0. (3.6) Next, define the integral vector t t z = z* - 5^|a«j0i = z + X^" ' i=i i'=i 1 _ L *J)0* a which is a feasible solution of Ax < b and satisfies || z — z ||oo < tA(A) < nA(A) . To complete the proof we will show next that the objective function value at z is larger than at z* . Indeed, c z + z Dz = c z* + z* Dz* - c (E*=i L«iJ*) - 2 ^ 7 J ( E ! T T T T + ( E L i L ^ J f f O ^ l E L i l«i\9i) - ( ' ( E ! = i L«.-J*) + r = c z*+z* Dz* T T r T = c z* + z* Dz* T T (2* + 2 £,-=i ^ - =1 - E!=i L«.-J*) J>(E!=I L«.-J w)) t (c (El M9i)+2z' D(EL Mg )) T r 1 -(E!=i(2ai - l^J)</O £>(E!=i r |ajtt) = c z* + r -(c (El=iL«dffO + 2 2 i ? ( E : = i K J ^ ) ) r 1 T l z* Dz* T - E!=i(2a,- - L"d) W ^ . - - E L Ej> ((2a,- - L«iJ)L«>J + (2«y - L « , J ) K J ) ^ ' > ' * * + z* I>** T r i -(c (E!=iLatJj/i) + 2« £>(E!=iL«.-JffO) - E L i ( 2 ^ r r [a^la^gfDgi where the inequality follows from the fact that gi (E C , [a;J > 0 and 2 ^ — [a,-J > 0 for all i which in turn implies ((2a, — [a 'J)L yJ + (2ay — [ayj) [ai\)gf Dgj < 0 . a t 48 Therefore t c z + z Dz T T > c z* + z* Dz* - c {Y^[<*i\gi) i=l T T T t - ^[a»J(2a-|- (2a - - [a \)g ) Dg • T t l l l i=l Now, since for cc,; < 1 , |_a;j = 0 , the only nonvanishing terms in the above summation correspond to a; > 1 . Further, since [a,-J) > a, > 1 , 2a; - [cti\ = a + ( « i t (2a - t D is negative semidefinite and of Dg^ < gf Dg - . This implies, t using (3.6), that t c z + z Dz T T > c z* + z* Dz* - Y, L«d { 9x + (2* + O i ) ^ f ) T T cT T t=i > C 0* + 2* D2* > C Z + 2 £>2 . T T T T • Observe that the above Theorem assures finite "test set" for problem (3.1). In other words, one has to check only a finite number (which depends only on the constraint matrix and the number of variables) of integral vectors in order to obtain a better solution or to verify the optimality of the current solution. Although the set is finite, it might require the exponential (in n ) number of comparisons in order to get better solution. 3.2. S E N S I T I V I T Y FORQUADRATIC INTEGER PROGRAMMING : T H E R I G H T H A N D SIDE C A S E In this Section we show that if z and z' are optimal solutions for (3.1) with negative definite matrix D , constraint matrix A of full row rank and right hand side vectors 6 and b' respectively, then 49 || z — z' ||oo £ a || b — b' \\\ +/? where a and 0 are parameters which depend only on restricting D A, D and n . Observe that to be negative definite implies that the continuous relaxation of the quadratic integer program has a unique optimal solution whenever the polyhedron P — {x : Ax < ft} is nonempty. For simplicity of exposition Theorem 3.2.2, to follow, will be stated and proved for the separable case. The general case will be discussed in Section 3.3. Theorem 3.2.2 is using a special case of Theorem 2.1 in [11] in which changes in the linear cost coefficients are considered. For completeness we will state the part of Theorem 2.1 in [ll] we use. LEMMA 3.2.1 n-vectors and x (resp., Let A be an m x n matrix, b an m-vector, c and c' D = diag(di) an n x n diagonal negative definite matrix. Let x' ) be the optimal solution for max{c x + x Dx r max{c' x + x Dx r T T : Ax < ft} (resp., : Ax < b}) . Then \\ X - x' Hoo^ — || C - c' ||i where K = — max{d, : i = 1 , . . . , n} > 0. PROOF See Daniel [11], Theorem 2.1 . • T H E O R E M 3.2.2 {AEX Let {Ax < ft} = {A x E = b ,Ajx E < ft/} and {Ax < ft'} = — b' , Ajx < b'j} have integral solutions where A is an integral mxn E matrix of full row rank and ft, ft' are m-vectors. Let c be an n-vector and D = diag(d{) a diagonal, negative definite n x n matrix. Then (i) For every optimal solution z for max{c x + x Dx T 50 T : Ax < ft, x integral} and every optimal solution z' , for max{c x + x Dx r II z - z' ||oo < nA{A)(H{D) 1 , . . . , n}/ min{|o!i| : i = : Ax < b',x integral} we have T \\ b - b' ||i +2) where l,...,n}. (ii) Assume, in addition, that D is integral. If f(b) value for max{c x + x Dx r H(D) = max{|a\| : i = T (resp., f(b') ) is the optimal : Ax < b , x integral} Ax < b' , x integral} ), then (resp., max{c x -f x Dx : T |/(6) - /(6')| < nA{A){\\ c || {2nA{A) + A{A\ ) + A{A\ '))){H{D) | | 6 - 6 ' | | i + 2 ) where A = b b c PROOF c x T +n \\ D ( A I 0 -2D A T I We will start by determining an upper bound on the difference between the optimal solutions to the corresponding continuous quadratic programs. To that end let us first write the dual of the continuous relaxation of (3.1) in primal form - ax (0^)Q m { *V)(£ + ( o)(o)> (3.7) S.t. -2D 2D A -A ) . o -I , T ' c ' —c . 0 , T \u ) Now, we will treat changes in the right hand side of (3.1) by considering changes in part of the linear cost coefficient of (3.7). To that end, recall that if x is an optimal solution for max{c x -+- x Dx r T : Ax < b} then x is also an optimal solution for the linear programming problem max{(c + 2x D)x r Thus if (x,u) and (x',u') : Ax < 6} see e.g. Dorn [13]. T are, respectively, optimal of (3.7) and the quadratic programming problem obtained from (3.7) by replacing b by b' then, for every feasible solution (x, u) of (3.7) we have - u b + 2x Dx T T - u b' + 2x' Dx T T < -u b + T 2x Dx T < -u' b' + 2x' Dx'. T 51 T (3.8) Substituting (x',u') (resp., (x, u) ) in the first (resp., second) inequality of (3.8) adding and rearranging terms results with 2{x' - x){-D){x' -x)< («' - filull b-b' u) {b - b') <|| s' T HJ. (3.9) Now, since both (x,u) and (x',tt')are feasible for (3.7), (x' — x, u' — u) = (v,w) satisfies 2Dv — A w = 0 and hence T A (u' -u) T Using the fact that A =2D{x'-x). is integral and has full column rank, Cramer's rule, and a T property of determinants we obtain || « ' - fi | | o o < A(A | 2D(x' - x)) < 2nA(A) \\ D H^H i ' - z ||oo • T (3.10) Now let K = min {—d{ : i = l,...,n} = —max {di : i = l,...,n} . Substituting (3.10) into (3.9) and observing that K > 0 results with 2K || x - x ||^< 2K || x' - x \\\< 2nA(A) \\ D ||oo|| x' - x W^W b' - b ||i (3.11) or II *' - x l U ^ n A ^ D H°° || > _ || nA(i)ff(i?) || 6' - 6 ||i . b 6 1= Using the fact that the continuous relaxation of our quadratic integer program has a unique solution and applying part (ii) of Theorem 3.1 it follows that for every pair of optimal solutions z and z! for the quadratic integer programming problem with right hand side vectors b and b' respectively || 2 2 ||oo^|| 2 || X X \\oo <nA{A){{H{D)\\b-b'IU+2). 52 X \\oo + || X Z ||oo^ To complete the proof we will show that part (ii) of the theorem follows from the above bound, the existence of the optimal solutions and Cramer's rule. Denote by dual solutions A = ^ ® ^ . Observe that an optimal pair of primal and T (x, u) for the continuous relaxation of (3.1) is a basic solution of a polyhedron defined by Ax < b , A u T integrality of A and D — 2Dx = c . Now, by Cramer's rule and the we get ||*||oo<|| ||oo<A(i|J). Thus, for an optimal integral solution we have ( by Theorem 3.1) II z ||oo<|| z ~ x ||oo + || x ||oo< nA(A) + A ( i |*) . Therefore II z ||oo + || z' !!«,< 2nA(A) + A ( A \ ) + A{A |*') . b c Now, | f(b) - f(b') | = | c (z - 2') + (z - z') D(z + z') |< T T <l lllll Z-z' Hoc +n || D Hooll 2 + 2' || oo |j 5 - z' ||oo< c < nA(A)(|| c ||, +n || L> (2nA(A) + A ( i |*|) + A ( i |f |))(tf(£>) || 6 - fc' ^ +2). • 3.3. E X T E N S I O N T O N O N S E P A R A B L E MIXED-INTEGER QUADRATIC PROGRAMMING The results given so far can be easily extended to separable quadratic mixedinteger problems of the form 53 T* max s.t. T f 1 c x + c y + x D\x + y D y 2 1 Ax + 2 (3.12) By<b integer x where c\ and x are k-vectors, c and y are (n — 2 fc)-vectors, an m x k (resp., rn x (n — k) ) integer matrix, D\ (resp., D (resp., 5 ) is ) is a k x k (resp., 2 (n — k) x (n — k) ) diagonal, negative semidefinite matrix and b is an m-vector. For example, Theorem 3.1.1 for the mixed-integer case should read "... (i) For each optimal solution (x ,y ) T T exists an optimal solution (z ,w T nA(A ) for (3.12) with || (z ,w ) — (x ,y ) T T T T ||oo< | B) , and (ii) For each optimal solution solution (x ,y ) T nA{A T for the continuous relaxation of (3.12) there T (z ,w ) T T for problem (3.12) there exists an optimal for its continuous relaxation with || (x ,y ) T T — (x ,y ) T T ||oo< | 5)." Consequently, Corollary 3.1.2 and Theorem 3.1.3 have analogous statements for the mixed-integer case and all the proofs follow in a straightforward way from the proofs given for the pure integer case. Unfortunately, Theorem 3.1.3 loses its significance in the mixed-integer case because it does not imply the existence of a finite "test set" any longer. The validity of the theory for the mixed-integer case allows us to consider a broader class of quadratic integer programming problems namely when the matrix D in (3.1) is not necessarily diagonal. Section 1.4) using an I x n matrix B This since (where 54 D can be diagonalized (see I is the rank of D ) such that D = B CB T , with C being a diagonal negative definite matrix. Recall here that, D' 0 without loss of generality, we can assume that D = ^ ~ S ^ J , where D' is an £ x £ negative definite matrix. Using the diagonalization for definite matrices proposed in [48], we obtain that D' = CB' or D = B CB T = [B',0) C(B',0) without T dealing with square roots, i.e. no irrationalities will occur. Thus, problem (3.1) can be equivalently written as rp max s.t. rp c x + x Cx\ x Ax <b (3.13) Bx - Ix =0 1 x integer or (3.14) x integer . Problem (3.14) is a mixed-integer, separable, quadratic programming problem for which the theory developed above is valid. Observe, however, that the bounds should be expressed in terms of n and A (/I) , where n = n + £ and A as defined in (3.14). Also, if B is not integral, we will have to multiply Bx — Ix = 0 by a large x enough constant which will not restrict generality but will enlarge the bound. Note, however, that the size of a constant might not be bounded by a polynomial in the size of A . A similar transformation can be carried out for nonseparable mixed-integer quadratic programs. The stability of mixed-integer quadratic minimization pro55 grams in the absence of boundedness on the feasible region and convexity on the objective function was studied by Bank and Hansel [2]. In order to generalize Theorem 3.2.2 to the nonseparable case observe that the proof of Theorem 3.2.2 up to equation (3.11) is valid without the diagonality assumption on the (negative definite) matrix D . However, in this case the constant K will be the smallest absolute eigenvalue of D . In order to obtain the bound on the difference between the two optimal integral solutions z and z' we used Theorem 3.1.1 in the Proof of Theorem 3.2.2 and, therefore, required separability of the objective function. At this point we can transform problem (3.1) to an equivalent separable mixed-integer problem (3.14). Using the fact that the optimal solutions x and x' to the continuous relaxation of (3.1) with right hand side vectors b and b' , respectively, are unique (since they are optimal solutions for strictly convex quadratic problems) and that the matrix B obtained in the diagonalization of D is nonsingular (and, as stated before, can be assumed to be integral), we can obtain the bound on the difference between the optimal solutions z and z' for (3.1) with right hand side vectors b and b' respectively, as follows : N-*' ||oo<|| ( £ ) - ( / , , ) II- — II (fiz) ~~ (fix) H°° + II (BX) ~ (fiz') IIO° + II (BX') ~ (BS') H°° < 2(2n)A(A) + (1+ U S ||oo) || x - x ' ||oo < (1+ || B \\ )A{A)H{C) 00 \\b-b' Hi +4nA{A) where A , B and C are given in (3.14) and (3.14) with right hand side vectors b (resp., b' ). 56 (resp., (^,) ) are optimal for Chapter I V NONLINEAR INTEGER PROGRAMS: SENSITIVITY ANALYSIS FOR B R A N C H A N D BOUND Recently, Schrage and Wolsey [42] studied the effect of small changes in the right hand side or objective function coefficients of a linear integer program. In this Chapter we will naturally extend their results to nonlinear integer programming problems. Although much attention has been given to sensitivity analysis for linear integer programming, unfortunately this is not the case for nonlinear integer programming. Some results for the latter problem can be found for e.g. in Radke [41] who developed a continuity analysis for nonlinear bounded integer programming, in [38] where McBride and Yormark solved a class of parametric quadratic integer programming problems which were obtained by changing the right hand side of a single constraint, or in [9] were Cooper solved a parametric family, with respect to the right hand side, of a pure integer nonlinear program with separable objective function and constraints. We will restrict our attention to a nonlinear integer program whose continuous relaxation is a convex programming problem satisfying the Kuhn-Tucker constraint qualification. This since we will make use of the duality theory for convex nonlinear programming problems as introduced by Wolfe [49]. In Section 4.1. we will consider pure 0 — 1 nonlinear programs. In Section 4.2. we will discuss the extension to the mixed-integer case as well as to the case when integer variables are not restricted to be 0 or 1 . Finally, the computational results for an example with 57 quadratic objective function, linear constraints and 0—1 variables will be given in Section 4.3. 4.1. T H E P U R E N O N L I N E A R 0-1 P R O G R A M Consider the nonlinear integer programming problem N(b) = min f{x) s.t. g(x) > b (4.1) 0 < x < 1 x integer where x is an n x l vector, b is an m x 1 vector, g(x) T = (gi(z),...,o (x)) , m / and gi , i = l , . . . , m are real-valued, differentiable functions and, furthermore, / is convex and gi , i = 1, ...ra are concave on R n . We will also assume that the continuous relaxation of (4.1) satisfies the Kuhn-Tucker constraint qualification (see e.g. [49]), which is automatically satisfied if the constraints are all linear. Explicitly assume the nonlinear integer programming problem (4.1) was solved by implicit enumeration and some small changes have been made in the right hand side or objective function coefficients of (4.1). The question we would like to answer is what information from the implicit enumeration tree, if at hand, will provide us with bounds on the optimal value of the perturbed problem. Before attempting to answer the above question observe that the continuous relaxation of (4.1) is a convex nonlinear optimization problem for which we can state the dual (see Wolfe [49]) max b u + e v +f(x) — u g(x) — (v 58 +v ) x s.t. u Vg(x) + v I + v I T 1T 2T = Vf(x) (4.2) u , v > 0 , v <0 1 where e T = (1,..., l) 2 and u (resp., v , v ) denotes the vector of dual variables 1 associated with the constraints g(x) 2 > b (resp., x > 0 , — x > —1 ). Solving the primal (i.e. the continuous relaxation of (4.1)) with some readily available computer code, one can obtain the value of these dual variables as a byproduct (e.g. using MINOS -Modular In-core Nonlinear Optimization System). R E M A R K 4.1.1 If all the constraints of (4.1) are linear, then the objective function of (4.2) can be written as (see e.g. Dorn [14]) Let b u + e v + f(x) T T 2 — x Vf(x) T . us start by solving (4.1) using implicit enumeration. In doing so we con- struct a tree with node 1 corresponding to the continuous relaxation of the original problem. At each node t of the tree one solves R\b) = min f{x) s.t. g(x) (4-3) > b L}<XJ<U}, j = l,...,n where L) = U} = 0 , jeFl L) = U} = 1 , jeFl L} = 0,1^ =1 ,jeF\(F*UFt) with F = { 1 , n ) and FQ (resp., F\ ) is the set of indices of variables fixed to zero (resp., one). Notice that (4.3) is the continuous relaxation of the integer nonlinear subproblem /*(&) associated with node t . For simplicity of exposition we will use 59 N(b) , P(b) and JR*(6) to denote the respective problems as well as their optimal value. Now, since for each j at most one of the constraints L - < Xj or ij < UJ can 1 be binding at any time, we will associate the same dual variable Vj with the two constraints. If otherwise < Xj is binding then the associated dual variable satisfies Vj > 0 vy < 0 . Let (uJ, xf, vf) be the associated dual solution obtained by solving (4.3). Using (4.2) the optimal objective function value of (4.3) equals R\b) = b u + Y, {vt)j + Y T t - - ufg{x ) t Y <' min ( t)i - m i n Y v jeF* > 0 + {° ^ f ( t)j) v 5 jcF\(FluF<) = b u + f(x ) - ufg(x ) . T t REMARK 4.1.2 t t If the constraints in (4.1) are all linear the optimal objective function value of (4.3) can be alternatively written as R'ib) = b u T t + Y + jeFl Y < ' m m + tt ) - ?Vf{x ) 0 Xt x t . jeF\{F*UF*) Assume now that (4.1) is perturbed by replacing b by a new vector d . We would like to use the information from the implicit enumeration tree to derive a lower bound on the value of the perturbed problem. To this end notice that the dual variables ut, Xf, i>t derived at node t of the tree remain feasible, but not necessarily optimal, for the perturbed problem. Therefore, a lower bound on the objective function of the perturbed problem is given by R {d) = d u t Let I (d) T t + f{x )-ujg{x ) t t . (4.4) denote a lower bounding function on the objective function value 60 /*(d) . For terminal nodes with feasible solutions for .#'(6) we can set f (d) = R*(d) . For terminal nodes with no feasible solutions set if R'(d) < 0 if R*(d) > 0 -oo + oo I^d) where 14 and Xt used in this case in the evaluation of R (d) are part of the dual variables (uJ, xf, vj) sibilities. (Having a problem with only linear constraints and using Remark 4.1.2, associated with the minimization of the sum of the infea- both Ut and vt and xt = 0 can be used in the evaluation of R*(d) .) For each nonterminal node t define I*(d) = max {R*(d) ,min ( I L(t) (d), l {d)}} (4.5) m where L(i) and R(i) are the two offsprings of t. Theorem 4.1.3 below provides us with a lower bound on the objective function value of the perturbed problem obtained from (4.1). T H E O R E M 4.1.3 PROOF l d) l is a lower bound for N(d) . We show first that for any node t and any d , I*(d) < /*(d) is valid. If t is a terminal node then the inequality follows from the definition of l'(d) and the convention that an infeasible minimization problem has objective function value +oo . Now, if t is not a terminal node, / (d) > R (d) > R*(d) . Further, from the 4 t implicit enumeration J*(d) = min {I M{d) , I W{d) } > min ( I L Therefore, R /*(d) > max (R*(d) , min {I L(f) 61 L(t) ( d ) , f {d) (^) , l {d)} m W } . and by (4.5), J*(d) > ^(d) . By induction towards node 1 of the tree we get N(d) = > I ^) • 1 • Theorem 4.1.4 to follow provides an answer to the following question. Assume we augment problem (4.1) by adding a new 0 — 1 variable, say x + i , resulting in n the addition of new linear terms in the constraints and some terms (not necessarily linear) in the objective function. Under what conditions will x + i n remain at zero level in the optimal solution to the modified integer nonlinear program? T H E O R E M 4.1.4. Suppose after solving (4.1) to optimality the problem was enlarged by introducing a new 0—1 of a new linear term, say variable, say x n + 1 , resulting in the addition , to each constraint i = 1, ...,m , and a number of a(X +i n new terms in the objective function given by / ( x ) x „ i . Then there exist an optimal + solution to the new problem with x n i + IF, where a T >N{b)-l\b-a) = ( a j , . . . , a ) , fp = /(x) and x is the optimal solution to the initial l m = 0 if problem (4.1). PROOF Suppose x n + i = 1 is in an optimal solution at node 1 . The remaining optimal values can thus be found by solving problem (4.1) with right hand side b—a . By Theorem 4.1.3, N(b — a) > I (6 — a) and therefore a solution to the enlarged 1 problem with x \ = 1 has objective function not less than n+ N = f Fl +I (6-a) . 1 Now, if N > N(b) the solution to the initial problem remains optimal. • 62 4.2. T H E M I X E D - I N T E G E R CASE Consider now problem (4.1) where only a subset of variables is restricted to be integer. Theorem 4.1.3 can be carried over without any changes. For Theorem 4.1.4 to be valid the assumptions remain unchanged, while the result should read : "Then there exist an optimal solution to the new problem with x i n+ — 0 if f{x) > N{b) - I ( 6 - a) 1 where f(x) denotes the sum of the new terms in the objective function evaluated at x , the optimal mixed-integer solution to the original problem, and x + i = 1 •" n Next, consider the nonlinear mixed-integer program of the form (4.1) except that the integer variables are not necessarily restricted to be zero or one. The bound (4.4) can be derived in a straightforward manner as for the 0 — 1 case and Theorem 4.1.3 will be valid without any changes. However, if x +\ n is an integer variable restricted to the interval [0,17], then we will restrict ourselves in Theorem 4.1.4 to the case in which the added terms in the objective function are linear in . In this event the bound can be improved as follows. If min{/(x)x + I (6 - ax ) 1 n+1 n+l :x n + i = 1,...,U} > N(b) then the solution to the initial problem remains optimal. 4.3 T H EQ U A D R A T I C 0-1 P R O B L E M : A N E X A M P L E Consider the quadratic integer programming problem Q[b) — min c x-\—x 63 Dx s.t. Ax > b (4.6) 0<x<l x integer where A is an ra x re and D an re x re matrix, c and x are re—vectors and 6 is an ra —vector. Observe that, although no restrictions are imposed on D , we can assume without loss of generality that D in (4.6) is symmetric and positive semidefinite. This will ensure the existence of a global minimal solution to the continuous relaxation of (4.6) whenever the polyhedron P = {x : Ax > b,0 < x < 1} is nonempty. Indeed, as stated in Section 1.4, if D is not of the desired form (4.6) can be replaced by an equivalent problem in which the objective function of (4.6) is replaced by [J-\\e )x + \x {\(D T + D) T T + \I)x where A is a positive scalar such that \(D + D ) + AJ is positive semidefinite, see T for example [25]. Taking into account Remark 4.1.1, the dual of the continuous relaxation of (4.6) can be written as (see e.g. Dorn [13]) max o u + e v x Dx 2 s.t. A u - Dx + Iv < c T -v > 0 . u>0, This since the continuous relaxation of problem (4.6) can be written as min {-x Dx T + c x : Ax T 64 >b,x>0} (4.7) where A = ^ A ^ and b = with e = (!,...,!) . Following Dorn [13] T Type I, page 60, its dual is 1 max {— w Dw + b z : A z — Dw < c, z > 0 } 2 which is equivalent to l max 2 /TT / T T / T T it; Dw + b z\ — e zo rp S.t. A Iz — Dw < c 2 ! - Z\ > 2 0 , 2 2 >0 . Now, replacing w by x , z\ by u and 22' by —v results in (4.7). From Remark 4.1.2, the bound (4.4) in this case becomes R {d) = d u +J2{v ) + t T t t It is easy to see that m i n j ( 0 , {v )j} ~ \xfDx t . t (4.8) R (d) can be further improved using information obtained t from other nodes in the tree (see also [42] for the linear case). Indeed if the dual prices of all nodes, say N , of the implicit enumeration tree are used, R (d) can be f improved to R*(d) = max {d u T s seN + V (v )j + Y] a ^ jeF* min{0, (u ) > - \x Dx }. T s y s s L jeF\(F*UF*) For problem (4.6), Theorem 4.1.2 specializes to " Suppose after solving (4.6) to optimality the problem was enlarged by adding a new column, say a Then, there exist an optimal solution to the new problem with x n+l c + ^(dn+l,n+l + *>+ ) rf 1 65 - n + i Q( ) ~ ^ ( ~ n+l) , b b a n + i = 0 if to A . where Fi is the set of variables fixed to 1 in the optimal solution for (4.6) with Q(b) its optimal objective function value." EXAMPLE 4.1 Consider the quadratic integer programming problem of the form Q — min 65xi - 10x + 7x + 58x — 8x + 23x — 8 x ^ 4 + 16xxx + 4 x x 2 4 3 5 6 6 4 6 s.t. 70X] - 20x + 30x - 20x + 90x + 100x > 200 2 3 4 5 6 lOOxj + 30x - 30x + 80x - 5x + 70x > 100 2 3 4 5 6 0 < X{ < 1 , X{ integer , i' = 1, ...,6 . The equivalent objective function of the form c x+\x Dx T matrix D with positive semidefinite T has (15,-10,7,50,-8,5) and /100 0 0 D = -8 0 V 16 0 0 0 0 0 0 The optimal solution to the continuous relaxation equals 0 0 0 0 0 0 -8 0 0 16 0 4 0 0 0 0 0 0 16 \ 0 0 4 0 36/ (0.20588,1,0.5196,0,1,1) with objective function value of 17.139 . The corresponding 0 — 1 optimal solution equals (0,0,1,1,1,1) with objective function value of 84 . The continuous relax- ation subproblems were solved using Q P S O L , a F O R T R A N package for Quadratic Programming developed at Systems Optimization Laboratory, Department of Operations Research, Stanford University, and implemented on A M D A H L 470 V-6 computer model II. Q P S O L minimizes an arbitrary quadratic function subject to linear constraints where upper and lower bounds on the variables are handled separately. It requires an initial estimate of the solution and a subroutine to define the quadratic part of the objective function. Among output arguments, the Lagrangian multipliers 66 for each constraint are given. In the case of an infeasible constraint set , the minimum of the sum of the infeasibilities was determined using the LINDO package. =1 = (1,1,0,0,1,1) , z = 86 XQ x T Xi = 1 xe - 0 infeasible CR x T X4 = 1 = (0,0,1,1,1,1) , 2 - 8 4 xi = 0 = 0 infeasible X4 Figure 4.1: Branch and Bound Tree for Example 4.1 Figure 4.1 describes the enumeration tree associated with example 4.1. The number above each node corresponds to the node index while the entry in each node represents the branching choice. For terminal nodes with feasible solution an optimal solution and the optimal objective function value are denoted by x and 2 , respectively. The lower bounding functions R*(d) for the continuous subproblems solved at each node are given by R {d) = d + d - 265 , 7 x 2 R {d) = 0.5di - 16 , e 67 R {d) =di+ 5 0.25d - 206.25 , 2 R {d) = 86 , 4 R {d) = 2.756<2 + 1.504d - 640.88 , 3 X R (d) 2 2 = 0.318**! - 1.68 , R (d) = 0A41di + 0.207d - 91.75 . : 2 The lower bounding functions for the corresponding integer problems are _ / -°° ' ~ \ +oo R() < 0 if R {d) > 0 i f T7(J\ " 1 f{d) = R {d) , T5(J\ -I - [ 7 d 7 ' 6 -oo > ~ \+oo if R [d) < 0 if R {d) > 0 ' 5 5 I(<2) = R {d) , 4 f{d) 4 = max {R {d) , min {I (<f), I (d)}} , 3 6 7 I {d) = max {R (d) , min {l {d),f{d)}} , ^{d) = max {R}{d) , min {l {d),f{d)}} . 2 2 4 2 A sample of sensitivity analysis for d\ e (180,240) and d e (60,140) is given in 2 Table 4.1. The first number in each cell equals the optimal value Q(d) , the second number equals I (d) , while the third number equals R (d) . 1 1 68 di 180 190 200 210 220 230 240 12 -0.106 -0.106 74 55.56 6.26 12 4.29 4.29 84 79 10.67 84 79 12.74 84 79 14.81 86 79 16.88 86 79 18.95 86 79 21.02 12 8.69 8.69 84 84 15.08 84 84 17.139 84 84 19.21 86 84 21.29 86 86 13.09 86 86 19.49 86 86 21.56 86 86 23.63 86 86 25.7 86 86 27.77 86 86 29.84 86 86 17.49 86 86 19.76 86 86 21.83 86 86 23.9 86 86 30.11 86 86 22.1 86 86 28.31 86 86 30.38 86 86 32.45 86 86 34.52 86 86 36.59 86 86 38.66 86 86 26.51 86 86 32.72 d 2 60 90 100 110 120 130 140 74 74 8.33 74 74 10.4 74 74 12.47 74 74 14.54 74 74 16.61 86 84 23.36 86 84 25.43 86 86 32.18 86 86 34.25 86 86 34.79 86 86 36.86 86 86 38.93 86 86 41 86 86 43.07 Table 4.1: Sensitivity Analysis Sample for Example 4.1 69 Chapter V SIMULTANEOUS APPROXIMATION I N Q U A D R A T I C 0-1 P R O G R A M M I N G Consider the following quadratic programming problem min s.t. c x H—x 2 T T Di Ax>b (5.1) 0 < x < 1 x, where A is an m x n matrix, D integer is an n x n symmetric matrix, c and x are n-vectors and b is an m-vector. Problem (5.1) is a natural representation of many problems in, for example, finance [34] and capital budgeting [31]. Different approaches for solving the above problem can be found in the literature, e.g., linearization methods where the quadratic problem is transformed into a linear 0—1 or a mixed-integer program can be found, respectively, in Watters [47] and Glover [22]. Algorithms based on a branch and bound method have been proposed by many authors, e.g., Mao and Wallingford [37], Laughhunn [31] and Hansen [26]. McBride and Yormark [38] gave an implicit enumeration algorithm in which at each node they solve a quadratic programming relaxation of a corresponding integer subproblem using Lemke-Howston's complementary pivoting algorithm. It is conceivable that a 70 success of such an implicit enumeration algorithm depends greatly on the efficiency of the quadratic programming algorithm used. Although, at present, the polynomiality of an algorithm can not always be identified with real world computational efficiency or practicality, it is an important theoretical result which leads the research efforts in the direction of constructing efficient problem oriented polynomial algorithms. As stated in Section 1.5. Kozlov, Tarasov and Hacijan [30] provided the first polynomial time algorithm for convex quadratic programming problems. For a class of strictly convex quadratic programming problems, in Chapter II we proposed a polynomially bounded algorithm in which the number of arithmetic steps is independent on the size of the numbers in the linear cost coefficients and in the right hand side vector. We show in this Chapter how to replace the objective function of a quadratic 0 — 1 programming problem with n variables by an objective function with integral coefficients whose size is polynomially bounded by of optimal solutions. n , without changing the set We will use Frank and Tardos' [19] algorithm which in turn uses the simultaneous approximation algorithm from Lenstra at al. [33]. The above result assures that the running time of any algorithm for solving quadratic 1 0 — programming problems can be made independent of the size of the objective function coefficients. This since the equivalent problem can then be solved by e.g. an implicit enumeration algorithm in which at each node the continuous relaxation of the corresponding integer subproblem is solved in polynomial time independent of the size of the objective function coefficients. Observe that since (5.1) is a 0—1 programming problem then a constraint i with b{ > Ey=i \ ij\ a 15 clearly infeasible. This since Yl^=i ij j a x — Ey=i \ ij\ a < ^» • Therefore, assuming that (5.1) is feasible automatically assures that the entries of b can be bounded by the entries of the constraint matrix A . Note, however, that this 71 does not imply that the input size of 6 is polynomially bounded by the input size of A since 6 can be a rational vector ^ ( p T = (p,, ...,p ) , o r n = (gi, q ) ) where n the size of p and (or) q is not polynomially bounded by the size of the entries of A . In any event, if the entries in the constraint matrix are polynomially bounded by the number of variables and/or constraints, then the continuous relaxations of the integer subproblems can be solved in strongly polynomial time using the algorithm presented in Chapter II. Recall that in a strongly polynomial algorithm the number of elementary arithmetic operations (i.e., additions, comparisons, multiplications and divisions) is independent of the size of the input and is polynomially bounded in the dimension of the input (i.e., the number of data in the input). In Section 5.1. we state the problem and give some preliminary definitions. The extension of Frank and Tardos' preprocesing algorithm to quadratic 0 — 1 problems is given in Section 5.2. 5.1. SETUP OF T H E PROBLEM For simplicity of exposition we will consider a problem with an objective function in homogeneous quadratic form mm s.t. 2 Ax>b (5.2) 0 < x < 1 x integer . This can be done without loss of generality since the transformation of the objective function of (5.1) to the homogeneous quadratic form given in (5.2) can be easily 72 achieved as stated in Section 1.4. For the sake of completeness we will give here some details. For example, by adding a new variable y = 1 problem (5.1) can be restated as (5.2) with ' A 0 A = (;)< ,o 0 ' and 1 ' b= -1 . b ' 1 ; -1 . = I , - .,n we h ave c x + ^x Dx T T = \x {D + 2C)i T where C is a diagonal matrix with ca = c , i = 1, ...,n. t In the sequel we will use some vector and matrix norms as defined in Section 1.1. Let S = {x £ f?2 Ax > 6}, where B : 2 a feasible solution = {0,1} . A vector v G S is said to be of (5.2) while a vector z G S for which z Dz T < v Dv T for every v G 5 is said to be an o p t i m a l solution for (5.2). The following lemma will justify the algorithm to follow. LEMMA 5.1.1 If for every u,v G S we have sign(u — v) D(u T + v) = sign(u — v) D(u T + v) for some symmetric matrices D and D, then problems (5.2) with matrices D and D , respectively, have the same set of optimal solutions. PROOF (resp., We will show that every optimal solution of (5.2) with matrix D ) in the objective function is optimal for problem (5.2) with (resp., D D ) in the objective function. To that end suppose that for some u G S u Du 1 73 D < v Dv is valid for every o £ S. Then it follows from the symmetricity of D T u Du - v Dv T = (u- T v) D(u T that + v) < 0 for all v e S. Now sign(tt-i,) D(u r t,) = { 1.0 !J ^ < ^ if u Du — v Dv . 1 + TT TT J By the assumption, sign(u — v) D(u + v) = sign(u — v) D(u + v) . This means that T u Du < v Dv T T for every v G 5, which in turn implies optimality of u for problem T (5.2) with the matrix D in the objective function. • 5.2. S I M U L T A N E O U S A P P R O X I M A T I O N O F OBJECTIVE FUNCTION COEFFICIENTS Frank and Tardos [19] presented an algorithm which replaces a rational cost coefficient vector w of a linear programming problem with an integral vector w, without changing the set of optimal solutions. Their algorithm uses a revised ver- sion of Lenstra, Lenstra and Lovasz's simultaneous approximation algorithm ( L L L algorithm) which is strongly polynomial. For the sake of completeness we will state Frank and Tardos' algorithm (F-T algorithm) [19] : INPUT w = (w(l), OUTPUT rational vector and an integer TV with 1 < TV < 2n! ...,w(n)) w = (td(l),...,w(n)) integral such that || w < 2 ' + JV ( ) n +2n2 2n n n+2 and sign (w,b) = sign (w,b) whenever b is an integral vector with || b \\\< TV. 0. Let M 1. Let = 2" +"+ TV 2 Ul' = 1 n+1 , wi=w, w = 0 and i = 1. TT—Ti— I!*".- Moo 2. Apply the revised L L L algorithm to 1 1 74 TV and w'^l), ..^w^n). Let p t = (pi(l),Pi{n)) and 1 < qx < || qiw\ — pi | | o o < 1/-W and g; denote the output. Then 2 n 2 + n N . n 3. Let Wi+\ = q{Wi — pi and w = Mw + pi. If it>;+i = 0, H A L T . Otherwise let i = t + 1 and G O T O 1. END. The algorithm presented above can be generalized into a preprocessing algorithm that will transform the objective function coefficients of a 0—1 quadratic programming problem into integer coefficients whose size will be bounded by a polynomial function of n and for which the set of optimal solutions remains unchanged. As stated above, without loss of generality, we will assume the homogeneous form in the objective function. PREPROCESSING ALGORITHMFOR Q U A D R A T I C 0-1 P R O B L E M S I N P U T D = (dij) an n x n symmetric rational matrix and an integer N = An . 2 O U T P U T D = (dij) an nxn symmetric integer matrix with 6 < where h = ( + ) n n v) l a = sign(u — v) D(u T n d £ — max{dij + v) i,j 2h +2h = 1, ...,n} and for which sign(u — v) D(u for every integral u,v with || u l n : d 2 ||oo< 2 , 1 and || v ||oo< d2n-, •••> dnn) h + T S T E P 1. Construct a rational vector d = ( d u , d dij 2^+ ~ N ( \ 1- where is the entry in the i th row and j th column of the matrix D. Recall that since D is a symmetric matrix, we only need to approximate ^ n STEP n + 1 2 ^ elements of D. 2. Apply F - T algorithm to the vector d and integer N obtaining the integral vector d. 75 h+2 S T E P 3. Construct the integer, symmetric n x n matrix D = (d{j) using the entries of the output vector d. END . Theorem 5.2.1 to follow is a generalization of Theorem 3.1 in [19]. THEOREM PROOF 5.2.1 The matrix D satisfies the output criteria. Using the entries of the vector d{ (resp., d' , pi ) from F - T algorithm, { (resp., D' , P; ). Denote by <5 (resp., 7T; ) the construct a symmetric matrix { t largest absolute value of the entries in JD (resp., t P, ) and by r the number of iterations in F - T algorithm. The first part of the output criteria (i.e., the bound on the entries of D ) is satisfied by construction of the matrix D and since the F - T algorithm is valid. The validity of the second assertion can be shown in a similar way it was done in [19] as follows. Recall that for a matrix D its max-norm is given by || D \\oo— m a x KKnEj=i Now, we first show that (u — v) D{(u + v) > 0 T implies (u — v) Pi(u + v) > 0 . Suppose, on the contrary, that (u — v) Pi(u + v) < 0. T T Then, from the integrality of u,v (u - v) Di(u + v) < —1. Therefore r = 6i{u - v) {fP T { + ^{qijy. - P )}(tt + v) t < 6i{=± + i ( u - v) {q D' < + f + j-n < T t + v) = Si(u - t;) 7J^(tt + v) T <$i{^ and P , (u — v) Pi(u T t { || u - || tt - - P )(tt + v)} V ||i|| qiD\ t - Pi v ||oo n || qid\ ||oo|| « + - 76 p { V |]oo} |]oo|| « + v ||oo} <^{^r + i^(IMIoo + IIHIoo)} 2 which is a contradiction. Interchanging the roles of u and v will result in a reversed inequality which in turn proves that ( i t — v ) D i ( u + v ) = 0 implies (u—v) P{(u+v) T 0. T From F - T algorithm and the construction of the vector D,Pi,...,P it follows that D as well as D r Therefore, if -j- v) = 0 (u — v) P{(u T d and the matrices are linearly dependent on for each = i , then Pi,...,P . r (u — v) D(u T + v) = + v) = 0 and in this case the theorem is proved. Now, suppose that this (u — v) D(u T is not the case and that j is the smallest index such that (u — v ) P j ( u + v) ^ 0. T F - T algorithm implies that sign(u — v) D(u + v) = sign(u — v) Dj(u T sign(w — v) Dj(u is equal to + v) T T sign(u — v ) P j ( u + v), T J^ T , where M M ~ Pi r = 1 l it remains to show T that sign(u — v ) P j ( u + v) = sign(u — v) D(u + v). Since + v) . To that end recall that D = is given in F - T algorithm. By induction on k we will prove that for j <k <r , s i g n ( « — u ) P j ( u + v) = sign Yli=i M ~ (u-v) Pi(u-\-v) T For k = j this follows because k (u — v) P{(u the induction hypothesis is true for T + v) =0 k— 1 . l T for i < j . Assume that Without loss of generality assume sign(u-i;) Py(u-|-v) =+1 . Then sign YAZI Mk-1~i{u - v ) P i ( u + v) =+1 , which T T together with the integrality of u, v and P, implies fc-i M ~ - (u k l l + v) > 1. - v) Pi(u T i=i Now, k J2 M^iu - v ) P i ( u + v)=MY, T i=l M * - - * ^ - v) P {u 1 T > M - 2 NN h2+h h + v)>M- > 0. 4n || p ||oo 2 k 77 T t i=l + (u - v) Pk[u . + v) The last inequality follows from F - T algorithm since < Q i < 2 h 2 + h N f i . This completes the proof. || a'- \ \ o o — 1 implies || p; \\oo 1 • The preprocessing algorithm described above can precede, for example, an implicit enumeration algorithm for solving quadratic 0—1 programming problems. At each node, due to the above transformation, the continuous relaxation of the corresponding integer subproblem can then be solved in time independent of the objective function coefficients. Observe that we can always assume, without loss of generality, that the continuous subproblems are convex quadratic programming problems, i.e. the matrix associated with the quadratic terms is positive semidefinite (see e.g. [25]). 78 C h a p t e r VI AREAS FOR FURTHER RESEARCH In this thesis we extended a number of recent results for linear programming problems to quadratic programming problems. Moreover, the results from Chapter IV were shown to be valid for a broader class of problems, namely for nonlinear integer programming problems whose convex continuous relaxations satisfy a given constraint qualification. One possible avenue of further research is to try and extend the results obtained in Chapter III to a broader class of problems, for example to separable convex problems in which some or all of the variables are restricted to be integral. As far as Chapter V is concerned, one might try to extend the given result to quadratic integer programming problems in which the integral variables are not necessarily restricted to be 0 or 1 . In Chapter II a polynomial algorithm (whose running time is independent of the size of the linear cost coefficients and the right hand side vectors) was proposed for a class of strictly convex quadratic programming problems. It is an open question whether there exists a strongly polynomial algorithm for the above class of problems, as well as whether there exists such an algorithm for a class of linear programs. Finally, although the results in this thesis have mainly theoretical significance, one might investigate the practical benefits in some cases. For example, the calculation of 79 a lower bound on the objective function value of a problem with perturbed right hand side vector (see Chapter IV) might help a decision maker in deciding on a suitable changes of the initial right hand side vector. 80 Bibliography [l] A.Bachem and B.Korte, An Algorithm for Quadratic Optimization Over Transportation Polytopes , Z. Angew. Math. Mech. 58 (1978) 456-461 . [2] B. Bank and R. Hansel, Problems , Mathematical Stability of Mixed-Integer Quadratic Programming Programming Study 21 (1984) 1-17 . [3] M.S. Bazaraa, J.J.Goode and C M . Shetty, Management Science, 18 (1972) 567-573 . [4] M . S . Bazaraa and C M . Shetty, rithms, Constraint Qualifications Revisited, Nonlinear Programming, Theory and Algo- John Willey, New York (1979) . [5] M . C . Biggs, Constrained Minimization Using Recursive Equality Quadratic Pro- gramming , Numerical Methods for Nonlinear Optimization, ed. F . A . Lootsma, Academic Press (1972) 411-428 . [6] J . C . G . Boot, Quadratic Programming : Algorithms, Anomalies, Applications, Studies in Mathematical and Managerial Economics, Vol 2, ed. H . Theil, NorthHolland Publishing Company (1964) . [7] J.W.S. Cassels, An Introduction to the Geometry of Numbers, Die Grundlehren Der Mathematischen Wissenschaften In Einzeldarstellungen, Band 99, SpringerVerlag (1959). [8] W . Cook, A . M . H . Gerards, A . Schrijver and E . Tardos, Sensitivity Theorems in Integer Linear Programming , Mathematical Programming 34 (1986) 251-264 . [9] M . W . Cooper, Postoptimality Analysis in Nonlinear Integer Programming: The Right-Hand Side Case , Naval Res. Logist. Quart. 28 (1981) 301-307 . [10] R . W . Cottle, Symmetric Dual Quadratic Programs , Quart. Appl. Math. 21 (1963) 237-243 . [11] J . W . Daniel, Stability of the Solution of Definite Quadratic Programs , Mathematical Programming 5 (1973) 41-53. [12] J . L . Debiesse and G . Matignon, Comparison of Different Methods for Calculation of Traffic Matrices , Ann. Telecommunic. 35 (1980) 91-102 . [13] W.S. Dorn, 155-162 . [14] Duality in Quadratic Programming , Quart. Appl. Math. 18 (1960) _, A Duality Theorem for Convex Programs, IBM J. of Res. and Devel. 4 (1960) 407-413. 81 [15] B . C . Eaves, On Quadratic Programming , Management Science Vol. 17 No. 11 (1971) 698-711 . [16] J . Edmonds, System of Distinct Representatives and Linear Algebra , J. of Res. Nat. Bur. Standards 71-B (1967) 241-245 . [17] D . T . Finkbeiner II, Introduction to Matrices and Linear Transformations, A Series of Books in the Mathematical Sciences, Third Edition, ed. V . Klee, W . H . Freedman and Company (1978) . [18] R. Fletcher, An Algorithm for Solving Linearly Constrained Optimization Problems , Mathematical Programming 2 (1972) 133-165 . [19] A . Frank and E . Tardos, A n Application of Simultaneous Approximation in Combinatorial Optimization , 26-th Annual puter Science, IEEE, Symposium on Foundations of Com- New York (1985) 459-463 . [20] U . M . Garcia-Palomares and O.L Mangasarian , Superlinearly Convergent QuasiNewton Algorithms for Nonlinearly Constrained Optimization Problems , Mathematical Programming 11 (1976) 1-13 . [21] P . E . Gill, W. Murray, M . A . Saunders and M . H . Wright, QP-Based Methods for Large-Scale Nonlinearly Constrained Optimization , Nonlinear Programming 4, ed. Mangasarian, Meyer and Robinson , Academic Press (1981) 57-98 . [22] F . Glover, Improved Linear Integer Programming Formulations of Nonlinear Integer Programs, Management Science 22 (1975) 455-460. [23] M . Grotschel, L . Lovasz and A . Schrijver, The Ellipsoid Method and torial Optimization, Springer, Heidelberg, to appear. Combina- [24] L . G . Hacijan, A Polynomial Algorithm in Linear Programming , Soviet Dokl. 20 (1979) 191-194 . [25] P.L.Hammer and A . A . Rubin, 0-1 variables , Revue Francaise Math. Some Remarks on Quadratic Programming with d'Informatique et de Recherche Operationalle 4 (1970) 67-79 . [26] P. Hansen, Quadratic Zero-One Programming by Implicit Enumeration, Nu- merical Methods in Nonlinear Optimization, ed. F . A . Lootsma, Academic Press, New York (1972) 265-278. [27] M . Held, P. Wolfe and H . Crowder, Validation of Subgradient Optimization , Mathematical Programming 6 (1974) 62-88 . [28] R. Helgason, J . Kennington and H . Lall, A Polynomially Bounded Algorithm for a Singly Constrained Quadratic Program, Mathematical Programming 18 (1980) 338-343 . 82 [29] J . Kennington and M . Shalaby, A n Effective Subgradient Procedure for Minimal Cost Multy-Commodity Flow Problems , Management Science 23 (1977) 9941004 . [30] M . K . Kozlov, S.P. Tarasov and L . G . Hacijan, Polynomial Solvability of Convex Quadratic Programming , Soviet Math. Dokl. 20 (1979) 1108-1111 . [31] D . J . Laughhunn, Quadratic Binary Programming with Applications to Capital Budgeting Problems , Operations Research 10 (1970) 454-467 . [32] R. Lazimy, Improved Algorithm for Mixed-Integer Quadratic Programs and a Computational Study , Mathematical Programming 32 (1985) 100-113 . [33] A . K . Lenstra, H . W . Lenstra,Jr and L.Lovasz, Factoring Polynomials with Rational Coefficients , Math. Ann. 261 (1982) 515-534 . [34] J . Lintner, The Valuation of Risk Assets and the Selection of Risky Investments in Stock Portfolios and Capital Budgets , Rev. Econ. Statist. 47 (1965) 13-37 . [35] L . Lovasz, A n Algoritmic Theory of Numbers, Graphs and Convexity , Report No.85368-OR, Institut fur Okonometrie und Operations Research, Universitat Bonn, (1985) . [36] O . L . Mangasarian, Science (1969) . Nonlinear Programming, McGraw Hill Series in Systems [37] J . C . Mao and B . A . Wallingford, A n Extension of Lawler and Bell's Method of Discrete Optimization with Examples from Capital Budgeting, Management Science 15 (1969) 851-860. [38] R . D . McBride and J.S. Yormark, Finding all Solutions for a Class of Parametric Quadratic Integer Programming Problems, Management Science 26 (1980) 784795. [39] M . Minoux, A Polynomial Algorithm for Minimum Quadratic Cost Flow Prob- lems , European Journal [40] of Operational J . J . Moder and C R . Phillips, Research 18 (1984) 377-387 . Project Management with CPM and PERT , Reinhold Ind. Eng. and Man. Sci. Texbook Series, New York (1964) . [41] M . A . Radke, Sensitivity Analysis in Discrete Optimization , Ph.D. Disserta- tion, University of California , Los Angeles (1974) . [42] L . Schrage and L . Wolsey, Sensitivity Analysis for Branch and Bound Integer Programming , Operations Research 33 (1985) 1008-1023 . [43] A. Schrijver, Theory of Linear and Integer Programming 83 , Wiley-Interscience Series in Discrete Mathematics and Optimization (1986) . [44] J . Stoer and C . Witzgall, Convexity and Optimization in Finite Dimensions I, Springer-Verlag (1970) . [45] E . Tardos, A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs , Operations Research 34 (1986) 250-256 . [46] C . Van de Panne, Methods for Linear and Quadratic Programming, Studies in Mathematical and Managerial Economics (ed. H. Theil), North-Holland Publishing Company (1975) . [47] L . G . Watters, Reduction of Integer Polynomial Problems to Zero-One Linear Programming Problems , Operations Research 15 (1967) 1171-1174. [48] J . Wilkinson and C . Reinsch, tation, Linear Algebra, Handbook for Automatic Compu- Vol.2 , Springer-Verlag, New York (1971) . [49] P. Wolfe, A Duality Theorem for Nonlinear Programming, Quart. Appl. 19 (1961) 239-244. 84 Math.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Quadratic programming : quantitative analysis and polynomial...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Quadratic programming : quantitative analysis and polynomial running time algorithms Boljunčić, Jadranka 1987
pdf
Page Metadata
Item Metadata
Title | Quadratic programming : quantitative analysis and polynomial running time algorithms |
Creator |
Boljunčić, Jadranka |
Publisher | University of British Columbia |
Date | 1987 |
Date Issued | 2010-08-18T19:16:41Z |
Description | Many problems in economics, statistics and numerical analysis can be formulated as the optimization of a convex quadratic function over a polyhedral set. A polynomial algorithm for solving convex quadratic programming problems was first developed by Kozlov at al. (1979). Tardos (1986) was the first to present a polynomial
algorithm for solving linear programming problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand side and the cost coefficients. In the first part of the thesis we extended Tardos' results to strictly convex quadratic programming of the form max {cTx-½xTDx : Ax ≤ b, x ≥0} with D being symmetric positive definite matrix. In our algorithm the number of arithmetic steps is independent of c and b but depends on the size of the entries of the matrices A and D.
Another part of the thesis is concerned with proximity and sensitivity of integer and mixed-integer quadratic programs. We have shown that for any optimal solution z̅ for a given separable quadratic integer programming problem there exist an optimal solution x̅ for its continuous relaxation such that z̅ - x̅ ∞≤n∆(A) where n is the number of variables and ∆(A) is the largest absolute sub-determinant of the integer constraint matrix A . We have further shown that for any feasible solution z, which is not optimal for the separable quadratic integer programming problem, there exists a feasible solution z̅ having greater objective function value and with z - z̅ ∞≤n∆(A). Under some additional assumptions the distance between a pair of optimal solutions to the integer quadratic programming problem with right hand side vectors b and b', respectively, depends linearly on b — b' ₁. The extension to the mixed-integer nonseparable quadratic case is also given. Some sensitivity analysis results for nonlinear integer programming problems are given. We assume that the nonlinear 0 — 1 problem was solved by implicit enumeration and that some small changes have been made in the right hand side or objective function coefficients. We then established what additional information to keep in the implicit enumeration tree, when solving the original problem, in order to provide us with bounds on the optimal value of a perturbed problem. Also, suppose that after solving the original problem to optimality the problem was enlarged by introducing a new 0 — 1 variable, say xn+1. We determined a lower bound on the added objective function coefficients for which the new integer variable xn+1 remains at zero level in the optimal solution for the modified integer nonlinear program. We discuss the extensions to the mixed-integer case as well as to the case when integer variables are not restricted to be 0 or 1. The computational results for an example with quadratic objective function, linear constraints and 0—1 variables are provided. Finally, we have shown how to replace the objective function of a quadratic program with 0—1 variables ( by an integer objective function whose size is polynomially bounded by the number of variables) without changing the set of optimal solutions. This was done by making use of the algorithm given by Frank and Tardos (1985) which in turn uses the simultaneous approximation algorithm of Lenstra, Lenstra and Lovász (1982). |
Subject |
Nonlinear programming Quadratic programming |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2010-08-18 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0097502 |
URI | http://hdl.handle.net/2429/27532 |
Degree |
Doctor of Philosophy - PhD |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- UBC_1987_A1 S58.pdf [ 4.31MB ]
- Metadata
- JSON: 1.0097502.json
- JSON-LD: 1.0097502+ld.json
- RDF/XML (Pretty): 1.0097502.xml
- RDF/JSON: 1.0097502+rdf.json
- Turtle: 1.0097502+rdf-turtle.txt
- N-Triples: 1.0097502+rdf-ntriples.txt
- Original Record: 1.0097502 +original-record.json
- Full Text
- 1.0097502.txt
- Citation
- 1.0097502.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 18 | 0 |
China | 6 | 13 |
Republic of Korea | 4 | 0 |
Sweden | 3 | 0 |
Unknown | 3 | 1 |
France | 2 | 0 |
Canada | 2 | 0 |
Russia | 2 | 0 |
Ireland | 2 | 0 |
Australia | 2 | 0 |
Poland | 1 | 0 |
Spain | 1 | 0 |
Japan | 1 | 0 |
City | Views | Downloads |
---|---|---|
Unknown | 10 | 2 |
Ashburn | 8 | 0 |
Shenzhen | 5 | 13 |
Stockholm | 3 | 0 |
Sunnyvale | 2 | 0 |
Cambridge | 2 | 0 |
Vancouver | 2 | 0 |
Berkeley | 2 | 0 |
Madison | 2 | 0 |
Taganrog | 2 | 0 |
Hobart | 2 | 0 |
London | 1 | 0 |
Seoul | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0097502/manifest