Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Quadratic programming : quantitative analysis and polynomial running time algorithms Boljunčić, Jadranka 1987-12-31

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
UBC_1987_A1 S58.pdf [ 4.31MB ]
[if-you-see-this-DO-NOT-CLICK]
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

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.  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Country Views Downloads
United States 22 0
China 8 15
Republic of Korea 4 0
Sweden 3 0
Unknown 3 1
Canada 2 0
Russia 2 0
India 2 0
France 2 0
Ireland 2 0
Australia 2 0
Poland 1 0
Spain 1 0
City Views Downloads
Unknown 10 2
Ashburn 9 0
Shenzhen 7 15
Stockholm 3 0
Fort Worth 3 0
Berkeley 2 0
Taganrog 2 0
Madison 2 0
Vancouver 2 0
New Delhi 2 0
Cambridge 2 0
Hobart 2 0
Sunnyvale 2 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

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>
                        
                    
IIIF logo 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

Comment

Related Items