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 p r e s e n t i n g t h i s thesis in p a r t i a l fulfilment of an advanced degree at the U n i v e r s i t y of B r i t i s h the L i b r a r y I further s h a l l make it of for thesis for It financial i s understood that gain s h a l l Ma/vay/vw^V The U n i v e r s i t y o f B r i t i s h 2075 Wesbrook P l a c e V a n c o u v e r , Canada V6T 1W5 Date Columbia, I agree reference and copying o f this for that study. thesis ferin. May Columbia ^ o copying or publication not be allowed without my written permission. Department pf requirements purposes may be granted by the Head of my Department or representatives. this available 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 for scholarly by h i s freely the W g 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 f i r s t 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 f i r s t 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. - ii - 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 - iii - 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 Function 37 6. Solution and Some Properties of the Bounding Problem 43 7. Convergence of, and Complementary Transformations in Procedure 1 49 8. Improving the Upper Bound 56 CHAPTER V 1. Notation 61 2. Preview of the Algorithm 61 3. Preliminary Results 62 4. 5. A Branch and Bound Algorithm Some Comments on Branch and Bound Procedures 66 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 Commonwealth 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 supervising this work, William Ziemba for his encouragement and support, Theresa Fong for her careful the faculty, typing of this manuscript and to all 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. portions, he can state the satisfaction The food comes in standard 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 nonindependent 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 <> f - The empty set {x: P(x)} - The set of x satisfying Rn P(«)- - The n dimensional real vector space. Constants denoted by a, b etc. and variables, unknowns etc. by x, y, z and so on. Rmxn - The space of (mxn) real matrices. Constants denoted by A, B, Q etc. In - The ( nxn) identity matrix. e1 - The ith column of I n . 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 x e X - x belongs to the set X. AnB - The intersection of two sets A and B. Au B - The union of two sets A and B. . Ac B - A is a subset of B. Max f(x) xeX - Find an x e X such that f(x) >_ f(y) for all y e X. N - The set {l,2,...,n}. n e s e t ° f elements { x ^ . X g . . . .»x }. 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 xe{0,l}n where Q is a real symmetric (nxn) matrix. (P) Throughout the work this formulation will be referred to as problem (P). This problem belongs to a theoretically important group of enigmatic 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 necessarily 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 discussed 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 A substantial be formulated. [23]) number of different types of selection problem can 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 V j both belong to A, v.. and V j both belong to B, v.j belongs to A and v^- belongs to B, "a 1f vn- belongs to B and V j 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: - 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 interpretation. 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. a numerical procedure for finding such an A. be found in Holzinger and Harman [19]. The centroid method is A complete description can - 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: where B is a (pxp) real symmetric matrix (p <_ n). Max x^x, xe{-l,l} p This can be seen to be a problem of maximizing a 0-1 quadratic function by the substitution: v . = \ ( x . +1), 3. i = 1,2,...,p. 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-. replaced by: This can be Q. i y. -, along with the constraints: Xi +Xj -(xi+Xj) + 2 y i j Y i j < 1 if < 0 if Q.. < 0, 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) ii) the i n i t i a l partition into subsets, the order of choosing the subsets that have not been fathomed for further division (branching), iii) 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 selecting 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 " Ii=i M=l Ij=i Lj=i max(0,0^j), such that i f a variable is fixed at a value -" z 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. xe{0,l}n x.0 (z° - pi) J for: Max x*Qx x e {0,l} n xj-l and ( z ° - min(p^,pl)) for: Max x^Qx. xe{0,l} n The most useful set of penalties are those which are additive, in J J the sense that the sum of the penalties associated with fixing the values - 10 - of a set of variables is a penalty for the whole set. p9 = max(0,Qjj) + ^ The penalties: max(0,Q...), i=l pi are additive. = -minfO.Q.j). It also follows that: z 1 = 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 negative 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. r - j = max(Qi j.B^^. ,ejq.), where 0 < anc ' t\=] &j = "1 (J = l»2,...,n). Let q. = min(0,q.) and J J _< 1 (i = 1,2,... ,n; j = 1,2,... ,n) Then the following is an upper bound on the maximum of the 0-1 quadratic function: - 11 - 2 1 = z z + yi-n rj=n 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 ii) 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. fathoming constraint have been suggested. Two types of The f i r s t 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. constraint: The conclusion would be that the 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 ~ Ddjj- 2Q 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. Hansen [16,17], De Smet [3], Laughhunn [21]. These can be found in - 13 - CHAPTER III This chapter will be used to introduce a very simple transformation 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- t i t y , 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 = x n , 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]jj = "Qii i Q., + 2Q, . c 1 [ Q 3 jk = _ Q ik f j = } ( 3 otherwise i f j = * ] J ) (3.2) ( 3 - 3 ) -Q^. if k = i (3.4) Qjk otherwise (3.5) - 14 - In addition let c n (x) = (x-j,... >x.j >x.j+-| , . . . ,x n ) 'C 1 [ • ] will be called the complementary transformation of Q at i . The following lemma justifies the claim from the preceeding paragraph about C. Lemma 3.1 For all x e {0,1 }n c 1 (xjV-tqic1 (x) = x V - Q^- (i = l , 2 , . . . , n ) Proof Let A be a matrix satisfying c i (x) t Ac i (x) = (3.1) to (3.5) then: lp I*™ } (3.6) A^c^x^.c^x)^ (3.7) -nl^^M/M, k=l + Aiic1(x)ic1(x)i + j=l k=l V 1 ( (3.7) x ) (3.6) = -2 I*™. Q i k (l - X i ) x k / ( x ) k ( 3 - 8 ) [by (3.4)] k=l 2 i$ k=l i kQx i x k - 2 EkVi k=l Q ikxk (3.9) - 15 - (3.7) = - Q . ^ l - x . ) ( l -x.) [by (3.1)] (3.10) [by (3.2) j=l = 1$ k=l j=l Zg?QikxjXk j=l + k=l 2 Ij- and (3.5)] Q j i X j 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 (3.11) - 16 - x Qx = 1 • x-j - 1 • x 2 - 1 • x-j • x 2 + 4 • x2 • = (1 - x-|) - 1 • x 2 - 2 • (1 - x-|) • x^ + 4x2 • x 3 1 - 1 • x-j - 3 • x 2 + 2xn • x 2 + 4x2 • x^ 1 + (x ] , x 2 , x 3 ) f - \ •1 1 0 1 -3 2 x2 0 2 0 • x3- = 1 + c^xjV [Q]c(x). ] x l • 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 c n (x) is n t , xe{0,l} 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- - Qii " = Ql1 + 2 heS 2 heS Qij Q i i3 f 1 i f 1 if CJ[Q]id = Qid £ S e ^ (i,j) £ (SxS)u(SxS) otherwise. In addition let c S (x) be the vector in {0,1}n/such that: c ° ( x ) i = x. 1 - x. if i if i e S e S. The consistency of these definitions with the previous section can be seen by identifying: S (T[Q] where S l-i le 1 r i? = C 1 C L . . . |C K[Q] 1 1 {i^»i2»,--'"'|^^- The following are analogues of lemma (3.1) and corollary (3.3). - 18 - Lemma 3.4 For a l l SCN, c S (x) t C S [Q]c S (x) l + IJ£S us Q i j = xV- • Corollary 3.5 x e {0,1}n is a solution to c (x) is a solution to Max x^Qx i f and only i f n x e {0,l} x Cb[Q]x. • Max xe{0,l}n Example 2.2 Using the Q from example (2.1) -1 Cm[0j 1-3 0 1 C { 1 ' 2 } [QJ C {1,2,3} [ Q ] 1 0 2 2 0 •1 0 -1 3 -2 0 -2 1 -1 1 0 1 -3 2 4 0 2 0 -1 0 1 •1 0 •1 -1 2 3 -2 0 2 -4 _ .{2} {3} = C -1 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 complement 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 ue JJn lp} i}n (Eft 2(2^-1)^^ - Ij- I j - (2xj-l)(2xi-l)Qijuiuj (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 f i r s t 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 i t will investigate the effect of generating bounds and fathoming constraints from complementary transformations 2. of the original problem. 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 xe{0,l}n (PP) - 22 - where Q e R is a real symmetric matrix such that the elements other than those on the diagonal are non negative. Also consider the following 1inear program: Max f f,x f if i=l < 0 if i71 or \H if \=i. -f 0 < x <_? . 1 ; j t (MFP) (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. 9 ( S ) = Define a set function g: P ^ R as follows: £(i,j)£SxS F ij" The next result is the maximum flow, minimum cut theorem of Ford and Fulkerson [8]. Theorem 4.1 Min g(S) = Max f SeP feT 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 = feT Min z ? z t \ z + c. ZeCO,!}*"^ Proof Let S be an arbitrary subset of P and z . = 1 i f i e S and =0 otherwise. 9<S) - . f t Then: Since z-j = 1 and z 9(S) - I j - - • ^r1 1 F , ^ ! Ift - Z j ). = 0 by definition: % ft? F l j ( l - Zj) • s i r A,^,»J Fuz, • F U + Ij-" 1 itf 1 « + where A . . = -F.j A ii c C = (i F J, i = 2 , 3 , . . . , £ > ! ; i j - F1i + F i ( i = 2 j = 2,3,...,£-1) >3"-->^) = yJ=£ F ^j=2 The desired conclusion is now apparent. • W'V - 24 - The last corollary shows that to every maximal flow problem there exists some 0-1 quadratic function that is minimized. (i t j ; i = l,...,n; conclusion is true. Corollary 4.3 If A . . £ 0 j = l , . . . , n ) then i t is obvious that the reverse Hence the next corollary. (Picard and Rati i f f [23]) Problem (PP) can be solved by a maximal network flow algorithm. • The importance of these results l i e 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 - Highest Power in Polynomial Bound to Algorithm Solve Ford and Fulkerson [7] (PP) 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, suggests that in general this is so. experience 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 ii + 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 j=l k=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 f i r s t 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) 1J • "( )-«11 9 A 1 + 2 W(1) U' q B*(1) - CSW^, + 2 Z T*(1) i:«« cS JeC and B"(1) - where CT + (i) = {j: C W3„ S + 2 Z cT-{i) E« j. cS Jc f C S [Q]., > 0} and C F ( i ) = {j: C S [ Q ] , . « 0} Then: for all i e N. A + (i) = B + (i) if i 4 S, (i) A + (i) = B"(i) if i (ii) A"(i) = B"(i) if i £ S A"(i) = B + (i) if i e e S, S and (iii) (iv) - 28 - Proof Only case (i) will be proved. The remainder can be proved similarly. From the definition of complementary transformations at S c S Mii + 2 W(i) c S [ Q ] i j -"ii " + 2 ' ii Q 2 Zj.s'lJ WojrSOlJ + 2 ^ r(i)nS ij Q e + 2 £j SnT (i) + E + 2 ^ + e T (i)n5 ij Q 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 xe{0,l}n xVx. (PO) 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 a l l solutions to (PO). As x is a solution to (P) i t must be that: heS-T and therefore that: heS Q ij ^ 0 - 30 - L leS-T L JeS 'ij - IieSUT I jeSuT Q°j = IieT Since: £ j e T Q°j + Ii£S_T ^sujQ?^ it-follows from (4.4) that: ^ieSUT ^jeSUT i j - ^ i e T ^ j e T Q Q ij This contradicts the assumption and therefore S - T = <>j for some solution to (PO). This proves the proposition. • Corollary 4.7 Let {x1} be the set of all solutions to (P) and S = { j : xj =1). 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 Let {y1} be the set of all solutions to (PO) and T 1 = { j : yj = 1}. Y be the set of all solutions in {y1} that are maximal with respect to the inclusion relationship; all y J e {y3}. i . e . y 1 e Y i f and only i f T 1 <£ T J for 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. 4 0 0" 4 CO Example 4.1 "0 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). now allows x^ and x^ to be deleted. The test 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 xe{0,l}n xVx. (PI) 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: ^jeR ^ieR Q i j - ^jeR ^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 a l l 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 knowledge about a suspected solution as in the other test. The two tests are in fact identical in the sense that C^EC^CQ] ] = Q°. 1 This implies that i f there is some solution x e {0,1} of (PO) such that - 33 - x.j = 0, then x i = 0 in some solution of (P). The following example will clearly illustrate this, Example 4.2 Q= 0 4 -1 -2 0 4 0 0 4 -8 2 0 4 -8 2 0 -1 2 -6 2 0 2 -6 2 -2 0 2 -3 0 0 2 -3 This is essentially the same matrix as that in example CN[Q] = Now and [C N [Q]] ] -2 4 •1 •2 4 -4 2 0 -1 2 0 2 -2 0 2 3 -8 4 0 0 4 -4 2 0 0 2 -2 2 0 0 2 -1 X V L Q ] ] ^ are: (1,1,1,1)*, (0,1,1,1)* Max x A t£ {0,l} i u , IJ j. Therefore from theorem (4.8) i t follows that (1,1,1,1) The solutions of: . (0,0,1,1) l . (4.1) a solution to: Max .t„N, , 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 Then there exists a solution y e {0,1} Max xe{0,l} of: xV^x and S = {i: t S x. 0 =1}. 1 Max y C [Q] y, with y e {0,l} n T = {i: y i = 1} such that T c S . Proof From the definitions of a complementary transformation the following are true. C S [Q 0 ].. = Q.. + 2 T. C Q ° . i 4S C S [Q 0 ].. = Q.. - 2 7. CQ?. i eS ^[Q0]^ = Q?j C S [ Q 0 ] i : J = -Q?j C IQ? S U - (i,j) e (S x S)u(S x S) (i,j) e (S x S)u(s - 2 & j e s Q l J = C IQ\ S + 2 x S) l C m% S us 1 eS (4.6) - 35 CS[Q]?j = Q?j = C S [ Q ° ] i : j (i,j) e (S x S)u(S x S) CS[Q]?j = max(0,-Qij) (i,j) e (S x S)u(s x S) Let x E {0,1}n be arbitrary with R = {i: x^ = 1}. ^ieRnS ^jeROS C ^ i j + 2 Xi.Rns hart c S ^ieRnS ^jeRns + (4.7) (4.8) Then: ^ij C « ?J ] Now consider the second term above: Eieins ^JEROS ^ ^ i j ^ieRnS ^ ^ i i + ^ieRns ^jeRnS lit** + c heMS S W ]ii-^ 0 i e R n s IjeROS CSCQ°Jij from (4.5) and (4.7). The second term from this last equality satisfies: ^iERnS EjeS C ^ i j ±- ^ieRns ^jeRns ^ ^ i j since only positive numbers are subtracted from the left. Z j e S CS W]?j - 36 - Putting all these results together gives: ^ieR E j e R c S ^ i j ^ieRnS ^ e R n S ^ ^ j 1 0 - ^ieRnS ^j RnS e + ^ieRnS ^jeRnS^^^ij j* C The last inequality following by the optimality of x and lemma ( 3 . 4 ) . Hence i t 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 } 1 y {0,l}n 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 ] One solution to: o •8 4 1 2 4 0 0 0 1 0 -4 2 2 0 2 -7 Max d xe{0,ir x l C l 1 , c s [Q] x, is ( 0 , 0 , 0 , 0 ) L . t plainly illustrates the theorem as (1,1,0,0) Max x {0,l}n £ xVx. • was a solution to This 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 x Q°x n n xe{0,l} xe{0,1} (4.9) t • 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. x £ {0,l} n However this bound is usually not very sharp as the next example demonstrates. Example 4.4 Q= -2 " " -2 3 3 -4 .1 -2 1 -1 Q° = " -2 3 0 3 -4 1 0 1 -1 - 38 - Max ^ x Qx = 0 and is attained at (0,0,0) xe{0,ir and is attained at (1,1,1) . and t Max xe{0,ir x Qx =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 Qx = x Q x. xe{0,l} n Then Max x Q x and let Max x Cb[Q] x = 0, where S = {i: n xe{0,l} u x. = 1}. 1 Proof Since equality holds for (4.9) i t must be that Q9^ = Q^. (i f j ; i e S; jeS). c " a d S t < han In turn this implies that: - Q „ - 2 Ij. «i. - c CQ°3„ s s ^eRnSCSW^ " W KS. 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 1 0 1 -4 1 1 -4 1 -1 1 1 0 1 1 =1 xe{0,l}' Max x t Q°x = 2 J x e {0,l} at x = (1,0,0)* or (0,0,1) at x = (1,0,1)* or (1,1,1 )* But C{1}[Q] = and -1 -1 1 -1 -2 1 1 1 -1 C{1}[Q]° -1 0 0 -2 1 1 Max x*C 1 [Q]°x = 0 at (0,0,0)*, (.1,0,1 )*:and (1,1,1)*. n xe{0,l} This transformation would not have been given by theorem (4.8) directly. • - 40 - Max x Q x may not be a very precise bound since i t ignores xe{0,l} n 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 efficient 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 i t ' s calculation. Firstly some more definitions. Let Q(x) e R n x n be given by: j r(i) ij £ Q(x)., = max(0,Q, •) (i = 1,2,....n) A (i f j ; i =1,2 j =1,2,. 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. • • 9 n), - 41 Proof For any x e {0,1 }n let S = {i: *. = 1}. Then: " 2 ^i=l ^jeT"(i)xij 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) x ij r + 2 + ^ieS ^j E SnT~(i) DieS ^jeSnT"(i) X ij + ^ieS £ j e S n T ~ ( i ) x i UeS ^jeSnT'(i') X ij] \ UeS ^jeSnT"(i) X ij " \ ^ieS ^j e SnT~(i) X ij' - 42 - Therefore x^Utf " j XjlT I j ^ d J ^ l j • + 1 IieS 2 £ieS I snT-(i)^i3 je ^jeSnT"(i)Xij' 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 rnV" U t Q ( X ) X " * ^ X J E T-(1) x 1j) ^ 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 W,A s.t. (BLP) w > (XVQUMX*-) - ijeT-(i)Aij X e U: 0 > X.j > 2Q.J; i = l , 2 , . . . , n ; where i s ^-e- M = 2 n ). U= 1.2,....M) jeT"(i)} = P - 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 e P that solves: [Note 1] s.t. Step 2 Find x k Min wk k wk > ( x ) Q ( x k ) ( x P ) - \ ^ P e t {0,1}n that solves: l ^ - ^ . (1 < p < k - 1). z k = Max x Q(x k )x t [Note 2] Step 3 If z k - 1 ^ I j e r ( i ) A < w k , stop (x ,x ) solves (BLP). k k j k 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 = [Note 2]: £.^-^1). 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 demonstrated by the next example. Example 4.6 1 -2 1 -1 1 -2 1 -1 -1 Q= Following procedure 1: Iteration 1 (a) Min w1 s.t. w1 >_ -Jr (x]3 + A ) 0 >.--x], A 3 1 3 The solution is A]3 = Xg-| = 0 ; (b) 1} - Max o x e {0,ir x* -1 1 0 1 -1 1 0 1 -1 Iteration 2 z1 - 1 (a) Min w2 ( A ] s.t. 3 + A 3 1 w^ = 0. z1 = 1 = 1 > 0. ) w2 > 1 + \ ( A 2 3 + A^) w > - 2 (x 1 3 + X 3 1 ) Solution is A 13 >. -4. x. The solution is x1 = ( 1 , 1 , 1 ) * ; (c) 3 1 32 A 1 2 2 _1 w -2 0 > x^ 3 ,'> -4 - 46 - (b) z - = Max o x xe{0,l} 0 -U c 1 1 l 0 Solution is x 2 = (0,0,0); 2 J z 2 = 0. 1 /,2 , , 2 \ _ 1 _ 2 _ 1 - ? (X 1 3 + X 3 1 ) - 2 " w - 2 i \ 2 (c) z Note however that the solutions to (0,1,1) and (0,0,0) Max . ~ x^Qx are (1,1,0)*, xe{0,ir 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 consequence 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 - i " l}J\ Ij r(i) ij' e Q l u r { ^) (4-10) (4.11) - 47 - Proof Under the assumptions made,after the f i r s t 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 = " otherwise equality would hold in (4.9). Therefore the test is not satis- t 2 fied and x Q°j > 0 since = (1,1,...,!) . At the next iteration the linear programming problem to be solved at step 1 is: (4.12) Min w AeP s. t. v i=n Yj=n n 0 2 w - M=l ij=l Q i j + 1 vi=n T 2 ii=l IjeJ 2 (i)Aij 2 1 vi=n v 2 w - " 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 and w -? ^jeT"(i)xij = " £jeT"(i)Qij X X Qij • 1=l j=1 Now at each iteration the value of w must not decrease. the lower bound (4.10) on (BP) is established. Therefore The upper bound (4.11) follows easily since for any x e P: and substituting X - • = 2Q. • (i = l , 2 , . . . , r i ; obtained. j e T"(i)), the bound is • There are at least three remaining areas of uncertainty for this new upper bound. The f i r s t 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 £jeT"(i)xij = "Ei=T £j£T"(i)Qij ' 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 x t Q(x)x < 0 n xe{0,l} (4.14) X eP (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 k = 1,2,3 and (4.15): r. = {i-j , i 2 , . . . for Then the following choice of X £ 0 satisfies (4.14) - 50 - ^-T(i )Ai j = "Qi i " 2 ^j£imQij ( m = 1 ' 2 r ) { 4 J 7 ) (4.15) is satisfied t r i v i a l l y 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: S t e P 2 r. >_ 0} If T = <> f stop. Else go to Step 3. [Note 1] s t e P 3 [Note 2] Set S = S n T . If S = N stop. Else go to Step 1 - 51 - [Note 1] If the procedure terminates at this step i t may be that: M a x ^ i e S £.jeS Q i j x i x j l ° » i x e { 0 ' 1 } V i S. e 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 [ Q ] , where V VCN is defined as {i: x^ = 1}, and x e {0,l} n is a solution of: Min xe{0,T} x t 0x. Then: C [ C [ Q ] ] = C [ Q ] , and, by construction, N C CQ]-j-j JL 0 for a l l i . v V V 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 xV[Q]x<^i:;^C^[Q]? , J Xe{0,l} n n j But from the definition of the complementary transformations: Max Xe{0,l} ) : xV[Q]x = Max Xe{U,l) x*Qx - lu Q,j. - 52 - Together these imply that: xe("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 S C N , then: yi=n rj=n S c m i 0 = yi=n yj=n 0 _ „ y Q y Q Proof ' V V (4.20) t., , V ' (4.21) y ' (4.22) On substituting the definitions of C S [Q].. into (4.20), (4.21) and (4.22) the following are obtained: «- °> • IUS 2 IjeS "?j " 2 ^ S J J t S "ij ( 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 Max x Qx < 1 vi=n vj=n n 0 2 M=l £j=l g i j * (4.26) 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, the upper bound converges to: 1 £|JJ J^. n = Q?^, for at least one compli- 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 - 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 But ij:?C 5 < - ^ { : ? ij:? o ? j - i as z]:, i j : , c s [Q],j - i u xJE-s Q,J - I 5 ijcs 1eS it must be true that: \ i f t ij:?c 5 < - ij:?c 5 K ] l j 4 1 ; - i j - ^ - i i e S ^ < 0. Therefore: ij:? c c«,d > * ij:? s • This contradicts the hypothesis that no variables could have their values fixed since: v i=n vj=n n l _ vi=n vj=n _ „ Y , n i=n rj=n n vi=h v ' - _ yi=n yj=n n 0 Q 1 t - 55 - and the fact that the hypothesis implies that this must be s t r i c t l y negative for all complementary transformations of Q. Hence the assumption is false and so j bound for (P). Q°j is an upper • Note that this corollary is useless in giving a calculable upper bound for (P) since to check the conditions would require solving the 2 n 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 conclusion to procedure 1, the criterion to judge the best complementary transformation might be to find S such that (4.27) is minimized. n xVCQlx. (4.27) But: Therefore, by invoking theorem (4.15) again, i t 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 f i r s t 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. = 1 Then Max x^x. x-=l 1 n X£{0,1} Max xe{0,l} x*Qx = Max z . . l<i<n 1 D The method replaces each z^ in this lemma by its upper bound. The following example will illustrate the procedure. - 57 - Example 4.7 •-1 1 -2 1 -1 1 -2 1 -1 The upper bound on: Max ? as in example (4.6). x*Qx, is i x e {0,ir z, = 1 z9 = d Z o = Max o x xe{0,ir Max 9 x xe{0,l}^ 1 1 1 -5 ' 1 -2 -2 1 -1=0 •1 = 0. Therefore the upper bound can be sharpened from ^ to 0. • Clearly in this improvement as proposed by lemma (4.16) the best problem to be used would be that for which ( 0 , 0 , . . . , 0 ) * is a solution. The second method follows a very similar idea to the f i r s t . a small amount of extra notation is needed. Define a matrix Qn(e) e R n x n as follows: Q ^ e ) ^ = Q.. + 0 if Firstly j = k= i otherwise. (e e R) - 58 - The following lemma is a preliminary to the bound. Lemma 4.17 Max xe{0,l} x*Qx = Max[ Max ( Max xtQ (e)x - e),0] n l£i<n x £ {0,l} 1 Proof Firstly i f ( 0 , 0 , . . . , 0 ) * is a solution to (P) then the result is trivial. Therefore i t may be assumed without loss of generality that ( 0 , 0 , . . . , 0 ) * is not a solution to (P). Let x e (0,1 }n be a solution to: Max xe{0,l} xV(8)x. n Then by definition: x QJ(e)x = xLQx + 9 -t = xlQx if x. = 1 J otherwise. Let y e {0,l} n be a solution to (P) with S = {i: assumption S f < > | and so there exists a j e S. y is a solution to: Max x t Q J (e)x. X£{0,l}n Max xV(e)x - e = XE{0,1} p = 1}. By It must now follow that Therefore for some j : Max x W x e {0,l} n The conclusion of the lemma is now apparent. • - 59 - As in the f i r s t method this lemma can be utilized to improve the upper bound for (P) by replacing: Max x t Q 1 (e)x, with an upper n xe{0,l} . In particular, i f (0,0,...,0) is a solution to (?), bound for this. e = rflj xV(e)x, Max n (i = l , 2 , . . . , n ) have no x e {0,l} variables that could have their value fixed, then this procedure will 1 - 1 J Q?,, and: 1 1 J 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 Q'(e) 0 1 -2 1 -1 1 -2 1 -1 Max , xV(e)x < 1 xe{0,ir Max ~ xtQ3(e)x xe{0,l} J < 1 = 1. Q3(e) -1 1 -2 1 -1 1 -2 1 0 (using procedure 1) (by symmetry) - 60 <T(e) = Max o Max ~ x*Qx < 0 xe{0,ir xQ (e)x £ 1 -1 1 -2 1 0 1 -2 1 -1 (by procedure 3) (by lemma 4.17) xeco.ir This concludes chapter four. • - 61 - CHAPTER V This chapter will discuss a branch and bound algorithm similar to that described in Chapter two. The motive behind the analysis is to demonstrate that certain simplifications may be possible in the procedure if i t is assumed that a known point is probably a solution to (P). 1. Notation In the branch and bound routine i t is necessary to fix the value df certain variables to characterize the partition into subsets. To accom- plish this a dual purpose notation will be used. Without loss of generality i t will be assumed that any variables that have their values fixed be given a value of zero. indices of such a set of variables. Let V C N be the Then the notation x e V will also be used, where i t is now meant that x e V implies that x^ = 0 for all i e V . 2. Preview of the Algorithm The strategy to be followed will be to fix the initial partition of subsets such that, for at least one subset, a solution of (P), to this subset, is readily found. restricted This solution will also probably be a solution to (P), but not proven as such. The remaining subsets in the partition and the branching rule will be constructed under this assumption so that any further computation in the routine will be minimized, given any specified upper bounding procedure. - 62 - 3. Preliminary Results For these results i t will be assumed that for problem (P), W is the set of indices of variables with values fixed at 1 , and_ V those with values at 0. From Chapter three and the f i r s t section of this chapter Max x ^ t Q I x is equivalent to the problem of finding the maximum of xeWuv xtQx on the subset defined by W and V. The next results characterize points in a subset that are not solutions of (P) when i t is restricted to that subset. Firstly a lemma is proved. Lemma 5.1 Max xV^QJx > XeWUV Max XeWUVu{i} xV^ 1} [Q]x + C W [Q], i for all W, V c N , WnV = <> j and i $ WuV. Proof From the definition of the complementary transformation Max XeWUV x^tQlx = Max xV^^fQlx XeWUV The result now follows because: + CW[Q]ii. - 63 Max xV^CQilx > XeWUV Max xV^ ' } [Q]x, 1 ' 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 or - xVCQ]* - Max x V ^ C O j x - C W [Q].. < 0, XeWUVU{i} Max xV^Ojx < 0, for any x E xeWUVu{i) then xVCQJx < Max x*Qx. XeWUV Proof Suppose xVcoJx - Max x^^CQlx XeWUVU{i} for some x e Wu\/ and i { Wuv. Then by lemma 5.1 C [Q].. < W 1 1 0 W uV and i { U u V, 64 - Max x V l Q l x - C W [Q].. > Max XeWUV XeWUVU{i} xV^IQlx > 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 V ^ t Q l x + C [Q].. XeWUVU{i} V Max x C W [Q]x xeWJV t Max Max xVtQlx xeWuVU{i} for a l l i i w u y . Proof Let x e Wuv be a solution of or x. = 0. Case i : Max xtCW[Q]x. xeVJuv Then either x. = 1 x^ = 1 x¥[Q]x = Max xV^EQlx xeWUVU{i} by the definitions of complementary + C^Q],, transformations, - 65 - Suppose now that: xV'tQJx < Max xVlQJx. i/juvu{i} Xe Then lemma 5.2 says that: assumption about x. x^Ox < Max x^Qx, which contradicts the xeWuv 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 - or xVfQJx - Max xV^fOJx Xel'M/u{i} - C W [Q].. < 0, 1 1 Max x V l Q l x < 0, XeWUVU{i} x V ^ Q l x < Max x V t O J x . xeWuv i f and only i f • Corollary 5.5 Let x e w u v be a solution to Max xV^fQlx, y 1 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 ^VtQly = Max x ^ f O J x , xeWuV x, = 0 implies y 2 t C W [Q]y 2 = Max xV^Qjx. xeWuV 1 1 ii) 1 • One interpretation of the above results is that i f the values of: i) Max • xV^tOJx xeW uvk-{i} (k = 1,2,...,K < n) k for ii) i $ Wk_1 u v k _ 1 . 1^ Max xV" [0]x, xeW uv 1 k k are known for increasing subsets ( W u v ) of N, W ° u v ° = <> i and Wk = U k _ 1 , k Vk = V k _ 1 u { i } or V k = V k _ 1 , Wk = W Max x*Qx, can be evaluated. xe{0,l} n formalize this. k_1 k u{i}, (i $ W k _ 1 uv " ), k 1 then: The next section gives a procedure to 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 t C W [Q]z 2 = Max zV^Ojz, and zEWuVu{i} [Note 2] [Note 3] zltCWU{i}[Q]z1 = Max ZeWUVU{i} zV^ }[Q]z, 1 where i £ W uV. D Step 2 = i , W = W and V = V. Find x [Note 4] Step 3 k k e W k u V k such that either i) . ,,k x r C w [Q]x - ii) xtCW'<[Q]x - v 2 > 0. If i) w - C V ] ii) [Q] p p > 0, or holds v-j = v 2 - [Note 4] If k w holds v 1 = v1 Step 4 Find either [Note 3] such that i) uk + Cw [Q] k i eW or ii) . k k k i e V and an x e (W uV ) [Note 4] x V ^ ^ t O l x = Max XeW UV k Set v 2 = [Q]x. k xV^^qix - 68 - k =k- 1 Step 5 [Note 5] If k = 0, stop optimum found. Step 6 Set !Al = k _ 1 Wk - {i} yk-" = v - {i} 1 k if i if i e' Wk, e or V. k 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 computations 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- - 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 = <b. This will simplify the whole procedure since i t can now be assumed that i f i A W for any k, then x. = 1 for some solution to Max x C [Q]x. Note 4 It should be noted that step 2 does not require that v^ or v 2 be known exactly, but i t is sufficient that upper bounds on both are known. Step 3 requires that at each iteration one be known exactly. a step to calculate v,,. Step 4 is This would suggest that the whole procedure could be effectively carried out by knowing only v-| exactly and an upper bound for v 2 at each step. From the previous note i t is known that x^ = 1 (i \. Wk) in some solution to: Max x C [Q]x, and hence that: Max x Cw [Q]x <. k k xeW k • k XeWku{i} l U U{l} W Max [Q]x = Max x C [ Q ] x + C [Q]... This will imply that 1 1 xeWk xeWku{i} if (1,1,...,!) is indeed the true solution to (P), then ( i i ) would always be true and hence that only v-j need be known exactly. Note 5 Upon termination of the algorithm the conclusion, that ( 1 , 1 , . . . , ! ) * is a solution can be shown by corollary 5.5. • - 70 - It remains to discuss a method for carrying outstep one of this procedure. If the interpretation in note (2) is adopted step one is the reverse of procedure 3. Procedure 4 below, will construct a W for step one by inspecting uoper bounds for v 2 of procedure 3, for each variable not already in W. If i t is possible to find a variable for which the upper bound satisfies ( i i ) of step 2, then the variable is added to W otherwise the procedure terminates. Procedure 4 This implicitly assumes that ( 1 , 1 , . . . , ! ) * is a solution to (P). Step 0 W = <)j Step 1 Test i f Max xtCW[Q]x can be solved. xeW [Note 1] Step 2 If yes stop, success. For all i W compute: [Note 2] Max x C"[Q]x. u XeWU{i} Step 3 = Min v 2i ifW [Note 3] < v 2k stop, failure. - 71 - Step 4 W = Wuk. Go to step 1. Note 1 Max xtCW[Q]x can be solved i f i t is possible to find one of the xeW upper bounds from the previous chapter that is equal to some known value of xV^fQlx, x e W . Note 2 Suitable v2l- can be found by using the upper bounds of Chapter four. Note 3 Instead of failure here the procedure can be carried out until termination occurs at step 1. If this modification is used i t is not possible to conclude that, with the W computed by this procedure, procedure 3 will terminate after a polynomially bounded number of steps. • 5. Some Comments on Branch and Bound Procedures In this section some'comments on the implementation of branch and bound procedures will be discussed. All concern the conclusions that are possible i f there is a point available that is suspected to be a solution. - 72 - The most obvious consequence is that for the branch and bound procedure the trial maximum will probably not alter during the procedure. In turn this implies that, given any specific scheme for calculating the upper bound, there will be overall fewer subsets that need to be divided and hence fewer upper bounds to be calculated. A second consequence is that the branch and bound algorithm has a different emphasis. Originally i t was used to find a solution but now i t is only used to check whether a point is a solution or not. two direct implications of this. There are F i r s t l y , i t will not be a great disaster i f the branch and bound routine is in error and produces an incorrect solution (which may occur since the branch and bound method is not self checking). Secondly, i t is possible to identify conditions under which the branch and bound will have a polynomial bound on the number of computations. For the quadratic problem this can be done with procedure 4. However i t should be noted that this does not necessarily imply that procedure 4 is bounded in this way since i t uses a procedure for which this does not hold. In Hansen [16,17] and Hammer and Rubin [15] the value of a good trial maximum is accepted without comment. method to obtain such a point. given in the next chapter. However neither proposes a The description of such a method will be - 73 - CHAPTER VI In this chapter an algorithm for finding a point that may be a solution to (P) will be discussed. 1. Introduction Throughout the last two chapters there was recurrent assumption. This took the form of assuming that some specified point was a solution to (P). It was usually made under such a condition. to show that some test would be stronger In addition the last chapter proposed that an algorithm to generate a point that was suspected to be a solution would probably improve branch and bound procedures. Therefore there is some justification for studying heuristic schemes for the solution of (P). In addition, for all practical applied problems, knowing that a point is in fact a solution may actually provide l i t t l e further information. Usually when an answer is proposed to an optimization problem a cost benefit analysis is carried out to find out the net-value of implementing that ^proposal . If this were always the case, then heuristic methods would have far greater value than more tedious but exact techniques. 2. Some Preliminaries It will not be the purpose of this chapter to discuss an entire heuristic for solving (P). detailed. Instead an interesting approach will be An algorithm can be easily deduced from the example that will follow later in the chapter. - 74 - The approach begins with a concept introduced by Hammer and Rubin [15] of a discrete f i r s t derivative. The vector v e Rn will be called x the vector of discrete f i r s t derivatives at x is given by: v x = (x + e V c K x + e 1 ) _ x^x i f x. = 0 = x*Qx - ( x - e V Q U - e 1 ) i f x. =1. The v are more easily obtained by noting that i f S = {i: x^ = 1} then x x x v.j = (-1) i S C [Q]^-- Therefore the formula for complementary transforma- tions can be used. A useful manner in which to use these derivatives would seem to be in a steepest ascent procedure. Intuitively, i f by changing the value of the ith variable the value of the quadratic function increases then some direction that includes the same change should also lead to an increase in the value of the function. In particular using a solution to the following problem may provide a useful direction: Find a v e Rn to satisfy: (x + v ^ Q U + v) > x*Qx + e (v X ) t v > 0 (DFP) (6.1) (6.2) - 75 - v e V = {v: (v1 = 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 quadratic 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 cease at a point with (-1) i 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: ijlj aiXi < b is a set SCN such that: ( a . > 0), 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 test. If this is not the case let x e { 0 , 1 } with S = {i: Max xe{0,l} ( 0 , 0 , . . . , 0 ) * x. = 1}. Then ( 0 , 0 , . . . , 0 ) t n is the 1-maximum under be the point of interest will be a 1-maximum of: x t C S [Q]x. n Procedure 5 Step 0 .— Set Sn = <> j u k = 1, T =4 StgeJ. Computer p k Step 2 Find a prime cover T.'of: sQ = 2 J . ^ ^0 ^ + 0^- [Note 1 ] Il.§., k -"(O.P^x, < such that T i TQ - J 1 e V i I J E V I Q U (6.4) and T e P, V l If no T exists, k = k - 1 . possible, else go to step 1 . V l If k = 0 stop no improvement - 77 - Vi Vl 'k k-l = Step 4 If l- r- I1 Step 5 U { T } S =S £-^ k UT r. Q.- > 0 J ^^i^ k = k + 1, T,, stop, ( 0 , 0 , . . . , 0 ) * is a 1-maximum. 'J = <}>. Go to step 1 Note 1 Tc is a set containing the prime covers evaluated for the inequab 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. For example P c may be the set of covers such that i f T e P, , then b k-l . r=k-l ^k-l T n T 1 = <> j for any T e u T<~ . • r=0 r The procedure is valid because i f : l^ s L j s ^ij £ e ScN, then for any T c S , S - T is a cover of: he! where max(0 s p i )x i < - l l- UJ eJ 0 0.. , > °' f o r s o m e - 78 - It should be noted that this argument also shows that procedure (5) is exact, i f P contains all prime covers, and will always distin- V l guish between 1-maxima and global maxima. 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 •1 2 1 -3 -4 2 -2 0 0 1 1 0 -2 1 0 -3 0 1 0 Max , xV. x {0,ir e 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). Therefore procedure (5) has to be invoked. This point is a 1-maximum. This was performed in table (6.1). This gives x = (1,1,0,1,0) as a new point with: x2 t V = (3,5,-6,2,-4) r . X This too is a 1-maximum. table (6.2) using: The procedure (5) calculations are given in - 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 1 S k-1 * p, k 4 k P3 k P5 " I1BS _ | < 1 ^jeS _ k 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 1 Q ij - 80 - Table (6.2) k S k-1 p, p5 A 1 <> f 4 1 -2 2 {1} - 3 3 {1,2,3} - 2 {1}* 1 +• " X l e S k-l ^»eSk-l 0 -1 _ 2 l -1 3 - - 2 2 6 - 3 2 1 -1 3 4 1 -2 0 -1 - 6 - -6 1 2 5 - - -2 3 2 4 2 {2} 3 {1,2} 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 • Q i j * Indicates that the second strategy in note (1) was used. So far the steepest ascent/direction finding approach has not been used. v x1 Suppose that t = (3,-5,2,2,-4) . = (0,1,0,1,1)* had been the starting point. The direction finding problem (DFP) (without writing constraint (6.1) explicitly) i s . that: Then Find v-|, v 2 , v^, v^, v 5 such - 81 - g ( v ) = 3v 1 - 5v2 + 2v 3 + 2v 4 - 4v g £ 0 (6.4) V e {0,1}, V e{0,-1}, V e {0,1}, V e{0,-1}, V e {0,-1}. 1 2 3 4 g There are many solutions to this problem. (6.5) One possibility is to l i s t a l l 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 f i r s t derivatives were evaluated ;is not a 1-maximum, i t is always possible to find at least one direction that gives an improvement. It is this apDroach that will be used to solve a l l later (DFP) for this example. For this f i r s t (DFP) the solution i s : (1,-1,0,0,-1) t . This gives x 2 = x1 + (1,-1,0,0,-1)* = (1,0,0,1,0)* and (x 2 )*Q(x 2 ) = -3 an improvement over (x 1 )*Q(x 1 ) = -5. v x2 t = (-4,5,-10,0,2)\ x The new (DFP) i s : -4v-j + 5v2 - 10v3 + 0v4 + 2v5 £ 0 V 1 e{0,-l}, V e { 0 , l } , 2 A solution is (-1,1,0,0,0)*. V e{0,l}, 3 V e{0,-1}, 4 x3 x t = (3,1,2,0,-4)^. 3v 1 5 This gives x 3 = (0,1,0,1,0)* and (x 3 )*Q(x 3 ) = -1. v V e{0,l}. The new (DFP) i s : + v 2 + 2v 3 + 0v 4 - 4v 5 > 0 - 82 - V 1 e {0,1}, V E { 0 , - 1 } , V e { 0 , l } , V e { 0 , - 1 } , V e { 0 , l } . 2 3 A solution is (1,0,0,0,0)*. 4 5 This gives x 4 = (1,1,0,1,0)* and < x « ) W ) - 2This is the solution to the example and the rest of the calculation is the same as above. • Several stages of the procedure in the example were left deliberately vague. These relate to empirical questions such as: a good starting point? How to find When to use steepest ascent over procedure 5? How to find solutions to (DFP) that minimize the amount of further computation? How to find sets of valid prime covers of (6.3) in procedure 5 that lead to fewest 1-maxima being accepted as global maxima? In addition to these questions there exists some theoretical considerations. For instance, finding alternative directions to those from (DFP) that lead to fewer 1-maxima. These problems need to be dealt with by further research. - 83 - CHAPTER VII 1. Conclusions The research proposed several modifications to a branch and bound scheme for the maximization of a 0-1 quadratic function. Part of moti- vation for this was to identify problems that could be solved efficiently by such a scheme. As most of the major results in the paper were expressed as computational procedure i t is interesting to examine them in terms of this criterion. Procedure (1) was to calculate upper bounds. since i t may involve generating 2 n constraints. It is not efficient However part of the research would seem to suggest that i f a trial solution, found by a heuristic, was available, then the procedure might behave as an efficient one. Procedure (2) was used to discover i f the upper bound of procedure (1) converged. It was not really intended that this procedure would find a way into a practical scheme. Procedure (3) was a modified branch and bound algorithm and would not be efficient in general. Procedure (4) is used to identify whether procedure (3) will a given problem efficiently. solve It is an efficient procedure given an effi- cient upper bound calculation. Procedure (5) is part of a heuristic to find a solution. The efficiency depends on the choice of the.sets of note [1] for that procedure. For the two choices suggested in the note i t will not be efficient. - 84 - The heuristic of Chapter six as a whole is not efficient since there is no guarantee that the ascent scheme will not v i s i t all points in {0,l} n . Ultimately the final conclusion about whether these procedures behave efficiently for a wide enough class of problems, and therefore from a basis for a useful optimization procedure, will depend on experimentation and experience. 2. Epilogue The relevance of this research is perhaps best illustrated by the conclusions of Hansen [18]: "The algorithm of Ford and Fulkerson is a powerful tool for computing the optimal solution of quadratic 0-1 problems. The examination of the class of problems which may be directly solved by that algorithm, as begun by Picard and Rati i f f [22], seems worth continuing. It seems also that the algorithm of Ford and Fulkerson could be efficiently used to,compute bounds in problems for which i t cannot give immediately a solution . . . " The reader is left to decide how close this research has approached in addressing these comments. 3. Further Research Without any computational experience available, as yet, an optimistic approach should not be taken in describing further research. Combining the six procedures into a workable practical structure is a very delicate task and all the tradeoffs involved will take many hours of careful empirical - 85 - work before a balance is found. Even then the u t i l i t y of such a program will be slight since, for practical purposes, i t will be sufficient to know that the methods of Chapter six converge to a solution for almost all problems. It is this line of work that is probably the most impor- tnat. As for extensions to the general approach, the most obvious choices would be in the inclusion of general zero-one nonlinear functions, mixed integer problems and constraints into the method. extension is suggested by previous research. In all three cases the (See for example Balinski [1], Hammer and Rubin [15], Hansen [17] and Rhys [25]). For the case of constraints i t would seem likely that an extension of the results from matroid theory may prove to be useful. - 86 - BIBLIOGRAPHY [1] Balinsky, E . L . , "On a Selection Problem," Management Science, 17, 230-231, 1970. [2] Beale, E.M.L., "Selecting an Optimum Subset," 451-462, in Abadie, J., editor, Integer and Nonlinear Programming," North Holland Publishing Co., 1970. [3] De Smet, J . , "Le Probleme des Signes de Thurstone," Revue VtancaM d' ln&ohmati.que. oX de RecfoeAcAe OpoAationnelZz, [4] 3, 57-64, 1968. Dinic, E.A., "Algorithm for Solution of a Problem of Maximum Flow in a Network with Power Estimation," Soviet Math. Voklady, 11, 1277-1280, 1970. [5] Edmonds, J. and Karp, R.M., "Theoretical Improvements in Algorithm Efficiency for Network Flow Problems," J . A . C M . , 19, 248-264, 1972. [6] Edwards, A.W.F. and Cavali Sfarza, L . A . , "A Method for Cluster Analysis," BiomntsUu, [7] 362-375, 1965. Fortet, R., "Applications de I'Algebra de Boole en Recherche Opera ti onell e," Revue FA.ancoc&e de Re.cheAc.ke. Ope/iationneUte., 4, 17-26, 1960. [8] Ford, L.R. and Fulkerson, D.R., "Flows in Networks," Princeton University Press, 1962. [9] Ginsburgh, V. and Van Peetersen, A . , "Une Algorithme de Programmation Quadratique en Variables Binares," Revue Tia.nc.aM> d'ln&ohmatlqan 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 PseudoBoolean 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 PseudoBoolean 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, [17] Academic Press, New York, 1972. 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 [21] Math. Voklady, 15, 434-437, 1974. 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 [23] [24] Integer Programs," OpeAationt, 21 , 361-369, 1973. Picard, J.C. and Ratliff, H.D., "Minimum Cuts and Related Problems," HoJtoiotiiih , 5, 357-370, 1975. Rao, M.R., "Cluster Analysis and Mathematical Programming," JotutnaZ ofa the. American [25] Ruzasich, Statistical. AA6ocitation, 66, 622-626, 1971. Rhys, J . , "A Selection Problem of Shared Fixed Costs and Network Flows," Management Science., 17, 200-207, 1970.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On methods for the maximization of a zero-one quadratic...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On methods for the maximization of a zero-one quadratic function Hawkins, Stephen Peter 1978
pdf
Page Metadata
Item Metadata
Title | On methods for the maximization of a zero-one quadratic function |
Creator |
Hawkins, Stephen Peter |
Date Issued | 1978 |
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. |
Subject |
Maxima and minima Equations, Quadratic |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-02-22 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0094223 |
URI | http://hdl.handle.net/2429/20745 |
Degree |
Master of Science - MSc |
Program |
Business Administration |
Affiliation |
Business, Sauder School of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1978_A4_6 H39.pdf [ 3.41MB ]
- Metadata
- JSON: 831-1.0094223.json
- JSON-LD: 831-1.0094223-ld.json
- RDF/XML (Pretty): 831-1.0094223-rdf.xml
- RDF/JSON: 831-1.0094223-rdf.json
- Turtle: 831-1.0094223-turtle.txt
- N-Triples: 831-1.0094223-rdf-ntriples.txt
- Original Record: 831-1.0094223-source.json
- Full Text
- 831-1.0094223-fulltext.txt
- Citation
- 831-1.0094223.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0094223/manifest