@prefix vivo: .
@prefix edm: .
@prefix ns0: .
@prefix dcterms: .
@prefix skos: .
vivo:departmentOrSchool "Business, Sauder School of"@en ;
edm:dataProvider "DSpace"@en ;
ns0:degreeCampus "UBCV"@en ;
dcterms:creator "Hawkins, Stephen Peter"@en ;
dcterms:issued "2010-02-22T22:38:14Z"@en, "1978"@en ;
vivo:relatedDegree "Master of Science - MSc"@en ;
ns0:degreeGrantor "University of British Columbia"@en ;
dcterms:description """The research addresses the problem of maximizing a zero-one quadratic function. The report falls into three main sections.
The first section uses results from Hammer [12] and Picard and Ratliff [23] to develop a new test for fixing the value of a variable in some solution and to provide a means for calculating a new upper bound on the maximum of the function. In addition the convergence of the method of calculation for the bounds is explored in an investigation of its sharpness.
The second section proposes a branch and bound algorithm that uses the ideas of the first along with a heuristic solution procedure. It is shown that one advantage of this is that it may now be possible to identify how successful this algorithm will be in finding the maximum of a specified problem.
The third section gives a basis for a new heuristic solution procedure. The method defines a concept of gradient which enables a simple steepest ascent technique to be used. It is shown that in general this will find a local maximum of the function. A further procedure to help distinguish between local and global maxima is also given."""@en ;
edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/20745?expand=metadata"@en ;
skos:note "ON METHODS FOR THE MAXIMIZATION OF A ZERO-ONE QUADRATIC FUNCTION by STEPHEN PETER HAWKINS B.Sc. (Economics), University of London, 1976 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE (BUSINESS ADMINISTRATION) in THE FACULTY OF GRADUATE STUDIES Department of Management Science Faculty of Commerce and Business Administration We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA May 1978 © Stephen Peter Hawkins In presenting th is thes is in p a r t i a l fu l f i lment of the requirements for an advanced degree at the Univers i ty of B r i t i s h Columbia, I agree that the L ibrary sha l l make it f ree l y ava i lab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho lar l y purposes may be granted by the Head of my Department or by his representat ives . It is understood that copying or pub l i ca t ion of th is thes is fo r f i n a n c i a l gain sha l l not be allowed without my wr i t ten permiss ion. Department pf M a / v a y / v w ^ V ^ o W g The Univers i ty of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date ferin. May Thesis Supervisor: F. Granot ABSTRACT The research addresses the problem of maximizing a zero-one quadratic function. The report falls into three main sections. The first section uses results from Hammer [12] and Picard and Rati i f f [23] to develop a new test for fixing the value of a variable in some solution and to provide a means for calculating a new upper bound on the maximum of the function. In addition the convergence of the method of calculation for the bounds is explored in an investigation of its sharpness. The second section proposes a branch and bound algorithm that uses the ideas of the first along with a heuristic solution.iprocedure. It is shown that one advantage of this is that i t may now be possible to identify how successful this algorithm will be in finding the maximum of a specified problem. The third section gives a basis for a new heuristic solution procedure. The method defines a concept of gradient which enables a simple steepest ascent technique to be used. It is shown that in general this will find a local maximum of the function. A further procedure to help distinguish between local and global maxima is also given. - i i -TABLE OF CONTENTS Acknowledgements v CHAPTER I 1. Introduction 1 2. Plan of the Report 2 3. Notation 3 CHAPTER II 1. Statement of the Problem and Prologue to the Research 4 2. Some Published Applications 5 3. Some Algorithms for Maximizing a 0-1 Quadratic Function 7 4. Computational Experience 12 CHAPTER III 1. Some Basic Concepts 13 2. The General Transformation 16 3. Relationship of Complementary Transformations to Other Results 19 CHAPTER IV 1. Introduction 21 2. A Result From Network Flow Theory 21 3. Simple Tests for Fixing the Value of a Variable 25 - i i i -4. Some More Tests for Fixing the Value of a Variable 28 5. Some New Upper Bounds on the Maximum of a 0-1 Quadratic 37 Function 6. Solution and Some Properties of the Bounding Problem 43 7. Convergence of, and Complementary Transformations in 49 Procedure 1 8. Improving the Upper Bound 56 CHAPTER V 1. Notation 61 2. Preview of the Algorithm 61 3. Preliminary Results 62 4. A Branch and Bound Algorithm 66 5. Some Comments on Branch and Bound Procedures 71 CHAPTER VI 1. Introduction 73 2. Some Preliminaries 73 3. A Procedure to Distinguish Some Local Solutions 75 4. An Example 78 CHAPTER VII 1. Conclusions 83 2. Epilogue 84 3. Further Research 84 BIBLIOGRAPHY 86 - iv -ACKNOWLEDGEMENTS I wish to express my gratitude to the peoples of the Common-wealth for giving me the opportunity to study for a Masters degree at the University of British Columbia. In particular I would like to thank Frieda Granot for super-vising this work, William Ziemba for his encouragement and support, Theresa Fong for her careful typing of this manuscript and to all the faculty, staff and students with whom I became acquainted during my brief stay in British Columbia. - v -To Catherine and all my other close friends with whom I share many fond and lasting memories. I will miss you a l l . - vi -- 1 -CHAPTER I 1. Introduction The research to be discussed in this report is concerned solely with the maximization of a quadratic function in which the variables are restricted to take only the values zero or one. This will be called a zero-one quadratic function. A realization of such a problem occurs in the following situation. For lunch a man visits a restaurant and selects one course from amongst the fixed number of dishes on that days menu. The food comes in standard portions, he can state the satisfaction he will obtain by consuming a single Dortion and he never orders more than one portion. In addition, there is an extra amount of pleasure or pain with the interaction of the tastes of two foods which he can also specify. If more than two foods are ordered the total enjoyment can be satisfactorily estimated by considering the sum of the interactions that occur between all possible pairs on the order. If i t is assumed that there are no other constraints on the order, the problem our subject faces in planning his meal is an example of maximizing a zero-one quadratic function. For added realism the diner can be replaced with a marketing manager planning the distribution of an advertising budget or a portfolio manager selecting from certain non-independent investment opportunities. - 2 -2. Plan of the Report The research proposed is to find some methods for solving this maximization problem. Chapter two provides a mathematical formulation of the problem and discusses the approach to algorithms that will be adopted. It ends with a limited survey of all the specific applications and algorithms that have been developed in the literature with regard to this problem. Chapter three is an introduction to a useful transformation that will be used extensively throughout the work. Chapter four describes some new approaches for reducing the size of the problem to be solved and for calculating an upper bound on the function to be maximized. Chapter five re-examines the branch and bound method of solution in the light of these results. The importance of heuristic solution techniques in the implementation of such methods will also be discussed. Chapter six details a method to solve the problem that can also be modified to produce several heuristic approaches. Finally chapter seven concludes the results in the current research and sheds light on further topics of interest. - 3 -3. Notation - The empty set {x: P(x)} - The set of x satisfying P(«)-Rn - The n dimensional real vector space. Constants denoted by a, b etc. and variables, unknowns etc. by x, y, z and so on. Rm x n - The space of (mxn) real matrices. Constants denoted by A, B, Q etc. In - The ( nxn) identity matrix. e1 - The ith column of In. A* - The transpose of A. {0,1}n - The set of elements in Rn with each component restricted to take the value of 0 or 1 only (i .e. the unit hypercube). {x-j}jjl\" ~ T n e s e t ° f elements {x^.Xg.. . .»x }. x e X - x belongs to the set X. A n B - The intersection of two sets A and B. A u B - The union of two sets A and B. . A c B - A is a subset of B. Max f(x) - Find an x e X such that f(x) >_ f(y) for all y e X. xeX N - The set {l,2,...,n}. Subsets of N are usually denoted by R, S, T etc. and referred to as sets of indices. S - The set of elements in N but not S. A x B - The set of ordered pairs (x,y) such that x e A, y e B. |A| - The number of elements in the set A. A - {i} - The set A without the element i . Other notation will be defined as used. - 4 -CHAPTER II 1. Statement of the Problem and Prologue to the Research This research is concerned exclusively with the problem of maxi-mizing a 0-1 quadratic function as described in the previous chapter. This can always be written as: Max x*Qx (P) xe{0,l}n where Q is a real symmetric (nxn) matrix. Throughout the work this formulation will be referred to as problem (P). This problem belongs to a theoretically important group of enig-matic mathematical programs, those for which there is no known algorithm that will solve i t in a polynomially bounded number of steps as discussed by Karp [19]. It is generally agreed that for such problems the speed at which they can be solved rapidly deteriorates with size. In this sense an algorithm for which the number of steps is bounded by such a polynomial will be cal1ed efficient. On the other hand a class of problems will be said to be solved efficiently i f there exists some algorithm, not neces-sarily efficient, for which a solution can be found in a polynomially bounded number of steps. However this research should be taken from a pragmatical viewpoint. Knowing that a problem cannot be solved efficiently is not very helpful since there may exist subclasses with this property. For nonlinear integer problems very l i t t l e work has been done in identifying such sets. - 5 -This report will attempt in some way to rectify this situation. Firstly improvements to existing branch and bound methods will be dis-cussed and secondly procedures that will check i f a problem can be solved efficiently by algorithms using these improvements will be given. 2. Some Published Applications The purpose behind this section is to detail some of the published uses for the maximization of a 0-1 quadratic function. No constrained problems will be described, although Hammer and Rubin [15] show that the problem of maximizing a 0-1 quadratic function subject to linear equality and inequality constraints can be converted to an unconstrained form. a) Selection Problems (e.g. Balinski [1], Rhys [25], Beale [2], Picard and Rati i f f [23]) A substantial number of different types of selection problem can be formulated. For an example consider the problem of minimizing the cost of partitioning a set V = {v-| , v 2 S . . • ,v } into two sets A and B with the following cost structure: v.j and Vj both belong to A, v.. and Vj both belong to B, v.j belongs to A and v^ - belongs to B, vn- belongs to B and Vj belongs to A. By defining a variable, x i , to be equal to one i f v^ belong to A and zero otherwise, the minimization problem becomes: \"a 1f - 6 -A direct application of this type of problem arises in Cluster Analysis, Rao [24]. This is a statistical technique for dividing a set of points into groups or clusters that possess some meaningful interpre-tation. Although many exact formulations for cluster analysis possess constraints, Edwards and Cavalli-Sfarza [6] have proposed repetitive usage of a dichotomous clustering routine until either the desired number of groups is obtained or each group satisfies some size criterion. The dicho-tomous clustering routine is an example of an unconstrained selection problem with an objective of minimizing intergroup distance or maximizing group separation. b) Factor Analysis (e.g. De Smet [3]) A somewhat indirect application of the maximization of a 0-1 qua-dratic function is to be found in Thurstone's centroid method of factor analysis. Briefly, factor analysis is a statistical method that attempts to resolve a class of descriptive variable into a much smaller set. Mathe-matically speaking, the problem is to find an (mxn) matrix A, such that: R = A^A + U, where R is the (nxn) correlation matrix of the descriptive variables and U is an nxn diagonal matrix such that the diagonal elements of R - U are the commonalities for each variable. The centroid method is a numerical procedure for finding such an A. A complete description can be found in Holzinger and Harman [19]. - 7 -The interest of this method to the present work lies in the fact that at one step the following problem has to be solved: Max x^x, xe{-l,l}p where B is a (pxp) real symmetric matrix (p <_ n). This can be seen to be a problem of maximizing a 0-1 quadratic function by the substitution: v . = \\ ( x . +1), i = 1,2,...,p. 3. Some Algorithms for Maximizing a 0-1 Quadratic Function In this section an attempt will be made to describe two methods that have been employed specifically to maximize a 0-1 quadratic function. It is not intended to survey any of the more general algorithms that could be used. a) Reformulation (e.g. Fortet [7], Glover and Woplsey [10]) The basic idea behind reformulation is that any problem of maximizing a 0-1 quadratic function can be written as a 0-1 linear integer programming problem. For example, consider the product term Q.-x-x-. This can be replaced by: Q. iy. -, along with the constraints: X i + X j - y i j < 1 i f Q.. < 0, - ( x i + X j ) + 2 Y i j < 0 i f Q i j > 0 . After this reformulation a 0-1 linear integer programming routine can be used to solve the problem. If the number of crossproduct terms is high, this reformulation will lead to a very large linear integer program. Given the current state of the - 8 -art for methods to solve linear integer problems, the conclusion must be that reformulation is not always computationally feasible. b) Branch and Bound Methods (e.g. Ginsburgh and Van Peetersen [9], Hammer and Rubin [15], Hansen [16,17] and Laughhunn [21]) The common approach in all of these schemes is to partition the set of all feasible points into a number of disjoint, totally exhaustive subsets. These are usually characterized by the variables that are given fixed values within them. In addition these subsets have to satisfy one of two conditions: a) An upper bound to the value that the function can take for any point in the subset is smaller than the maximum, or g) The value of the function is a constant for all points in the subset and is equal to the maximum. In practice the partition into subsets is not known and neither is the maximum value. Therefore each scheme commences with some arbitrary partition and refines i t until either a) is satisfied for the new subsets, which are now called fathomed, or e ) is satisfied. If the maximum is not known at the beginning of this procedure a trial maximum can be used instead. This will usually be the value of the function evaluated at some arbitrary point. As the computation proceeds the function value will be evaluated at other points. If at some point the function value exceeds the trial maximum this value will become the new t r i a l . - 9 -The art of any branch and bound scheme lies in the choices of: i) the initial partition into subsets, i i ) the order of choosing the subsets that have not been fathomed for further division (branching), i i i ) the upper bound. The major advances in applying branch and bound methods to the maximization of 0-1 quadratic functions have come in the areas of selec-ting an upper bound and in generating some additional information that enables a subset to be fathomed without the upper bound. Both of these will be described separately. i) Penalty Functions (Hansen [16,17]) A penalty is defined to be a decrement to the upper bound: 0 _ vi=n vj=n - \" M=l Lj=i of 0 or 1, a valid upper bound for the restricted problem is obtained. To see how penalties are useful in providing upper bounds let p^ and pi be the decrement to z^ when variable x. is fixed at 0 and 1 J J respectively. Then {z® - p9) is an upper bound for: Max xV. (z° - pi) for: Max x*Qx xe{0,l}n J xe{0,l}n x . 0 xj-l and ( z ° - min(p^,pl)) for: Max x^ Qx. J J xe{0,l}n The most useful set of penalties are those which are additive, in the sense that the sum of the penalties associated with fixing the values z \" = Ii=i Ij=i max(0,0^j), such that i f a variable is fixed at a value - 10 -of a set of variables is a penalty for the whole set. The penalties: p9 = max(0,Qjj) + ^ max(0,Q...), i=l p i = - m i n f O . Q . j ) . are additive. It also follows that: z1 = z ° - ipmin(p0,pj), (2.1) is a new upper bound for the maximum of the function. Observe that the bound in (2.1) does not take account of the nega-tive elements in Q. This can be done by noting that, q. = pi - p9, is 3 3 3 the change in the penalty obtained by fixing the variable, x-, to equal 1 instead of 0. Also i f q. _< 0, then x- was implicitly fixed at 1 when computing (2.1). Therefore i f : q^ £ 0 , < 0 and Q .^ £ 0 , (2.1) can be further reduced by -Q^- unless q. _> 0 -^ or q^ _> Q^-. In the former case the bound can be reduced by -q^ and by -q- in the latter. This procedure can be extended to cover the case when more than one negative element is considered as follows. Let q. = min(0,q.) and J J r - j = max(Qi j.B^^. ,ejq.), where 0 < _< 1 (i = 1,2,... ,n; j = 1,2,... ,n) anc' t\\=] &j = \"1 (J = l » 2 , . . . , n ) . Then the following is an upper bound on the maximum of the 0-1 quadratic function: - 11 -2 = 1 yi-n rj=n z z + M=l j^=l r i j Q i j < o i 2 The values of 3- that minimize z can be found by a linear program. •J i i ) Fathoming Constraints (e.g. Hammer and Rubin [15], Hammer and Hansen [13], Laughhunn [21]) A constraint will be called a fathoming constraint i f its violation necessarily implies that a point cannot be a solution. Two types of fathoming constraint have been suggested. The first follows from :the fact that although an upper bound for a subset may suggest that a solution lies within i t , in fact no such point does. The conclusion would be that the constraint: x^ Qx _> M (M = maximum or trial maximum) should be considered for every subset. The second type of constraint follows by considering the definition of a local maximum for a 0-1 quadratic function. A point is said to be a local maximum of its function value is equal to or higher than for any other point that differs from i t in a single coordinate. In [15] i t is shown that a point is a local maximum i f each of the following constraints is sati sfied: (2Xi ~ D d j j - 2 Q i j X i + Q..) > 0 (2-2 i) (i = l , 2 , . . . , n ) . .j=l Since a global maximum is necessarily a local maximum, the validity of the constraints as fathoming constraints is obvious. - 12 -Even i f a fathoming constraint is not violated by all members of a subset some useful information may be obtained. For example a fath-oming constraint may be satisfied only i f certain free variables must have fixed values. This will certainly affect the manner in which the subset is divided further. Illustrations of methods for finding such implications can be found in the references. 4. Computational Experience To my knowledge there are no reports of computational experience with algorithms to maximize an unconstrained 0-1 quadratic function specifically. However Hammer and Peled [14] give some details of results for maximization of a general unconstrained non-linear 0-1 function. Some authors have reported experience for constrained 0-1 quadratic programs using a branch and bound algorithm. These can be found in Hansen [16,17], De Smet [3], Laughhunn [21]. - 13 -CHAPTER III This chapter will be used to introduce a very simple transfor-mation of the original maximization problem (P) into an equivalent one. 1. Some Basic Concepts The idea behind the transformation will be explained here in a simplified form. The obvious generalization that will be used in the remainder of the work is given in a later section. The transformation uses the concept of the binary complement of a variable. This is defined to be another variable, x, such that the iden-tity, x = 1 - x, always holds. The transformation is designed to produce another problem, using the variables, {x-| ,Xr,, ••• >xj_i >*i >x-j+p • • • ' x n ^ » such that i f x e {0,1 }n is a solution to the original problem then y e {0,1 }n, with ^ = x ] , . . . . y ^ T = x._-, = 1 - x i , . . . and y p = xn, is a solution to the new problem. Define a. matrix transformation C 1 : R n x n -> R n x n such that: c 1 ' [ Q ] j j = \" Q i i i f j = } ( 3 J ) Q., + 2Q, . otherwise (3.2) c 1 [ Q 3 j k = _ Q ik i f j = ]* ( 3 - 3 ) -Q^. i f k = i (3.4) Qjk otherwise (3.5) - 14 -In addition let cn(x) = (x-j,... >x.j >x.j+-| , . . . ,xn) 'C 1 [ • ] will be called the complementary transformation of Q at i . The following lemma justifies the claim from the preceeding para-graph about C. Lemma 3.1 For all x e {0,1 }n c1 (xjV-tqic1 (x) = xV - Q^ - (i = l ,2 , . . . ,n ) Proof Let A be a matrix satisfying (3.1) to (3.5) then: c i(x) tAc i(x) = lp} I*™ A ^ c ^ x ^ . c ^ x ) ^ (3.6) -nl^^M/M, (3.7) k=l + A i i c 1 ( x ) i c 1 ( x ) i (3.7) + V 1 ( x ) / ( x ) k ( 3 - 8 ) j=l k=l (3.6) = -2 I*™. Q i k(l - X i ) x k [by (3.4)] k=l 2 i $ Q k=l i k x i x k - 2 EkVi Q ik x k k=l (3.9) - 15 -(3.7) = - Q . ^ l -x.)( l -x.) [by (3.1)] (3.10) j=l k=l j=l = 1$ Z g ? Q i k x j X k + 2 I j - Q j i X j [by (3.2) and (3.5)] (3.11) j=l k=l j=l Hence by summing (3.9), (3.10) and (3.11) which is the desired result. • The following example illustrates these ideas, Example 2.1 Let Q 1 -1 0 -1 -1 2 0 2 0 - 16 -x Qx = 1 • x-j - 1 • x2 - 1 • x-j • x2 + 4 • x2 • = (1 - x-|) - 1 • x2 - 2 • (1 - x-|) • x^ + 4x2 • x3 1 - 1 • x-j - 3 • x2 + 2xn • x2 + 4x2 • x^ 1 + (x] ,x 2 ,x 3) •1 1 0 1 -3 2 0 2 0 f - \\ x l x2 • x3-= 1 + c^xjV [Q]c](x). • Two very obvious results about this transformation are: Corollary 3.2 C^C^Q]] = 0 (i = 1,2,.. .,n). • Corollary 3.3 x e {0,1 }n is a solution to Max x^ Ox i f and only i f cn(x) is t , xe{0,l}n a solution to Max x C [Q]x. • xe{0,l}n 2. The General Transformation In the general transformation the single index is replaced by a subset S of N. The basic idea is to make a substitution, in terms of i t ' s binary complement, for every variable whose index is in S. - 17 -The definition of the complementary matrix to Q at S is now given by: c Win- - Q i i \" 2 heS Q i j i f 1 £ S = Ql1 + 2 heS Qi3 i f 1 e ^ C J [Q] i d = Q i d i f (i , j) £ (SxS)u(SxS) otherwise. In addition let cS(x) be the vector in {0,1}n/such that: c ° ( x ) i = x. i f i e S 1 - x. i f i e S. The consistency of these definitions with the previous section can be seen by identifying: S 1 (T[Q] = C 1 l-i r i ? 1 1 le C L . . . |C K[Q] where S { i ^ » i 2 » , - - ' \" ' | ^ ^ -The following are analogues of lemma (3.1) and corollary (3.3). - 18 -Lemma 3.4 For all SCN, c S(x) tC S[Q]c S(x) + lus I J £ S Q i j = xV- • Corollary 3.5 x e {0,1}n is a solution to Max x^ Qx i f and only i f xe{0,l}n c (x) is a solution to Max x Cb[Q]x. • xe{0,l}n Example 2.2 Using the Q from example (2.1) C m [ 0 j -1 1 0 1 - 3 2 0 2 0 C { 1 ' 2 }[QJ 1 -1 0 •1 3 -2 0 -2 4 _ .{2} -1 1 1 -3 0 2 0 2 0 C{1,2,3} [Q] 1 -1 •1 -1 0 2 0 2 -4 = C {3} 1 -1 •1 0 3 -2 0 - 2 4 • - 19 -For the purposes of interpretation lemma (3.4) shows that the general transformation is simply a relocation of the origin and a reflection of the axes of those variables for which the binary comple-ment has been substituted. 3. Relationship of Complementary Transformations to Other Results The complementary transformation has appeared in two other papers, Hammer and Rubin [15] and Picard and Rati i f f [22], In both papers i t was used to provide a criterion for establishing whether a given point was a solution to (P) or not. Their optimality conditions can be obtained as follows. Theorem 3.6 Hammer and Rubin [15] x e {0,1}n is a solution of (P) i f and only i f for every S c N, Corollary 3.7 Picard and Rati i f f [22] x e {0,1}n is a solution of (P) i f and only i f u eJJn i } n ( E f t lp} 2 ( 2 ^ - 1 ) ^ ^ - I j - I j - ( 2 x j - l ) ( 2 x i - l ) Q i j u i u j (3.12) is equal to zero. • - 20 -It should be noted that the coefficient of u. «u- in (3.12) is just C S[Q],, , where S = {i: x. = 1}. - 21 -CHAPTER IV This chapter will look at some aspects of a branch and bound algorithm for maximizing a 0-1 quadratic function. 1. Introduction In Chapter two branch and bound algorithms for problem (P) were described and two specific embellishments were also discussed. The first of these was an improvement in the calculation of the upper bound and the second was in defining relationships that may lead to fathoming or fixing the value of a variable. This chapter shows that a unified approach can be adopted for both of these types of improvement. This unification is in the sense that a similar calculation procedure can be used in either. In addition it will investigate the effect of generating bounds and fathoming constraints from complementary transformations of the original problem. 2. A Result from Network Flow Theory It will now be demonstrated that for certain types of 0-1 quadratic function, the problem of finding the maximum is equivalent to finding the maximal flow through a constrained network. Consider the problem: Max n x*Qx (PP) xe{0,l}n - 22 -where Q e R is a real symmetric than those on the diagonal are non Also consider the following Max f f,x 0 < x 1 ; j <_ ?. t ( i matrix such that the elements other negative. 1inear program: f i f i=l < 0 i f i71 or \\H (MFP) -f i f \\=i. This is the linear programming formulation of the problem of finding the maximal flow in a capacitated network. Let L = { 1 , 2 , . . . , £ } and P be the set of al1 subsets, S, of L such that 1 e S and I | S. Define a set function g: P ^ R as follows: 9 ( S ) = £ ( i , j ) £ S x S F i j \" The next result is the maximum flow, minimum cut theorem of Ford and Fulkerson [8]. Theorem 4.1 Min g(S) = Max f SeP f eT where T is the feasible region of MFP. • - 23 -Corollary 4.2 (Hammer [12]) There exists an A e R £ _ 2 > a \" 2 and a c e R such that: Max f = Min ? z z t \\ z + c. feT ZeCO,!}*\"^ Proof Let S be an arbitrary subset of P and z . = 1 i f i e S and = 0 otherwise. Then: 9~~ ! ; j = 2 , 3 , . . . , £ - 1 ) A i i = F i j - F1i + F i ( i = 2> 3\"-->^) c = y J = £ F C j^=2 The desired conclusion is now apparent. • - 24 -The last corollary shows that to every maximal flow problem there exists some 0-1 quadratic function that is minimized. If A . . £ 0 (i t j ; i = l , . . . , n ; j = l , . . . , n ) then i t is obvious that the reverse conclusion is true. Hence the next corollary. Corollary 4.3 (Picard and Rati i f f [23]) Problem (PP) can be solved by a maximal network flow algorithm. • The importance of these results l ie in the properties of some algorithms to solve the maximal flow network problem. These algorithms have been shown to be such that the number of computations required to find a solution is bounded by a polynomial function in the number of variables in (MFP). This implies that the number of computations to solve (PP) will also be bounded by a similar polynomial in the number of its variables. In contrast the problem of maximizing a general 0-1 quadratic function does not have such a good bound. To illustrate the bounds for the three most well known procedures to solve the maximal flow problem are given below in Table 1. - 25 -Algorithm Highest Power in Polynomial Bound to Solve (PP) Ford and Fulkerson [7] 5 (with Edmonds and Karp [5] modification) Dinic [4] 5 Karzanov [20] 3 Table 4.1 - Polynomial Bound for Maximal Network Flow Algorithms Although this type of bound does not guarantee that problem (PP) will be solved in the shortest time possible on every occasion, experience suggests that in general this is so. In particular as the number of variables increases the improvement over a branch and bound scheme may be quite great. 3. Simple Tests for Fixing the Value of a Variable This section will present two very simple tests for fixing the value of a variable. Firstly define the following subsets: T + (i) = {j: > 0, j / i } and T\"(i) = {j: Q... < 0, j jH} (4.1) - 26 -The next result gives these simple tests in a precise form. Theorem 4.4 If there exists an index i such that either: • ° r Q i i + 2 J.1eT-(i) °id ^ 0 <4-3> then for some solution, x e {0,1}n, of (P), x. = 0 i f (4.2) and x. = 1 i f (4.3). Proof Suppose y e {0,1}n and y. =1. Then i f (4.2) holds: j=l j=l k=l j=l k=l Hence i f y is a solution to (P), then y* e {0,1 }n, with y*. - y. (j f i) 3 3 and y | = 0, must also be a solution to (P) and the first case is proved. A similar proof holds for (4.3). n The subsequent theorem answers the question about applying these simple tests to a complementary transformation of Q. 27 -Theorem 4.5 Let S be an arbitrary subset of N, A <<> + 2 W ( 1 ) 9 1 J • A \" ( 1 ) - « 1 1 + 2 W ( 1 ) q U ' and B*(1) - CSW^, + 2 Z J e CT*(1) c Si:«« B\"(1) - CSW3„ + 2 Z J ccT-{i ) c S E« fj. where CT +(i) = {j: C S[Q]., > 0} and CF( i ) = {j: C S [ Q ] , . « 0} Then: A +(i) = B +(i) i f i 4 S, (i) A +(i) = B\"(i) i f i e S, (ii) A\"(i) = B\"(i) i f i £ S and ( i i i ) A\"(i) = B +(i) i f i e S (iv) for all i e N. - 28 -Proof Only case (i) will be proved. The remainder can be proved similarly. From the definition of complementary transformations at S c S M i i + 2 W ( i ) c S [ Q ] i j - \" i i + 2 Zj .s'lJ + 2 W o j r S O l J \" 2 ^ e r ( i ) n S Q i j ' Q i i + 2 £j ESnT+(i) + 2 ^ e T + ( i ) n 5 Q i j The last theorem shows that i f a variable can have its value fixed by the tests in theorem (4.,4) then i t must also be fixed in any problem equivalent to (P) by a complementary transformation. Therefore nothing is to be gained by applying the test to any other than (P). In later sections other tests will be proposed for which this conclusion is not valid. 4. Some More Tests for Fixing the Value of a Variable In this section some more tests for fixing the value of a variable will be proposed. The amount of computation in these tests is greater than those for section two but they yield stronger implications. - 29 -Define a new matrix Q° as follows: Q^ - = Q-j-j (i = l ,2 , . . . ,n ) .Q?j = max(0,Qij.) ( i / j ; i = 1,2 n; j = l ,2 , . . . ,n ) and a new maximization problem: Max xVx. (PO) xe{0,l}n The following theorem will yield a test to fix the value of certain variables at zero. Theorem 4.6 Suppose x e {0,1}n is a solution to (P) with S = {i: x. = 1}. Then there exists a y e {0,1}n that is a solution to (PO) with T = {i: y\\ = 1} such that Sc T. Proof Suppose S - T f <(> for all solutions to (PO). As x is a solution to (P) i t must be that: heS-T heS Q i j ^ 0 and therefore that: - 30 -L l e S - T LJeS ' i j -Since: IieSUT IjeSuT Q°j = IieT £ j e T Q°j + Ii£S_T ^sujQ?^ it-follows from (4.4) that: ^ieSUT ^jeSUT Q i j - ^ieT ^jeT Q i j This contradicts the assumption and therefore S - T = for some solution to (PO). This proves the proposition. • Corollary 4.7 Let {x1} be the set of all solutions to (P) and S 1 = { j : xj =1). Then there is a solution y of (PO) with T = { j : y. = 1} such that u S. c T. • The last corollary leads immediately to the following test for fixing the value of a variable. Let {y1} be the set of all solutions to (PO) and T1 = { j : yj = 1}. Let Y be the set of all solutions in {y1} that are maximal with respect to the inclusion relationship; i .e. y1 e Y i f and only i f T1 <£ T J for all y J e {y3}. In addition define T = n T 1 . Then i t follows from yieY corollary (4.7) that for i at T, = 0 for all x J e {x }. - 31 -Intuitively the best transformation of the problem (P) to be used in this test would be any of those such that (0,0,...,0)^ is a solution of the transformed problem. However to find this would require knowledge of a solution to (P) or at least some point that is suspected to be a solution. Finding such a point introduces a novel feature and will be discussed in a later chapter. The next simple example illustrates the test. Example 4.1 \" 0 4 0 0 \" 4 CO 2 0 0 2 -6 2 0 0 2 -3 The solutions are (0,0,0,0)L, (1,0,0,0) and (1,1,0,0). The test now allows x^ and x^ to be deleted. It should also be noted that these variables would not have been deleted under the test in section two. • The last theorem dealt with the case of fixing the value of a variable at zero. The next result will give the condition needed to fix the value of any variable at one. Firstly a new matrix oJ is defined as follows: 0.]- = max(0,Q.i) ( i * j ; i = 1,2, — ,n; j = l ,2 , . . . ,n ) - 32 -which also leads to a new maximization problem: Max xVx. (PI) xe{0,l}n Theorem 4.8 Let x e {0,1}n be a solution to (PI) with T = {i: x- = 1}. Then there exists a solution, y e {0,1}n, to (P) with S = {i: y. = 1} such that Tc s. Proof The proof is similar to that in theorem (4.6) with the roles of T and S reversed and using: j^eR ^ieR Q i j - j^eR ^ieR Q i j for any arbitrary subset R of N. • The test for fixing the value of variable at one is simply to find a non-zero solution to (PI) and fix all the variables that have value one, at one in a solution of (P). Intuitively the best transformation would be that for which (1,1,. . . ,1)* is a solution to (PI). Once again this requires some know-ledge about a suspected solution as in the other test. The two tests are in fact identical in the sense that C^EC^CQ]1] = Q°. This implies that i f there is some solution x e {0,1} of (PO) such that - 33 -x.j = 0, then xi = 0 in some solution of (P). The following example will clearly illustrate this, Example 4.2 Q = 0 4 -1 -2 4 -8 2 0 -1 -2 2 0 -6 2 2 -3 0 4 0 0 4 -8 2 0 0 2 -6 2 0 0 2 -3 This is essentially the same matrix as that in example (4.1) Now CN[Q] = -2 4 -1 -2 4 -4 2 0 •1 2 0 2 •2 0 2 3 and [CN[Q]]] -8 4 0 0 4 -4 2 0 0 2 -2 2 0 0 2 -1 The solutions of: XVLQ ] ]^ are: (1,1,1,1)*, (0,1,1,1)* . A t i u , I J j. (0,0,1,1) l. Therefore from theorem (4.8) i t follows that (1,1,1,1) Max x£{0,l} . t„N, a solution to: Max , x C [Q]x. xe{0,ir • - 34 -The discussion in the last paragraph would seem to imply that for test one to be at its strongest, the transformation to be used should be the one that leads to a problem (PO) with one solution containing as many variables with a value zero as possible. The next result is helpful in this respect. Theorem 4.7 Let x e {0,1 }n be a solution to Max xV x^ and S = {i: x. =1}. xe{0,l} t S 0 1 Then there exists a solution y e {0,1} of: Max y C [Q] y, with y e{0,l}n T = {i: y i = 1} such that TcS . Proof From the definitions of a complementary transformation the following are true. C S [Q 0 ] . . = Q.. + 2 T. CQ°. i 4 S C S[Q 0]. . = Q.. - 2 7. CQ?. i e S ^ [ Q 0 ] ^ = Q?j (i , j ) e (S x S)u(S x S) C S [Q 0 ] i : J = -Q?j (i , j) e (S x S)u(s x S) CSIQ?U - - 2 & j e s Q l J = CSIQ\\ + 2 lusCSm% 1 e S (4.6) - 35 CS[Q]?j = Q?j = C S [ Q ° ] i : j ( i , j) e (S x S)u(S x S) (4.7) CS[Q]?j = max(0,-Qij) (i , j) e (S x S)u(s x S) (4.8) Let x E {0,1}n be arbitrary with R = {i: x^ = 1}. Then: ^ieRnS j^eROS C ^ i j + i^eRnS ^jeRns C ^ i j + 2 Xi.Rns hart c S « ] ? J Now consider the second term above: Eieins ^JEROS ^ ^ i j ^ieRnS ^ ^ i i + ^ieRns j^eRnS C S W ]?j l i t * * c S W 0 ] i i - ^ i e R n s Z j e S + heMS IjeROS CSCQ°Jij from (4.5) and (4.7). The second term from this last equality satisfies: i^ERnS EjeS C ^ i j ±- ^ ieRns ^jeRns ^ ^ i j since only positive numbers are subtracted from the left. - 36 -Putting all these results together gives: ^ieR E j e R c S ^ i j 1 i^eRnS ^ e R n S ^ 0 ^ j + i^eRnS ^jeRnS^^^ij - i^eRnS ^jeRnSC j * The last inequality following by the optimality of x and lemma (3 .4) . Hence it follows that for any solution y e {0,1}n of: Max . . ^ (^ [Q^y , with R = {i: y. = 1}, there is also a solution y e {0,1 } n y £ {0 , l } n 1 with y. = 1 i f i e R n S and zero otherwise. This proves the theorem. • Example 4.3 Continuing from examples (4.1) and (4.2) c n , 2 } [ Q ] o •8 4 4 0 1 0 2 0 1 2 0 0 -4 2 2 -7 One solution to: Max d x l C l 1 , c s [Q] x, is ( 0 ,0 ,0 ,0 ) L . This xe{0,ir t plainly illustrates the theorem as (1,1,0,0) was a solution to Max xVx. • x £ {0 , l } n - 37 -5. Some New Upper Bounds on the Maximum of a 0-1 Quadratic Function This section will use the same approach as in the last sections to produce an upper bound on the maximum of a 0-1 quadratic function. Firstly i t should be noted that as Q° was formed from Q by deleting those elements that are strictly negative and off the diagonal, the following theorem is true. Theorem 4.10 Max x*Qx < Max xtQ°x (4.9) xe{0,l}n xe{0,1}n • As was explained earlier the right hand side of (4.9) may be a lot easier to compute than the left hand side. This property makes: Max x ^ x , fairly attractive as an upper bound. However this bound x£{0,l}n is usually not very sharp as the next example demonstrates. Example 4.4 \" -2 3 -2 \" \" -2 3 0 Q = 3 -4 .1 Q° = 3 -4 1 -2 1 -1 0 1 -1 - 3 8 -Max ^ x Qx = 0 and is attained at (0,0,0) and Max x Q x = 1 xe{0,ir t xe{0,ir and is attained at (1,1,1) . Another interesting aspect of this example is that the same point is not necessarily a solution for both the left and right hand sides of (4.9). • A direct corollary of theorem (4.9) can be used to provide some information about equality in (4.9). Corollary 4.11 Let x e {0,1} be a solution to Max x Q x and let Max x Qx = x Q x. Then Max x Cb[Q]ux = 0, where S = {i: x. = 1}. xe{0,l}n xe{0,l}n 1 Proof Since equality holds for (4.9) i t must be that Q9^ = Q .^ (i f j ; i e S; j e S ) . In turn this implies that: c S t < -Q„ - 2 Ij.s«i. - csCQ°3„ KS. a\"d han ^ e R n S C S W ^ \" W W ^ l d < 0 . where the last inequality follows by the optimality of x. Therefore for arbitrary xce {0,l}n, xtCS[Q]9, <_ 0, by theorem (4.9) and the corollary is proved. • - 39 -The converse of this corollary may in general be false. The following illustrates the corollary's weakness. Example 4.5 1 1 -1 1 -4 1 -1 1 1 = 1 xe{0,l}' 1 1 1 -4 0 1 0 1 1 at x = (1,0,0)* or (0,0,1) Max x tQ°x = 2 x e{0,l} J at x = (1,0,1)* or (1,1,1 )* But C { 1 } [Q] = -1 -1 1 -1 1 -2 1 1 -1 C { 1 } [ Q ] ° -1 0 1 0 -2 1 and Max x*C 1 [Q]°x = 0 at (0,0,0)*, (.1,0,1 )*:and (1,1,1)*. xe{0,l}n This transformation would not have been given by theorem (4.8) directly. • - 40 -Max xe{0,l} n x Q x may not be a very precise bound since i t ignores the off diagonal elements of Q that are strictly negative. However a useful property i t possesses is that i t can be calculated with an effi-cient algorithm. The next part of the research looks at a more precise bound that takes into account these elements and yet retains the conditions necessary to be able to use an efficient algorithm in it 's calculation. Firstly some more definitions. Let Q(x) e R n x n be given by: j£r(i)Aij (i = 1,2,....n) Q(x). , = max(0,Q, •) (i f j; i =1,2 n; j =1,2,. • • 9 n), where the X. • are any real numbers satisfying: 0 > X-j > 2 Q i j . The next theorem allows a new upper bound to be calculated. Theorem 4.12 Let P = (X: 0 > X..->2Q.,; i = 1,2,... ,n; j e T\"(i)}. Then n x°Qx. - 41 Proof For any x e {0,1 }n let S = {i: *. = 1}. Then: \" 2 ^i=l ^jeT\"(i) xi j Consider the last two terms on the right hand side. ^ieS £ j e T \" ( i ) X i j \" I ^i=l ^ e T \" ( i ) A i j ^ieS ^jeSnT\"(i) xij + ^ieS ^jESnT~(i) rDieS ^jeSnT\"(i)Xij + ^ieS £ j e S n T ~ ( i ) x i + 2 UeS ^jeSnT'(i')Xij] \\ UeS ^jeSnT\"(i)Xij \" \\ ^ieS ^j eSnT~(i)Xij' - 42 -Therefore x ^ U t f \" j XjlT I j ^ d J ^ l j • + 1 IieS I j esnT-(i)^i3 2 £ i e S ^j e SnT\"(i) X i j ' Taking the minimum of both sides with respect to \\ e P yields: MintxtQUJx - 1 I j e T - ( 1 )V - xV. The desired conclusion is now apparent. • Corollary 4.13 ^3 r n V \" U t Q ( X ) X \" * ^ XJET-(1)x1j) ^ M a x x ^ x -Proof The follows from the theorem along with the fact that: Max Min g(x,y) <_ Min Max g(x,y), XeX yeY yeY XeX for any independent sets X and Y and all g: X x Y P.. • The calculation of this new upper bound involves solving the following problem: - 43 -This will be called the bounding problem for Q. An algorithm to facilitate solution along with some of the properties of (BP) will be given in the next section. 6. Solution and Some Properties of the Bounding Problem The bounding problem (BP) is an example of a non-differentiable optimization problem. However there does exists a simple equivalent form for which a solution can sometimes be characterized. It is this approach that will be followed in this section. To begin i t should be noted that for any finite n, {0,l}n is a finite set of points. Hence (BP) is equivalent to the following linear program: Min w (BLP) W,A s.t. w > (XVQUMX *-) - i j e T - ( i ) A i j U = 1.2,....M) X e U: 0 > X.j > 2Q.J; i = l , 2 , . . . , n ; j e T \" ( i ) } = P where i s ^ - e - M = 2 n). - 44 -Observe that for large n, (BLP) has a very large number of constraints. Hopefully there will be very few that are binding for the solution. Procedure 1 below attempts to exploit this property by solving a sequence of relaxations of (BLP) that are generated by considering the violated constraints in (BLP) for each relaxation. Procedure 1 Step 0 Set k = 1 x1 = (0,0,. . . ,0)*. Step 1 Find A k e P that solves: Min wk [Note 1] s.t. wk > (x P) tQ(x k )(x P ) - \\ ^ l ^ - ^ . (1 < p < k - 1). Step 2 Find xk e {0,1}n that solves: z k = Max x tQ(xk)x [Note 2] Step 3 If z k - 1 ^ I j e r ( i )A k j < wk, stop (xk,xk) solves (BLP). Else go to Step 4. Step 4 k = k + 1. Go to step 1. [Note 1]: This step requires the solution of a linear program with r + k constraints and r variables, where r is the number of negative coefficients in Q (i .e. r = £ . ^ - ^ 1 ) . [Note 2]: This step requires the maximum of a 0-1 quadratic function. But by definition this function has no product terms (x^ ' x-, - 45 -with a negative coefficient. Therefore i t can be solved using a maximal flow network algorithm (see section 2). • The use of procedure 1 in calculating the upper bound is demon-strated by the next example. Example 4.6 Q = -1 1 -2 1 -1 1 -2 1 -1 Following procedure 1: Iteration 1 (a) Min w1 s.t. w1 >_ -Jr (x]3 + A 3 1 ) 0 >.--x]3, A 3 1 >. -4. Iteration 2 The solution is A] 3 = Xg-| =0; w^ = 0. (b) 1} - Max o x* x e{0,ir -1 1 0 1 -1 1 0 1 -1 x. The solution is x1 = (1,1,1)*; z1 = 1 (c) z1 - 1 ( A ] 3 + A 3 1 ) = 1 > 0. (a) Min w2 s.t. w2 > 1 + \\ ( A 2 3 + A ^ ) 0 > x ^ 3 , ' > -4 w > - 2 (x 1 3 + X 3 1) Solution is A 13 A32 1 2 2 _ 1 w - 2 - 46 -(b) z = Max o x - xe{0,l} -U c 1 0 0 1 l2 J Solution is x2 = (0,0,0); z 2 = 0. i \\ 2 1 /,2 , , 2 \\ _ 1 _ 2 _ 1 (c) z - ? (X 1 3 + X 3 1) - 2 \" w - 2 Note however that the solutions to Max . ~ x^ Qx are (1,1,0)*, xe{0,ir (0,1,1) and (0,0,0) with a function value of 0. This illustrates that in general the bound may not be equal to the maximum. • In light of section four i t will be assumed that for (P) there are no variables that could have their values fixed. In addition the assumption that (0,0,. . . ,0)* is a solution to (P) will be made. In turn these imply that (1 ,1, . . . ,1) t is a solution to (P0). With these assumptions the following theorem is a simple conse-quence of procedure 1. Theorem 4.4 lp, Q?j < Min x e M a X i } n ( x t 0 ( x ) x - l l i - l u r { ^ ) (4-10) i \" l}J\\ Ijer(i)Qij' (4.11) - 47 -Proof Under the assumptions made,after the first application of step one of procedure 1 the following will be obtained as the solution of the linear program. w1 = 0 = 0 (i = 1,2 n; j e T\"(i)). Also by assumption the test to be satisfied at step three is: Max xVx < 0. The solution to this is (1,1 1) t and J|l =\" Q°j > 0 since otherwise equality would hold in (4.9). Therefore the test is not satis-2 t fied and x = (1,1,. . . , !) . At the next iteration the linear programming problem to be solved at step 1 is: Min w AeP (4.12) s. t. w 2 vi=n Yj=n n0 + 1 vi=n T 2 - M=l ij=l Q i j 2 ii=l IjeJ ( i ) A i j w 2 1 vi=n v 2 - \" 2 M=l ^ j e T\"( i ) X i j • A solution can be obtained by choosing any x e P such that: - 48 -Ei=l ^jeT\"(i) xi j = \" £ j e T \" ( i ) Q i j and w - ? X1=l Xj=1 Qij • Now at each iteration the value of w must not decrease. Therefore the lower bound (4.10) on (BP) is established. The upper bound (4.11) follows easily since for any x e P: and substituting X - • = 2Q. • (i = l , 2 , . . . , r i ; j e T\"(i)), the bound is obtained. • There are at least three remaining areas of uncertainty for this new upper bound. The first would be to enquire under what conditions there is equality in (4.10). The second follows from the assumption that (0,0,...,0) was a solution to (P) in proving theorem (4.14) and concerns finding the complementary transformation of (P) that leads to the sharpest upper bound. The third relates to strategies for generally improving the sharpness of this bound.' Answers to the three problems are given in the next two sections. - 49 -7. Convergence of, and Complementary Transformations in Procedure 1 In the proof of theorem (4.14) at the end of the first step of the second iteration the linear program (4.12) was solved. The solution 2 was to choose any \\ z P such that: Ei=l £ j e T \" ( i ) x i j = \"Ei=T £ j £ T \" ( i ) Q i j ' 2 If the upper bound is to equal (4.10) i t must be that for the x t 2 chosen: Max x 0(x )x <_ 0, for this is the test to be performed at xe{0,l}n step three of the second iteration. The 'problem of finding conditions on 0 for which the upper bound equals (4.10) is clearly equivalent to finding a X that satisfies the three constraints: Max xtQ(x)x < 0 (4.14) xe{0,l}n X e P (4.16) Suppse that the set N has been ordered to form a set I = {i-j , i 2 , • • . , i } where r = |N| and let I = {i-j , i 2 , . . . for k = 1,2,3 r. Then the following choice of X £ 0 satisfies (4.14) and (4.15): - 50 -^ - T ( i )Ai j = \" Q i i \" 2 ^ j £ i m Q i j ( m = 1 ' 2 r ) { 4 J 7 ) (4.15) is satisfied trivial ly and (4.14) follows by repeated application of (4.2) and theorem (4.1) to deduce that (.0,0,...,0)* is a solution to: Max xtQ(x)x < 0. (4.16) and (4.17) can be satisfied simultaneously i f : mm m Tm N n The left hand side of (4.18) is the same as C [C [Q] ]. . . Therefore to determine i f there is some ordering of N that satisfies (4.18) is very easy and involves examining the elements of c \\ o j . This is done in the following procedure. Procedure 2 Step 0 Set S = {i: ^ [ Q ] ^ > 0}. Step 1 For i e S compute r. = ^[Q]^. + I j e S C N [ Q ] ° U Let T = {i: r. >_ 0} S t e P 2 If T = stop. Else go to Step 3. [Note 1] s t e P 3 Set S = SnT. If S = N stop. Else go to Step 1 [Note 2] - 51 -[Note 1] If the procedure terminates at this step i t may be that: M a x ^ieS £.jeS Q i j x i x j l ° » x i e { 0 ' 1 } V i e S. If this is true the equality of the upper bound to (4.10) s t i l l holds. [Note 2] If the procedure terminates at the step i t will be known that the upper bound equals (4.10), although the procedure will not produce the ordering of N needed to accomplish this. • Procedure 2 may terminate without exhibiting that an ordering of N exists (despite [Note 1]). For example i f C ^ [ Q ] ^ < 0 for all i . Note also that this procedure is valid for any of the complementary transformations of Q since no special assumptions were made about Q. Suppose now, that instead of Q, the procedure used C V [ Q ] , where VCN is defined as {i: x^ = 1}, and x e {0,l}n is a solution of: Min xt0x. Then: C N [ C V [ Q ] ] = C V [ Q ] , and, by construction, :) xe{0,T} CvCQ]-j-j JL 0 for all i . In this case procedure 2 will terminate at step 3 and an approoriate ordering for this problem will have been found. This implies that: Max n x V [ Q ] x < ^ i : ; ^ C ^ [ Q ] ? j , Xe{0,l}n J But from the definition of the complementary transformations: Max x V [ Q ] x = Max x*Qx - lu- Q,j. Xe{0,l} Xe{U,l) - 52 -Together these imply that: x e ( \" n \" x t Q x - * l \" ^ c* m\" + ^ ^ <4-19) The next theorem evaluates the right hand side of (4.19) and has some very interesting corollaries. Theorem 4.15 Let SCN, then: yi=n rj=n c S m i 0 = yi=n yj=n Q0 _ „ y y Q Proof V ' V V ' (4.20) (4.21) t., , y ' (4.22) On substituting the definitions of C S[Q].. into (4.20), (4.21) and (4.22) the following are obtained: «-2°> • IUS IjeS \"?j \" 2 ^ S J J t S \" i j ( 4 - 2 3 ) - 53 -(4.24) (4.25) Adding (4.23), (4.24) and (4.25) gives the desired result. • Rewriting (4.19) using this result gives This result is important since i t shows that under the condition that none of the variables in problem (P) could have their values fixed, mentary transformation of the original problem. This quantity could also have been proved to be an upper bound as a direct consequence of the theorem.(4.14). Corollary 4.15 If none of the variables in problem (P) can have their variables fixed by tests based on theorems (4.6) and (4.8), then Max x Qx < 1 vi=n vj=n n0 2 M=l £j=l g i j * (4.26) the upper bound converges to: 1 £|JJ J^. = n Q? ,^ for at least one compli-- 54 -Proof Suppose that there exists an x e {0,1}n such that x*Qx > \\ i l ! \" i j ! \" Q?j and let S = {i: x. = 1}. Then by theorem (4.14): J i H T i j : ? C 5 < - ^ { : ? i j : ? o ? j - i 1 t 5 i j £ s « « • • But as z]:, i j : , cs[Q],j - i u 5 xJE-s Q,J - I 1 e S ijcs i t must be true that: \\ i f t i j : ? c 5 < - i j : ? c 5 K ] l j 4 1 ; - i j - ^ - i i e S ^ < 0. Therefore: i j : ? csc«,d > * i j : ? • This contradicts the hypothesis that no variables could have their values fixed since: vi=n vj=n n l _ vi=n vj=n n , v i = h v ' - n _ „ Yi=n rj=n n _ yi=n yj=n Q0 - 55 -and the fact that the hypothesis implies that this must be strictly negative for all complementary transformations of Q. Note that this corollary is useless in giving a calculable upper problems involved in the tests. However this section has shown that the upper bound introduced in section five will converge to this value i f the conditions are satisfied. As a by-product of this development some information is obtained about which complementary transformation of (P) would be test to use in procedure 1. As (4.26) will probably be the upper bound obtained at the conclu-sion to procedure 1, the criterion to judge the best complementary trans-formation might be to find S such that (4.27) is minimized. Hence the assumption is false and so j Q°j is an upper bound for (P). • bound for (P) since to check the conditions would require solving the 2 n n xVCQlx. (4.27) But: Therefore, by invoking theorem (4.15) again, it can be seen that (4.27) is a constant for all S. - 56 -This implies that no complementary transformation of (P) would be better in procedure 1 than any other. However the next section will demonstrate methods that may lead to a different conclusion. 8. Improving the Upper Bound This section will propose two simple methods for improving the bound to a small extent. The first method is based on the idea of fixing the value of one of the variables in turn and applying the bounding procedure 1 to the residual problem. The validity of this idea depends on the next lemma which will not be proved here. Lemma 4.16 Let z. = Max x^x. 1 x-=l 1 n X£{0 ,1 } Then Max x*Qx = Max z.. D xe{0,l} l~~* and so there exists a j e S. It must now follow that y is a solution to: Max xtQJ(e)x. Therefore for some j : X £ { 0 , l } n Max xV(e)x - e = Max xW XE{0,1} p xe{0,l}n The conclusion of the lemma is now apparent. • x QJ(e)x = xLQx + 9 -t -= xlQx - 59 -As in the first method this lemma can be utilized to improve the upper bound for (P) by replacing: Max xtQ1(e)x, with an upper xe{0,l}n . bound for this. In particular, i f (0,0,...,0) is a solution to (?), e = rflj Q?,, and: Max n xV(e)x, (i = l ,2 , . . . ,n ) have no 1 - 1 J 1 1 J xe{0,l} variables that could have their value fixed, then this procedure will produce a tight upper bound. If for some choice of e, i t turns out that the last condition of the preceeding paragraph is violated for all i , then the two methods become the same. However i t is also possible that smaller values of e will satisfy this condition. Although, for these e, the improved bound may not be tight i t may well be useful in procedures that only require showing that an upper bound is smaller than a given fixed quantity. The major advantage possessed by the second improvement scheme is that such e may be readily available by considering the linear programming problem that was solved in procedure 1, just prior to termination. The following example illustrates the second improvement. Example 4.8 Following example (4.7) with = 1. Q'(e) 0 1 -2 1 -1 1 -2 1 -1 Q3(e) -1 1 -2 1 -1 1 -2 1 0 Max , xV(e)x < 1 xe{0,ir (using procedure 1) Max ~ xtQ3(e)x < 1 xe{0,l}J (by symmetry) - 60 Max xV^ 1 } [Q]x + CW[Q], i XeWUV XeWUVu{i} for all W, VcN, WnV = and i $ WuV. Proof From the definition of the complementary transformation Max x^ tQlx = Max xV^^fQlx + C W [Q] i i . XeWUV XeWUV The result now follows because: - 63 -Max xV^CQilx > Max xV^1' }[Q]x, XeWUV ' XeWUVU{i} as the left hand side is just a relaxation of the right. • In the next lemmas i t will be assumed that W and V are arbitrary, possibly empty, disjoint subsets of N. Lemma 5.2 If: xVroix - Max x V ^ C O j x - CW[Q].. < 0, XeWUVU{i} or xVCQ]* - Max xV^Ojx < 0, for any x E W uV and i { U u V , xeWUVu{i) then xVCQJx < Max x*Qx. XeWUV Proof Suppose xVcoJx - Max x^^CQlx - CW[Q].. < 0 XeWUVU{i} 1 1 for some x e Wu\\/ and i { Wuv. Then by lemma 5.1 64 -Max x V l Q l x - CW[Q].. > Max x V ^ I Q l x XeWUV XeWUVU{i} > x C [0]x - C [Q] i. Therefore Max • xVtOjx > xVtQjx . xeWJV A similar proof holds for the other case. • Lemma 5.3 Max x tCW [Q]x xeWJV Max Max x V ^ t Q l x + CV[Q].. XeWUVU{i} Max xVtQlx xeWuVU{i} for all i i w u y . Proof Let x e Wuv be a solution of Max xtCW[Q]x. xeVJuv Then either x. = 1 or x. = 0. Case i : x^ = 1 x ¥ [ Q ] x = Max x V ^ E Q l x + C^Q], , xeWUVU{i} by the definitions of complementary transformations, - 65 -Suppose now that: xV'tQJx < Max xVlQJx. Xei/juvu{i} Then lemma 5.2 says that: x^ Ox < Max x^ Qx, which contradicts the xeWuv assumption about x. Therefore the result is proved for this case. Case i i x^ = 0 Similar to case i . • Corollary 5.4 For all x e Wuy then for some i either:' x-VtQlx - Max x V ^ f O J x - CW[Q].. < 0, Xel'M/u{i} 1 1 or xVfQJx - Max x V l Q l x < 0, i f and only i f XeWUVU{i} xV^Qlx < Max xVtOJx. • xeWuv Corollary 5.5 Let x e w u v be a solution to Max xV^fQlx, y1 e Wuvu{i} a solution 4 . ii i r • i o xelftMV , w to Max x t H 1 | [ Q ] x and y e Wuvu{i} a solution to Max xV[Q]x, xeWUVU{i} xeWUVU{i} for any i £ WuV. - 66 -Then: i) x. = 1 imulies ^ V t Q l y 1 = Max x^fOJx , 1 xeWuV i i ) x, = 0 implies y 2 tCW[Q]y 2 = Max xV^Qjx. • 1 xeWuV One interpretation of the above results is that i f the values of: i) Max • xV^tOJx (k = 1,2,...,K < n) xeWkuvk-{i} for i $ W k _ 1 u v k _ 1 . 1^ i i ) Max xV\"1 [0]x, xeWkuvk are known for increasing subsets ( W k u v k ) of N, W°uv° = ** and Wk = U k _ 1 , Vk = V k _ 1 u { i } or Vk = V k _ 1 , Wk = W k _ 1 u { i } , (i $ W k _ 1 u v k \" 1 ) , then: Max x*Qx, can be evaluated. The next section gives a procedure to xe{0,l}n formalize this. 4. A Branch and Bound Algorithm Procedure 3 Step 1 Choose W, V disjoint. Find z 1 , z 2 e WuVu{i} such that: - 67 -[Note 1] z 2 tCW[Q]z 2 = Max zV^Ojz, and zEWuVu{i} [Note 2] [Note 3] z l t C W U { i } [ Q ] z 1 = Max zV^ 1 } [Q]z, ZeWUVU{i} where i £ W uV. D = i , Wk = W and V k = V. Step 2 Find x e W k uV k such that either [Note 4] . ,,k wk i) x rCw [Q]x - V ] - Cw [Q]p p > 0, or i i ) xtCW'<[Q]x - v 2 > 0. Step 3 If i) holds v-j = v2-[Note 4] uk If i i ) holds v1 = v1 + Cw [Q] . k k k k Step 4 Find either i) i e W or i i ) i e V and an x e (W uV ) [Note 3] such that [Note 4] x V ^ ^ t O l x = Max xV^^qix XeWkUVk Set v 2 = [Q]x. - 68 -k = k - 1 If k = 0, stop optimum found. Set ! A l k _ 1 = Wk - {i} i f i e' Wk, or yk-\"1 = vk - {i} i f i e Vk. Go to step 2. Notes to Accompany the Algorithm For the notes i t will be assumed without loss of generality that (1 ,1 , . . . , ! ) * is a solution to (P). A similar approach was adopted in the previous chapter. Note 1 The aim of step 1 is to find a problem, through fixing the values of some variables, that can be solved by an efficient algorithm. The last chapter dealt with some methods of solution where the number of compu-tations was bounded by a polynomial. The concept was taken as an indica-tor of an efficient algorithm. Note 2 One implementation is that W and V be found so that |WuV| is as small as possible to minimize further calculation. This step can also be interpreted as an attempt to find W and V so that i t can be readily deter-Step 5 [Note 5] Step 6 - 69 -mined whether the problem is solvable in a number of steps that can be expressed as a polynomial in n. With this interpretation i t is not possible to specify how to carry out this step at the moment. This will be taken up again after the remainder of the algorithm has been explained. Note 3 Steps 1 and 4 can be integrated together by making V = x*Qx + e (6.1) (vX) tv > 0 (6.2) - 75 -v e V = {v: (v 1 = 1 i f x. = 0) or (v i = -1 i f x i = 1) or (v. = 0)}, (6.3) where e > 0, is some given tolerance. Constraint (6.1) is added to ensure that the value of the 0-1 qua-dratic function actually increases for a solution of (DFP). This does not seem to be an obvious requirement but i t was found that when this method was applied to some problems a stage was reached when cycling of the x's, at which the derivatives are computed, occurred. The steepest ascent algorithm characterized by (DFP) will obviously x i cease at a point with (-1) v. <_ 0. Such a point is called a 1-maximum by Hammer and Rubin since any other point that differs from this in exactly one co-ordinate must not have a greater function value. Not all 1-maxima need be solutions to (P) but any solution to (P) must be a 1-maximum. It will be necessary to distinguish 1-maxima that are not necessarily solutions to (P) in order to make any heuristic for solving (P) effective. A procedure for carrying this out will be discussed in the next section. 3. A Procedure to Distinguish Some Local Solutions Following the last section, this section will provide a procedure to discriminate between some of the 1-maxima found by the steepest ascent procedure and the global maximum. In the procedure, use will be made of the concept of a cover as described in Granot and Hammer [11]. - 76 -A cover for the linear inequality: i j l j a i X i < b ( a . > 0), is a set SCN such that: Y . c a- > b. It will be called a prime cover i f no proper subset of S is also a cover. The following procedure will be used to distinguish 1-maxima. Throughout i t has been assumed that ( 0 , 0 , . . . , 0 ) * is the 1-maximum under test. If this is not the case let x e { 0 ,1 } n be the point of interest with S = {i: x. = 1 } . Then ( 0 , 0 , . . . , 0 ) t will be a 1-maximum of: Max xtCS[Q]x. x e {0 , l } n Procedure 5 Step 0 Set Sn = k = 1 , T = 4 . — u sQ S t g e J . Computer pk = 2 J . ^ ^ 0 ^ + 0 ^ -Step 2 Find a prime cover T.'of: [Note 1] Il.§k., - \" ( O . P ^ x , < - J 1 e V i I J E V I QU (6.4) such that T i TQ and T e P, V l V l If no T exists, k = k - 1 . If k = 0 stop no improvement possible, else go to step 1 . - 77 -Vi =Vl U { T }' Sk =Sk-lUT Step 4 If l- r- I- r. Q.- > 0 stop, (0,0,. . . ,0)* is a 1-maximum. 1 £-^ k J ^^i^ ' J Step 5 k = k + 1, T,, = <}>. Go to step 1 Note 1 T c is a set containing the prime covers evaluated for the inequa-b k- l 1 ity (6.4). This inequality is uniquely given by . Pc is a set of admissable prime covers for (6.3). This set may b k- l be just all prime covers. On the other hand i t might consist of very few. then For example Pc may be the set of covers such that i f T e P, , b k- l . r=k-l ^k-l TnT 1 = for any T e u T<~ . • r=0 r The procedure is valid because i f : l^£s L j e s ^ij > ° ' f o r s o m e ScN, then for any TcS , S - T is a cover of: he! max(0spi)xi < - lUJ l-eJ 0.. , where 0 - 78 -It should be noted that this argument also shows that procedure (5) is exact, i f P guish between 1-maxima and global maxima. contains all prime covers, and will always distin-V l 4. An Example The function in the following example is taken from Hammer and Rubin [15]. Example 5.1 •3 2 -4 1 0 2 -4 •1 2 2 -2 1 0 -3 0 1 0 1 -3 0 0 -2 1 1 0 Max , x e{0 , i r x V . The starting point for the steepest ascent approach will be: t 1 x(0,0,0,0,0) and v x = (-3,-1,-2,-2,0). This point is a 1-maximum. Therefore procedure (5) has to be invoked. This was performed in table (6.1). This gives x = (1,1,0,1,0) as a new point with: x2 t V X = (3,5,-6,2,-4) r. This too is a 1-maximum. The procedure (5) calculations are given in table (6.2) using: - 79 -C{1,2,4} [ Q ] = -3 2 4 1 0 2 -5 -2 1 3 4 -2 -6 0 0 1 1 0 -2 -1 0 3 0 -1 -4 This shows that (1,1,0,1,0) is a likely candidate as a solution to the problem. Table (6.1) k Sk-1 p,k 4 k P3 k P5 \" I 1 B S | < _ 1 ^jeSk_1 Q i j 1 * 0 4 0 1 1 -2 {2} 2 - 2 2 -5 1 3 {1,2} - - • -6 3 -5 0 4 {1,2,4} - - -6 - -4 -2 - 80 -Table (6.2) k Sk-1 p, A p5 \" X l e S k - l ^ » e S k - l Q i j 1 4 1 -2 0 -1 _ 2 {1} - 3 2 l -1 3 3 {1,2,3} - - - 2 2 6 2 {1}* - 3 2 1 -1 3 1 + • 4 1 -2 0 -1 -2 {2} 6 - -6 1 2 5 3 {1,2} • - - -2 3 2 4 4 {1,2,4,5} - - -2 - - 0 3 {1,2} - - -2 3 2 4 2 {2}* 6 - -6 1 2 5 1 * 4 1 -2 0 -1 0 * Indicates that the second strategy in note (1) was used. So far the steepest ascent/direction finding approach has not been used. Suppose that = (0,1,0,1,1)* had been the starting point. Then x1 t v = (3,-5,2,2,-4) . The direction finding problem (DFP) (without writing constraint (6.1) explicitly) is . Find v-|, v 2 , v^, v^, v 5 such that: - 81 -g(v) = 3v 1 - 5v2 + 2v3 + 2v4 - 4vg £ 0 (6.4) V 1 e {0,1}, V 2 e{0,-1}, V 3 e {0,1}, V 4 e{0,-1}, V g e {0,-1}. (6.5) There are many solutions to this problem. One possibility is to l i s t all solutions to (6.4), (6.5) in order of decreasing values of g (« ) until one is found with an improved function value in (P). Provided that the point at which the first derivatives were evaluated ;is not a 1-maximum, i t is always possible to find at least one direction that gives an improve-ment. It is this apDroach that will be used to solve all later (DFP) for this example. For this f irst (DFP) the solution is: (1,-1,0,0,-1) t. This gives x2 = x1 + (1,-1,0,0,-1)* = (1,0,0,1,0)* and (x2)*Q(x2) = -3 an improvement over (x1)*Q(x1) = -5. x2 t v x = (-4,5,-10,0,2)\\ The new (DFP) is: -4v-j + 5v2 - 10v3 + 0v4 + 2v5 £ 0 V 1 e{0,-l}, V 2 e { 0 , l } , V 3e { 0 , l } , V 4e {0,-1} , V 5e { 0 , l } . A solution is (-1,1,0,0,0)*. This gives x3 = (0,1,0,1,0)* and (x3)*Q(x3) = -1. x3 t v x = (3,1,2,0,-4)^. The new (DFP) is: 3v 1 + v 2 + 2v3 + 0v4 - 4v5 > 0 - 82 -V 1 e {0,1}, V 2 E {0 , -1 } , V 3e { 0 , l } , V 4e {0 , -1} , V 5e { 0 , l } . A solution is (1,0,0,0,0)*. This gives x4 = (1,1,0,1,0)* and d'ln&oh-matlqan e.t Re.cheJic.ke. 0pkzn.ationn.dile., 3, V-2, .57-64, 1969. - 87 -[10] Glover, F. and Woolsey, R.E.D., \"Further Reduction of Zero-One Polynomial Programs to Zero-One Linear Programming Problems,\" OpeAcutloni ReAWAch, 21 , 156-161 , 1973. [11] Granot, F. and Hammer, P.L., \"On the Use of Boolean Functions in 0-1 Programming,\" U^thodi> oi 0veAa£Lovu> Runajtck, 12, 154-184, 1972. [12] Hammer, P.L., \"Some Network Flow Problems Solved with Pseudo-Boolean Programming,\" OpeAatloru R&>e.cvich, 13, 388-399, 1965. [13] Hammer, P.L., and Hansen, P., \"On Quadratic 0-1 Programming,\" CORE Discussion Paper, 1972. [14] Hammer, P.L. and Peled, U. , \"On the Maximization of a Pseudo-Boolean Function,\" J . A . C M . , 19, 265-282, 1972. [15] Hammer, P.L. and Rubin, A.A. , \"Quadratic Programming with 0-1 Variables,\" Technion, 1969. [16] Hansen, P., \"Quadratic Zero-One Programming by Implicit Enumeration,' 265-278 in Lootsma, F.A., ;editor, Mumejvical MzthocU, In Nontlmaji Optimization, Academic Press, New York, 1972. [17] Hansen, P., \"Fonctions devaluation et Penalite's pour les Programmes Quadratiques en Variables Zero-Un,\" 361-370 in Roy, B., editor, \"Combinatorial Programming Methods and Applications,\" Reidel, Dordrecht, 1975. [18] Hansen, P., \"Methods of Nonlinear 0-1 Programming,\" presented at Discrete Optimization 1977, Vancouver, August 1977. [19] Holzinger, K.J. and Harman, H.H., \"Factor Analysis,\" University of Chicago Press, 1941. - 88 -[20] Karzanov, A.V. , \"Determining the Maximal Flow in a Network by the Method of Preflows,\" Soviet Math. Voklady, 15, 434-437, 1974. [21] Laughhunn, D.J., \"Quadratic Binary Programming with Applications to Capital-Budgeting Problems,\" OpeAaXlom Rue.aM.ch, 14, 454-461 , 1970. [22] Picard, J.C. and Ratliff, H.D., \"A Graph-Theoretic Equivalence for Integer Programs,\" OpeAationt, Ruzasich, 21 , 361-369, 1973. [23] Picard, J.C. and Ratliff, H.D., \"Minimum Cuts and Related Problems,\" HoJtoiotiiih , 5, 357-370, 1975. [24] Rao, M.R., \"Cluster Analysis and Mathematical Programming,\" JotutnaZ ofa the. American Statistical. AA6ocitation, 66, 622-626, 1971. [25] Rhys, J. , \"A Selection Problem of Shared Fixed Costs and Network Flows,\" Management Science., 17, 200-207, 1970. "@en ;
edm:hasType "Thesis/Dissertation"@en ;
edm:isShownAt "10.14288/1.0094223"@en ;
dcterms:language "eng"@en ;
ns0:degreeDiscipline "Business Administration"@en ;
edm:provider "Vancouver : University of British Columbia Library"@en ;
dcterms:publisher "University of British Columbia"@en ;
dcterms:rights "For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."@en ;
ns0:scholarLevel "Graduate"@en ;
dcterms:subject "Maxima and minima"@en, "Equations, Quadratic"@en ;
dcterms:title "On methods for the maximization of a zero-one quadratic function"@en ;
dcterms:type "Text"@en ;
ns0:identifierURI "http://hdl.handle.net/2429/20745"@en .
*