UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Covering relaxation methods for solving the zero-one positive polynomial programming problem Vaessen, Willem 1981

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1981_A6_7 V24.pdf [ 3.86MB ]
Metadata
JSON: 831-1.0051834.json
JSON-LD: 831-1.0051834-ld.json
RDF/XML (Pretty): 831-1.0051834-rdf.xml
RDF/JSON: 831-1.0051834-rdf.json
Turtle: 831-1.0051834-turtle.txt
N-Triples: 831-1.0051834-rdf-ntriples.txt
Original Record: 831-1.0051834-source.json
Full Text
831-1.0051834-fulltext.txt
Citation
831-1.0051834.ris

Full Text

c,/  C O V E R I N G R E L A X A T I O N METHODS FOR S O L V I N G T H E ZERO-ONE P O S I T I V E P O L Y N O M I A L PROGRAMMING P R O B L E M  B.Sc,  U n i v e r s i t y o f B r i t i s h Columbia,  1978  A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T OF T H E R E Q U I R E M E N T S FOR T H E D E G R E E OF M A S T E R OF S C I E N C E in T H E F A C U L T Y OF GRADUATE  STUDIES  (Department o f Computer  Science)  We a c c e p t t h i s t h e s i s a s c o n f o r m i n g to the required standard.  T H E U N I V E R S I T Y OF B R I T I S H C O L U M B I A April  30, 1980  (c) W i l l e m V a e s s e n ,  1980  In p r e s e n t i n g  this thesis i n partial  f u l f i l m e n t of the requirements f o r  an advanced degree a t the U n i v e r s i t y o f B r i t i s h C o l u m b i a , I agree t h a t the L i b r a r y s h a l l make i t f r e e l y  a v a i l a b l e f o r r e f e r e n c e and s t u d y .  I f u r t h e r agree t h a t p e r m i s s i o n f o r e x t e n s i v e  copying o f t h i s  thesis  f o r s c h o l a r l y purposes may be g r a n t e d by t h e Head o f my Department o r by h i s r e p r e s e n t a t i v e s .  I t i s understood t h a t c o p y i n g o r p u b l i c a t i o n  of t h i s t h e s i s f o r f i n a n c i a l written  gain s h a l l  permission.  Department o f The U n i v e r s i t y o f B r i t i s h Columbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5  DE-6  B P  75-51  1 E  not be a l l o w e d w i t h o u t my  ABSTRACT  Covering r e l a x a t i o n algorithms were f i r s t developed by G r a n o t e t a l f o r s o l v i n g p o s i t i v e 0-1 p o l y n o m i a l p r o g r a m m i n g (PP) p r o b l e m s w h i c h m a x i m i z e a l i n e a r o b j e c t i v e f u n c t i o n in 0-1 variables subject to a set of p o l y n o m i a l i n e q u a l i t i e s containing only p o s i t i v e c o e f f i c i e n t s ["Covering Relaxation for Positive 0-1 P o l y n o m i a l P r o g r a m s " , M a n a g e m e n t S c i e n c e , V o l . 25, ( 1 9 7 9 ) ] . The c o v e r i n g r e l a x a t i o n a p p r o a c h appears to cope successfully with the non-linearity of t h e PP p r o b l e m a n d i s a b l e t o s o l v e m o d e s t s i z e (40 variables and 40 c o n s t r a i n t s ) s p a r s e PP p r o b l e m s . This thesis develops a more s o p h i s t i c a t e d covering relaxation method which accelerates the performance of t h i s approach, e s p e c i a l l y w h e n s o l v i n g PP p r o b l e m s w i t h m a n y t e r m s in a constraint. Both the o r i g i n a l covering relaxation a l g o r i t h m and the newly introduced accelerated algorithm are cutting plane algorithms i n which the r e l a x e d p r o b l e m i s the s e t c o v e r i n g problem and the cutting planes are linear covering constraints. In c o n t r a s t with other c u t t i n g p l a n e methods in i n t e g e r programming, the a c c e l e r a t e d c o v e r i n g relaxation algorithm developed i n t h i s t h e s i s does not s o l v e the r e l a x e d problem to o p t i m a l i t y a f t e r the i n t r o d u c t i o n o f the cutting plane constraints. Rather, the augmented r e l a x e d problem i s f i r s t solved approximately and only if the approximate solution i s f e a s i b l e t o t h e PP p r o b l e m i s t h e relaxed problem solved to o p t i m a l i t y . The p r o m i s e o f this a p p r o a c h stems from the e x c e l l e n t p e r f o r m a n c e of a p p r o x i m a t e procedures for solving integer programming problems. Indeed, the extensive c o m p u t a t i o n a l e x p e r i m e n t s t h a t were p e r f o r m e d show t h a t t h e a c c e l e r a t e d algorithm has reduced both the number o f s e t c o v e r i n g p r o b l e m s t o be s o l v e d a n d the o v e r a l l time r e q u i r e d to solve a PP problem. The improvements are p a r t i c u l a r l y s i g n i f i c a n t f o r PP p r o b l e m s w i t h many t e r m s i n a c o n s t r a i n t .  iii  T A B L E OF C O N T E N T S  1. I n t r o d u c t i o n  1  2. M a t h e m a t i c a l  Preliminaries  7  3. T h e C o v e r i n g  Relaxation Approach  4. E v a l u a t i o n o f t h e B a s i c C o v e r i n g 5. M o d i f i c a t i o n s o f t h e C o v e r i n g 6. G r e e d y - l i k e  7.  12 Relaxation Algorithm  Relaxation Approach  Approximate Procedures  19 21 32  6.1  Greedy-like  procedures  f o r t h e SC P r o b l e m  33  6.2  Greedy-like  procedures  f o r t h e MC P r o b l e m  37  Evaluation of the Accelerated Covering Algorithm  Relaxation 39  7.1  Aspects  of the Implementation  7.2  Problem Generator  45  7.3  Computational  47  Results  40  8. B i b l i o g r a p h y  61  9. A p p e n d i x : T h r e e B e n c h m a r k P r o b l e m s  64  L I S T OF  TABLES  Table  I  53  Table  II  54  Table  III  55  Table  IV  56  Table V  57  T a b l e VI  58  L I S T OF FIGURES  Figure  1.  CPU  Time Use  Figure  2.  Method  I v s Method VA  59 60  ACKNOWLE DGEMENT  I would l i k e advice  t o thank p r o f e s s o r  and  encouragement;  P a u l C. G i l m o r e my  thesis  supervisors,  p r o f e s s o r s F r i e d a and D a n i e l Granot, f o r t h e i r and  financial  interest  support;  and  Ihor  guidance  Gowda f o r t a k i n g a n  i n my w o r k .  This thesis i s dedicated Zero and One.  for his  to  1  1.  This positive  Introduction  thesis considers 0-1  polynomial  and  develops  programming problem  a l i n e a r o b j e c t i v e f u n c t i o n i n 0-1 by a s e t o f p o l y n o m i a l coefficients.  methods f o r s o l v i n g which  variables that i s  inequalities  I t i s of the  (PP)  containing  the  maximizes constrained  only  positive  form:  n CftXh  E  MAX  h=l  subject  to  F.[ (x) < b i  i = l , ...  ,m  h=l,  ,n  (PP) x  €  n  {0,1}  where f o r each h,  ...  i and  j  PU)  Fi(x) = a^j > N^j  TT x ; kSNij  > aij j=l cjj >  0;  k  0  i s a subset  and o f N = { l , 2 , ...  N^j  i s the  Fi  w i l l be r e f e r r e d t o a s a p o s y n o m i a l s i n c e i t i s a  with  set of v a r i a b l e s i n j  ,n}.  h  term of the  i  t  h  constraint. polynomial  only positive c o e f f i c i e n t s . General  t o be  t  polynomial  useful for  engineering.  For  c o n s t r a i n t s i n 0-1  modeling example,  into c a p i t a l budgeting  diverse they  [22], to plan  v a r i a b l e s were  problems are  business  and  used to i n c o r p o r a t e  risk  irrigation  in  found  systems  [21],  to  2  perform  cluster  scheduling problems  analysis  [ 2 4 ] , and  to  formulate  [17,23].  T h i s t h e s i s , however,  various  focuses  on  the p o s i t i v e polynomial problem.  Methods o f S o l u t i o n  The  PP  problem,  optimization  like  problems,  optimization problem,  such  have  been  p r o b l e m employ  the  NP-complete  proposed at  as  travelling  some  problems.  i n the literature stage  searching very large solution  an  approaches.  o f t h e PP problem  problem by  an  enumeration  term i n  a  additional  PP  0-1  technique  for  spaces.  directly.  Both  approaches  i t t o a l e s s complex  approach  equivalent  methods  and t h e b o o l e a n  Neither approach tackles the n o n - l i n e a r i t y  reducing  linearization  The  f o r s o l v i n g t h e PP  The two m a j o r m e t h o d s a r e t h e l i n e a r i z a t i o n algebra  salesman  i s a t l e a s t as hard t o s o l v e as any one o f  the n o t o r i o u s l y d i f f i c u l t that  many o t h e r w e l l known m a t h e m a t i c a l  [8,9,29]  linear  problem  is  replaced  problem. by  the  l i n e a r problem.  t r a n s f o r m s t h e PP  programming  solve  a  new  problem Each  PP The into  distinct  variable  and  constraints are introduced to ensure that the values  o f t h e t e r m a n d t h e new v a r i a b l e c o i n c i d e . t/l X|<. kSNij  Explicitly, l e t  T h e n T ^ J c a n b e r e p l a c e d b y a new 0-1 v a r i a b l e  Tji  =  yij  i n every constraint  i n which T ^ j occurs i f the f o l l o w i n g  l i n e a r c o n s t r a i n t s , which  are written  i n terms o f  the  two  original  0-1 v a r i a b l e s x ^ a n d t h e new v a r i a b l e s Y i j , a r e s a t i s f i e d :  3  £  x  k ± Y i j + |Nij| - 1  > x kGNij  k  >  |Nij|yij.  A s l i g h t l y more e f f i c i e n t of constraints less  exponentially problem.  In  p o s s i b l e number o f p o s y n o m i a l t e r m s  with  t h e number o f v a r i a b l e s i n  [26,27]  an  implicit  are  obviously  standard  linearization  only  suffers  considered  from  boolean algebra  original  employing t h i s  This  al  transformation  original  Their  PP  algorithm for been by t h e  implicitly.  This  drawback  computational  as  the  results  conclusion. Granot  and  Hammer  PP p r o b l e m i s e q u i v a l e n t  a t t e m p t t o s o l v e PP  failed  because  i n the equivalent  the  to of  problems  number  linear covering  [14]  of  problem  large.  attempt  the covering [10],  increases  problem i n the complementing v a r i a b l e s  problem.  constraints  is often very  since  PP  very  introduced  same  The  techniques,  h a v e shown c o n s t r u c t i v e l y t h a t e v e r y a linear set covering  the  approach.  i n [26,27] u n d e r s c o r e t h i s  Using  covering  enumeration  be  i n the  0-1 l i n e a r p r o g r a m m i n g p r o b l e m h a s  approach  the  the  i n which the a d d i t i o n a l constraints  l i n e a r i z a t i o n process  to  potentially  the  solving the transformed developed  found  The number o f v a r i a b l e s  0-1 l i n e a r p r o g r a m m i n g p r o b l e m i s  since  reported  t h a t r e d u c e s t h e number  i s p o s s i b l e , s e e [ 9 ] . B u t i t was  effective computationally.  transformed large  transformation  i s , nevertheless,  o f t h e o r e t i c a l importance  r e l a x a t i o n a p p r o a c h , d e v e l o p e d by  overcomes  i t s major  deficiency.  The  Granot  et  covering  4  r e l a x a t i o n approach i s produces of  a  an  optimal  sequence  cutting  plane  type  algorithm.  It  s o l u t i o n t o t h e PP p r o b l e m b y s o l v i n g e a c h problems  to  set  covering problem i s a r e l a x a t i o n of  the  o r i g i n a l PP p r o b l e m a n d  u s u a l l y contains only a small subset  of  optimality.  the  of  a  Each  constraints  computational covering  nested  of  the  results  relaxation  linear  the  covering  equivalent set covering problem.  reported approach  m o d e s t s i z e (40 v a r i a b l e s a n d However,  set  in is  [10] a  indicate  The  that  the  v i a b l e method f o r s o l v i n g  40 c o n s t r a i n t s )  sparse  problems.  p e r f o r m a n c e o f the method d e t e r i o r a t e s r a p i d l y as  t h e number o f d i s t i n c t  t e r m s i n t h e c o n s t r a i n t s o f a PP  problem  increases. Using developed  a s i m i l a r approach, an  programming  An  and  F. G r a n o t  f o r s o l v i n g the g e n e r a l  [11]  0-1  have  polynomial  problem.  Outline  The the  algorithm  D. G r a n o t  p l a n o f t h i s t h e s i s i s as f o l l o w s .  b a s i s of the o r i g i n a l c o v e r i n g r e l a x a t i o n approach of Granot  et  which  will  r e l a x a t i o n approach  is  of Granot  be  and  reviewed  evaluated  Hammer  [14]  reviews the  [10],  work  2  that forms  al  theoretical  Chapter  i n chapter in  chapter  3. 4.  The The  c o n t r i b u t i o n o f t h i s t h e s i s , t o be p r e s e n t e d  in chapter  improved covering r e l a x a t i o n algorithm.  three  incorporated shortcomings  in  the  improved  The  algorithm  in  5,  major i s an  modifications  are motivated  of the o r i g i n a l a l g o r i t h m d i s c u s s e d  covering  by  the  chapter  4.  5  The  most  i n t e r e s t i n g o f t h e s e m o d i f i c a t i o n s makes n o v e l u s e o f  approximate procedures f o r s o l v i n g the s e t covering reduce to  t h e number o f s e t c o v e r i n g p r o b l e m s  optimality.  covering  The i m p r o v e d  problem  to  is first  optimality  solved  only  i f  does  f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m . that  is  problem third  introduced  t o produce  uses  an  a better  modification  second  procedures similar  has  the  procedures  covering of  for  set  that  constraints.  improved  develops covering can  Chapter  be  approach.  a  helpful  and  The i m p l e m e n t a t i o n  enumeration  t h e number,  greedy-like problem.  used  to  7 discusses  reliable employs  The  a  the  approximate  I t also produce  discusses tight  set  the p e r t i n e n t aspects  r e l a x a t i o n approach tool  that  solved to  for  which  the development  rudimentary  implicit  a l g o r i t h m f o r s o l v i n g the s e t covering problem.  computational results reported  is  the performance  the s e t c o v e r i n g problems  the implementation of the covering been  problem.  i n c h a p t e r 7 show  density 6  be  set covering constraints.  size  Chapter  will  s o l u t i o n f o r t h e PP  r e l a x a t i o n a p p r o a c h by r e d u c i n g  optimality.  Instead, a  modification  t o be r e p o r t e d  of  set  The  of the covering the  a  solution  i n i t i a l set covering  m o d i f i c a t i o n s have s i g n i f i c a n t l y  and  solve  approximate  approximate  generates tighter  The c o m p u t a t i o n a l r e s u l t s these  not  a p p r o x i m a t e l y and  the  to  t o h a v e t o be s o l v e d  to o p t i m a l i t y at every i t e r a t i o n .  set c o v e r i n g problem solved  algorithm  problem  i n chapter 7  that  i f the  number o f v a r i a b l e s and t h e d e n s i t y o f t h e s e t c o v e r i n g  problems  to  required  for  be s o l v e d solving  show  The  t o o p t i m a l i t y i s l a r g e , t h e n t h e CPU t i m e a  PP  problem  to  optimality  i s almost  entirely  6  devoted to solving the set covering measures i n d i c a t e that covering  problem  i f a more e f f i c i e n t  (see  for  properly,  then the covering  s o l v e much  l a r g e r PP  pseudo-randomly accelerated  The collected Polynomial  PP  The  new m a t e r i a l in  ["An  Problem",  Administration,  performance  algorithm  [1,5])  is  appendix  f o r the s e t implemented be a b l e  to  contains  three  problems that were s o l v e d  by t h e  algorithm.  The  set  covering  to optimality are also included  I t i s hoped that these  benchmarks f o r f u r t h e r  The  r e l a x a t i o n approach w i l l  relaxation  problems t h a t were s o l v e d appendix.  instance  problems.  generated  covering  problems.  PP  problems  will  i n the  serve  as  thesis  is  f o r the Postive  0-1  research. that  is  Accelerated Faculty  University  F . G r a n o t , D. G r a n o t a n d W.  of  developed  in  Algorithm of  Commerce  British  Vaessen.  this  and  C o l u m b i a , May  Business 1980] by  7  2.  This chapter of  [2,14]  approach  that  Mathematical P r e l i m i n a r i e s  summarizes the t h e o r e t i c a l  results  form  covering relaxation  the  and  Hammer  [14] u s e d  show t h a t e v e r y p o s y n o m i a l equivalent set of linear be  accomplished,  inequality  (1)  of  t o be d i s c u s s e d i n c h a p t e r  Granot  can  basis  of the  x  1  3. boolean  inequality  algebra techniques  can  be  replaced  covering inequalities. consider,  notions  first  of  by  T o s e e how  a l l  the  to an this  linear  form:  n >! a - i i - / j=l  Definition  the  and  b  w h e r e a-pO,  j = l , ...  ,n.  A s u b s e t U o f N, N = { l , 2 , ... of  (1) i f  j>  ,n},  i s a cover  a j > b.  jeu  Definition  2  A  c o v e r U i s p r i m e i f no p r o p e r  subset of U i s a  cover. Definition  2a  |u|  i s the c a r d i n a l i t y  Definition  2b  The  c a r d i n a l i t y of a prime cover  is  s m a l l e r than or equal to the c a r d i n a l i t i e s  all  other prime covers of  Let  of the prime cover  C be t h e s e t o f a l l p r i m e c o v e r s o f  Theorem 1 T[  jeu  A 0-1  if it  (1). (1).  v e c t o r x s a t i s f i e s (1) i f a n d o n l y i f  x-j = 0 f o r a l l U 6  equivalently,  i s minimal  U.  C,  i f and o n l y i f y , t h e c o m p l e m e n t o f x,  satisfies  of  8  (2)  > jeu  Thus  the  reduced in  y-; > 1 f o r a l l U 6 C, w h e r e  linear  t o an e q u i v a l e n t  equivalent  a  independently completely The  P  >. k=l  0-1  vector  (4)  by  linear  problem. Balas  and  i n e q u a l i t i e s . Consider  a  k  z such  i n e q u a l i t i e s (2)  problem A  to  similar  Jeroslow  obtain  an  result [2]  was  using  a  i n [ 1 4 ] f o r p o s i t i v e 0-1  the i n e q u a l i t y o f the form:  k  x  satisfies  (3)  ,p a n d N  i f and o n l y  k  (2 N  i f there  i s a 0-1  t h a t x and z s a t i s f y :  a^Zfc < b a n d z  k  _ = T| x-; f o r k = l , ... j6N  ,p.  k  L e t C be t h e s e t o f a l l p r i m e c o v e r s (3) i s s a t i s f i e d  ]T z kGU  k  equivalently, TT kGU  x c a n be  k  k=l  Then  0-1 v e c t o r  TT x-; < b , w h e r e a > 0 , k = l , ... j€N  vector  P >.  the  d i f f e r e n t approach.  above r e s u l t s were g e n e r a l i z e d  polynomial  (3)  0-1  covering  obtained  in  T h i s r e d u c t i o n c a n be a p p l i e d t o e v e r y  positive  linear  (1)  set of linear covering  t h e complement o f x.  constraint of  A  inequality  y=l-x.  of the i n e q u a l i t y  of  (4).  i f and o n l y i f  = 0 f o r a l l U e C, i f and o n l y i f  Tf j6N  X J  = 0 f o r a l l U 6 C.  k  T h i s c o n d i t i o n c a n a l s o be r e w r i t t e n a s a s e t o f l i n e a r c o v e r i n g  9  inequalities Theorem 2  i n the complementing  A 0-1  vector  c o m p l e m e n t o f x,  (5)  x satisfies  Thus,  S(U)  i s the  every  covering  simplify  relaxation  the  approach  3^  D e f i n i t i o n 3a  be  in  reduced  three  if  y,  the  an  polynomial  equivalent  set  of  a l i n e a r set covering polynomial  discussion  (SC)  problem. of  properties  constraint  not  e x i s t a subset  3> J6R  y-; > 1 c a n  The  size  of  (5)  the of  covering covering  i s prime i f there  R o f S(U)  such  a l s o be g e n e r a t e d S(U)  is  the  constraint, i n the  minimal i f i t i s smaller cardinalities  of  be d e r i v e d  The  covering  a l l other from  from  i.e.  than  (3).  (3). of  number  the of  constraint.  constraint or  does  that  cardinality  c a r d i n a l i t y of a covering  t h a t can  0-1  defined.  A covering  The  kGU.  positive to  related  variables occuring 3b  only  for a l l  k  a  subsequent  covering  Definition  of N  t o t h e o r i g i n a l 0-1  c o n s t r a i n t s n e e d t o be  Definition  union  c o n s t r a i n t s to obtain  problem equivalent To  i f and  C,  constraint  programming problem can linear  (3)  satisfies  > y-; > 1 f o r a l l U 6 JSS(U)  w h e r e y = l - x and  variables.  equal  covering  (5) to  is the  constraints  10  The  reader  who i s u n f a m i l i a r w i t h  urged t o examine  Example  1.  the f o l l o w i n g  t h e above  Set o f Covering  2  z  l  z  l 3  2  z  z  >  X  2 3 4  =  0  < = >  X  1 2 3 5  =  <=> <=>  4  X i = l - y i  The  z  <  4  3  2  u  z z z =o 2  z  2  =  z z =0 1  l  first  three  X  X  X  X  X  = 0  X  2 3 6 X  X  = U  x x x x x x =o 1  2  3  for  4  5  6  < 9  4  <=>  Y2+Y3+Y4 - 1  <=>  yi+Y2 y3 Y5  <=>  +  Y2+Y3+Y6 y +y 1  + 2  +  constraints  are  [14,15]  used the above  t o an equivalent  o p t i m a l i t y by a standard  fairly n j> j=l  SC p r o b l e m  s m a l l PP p r o b l e m s .  SC p r o b l e m which  method.  attractive computationally the equivalent  prime.  result  PP  in  ^ 1  The  and second c o n s t r a i n t are minimal.  f o r s o l v i n g t h e PP p r o b l e m t h a t f i r s t  not  1  y3 y4+y5+y6  an a l g o r i t h m problem  - 1  +  i=l,2,3,4,5,6.  covering  a n d Hammer  z  <=>  = 0  c a r d i n a l i t i e s o f t h ef i r s t  Granot  3  t o an  Constraints.  8x2X3 + 5 x X 4 + 3x^x3X5 + 2 x x g z  i s  example:  Reducing a Posynomial Constraint Equivalent  material  This  because i s often  F o rexample,  t o propose  reduces the  i sthen solved t o  algorithm,  however,  i s  t h e number o f c o n s t r a i n t s very  large,  even f o r  a c o n s t r a i n t o f the  form  x-i < T(n/2), where T ( r ) denotes the i n t e g e r p a r t o f r ,  11  is  equivalent The  next chapter  w h i c h was  developed  deficiency the  t o C(n,T(n/2)+1) c o v e r i n g  solves  by  Granot  of employing  SC p r o b l e m .  generate  describes  and  solve  The  each o f which  the c o v e r i n g et  al  covering  sequence  relaxation  o f much  r e l a x a t i o n approach  [10]  the t r a n s f o r m a t i o n  the e n t i r e e q u i v a l e n t  each o f a nested  constraints.  to  overcome  o f t h e PP p r o b l e m approach  SC p r o b l e m smaller  i s a r e l a x a t i o n o f the PP p r o b l e m  does  but SC  t o be  the to not  instead, problems,  solved.  12  3.  The  covering  algorithm. solve for  the  LP  idea  (LP)  A  current  to  the  the are  is  problem  LP  r e q u i r e m e n t s on The  motivation  technique  for  Rather  than  covering  that  original  PP  covering  relaxation  The small  subset  of  problem  w h i c h do of  constraints the  are  the  solves  covering  SC  for  the  The  ILP  until  the  ILP  a d d i n g one cut  off  remove any  initial  integer Such  relaxation integrality  problem. of  a  cutting  often  plane  unmanageable  equivalent  SC  SC  problem.  problem,  a nested  are  the  sequence  t i g h t e r r e l a x a t i o n s of  problems  or the  problem.  the  i s the  each of  ILP  linear  problem  by  ILP  equivalent  successively  (CR)  the  the  entire  The  not  dropping  problem in  ILP  which  the  application  problem.  initial  LP  by  PP  [7]  tighter  i s obtained  for  the  to  e.g.  requirements of  from  r e l a x a t i o n approach  problems  original  variables  solving  algorithms  cutting planes.  s o l v i n g the  number o f c o v e r i n g  the  region  obtained  developed See  successively  integrality  optimum b u t  called  the  of  current  type  technique.  relaxation  feasible  constraints the  the  first  problems.  c u t t i n g plane  relaxations  non-integer from  this  i s a c u t t i n g plane  were  (ILP)  a sequence o f  t i g h t e r LP  more c o n s t r a i n t s  SC  the  optimum s a t i s f i e s  problem.  points  of  of  Approach  approach  programming  i s to solve  programming  Relaxation  algorithms  treatment  basic  problems  plane  linear  in-depth  The  Covering  relaxation  Cutting  integer  an  The  referred  of the  to  as  problems. relaxation  covering  (CRg)  constraints  problem c o n s i s t s of of  the  equivalent  a SC  13  problem.  Each  constraint cutting terms  set  planes in  that  current  CR  that  of  i t s predecessor  violated  is  obtained with  constraints  at  the  tighter  than  The  a  They c u t - o f f  relaxation  of  These  generated  those  from  o f the o r i g i n a l  solution  solutions  the  version  i n an i n f o r m a l  of covering procedural  some a s p e c t s o f t h e i m p l e m e n t a t i o n  f o r the  t o t h e CR p r o b l e m s  problem.  C l e a r l y , e a c h CR  original  PP p r o b l e m  relaxation fashion.  The d i s c u s s i o n  i s deferred  until  chapter  a s t a r t i n g node;  g e n e r a t e CRg w i t h  t h e s t a r t i n g node;  repeat solve  the c u r r e n t  attempt  CR p r o b l e m  that  the  CR p r o b l e m ;  current no c u t s  the also until stop.  to optimality;  t o g e n e r a t e one o r more a d d i t i o n a l  constraints  if  and i s  a p p r o a c h c a n now  BASIC COVERING RELAXATION ALGORITHM  find  the  a l l i t s predecessors.  basic  stated  augmenting  cutting planes.  optimal  are not f e a s i b l e t o the o r i g i n a l is  by  posynomial c o n s t r a i n t s  do n o t v a n i s h problem.  problem  be  problem  are covering  the  problem  CR  c u t o f f the o p t i m a l  c a n be added  optimal  solution  optimal  solution to  then to the c u r r e n t  f e a s i b l e t o the o r i g i n a l  the c u r r e n t  covering  solution  CR p r o b l e m i s  PP p r o b l e m ; i s feasible;  of 7.  14  The  algorithm  terminates  PP p r o b l e m i n a t m o s t finitely 2  n  in  iterations.  n  solution for  Termination  at each i t e r a t i o n  problem i s discarded.  [10]  an o p t i m a l  many s t e p s b e c a u s e t h e s o l u t i o n s p a c e  b i n a r y v e c t o r s and  t h e CR  2  with  (The  significantly  better!)  The  occurs  experimental  s o l u t i o n on  in  c o n t a i n s at most  the o p t i m a l  show t h a t t h a t t h e a v e r a g e b e h a v i o u r  the  solution  to  results reported  of the a l g o r i t h m  termination  is  is  optimal  b e c a u s e e a c h CR p r o b l e m i s a r e l a x a t i o n o f t h e PP p r o b l e m t o  be  solved. A single  covering  optimal  solution  t h a n one  posynomial  t h a n one  c o v e r i n g c o n s t r a i n t can  posynomial basic  to  constraint  covering  See  to  a  s e c t i o n 7.1  to  for  dominated  whose v a l u e s can  from  is  If at  most  one  i n the  reduce  iteration  to form  technique  f o r s o l v i n g SC p r o b l e m s  optimal  dimensions  large.  be  in  the  number  of  of  CR  effective  the  rules that variables  for instance  is  problem, then [7] c a n  and  added  each  a cutting  plane  be e m p l o y e d t o  because  [7].  at  f o r the augmented problem.  however, i s u n l i k e l y to i t e r a t i o n s w i l l be  constraints  constraint  t h e a u g m e n t e d CR  solution  more  accelerated  the  i n advance, see  covering  the  each v i o l a t e d  exploited  extent  the  covering  be d e t e r m i n e d  off  addition,  by a p p l y i n g a s m a l l number o f s i m p l i f i c a t i o n  will eliminate  the  cut  details.  i s o f t e n p o s s i b l e to reduce  problem  In  be g e n e r a t e d  larger  algorithm  to  In g e n e r a l , however, more  This f l e x i b i l i t y  and  relaxation  iterations.  CR p r o b l e m .  constraint is violated.  constraint.  algorithm  It  a  suffices  the  This  obtain method,  number  of  15  The (1,1,  starting  ...  by  the  basic  algorithm  b a s i c a l g o r i t h m g e n e r a t e s one c o v e r i n g c o n s t r a i n t  violated  constraint the  used  is  ,D.  The each  node  posynomial  constraint.  To  from  see which c o v e r i n g  i s generated, c o n s i d e r the posynomial  constraint  of  form: P  >. a^Pfc < b , w h e r e P k=l The  k  denotes a product of  b a s i c a l g o r i t h m generates the prime cover  covering constraint  i n the f o l l o w i n g  variables. which  forms  the  manner:  begin order the terms P prime-cover lhs  :=  k :=  :=  such that a _ j > a  k  k  k  f o r k = 2,...,p;  0  0;  1;  repeat lhs  := l h s +  prime-cover k := k until  a^; := p r i m e - c o v e r + U n i o n ( p r i m e - c o v e r , { k } ) ;  +1;  l h s > b or k  >p  end The prime  ordering cover  However, constraint  this  of  the terms ensures t h a t the c a r d i n a l i t y o f  forming  the  condition  i s prime.  covering does  Hence, the  constraint  not quarantee cardinality  c o n s t r a i n t g e n e r a t e d i n the above manner i s n o t  is  the  minimal.  t h a t the c o v e r i n g of  the  minimal.  covering  16  E x a m p l e 2.  Solving  a p o s i t i v e 0-1 p o l y n o m i a l  problem.  Solve MAX 7X>L + 5 x + 4 x + 3 x + 3 x + 2 x 2  3  4  5  g  s. t . 1)  8x^x2X3  + 6x2X4  + 5x3 + 4x3X5  2)  7x2X3X5  + 2x^x  6  < 6  3)  7x4x5  +  4x]X  + 4x x x  4)  5x x  + 5x^5 + 3x + 2x <7  5)  3x2X4  2  3  2  5  6  <  6  +2x3X4  + 2x4X5  4  + 2x5X5  + x^xg < 5  ( 1 , 1 , ... ,1) t o g e n e r a t e o n e c o v e r i n g  violated posynomial constraint f r o m 1)  The  8  for i=l,2,3,4,5,6.  Xi6{0,l}  Use  4  < 13  i n t h e manner d e s r i b e d  from  each  above:  x^X2X3X4=0  2)  x x x X5Xg=0  3)  x x x =0  4)  x x x x =0  5)  x x x X5=0  1  1  1  2  4  2  2  3  3  5  3  5  4  fourth constraint  therefore written  constraint  dominates  be dropped. as covering  relaxation  problem.  t h e second c o n s t r a i n t , which c a n  The four constraints  remaining  constraints are  t o form t h e i n i t i a l  covering  17  Iteration MIN 7 y i  1.  Solve the i n i t i a l  + 5y  2  + 4y  3  + 3y  4  +  2  +  3  +  y  4  +  Y  4  CR  + 3y  problem: + 2y  5  6  s. t . Y l  y  y  Yl +  y i  y  2  +  y  3  y  2  +  y  3  +  y  > 1  4  +  Y5  -  +  y  5  > 1  +  y  5  > 1  1  Yie{0,l} f o r i=l,2,3,4,5,6. Observe y  that  the value of y  can s a t i s f y  3  The  t h e same c o n s t r a i n t s a t a l o w e r  s o l u t i o n f o r the f i r s t  y4 Y5=1•  x*=(1,1,1,0,0,1) f r o m 1)  2  is  2  2  and  3  to generate additional covering  2  3  i  x =x =0. 4  5  a n d  Use  constaints:  6  since  c o n s t r a i n t needs  i t dominates  2.  t o be i n c l u d e d  the former.  S o l v e t h e a u g m e n t e d CR  + 5y  2  + 4y  3  + 3y  + 3y  4  5  problem: + 2y  6  s. t .  +  Y2  +  Y3  + +  Yl Yl  = 0  3  x x x =0  Iteration  Yl  cost.  yi=y =y =y6  x^=x =x =Xg=l,  because  3  Only the l a t t e r  7y!  problem  at 0  x^x x xg=0  4)  problem  CR  Equivalently,  =  MIN  c a n be f i x e d a p r i o r i  2  +  Y2  +  Y3  Y2  +  Y3  Y2  +  Y3  y i e { o , 1} :f o r  +  y y  y  4  4  +  Y5  > 1 > 1  +  Y5  > 1  +  Y5  > 1  4  i = l , 2,3,4,5,6.  +  Y6  ^ 1  i n the augmented  18  Its Use  solution i s yi Y2 Y5 Y6 ^' =  =  =  =(  x*=(1,l 0,0,1,1)  to  f  a n c  ^ Y3 Y4 1 • =  =  generate  additional  covering  constraints: from 4)  x^x xg=0 5  I t e r a t i o n 3.  Solve the augmented CR  + 5y  Yl  +  + 4y  2  +  Y2  + 3Y4  3  V3  Yl Yl  +  Y2  +  Y3  Y2  +  Y3  Y2  +  Y3  +  Y4  +  Y4  +  + 3y  problem: + 2ye  5  > 1  Y4  +  Y5  > 1  +  V5  > 1  +  Y5  > 1  +  Yl  Y5  +  Y6 > 1  +  Y6 > 1  y i S { 0 , l } f o r i=l,2,3,4,5,6. Its  solution  x^=X2=X4=xg=l,  is and  y =y =y =yg=0, 1  2  4  x =x =l. 3  No  5  generated w i t h x*=(l,1,0,1,0,1). to the o r i g i n a l PP problem.  and  Y3 Y5 1• =  covering  =  Equivalently,  constraint  can  be  In other words, i t i s f e a s i b l e  Since x  i s an o p t i m a l s o l u t i o n f o r  a r e l a x a t i o n of the PP problem i t i s an o p t i m a l s o l u t i o n f o r the PP problem  itself.  Solving  this  problem  l i n e a r problem r e q u i r e s constraints.  A  example  will  first  t r a n s f o r m i n g i t to a  14 e x t r a v a r i a b l e s and at l e a s t 21  considerable  to reduce the e q u i v a l e n t This  by  0-1  extra  amount of computation i s r e q u i r e d  SC problem to 9 c o v e r i n g  constraints.  be used i n chapter 5 to i l l u s t r a t e the  e f f e c t s of the m o d i f i c a t i o n s  of the b a s i c  algorithm.  19  4.  Evaluation  The  of the Basic covering  experimental  covering  relaxation  randomly generated  results  required second  to solve and  an  to  problems with using  in  Algorithm  [10]  exceeded  1  up  to  50  IBM 3 7 0 / 1 6 8 . )  only  of terms. The number  f o r three  and  50  The CPU  i n the o r i g i n a l problem.  time  l e s s than  1  problems with  The number  a  obtained  constraints  f i n a l CR p r o b l e m u s u a l l y d i d n o t e x c e e d t h e n u m b e r constraints  200  (These r e s u l t s were of covering  the  Over  variables  the basic algorithm.  minute  showed  be v e r y p r o m i s i n g .  e a c h i n d i v i d u a l p r o b l e m was o f t e n  r e l a t i v e l y l a r g e number on  reported  approach  c o n s t r a i n t s were s o l v e d  relaxation  i n the  of posynomial o f CR  problems  s o l v e d w a s t y p i c a l l y b e t w e e n 1 a n d 7. The be  success  of the covering  a t t r i b u t e d to the  introduced  in  the  fact  r e l a x a t i o n approach can l a r g e l y  that  no  additional  solution process.  variables  are  I t i s worthwhile to note  that the major shortcoming o f the procedures that l i n e a r i z e posynomial number  constraints  from the r a d i c a l  increase  o f v a r i a b l e s i n t h e l i n e a r i z e d p r o b l e m t o be  However, average only all  stems  three  most  of the problems solved  3 terms per c o n s t r a i n t . performance  of covering  CR  as  the  solved.  i n [10] c o n t a i n e d  i n d i c a t o r s ( t h e CPU t i m e ,  deteriorate  constraints  a v e r a g e number  i n the  increase.  is  d e n s i t y o f t h e CR p r o b l e m s .  final  marked  d u e , i n p a r t , t o t h e much  The c o m p u t a t i o n a l  of  o f terms i n a  The CPU t i m e showed t h e m o s t  increase  on that  t h e number  c o n s t r a i n t becomes l a r g e r . This  i n the  I t was shown i n [10]  i t e r a t i o n s , a n d t h e number problem)  the  results  in  higher [10]  20  reveal  t h a t t h e d e n s i t y o f t h e CR p r o b l e m h a s a d r a m a t i c e f f e c t  on t h e CPU The  time required accelerated  be d i s c u s s e d  i n chapter  to solve  covering  t h e PP  problem.  relaxation algorithm,  which  will  that  are  5, e m p l o y s t h r e e m o d i f i c a t i o n s  shown t o s u b s t a n t i a l l y i m p r o v e t h e e f f e c t i v e n e s s o f t h e r e l a x a t i o n approach for less sparse  PP  problems.  covering  21  5. M o d i f i c a t i o n s  The a c c e l e r a t e d be p r e s e n t e d the  algorithm  of the covering  accelerated  relaxation  covering  as  the  usual  conceptual  algorithm  programming  approximate  solutions.  solution  o r i g i n a l problem.  The  (IP) i s t h a t  solution  at  performance problems,  see  this  section  6.1.  These  optimal  solutions  is  iteration  are  i s not  generated  CR  SC  feasible  the  to  the  by a d d i n g  one  t o compute  problem.  stems from the  problem  on  in  approximate  relaxation algorithm  procedures are fast  obtained  relaxed  as  i s implemented  [3,6,19,25,28]. the  each  approximately  approximate algorithms  approximate procedures for  cutting  t o o p t i m a l i t y o n l y when  of this modification  example  the  other  successive  problem  The m o d i f i c a t i o n  for  the  idea  each  the  i s solved  for  of the various  of  The b a s i c  C u t s c a n be  s o l u t i o n f o r the current  promise  of  effectiveness  and  t h e CR p r o b l e m s  step to the b a s i c covering  an a p p r o x i m a t e  will  between  to optimality.  eliminate  A n CR p r o b l e m  approximate  extra  to  the  difference  relaxation  1 i s to solve  manner  Three aspects  to improve  f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m . the  which  approach.  i s not n e c e s s a r i l y solved  of modification long  The  Approach  i s a more s o p h i s t i c a t e d v e r s i o n  relaxation algorithm.  methods i n i n t e g e r  problem  Relaxation  relaxation algorithm,  have been m o d i f i e d  M o d i f i c a t i o n 1.  plane  covering  in this chapter,  basic covering  basic  of the Covering  excellent  for solving Four  are  greedy-like  developed  and t h e v a l u e s  average  within  IP  in  of the 2%  of  22  optimality.  Observe  that  i f the  approximate procedures f o r  s o l v i n g t h e SC p r o b l e m o b t a i n t h e o p t i m a l s o l u t i o n most t i m e , t h e n t h e n u m b e r o f t i m e s t h a t a CR p r o b l e m w i l l solved to optimality w i l l It solved  is to  optimality. technique  will  to  eliminate  the  a  slightly  modified  i s used the c u r r e n t b e s t s o l u t i o n The  is  enumeration  encountered.  original  otherwise  of  the  PP  covering  If  problem  current  this  then  constraints  i sf o r CR  than the  solution  the are  is  enumeration  generated  to  t h i s s o l u t i o n and the enumeration o f t h e augmented  p r o b l e m s t a r t s anew. problem  that  be i n t e r u p t e d w h e n e v e r a s o l u t i o n b e t t e r  current best solution  continues;  t o be  b e v e r y c l o s e t o 1.  Suppose  s o l v i n g t h e CR p r o b l e m s .  feasible  need  the  p o s s i b l e t o e n s u r e t h a t o n l y a s i n g l e CR p r o b l e m i s  enumeration  problem  of  terminates  If then  the  enumeration  of  the  the current best solution  CR  current  CR  i s feasible  a n d o p t i m a l t o t h e o r i g i n a l PP p r o b l e m . There to  the  is  e v i d e n c e t h a t m o d i f i c a t i o n 1 c a n a l s o be a p p l i e d  covering  polynomial  relaxation  programming  approach  problem.  F. G r a n o t a r e c u r r e n t l y i n v e s t i g a t i n g very for  similar  for  the  Moreover, the  general  0-1  D. G r a n o t  effectiveness  idea f o r improving Benders p a r t i t i o n i n g  and of  a  procedure  s o l v i n g m i x e d i n t e g e r p r o g r a m m i n g p r o b l e m s , s e e [12].  Modification employed  to  2.  An a p p r o x i m a t e  s o l u t i o n f o r t h e PP  o b t a i n a n i n i t i a l CR p r o b l e m .  in a sense, a closer  approximation of  the  problem  is  T h i s CR p r o b l e m i s , PP  problem  n e i g h b o r h o o d o f i t s o p t i m a l s o l u t i o n t h a n t h e i n i t i a l CR  in  the  problem  23  g e n e r a t e d by the  ( 1 , 1 , ...  excellent  solving  performance  IP p r o b l e m s .  implemented the  ,1).  PP  Modification of  the  F . G r a n o t a n d W.  2 i s a l s o m o t i v a t e d by  approximate procedures for Vaessen  have  developed,  and a n a l y z e d g r e e d y - l i k e a p p r o x i m a t e p r o c e d u r e s f o r  problem,  approximate  see  F. G r a n o t  solutions  found  [12]. by  The  these  values  CRQ number  i s formed of  by g e n e r a t i n g  different  approximate designate  starting  covering  an  constructed  approximate  i n the following  constraints  Explicitly,  s o l u t i o n f o r t h e PP p r o b l e m . manner:  begin CR  0;  :=  Zeros  :=  {v|x (v)=0}; p p  starting-node  :=  for  do  v 6 Zeros  Xpp?  begin starting-node(v)  :=  1;  g e n e r a t e augmented CR w i t h s t a r t i n g - n o d e ; starting-node(v) end CRQ  end  :=  CR;  :=  0;  were to  the  t h a t were s o l v e d .  nodes that are d e r i v e d  s o l u t i o n f o r t h e PP p r o b l e m .  the  procedures  c o n s i s t e n t l y c l o s e t o t h e o p t i m a l v a l u e s and were e q u a l o p t i m a l v a l u e s i n o v e r 60% o f t h e p r o b l e m s  of  from  a  from  the  let  Xpp  CRQ i s  24  The  approximate  solutions produced  [ 1 2 ] c a n n o t be i m p r o v e d to  1.  This  in  by c h a n g i n g one o r more v a r i a b l e s f r o m  property  starting-node will  by t h e m e t h o d s d e s c r i b e d  X p p ensures  of  that  at  least  be i n f e a s i b l e and h e n c e t h a t CRQ w i l l  0 on  not  be  close  to  then the s o l u t i o n of  CRQ  empty. It the  o p t i m a l s o l u t i o n of the P P problem,  formed  i n the above  solution  of  g e n e r a t e d by and  i f X p p i s equal  i s i n t u i t i v e l y clear that  the  the  likely  is  original  ( 1 , 1 , ...  number  therefore,  manner  of  likely  to  PP problem  ,1).  The o v e r a l l number  constraints  in  t o be s m a l l e r .  the  CR  problems  can  be  p r o c e d u r e s o l v i n g t h e CR p r o b l e m  Modification improved  by  3.  The q u a l i t y implicitly  can  be  constraints  and  selecting  covering  tighter  3, w h i c h w i l l  covering  Let solution  of  x(c)  (3).  iterations  CRQ  are,  generated  problem the  to optimality.  the  covering  constraints  a l l or most o f the  from  the  violated  t h o s e prime c o v e r s whose  be j u s t i f i e d  is  prime  posynomial associated  The o b j e c t i v e  of  shortly, i s to generate  constraints. designate  f o r the current  inequality  CRQ  as l o w e r b o u n d s by  c o n s t r a i n t s have minimal c a r d i n a l i t y .  modification  the  lower.  utilized  of  generated  of  s o l u t i o n s f o r the PP  enumerating  covers that  to  the f i n a l CR problem  The d e n s i t y  The v a l u e s o f the a p p r o x i m a t e  closer  than the s o l u t i o n of  i n t h e above manner i s n o t n e c e s s a r i l y  and  be  or  either  CR p r o b l e m .  an  approximate Consider  L e t R={i|vj6Ni, X j ( c ) = l } .  the  or  optimal  posynomial  R r e p r e s e n t s the s e t  25  of  non-vanishing  inequality  from  dropped w i l l  >  (6) The  terms  a i  i6R  covering  which  of the  (3)  at  terms  x(c).  The  vanishing  posynomial  a t x ( c ) have  been  be o f t h e f o r m :  TT  XJ < b .  jGNi  c o n s t r a i n t s t h a t c a n be d e r i v e d  from  (6) a r e o f t h e  form: 3>  y j > 1, w h e r e S i s a s u b s e t  o f N.  jes Let  be s u c h a c o v e r i n g  prime  ( s e e d e f . 3)  with a  S=S2 s u c h t h a t S  better  choice  associated  with  then there 2  than  S .  constraint with  since  minimal  ( s e e d e f . 3b) t h e n t h e r e  with  2  S=S  such that C  between C^ and C of covering suffice do  to  2  i s prime  exists a covering and  space o f current  The  2  into account the properties For  constraint  | S | < |S-j_|.  in  the r e l a t i v e merits  augmented.  2  2  is  h a n d , C^ i s p r i m e b u t n o t  constraints that are defined  be  Clearly, C  C  i t dominates the constraint  C  2  choice  The p r o p e r t i e s  chapter  2  o f C^ a n d C  2  do  not  since  they  and s t r u c t u r e o f t h e  lack of insight, C  because, f i r s t o f a l l , i t eliminates solution  o f S]_.  i s not  constraint  i s not c l e a r - c u t i n t h i s case.  to evaluate  n o t take  problem  2  subset  I f , on the other  2  If  exists a covering  i s a proper C^  S=S^.  2  m o r e 0-1 v e c t o r s  CR p r o b l e m a n d s e c o n d l y ,  CR  i s chosen from  the  the solution  o f t h e a u g m e n t e d CR p r o b l e m i s m o r e l i k e l y t o move c l o s e r t o t h e optimal The  solution since C j i s a tighter covering previous  constraints cardinality  with  paragraph motivates minimal  the  cardinality.  constraint.  search Formally,  (MC) p r o b l e m c a n b e s t a t e d a s f o l l o w s :  for  covering  the minimal  26  Minimize SCR (MC)  | Union ies  |  subject to > jes  If  aj > b  |R| i s n o t m u c h  implicit  enumeration  larger  than  by  encountered MC  the  covering  N o t e t h a t i f (6) i s a l i n e a r  on  an If a  constraint  feasible  solution  tree of  the  i n e q u a l i t y , then the  i s also the optimal solution. than  |N|, t h e n  a p p r o x i m a t e p r o c e d u r e s c a n b e e m p l o y e d t o s o l v e t h e MC  problem.  Greedy-like developed  the  employ  t h e MC p r o b l e m .  the basic algorithm i s the f i r s t  feasible solution If,  then  can  i n a depth-first search of the solution  problem.  first  we  technique f o r solving  f i x e d b r a n c h i n g method i s used, produced  |N|,  other hand,  approximate  in section  The  |R| i s m u c h l a r g e r  procedures  for  the  constraints  generated  e n u m e r a t i o n o f t h e s o l u t i o n t r e e o f t h e MC approximate  g u a r a n t e e d t o be p r i m e . 3>  problem  are  6.2.  covering  greedy-like  MC  procedures  to  by  a  problem be  restricted or  by  the  discussed, are not  Explicitly, l e t  y ; > 1 be a c o v e r i n g c o n s t r a i n t p r o d u c e d f r o m  (6) u s i n g  jev an a p p r o x i m a t e m e t h o d . V  of  V  inequality  Then i t i s p o s s i b l e t h a t a p r o p e r s u b s e t  i s also a covering constraint (6). This condition can  x i ( v ' ) = l i f i S V and 0 o t h e r w i s e .  easily Then  only i f there exists a proper subset V not  violated  by x ( v ' ) .  f o r t h e same p o s y n o m i a l  V  be  detected.  i s not prime  o f V such  that  Let i f and  (6)  is  27  The a c c e l e r a t e d v e r s i o n o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h can  now be s t a t e d i n a n i n f o r m a l p r o c e d u r a l  ACCELERATED  COVERING RELAXATION  fashion.  ALGORITHM  f i n d a n a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m ; generate  CRg u s i n g t h e a p p r o x i m a t e s o l u t i o n ;  repeat s o l v e t h e c u r r e n t CR p r o b l e m attempt  to generate  approximately;  additional cuts to  eliminate the approximate s o l u t i o n ; if  the approximate s o l u t i o n i s f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m  then  begin s o l v e t h e c u r r e n t CR p r o b l e m t o o p t i m a l i t y ; attempt  to generate  additional cuts  to eliminate the optimal s o l u t i o n ; i f no c u t s w e r e a d d e d the o p t i m a l  then  s o l u t i o n t o t h e CR  problem  i s f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m ; end u n t i l the current optimal  solution is feasible;  stop.  The a l g o r i t h m t e r m i n a t e s PP  problem  in  at  most  2  with n  an o p t i m a l  iterations.  solution  Termination  f i n i t e l y many s t e p s b e c a u s e t h e s o l u t i o n s p a c e  contains  for  the  occurs i n at  most  28  2  n  binary  vectors  and a t e a c h i t e r a t i o n e i t h e r an  s o l u t i o n o r an o p t i m a l termination  is  solution i s discarded.  optimal  constraint  If  cardinalities  the  i s a r e l a x a t i o n o f t h e PP  algorithm  covering  solution  t o t h e PP p r o b l e m b e c a u s e  t o t h e CR p r o b l e m w h i c h The a c c e l e r a t e d  The  i t is  violated  the covering  problem.  those  that  constraints, covering the  can  be  then the accelerated  constraint  CR  constraint.  constraints  that can  are v i o l a t e d .  Example 2  + 5x  1  only  + 4x  2  constraint  See s e c t i o n  a  + 3x  3  7.1  from those  + 3x  4  +  5  2x  g  s. t . 1)  8x^X2X3  + 6x x  2)  7x x x 3  5  +  3)  7x x  5  + 4X]^x  4)  5X2*3  5)  3x  2  4  x 2  +  2  5  x  2X"LX  i  x  4 +2x x  Xi€{0,l}  3  5 4  for  + 5x  4  6  + 4x x  3  3  2  +  < 13  < 6  + 4x x x  4  6  3 x  6  + 2x x 4  5  6  4  < 8 -  +  2 x  7  5  + 2x x 5  i=l,2,3,4,5,6.  '.  1  g  + x-^g  < 5  posynomial attempts  constraints  details.  solved:  one  t o augment  algorithm  for further  PP p r o b l e m was  smaller  than  few  revisited.  In example 2 the f o l l o w i n g 7x  if  be  posynomial  uses more  are v i o l a t e d then the a c c e l e r a t e d  E x a m p l e 3.  MAX  from a l l other  algorithm  Furthermore,  t o add more t h a n one c o v e r i n g that  are  from t h i s posynomial c o n s t r a i n t  problem.  constraints  generated  one  posynomial  g e n e r a t e d f r o m one p a r t i c u l a r p o s y n o m i a l c o n s t r a i n t than  on  optimal  does not n e c e s s a r i l y generate  from each of  approximate  29  To i l l u s t r a t e m o d i f i c a t i o n  2,  x  p p  =(1,1,0,1,0,1)  will  be used  to  generate CRg. The  first  from  starting-node  1)  x^X2X x =0  x x x =0 2  second  starting-node  f r o m 3)  5  x x x =0 1  6  5  X2X4X x =0  5)  6  5  two s e t s o f c o n s t r a i n t s a r e s i m p l i f i e d  o f covering  1.  Iteration MIN  generates  (1,1,0,1,1,1)  xjX4X =0  4)  set  6  3  X3X2X5X4X5=0  5)  These  4  3  4)  The  generates  (1,1,1,1,0,1)  constraints  + 4y  2  + 3y  3  as a  t o f o r m t h e i n i t i a l CR p r o b l e m .  Solve the i n i t i a l  7Y! + 5 y  and written  CR p r o b l e m :  + 3y  4  +  5  2y  6  s. t . Yl  +  Y2  +  Y2  +  y  3  y  3  +  y  4  + +  Yl  Y  4  Yl +  Y2  Y4  +  Y5  +  y  +  Y5  y  6  >  1  >  1  ^ 1 +  5  +  y  6  ^ i  Y6 -  1  yiS{0,l} f o r i=l,2,3,4,5,6. Its x  l  =  i s y =y2=y =y =0,  solution x  2  =  x  3  =  x  1  1)  4)  =  4  x^X2X =0 3  X l  x x x =0 2  3  5  and x =xg=0.  5 l'  additional covering from  3  5  constraints:  and y =Y6=l.  Use  4  (1,1,1,0,1,0)  Equivalently, to  generate  30  The  former  therefore  c o n s t r a i n t dominates the l a t t e r  not included  constraint CR  also  i n the  eliminates  augmented the f i r s t  c o n s t r a i n t which i s  problem.  The  former  c o n s t r a i n t i n the  initial  problem.  Iteration MIN  ly  ±  2.  S o l v e the augmented  + 5y  2  + 4y  3  + 3y  4  y  2  +  y  3  +  4  y  2  +  y  3  CR  + 3y  problem: +  5  2y  6  s. t .  Yl  y  > 1 +  +  Y4  +  Yl Y2  +  solution  is  2  4  2  6  3  o p t i m a l t o t h e PP  To  illustrate  4  5  modification  Y5  +  +  Y5  +  v  1  6  -  Ye  -  6  and  1  1  y =y =l. 3  Equivalently,  5  x*=(1,1,0,1,0,1) i s  3,  (1,1,1,1,1,1)  constraints with minimal  feasible  and  w i l l be u s e d t o  cardinality:  x^x x =0 2  3  5)  x x x x x =0  3)  xix x =0  4)  x x x =0  5)  x x x x =0  1  2  3  4  2  2  3  3  5  6  5  6  4  5  This set of constraints covering  -  problem.  generate covering f r o m 1)  5  +  y - j _ = y = y = y = 0,  x = x = x = x = l , and x = x = 0 . 1  > 1  6  for i=l,2,3,4,5,6.  y^e{0,l}  Its  Y4  v  y  is simplified  and w r i t t e n  c o n s t r a i n t s to form the i n i t i a l  CR  as as a s e t o f  problem.  31  Iteration MIN 7yx  1.  Solve  t h e i n i t i a l CR p r o b l e m :  + 5y  2  + 4y  3  +  2  +  3  + 3y  + 3y  4  5  + 2y  6  s.t. y i  y  y  > 1  Yl  + y  2  +  y  3  Y  2  +  Y  3  solution  xi=x =x =x =0, 2  3  optimal  This  Y5  +  +  +  Y  4  +  Y5  y  6  1  > 1 -  1  f o r i=l,2,3,4,5,6.  Yie{0,l}  Its  Y4 •  5  is  Yl Y2 Y4 Y6  and  =  =  =  x =x =l. 4  g  = 0  '  a n d  Y3~Ys -  Equivalently,  = 1  x*=(l,1,0,1,0,1)  i s f e a s i b l e and  t o t h e PP p r o b l e m .  example  construct  i s perhaps misleading.  an example  successful.  f o r which  the  I t i s not too d i f f i c u l t modifications  are  not  to as  32  6.  Greedy-like  Approximate  f o r t h e S C a n d MC  This used  chapter  by  t h e CR a n d MC p r o b l e m s  usually  (l l f  Initially  f  algorithm  to obtain  greedy approach s t a r t s with ,1),  ...  and  a l l variables  moves  are  free.  of a variable  i s the expected pay-off  At  from the current  of other  i t e r a t e s u n t i l no more v a r i a b l e s c a n be  moves  towards  free.  At each i t e r a t i o n  calculated current The  determine  solution.  dual  starts  a feasible solution.  to  which  The  promise  The  at and  primal  dropped.  (0,0,  with  which  i t s value  fixed.  ...  ,0)  and  I n i t i a l l y a l l variables are  the promise o f each  Once a v a r i a b l e  approach  are  the  the variable  i s dropped,  approach  approach  iteration  solution.  the value  greedy  variables  optimum.  to determine  of fixing  Once a v a r i a b l e  solution,  local  each  possibly  The d u a l  are  good s o l u t i o n s f o r  a  i s calculated  be d r o p p e d  value.  that  a feasible  towards  variable will  particular  procedures  at polynomial cost.  "promise" o f each free v a r i a b l e  a  Problems  develops the greedy-like  the accelerated  The p r i m a l  Procedures  variable  free  variable  is  w i l l be a d d e d t o t h e  i s added, i t s value  iterates until a l l covering  i s fixed.  constraints  are  satisfied. An often primal  approximate solution obtained  be i m p r o v e d  by a p p l y i n g  by t h e d u a l  the primal  procedure to  procedure w i l l drop to 0 the variables  needed t o ensure  feasibility.  procedure can  that  i t .  a r e no  The  longer  33  6.1  Greedy-like  The  approximate  described  procedures  shortly,  approaches. The  Procedures f o r the  Two  are  modifications  Problem  for  variants  the  problem,  basic primal  10-JL | i s t h e However,  cardinality if  the  of  the  variability  is substantial,  promise  by  calculated  constraints  r e s u l t s t o be  reported  this weighting effectiveness  in  of the  taking  which  Yi  in section  factor  in  y^,  promise.  The  then  and  a  ratio  |Cj_|, w h e r e with  more  y^.  of  the  accurate  i n t o account the c a r d i n a l i t i e s occurs. 7.3  The  show t h a t  calculating  i n [20]  as the  cardinalities  computational  the  promises  approximate procedures.  independently proposed  dual  associated  the  unsatisfied constraints is  with  column of  be  and  is usually calculated  cost-coefficient associated  to  introduced.  f i r s t o f t h e s e c a l c u l a t e s a more a c c u r a t e  C i , the  o f the  SC  of the  have been  promise of a f r e e v a r i a b l e y^ of  SC  inclusion improves  A s i m i l a r idea  f o r the m u l t i d i m e n s i o n a l  of the was  knapsack  problem. The for  second modification  which  the  promise  c o n s i s t s of the constraints.  free The  the  calculated.  variables  that  set of free The  occur  e f f e c t of t h i s m o d i f i c a t i o n  of variables occuring early  is  restricts  in tight constraints  variables  restricted in  the  is that  set  tightest the  are determined at  value an  stage. I t i s assumed t h a t  s t r i c t l y greater  than  the 1.  c a r d i n a l i t y of  each  constraint  is  34  Consider  t h e SC p r o b l e m  MIN  n > c-jYj j=l  subject  (SC)  to  n >. a i j y - i > 1 f o r i = l , j=l yj6{o l}  for  f  ,m  jSN,  where a i j 6 { o , l }  for Vi,j.  Define - 1 i f y£ i s f r e e fi  =  - 0 i f yj[ i s f i x e d t o e i t h e r  0 or 1  F = {i|fi=l}  hi(y)  =  n - 0 i f > ajiyj j=l - 1 otherwise  (y)  =  {i|hi(y) 0}f  H  are Now,  is  b y a p a r t i c u l a r 0-1 v e c t o r  f o r a 0-1 v e c t o r  n Ri(f) = E j=l T(y)  i . e . H(y) i s the s e t o f c o n s t r a i n t s  =  satisfied  that  y.  y and a c o r r e s p o n d i n g  vector  f=(fj_) l e t  a-i-^f-; a n d l e t  = {j6F|3i the  > 1  set  (  =l A v M i  a i j  of  free  unsatisfied covering M = { l , 2 , ...  ,m};  positive constants.  (1 < R j ( f ) < R ^ f ) ) ) } ,  variables  constraints  occuring a t y.  and l e t e and e  r  in  the  i.e. T(y) tightest  Further l e t  designate  suitably  small  S u b s e q u e n t l y , h-jjy), H(y) , R i ( f ) and T ( y )  w i l l b e d e n o t e d b y h ^ , H, R^ a n d T  respectively.  SC PRIMAL G R E E D Y - L I K E PROCEDURE i n i t i a l i z e H, R a n d T; y := 1;  f :=  1;  repeat i f s l o w - o p t i o n t h e n S := F e l s e S := T; m f o r j G S c o m p u t e p j = C j / ( >; i=l k := MAX  j/((Ri~l)hj[+e )) r  p i , i n c a s e o f a t i e MIN c ^ ;  ies if p  > e then  k  begin y := 0; f := 0; for i : = l t o n i f R i = 1 then k  k  begin j  :=  0;  r e p e a t j := j + 1 until ^ijfj fj  = 1;  := 0  update  H;  end u p d a t e R a n d T; end until p  k  < e o r F=0  or  H=M;  stop. "Ri-l"  i s the weighting factor  f o r the primal  approach,  36  SC DUAL G R E E D Y - L I K E initialize T  PROCEDURE H a n d R;  f  y := 0; f := 1; repeat if  s l o w - o p t i o n t h e n S := F e l s e S := T;  for  j G S c o m p u t e p.; = c+/{  m >_ a i - ; / ( R i h i + e ) ) i=l r  k := M I N p j ^ , i n c a s e o f a t i e M I N c ^ ; ies if p  > e then  k  begin Yk  : =  1  >  f  k  : =  °'  u p d a t e T a n d H; end until p  k  < e o r H=M;  stop. "Rihi"  i s the weighting factor  f o r the dual  Both procedures run i n O(n^) time. are  an i n s i g n i f i c a n t o v e r h e a d  problem At options  the  These time  i n the context  of  every iteration for  the  solving  the accelerated algorithm  a  employs  the p r i m a l and f o r the d u a l procedure t o f i n d  s o l u t i o n s t o t h e c u r r e n t CR p r o b l e m .  PP  The  both four  solution  s m a l l e s t o b j e c t i v e f u n c t i o n v a l u e i s used t o generate  c o v e r i n g c o n s t r a i n t s t h a t w i l l be added t o  problem.  requirements  to optimality.  approximate with  approach.  the  current  CR  37  6.2 G r e e d y - l i k e  P r o c e d u r e s f o r t h e MC  Problem  T h e t w o a p p r o x i m a t e p r o c e d u r e s f o r t h e MC p r o b l e m a r e a  variation  consider  of  t h e g r e e d y theme.  To s i m p l i f y the  a s l i g h t l y different formulation  Minimize subject |  yj  o f t h e MC  again  discussion, problem:  |U(y)| to  a  j  y  j  > b  e{o,i},  where U(y) Nj  i s the union o f a l l Nj f o r which i s the set of variables  yj=l.  i n the j t h term,  R i s the s e t o f non-vanishing terms d e f i n e d as b e f o r e  define  !- 1 i f yi fi  =  F(y) V(y)  i s free  0 i f y i i s fixed to either =  earlier,  0 or 1  {i|fi=l}.  represents  the s e t of free v a r i a b l e s  p a r t i a l covering  constraint.  i n the  current  38  MC P R I M A L G R E E D Y - L I K E P R O C E D U R E  V := U n i o n N j f o r V J 6 R ; y := 1; f := 1; repeat f o r j 6 F i f a-j > >  a  iYi  ~  D  t h e n f-i=0;  i6F if  F?i0  then  begin f o r j 6 F c o m p u t e p j := ( | V | - | V / N j | ) / a j ; k := MAX p-;, i n c a s e o f a t i e MAX a j ; jSF y  := 0; f  k  k  := 0; V :=  V/N ; k  end until  F=0  stop.  MC DUAL G R E E D Y - L I K E  0;  V :=  PROCEDURE  y := 0; f := 1;  repeat f o r j S F c o m p u t e p j := ( | U n i o n ( V , N j ) | - | V | ) / a j ; k := MIN p-;, i n c a s e o f a t i e MAX a-;; jGF Yk  : =  V := until stop.  F=0  1  '  f  k  : =  °'  Union(V,N ); k  39  7.  E v a l u a t i o n of the A c c e l e r a t e d Covering  The  development  optimization initial  problem  a l g o r i t h m has  implementation  worst-case  almost the  is  often  been  algorithm an  stage  order  in  combinations  mathematical  iterative process.  developed  a  Analytic techniques tend  results  for  show  assess  determining  an  average  to f a i l because the a l g o r i t h m  the  valuable initial  the development process to  correct  Once  behaviour  a l w a y s t o o c o m p l e x t o o b t a i n any  then  a  i s r e q u i r e d to i n v e s t i g a t e the average  behaviour  promising,  for  reliable  experimental  the  an  Algorithm  and  o f the a l g o r i t h m . and  of  Relaxation  can  is  results.  algorithm  If  to  advance to the  be  next  the e f f e c t i v e n e s s o f s t r a t e g i e s and  of s t r a t e g i e s t h a t can  be  performance of the a l g o r i t h m .  incorporated  This stage  to  improve  i s repeated  until  either  the p e r f o r m a n c e of the a l g o r i t h m becomes s a t i s f a c t o r y  or  until  the  of  algorithm  designers  abandon the p r o j e c t f o r l a c k  effective strategies. If  empirical  techniques  p r o p e r t i e s of the a l g o r i t h m , will  depend  tested. to  a  on  are  then  used  the  to determine  problem  algorithm's  i s , therefore expressed  p a r t i c u l a r class of problems.  random  investigate  the  performance  t h e c l a s s o f p r o b l e m s on w h i c h t h e a l g o r i t h m  Average behaviour  difficult  to  is  which the a l g o r i t h m  empirically vague.  with  respect  Truly average behaviour because  Ideally,  the  is  of  a  the c l a s s of problems  on  is tested is representative  concept  is  of  real  world  problems. In view of these o b s e r v a t i o n s , c a r e f u l d e s i g n  and  complete  40  and  accurate  particularly  reporting important  mathematical  computational  aspects  of  the  p r o g r a m m i n g a l g o r i t h m s and  [4] h a v e r e c o m m e n d e d a presenting  of  set  computational  of  inadequate.  This  guidelines  development  of  adheres  Crowder et a l  for  designing  Their  the standards i n  thesis  are  software.  experiments.  p r o f e s s i o n a l j o u r n a l s found  experiments  survey  this  where  of  area  possible  to to  and the be the  recommendations of [4].  7.1  Aspects of the  The about for  Implementation  following sections  the  supply  implementation  section  the  allow  experimental  results  f i e l d of s c i e n t i f i c  i n FORTRAN^. usual  the  reader  that will  to  correctly  be d i s c u s s e d i n  The  endeavour,  reader w i l l pardon  and w i d e s p r e a d the program the author  convention  was  written  for o m i t t i n g the  justifications. The  program  subroutines. 6000  information  7.3.  In k e e p i n g w i t h the t i m e - h o n o u r e d in this  pertinent  o f the c o v e r i n g r e l a x a t i o n a l g o r i t h m  t h e PP p r o b l e m w h i c h w i l l  interpret  the  lines  2000 r a n d o m l y  consists  of  The  source code,  long.  During  more  including  f i f t y f u n c t i o n s and  comments,  is  roughly  the course of the experiments,  generated problems  have been removed from the  than  were s o l v e d .  All  known  over bugs  program.  1 F o r p o r t a b i l i t y , A N S I F O R T R A N was e m p l o y e d . b e e n t e s t e d o n IBM a n d DEC machines.  The  program  has  41  The P u r p o s e and C a l l i n g H i e r a r c h y  1.  PP-OPT s o l v e s  Inputs:  PP  o f the Major  Procedures  a PP p r o b l e m t o o p t i m a l i t y .  problem;  approximate  solution;  value  a p p r o x i m a t e s o l u t i o n w h i c h c a n be u s e d a s a l o w e r Output: optimal  1.1  an  bound.  s o l u t i o n f o r t h e PP p r o b l e m .  CR-GENERATOR  solution  of  generates  f o r the current  a n a u g m e n t e d CR p r o b l e m  CR p r o b l e m  o r i g i n a l PP p r o b l e m .  Covering  a pool  which  of constraints  is  infeasible  constraints  i s formed  i fthe to  are selected  by r e p e a t e d l y  the from  invoking  SOLVE-MC. Input: approximate or optimal  solution for  the  current  CR  solution  to  problem. Outputs: l o g i c a l v a r i a b l e which the  current  CR p r o b l e m  a u g m e n t e d CR  i s true  i f the  i s f e a s i b l e to the o r i g i n a l problem;  problem.  1.1.1 SOLVE-MC c o l l e c t s a s m a l l MC p r o b l e m u s i n g Inputs:  an i m p l i c i t  posynomial  indicating  set of solutions  f o r the  enumeration.  constraint;  integer  t h e maximum n u m b e r o f s o l u t i o n s  variable that w i l l  be  examined. Output: the  s e t of the k best  search  covering  of the solution tree.  constraints  k is a  found i n  constant.  42  1.1.2  ADD-CC  adds  a  covering  p r o b l e m and removes d o m i n a t e d Input: covering  ELCOLS  to  the  CR  constraints.  constraint.  O u t p u t : u p d a t e d CR  1.1.3  constraint  problem.  finds  the  variables  whose v a l u e s can  d e t e r m i n e d i n a d v a n c e and e l i m i n a t e s them  from  the  be CR  problem. I n p u t : CR  problem.  O u t p u t : r e d u c e d CR  1.2  problem.  SC-APPRO f i n d s an a p p r o x i m a t e  solution  using the g r e e d y - l i k e procedures described I n p u t : CR  problem  earlier.  problem.  Output: approximate  1.3  f o r a SC  solution  f o r t h e CR  SC-OPT f i n d s an o p t i m a l s o l u t i o n  an i m p l i c i t  problem.  f o r a SC p r o b l e m  using  enumeration.  I n p u t s : CR p r o b l e m ;  lower bound; s t a r t i n g  Outputs: optimal solution  node.  f o r t h e CR p r o b l e m ;  first  feasible  solution.  2.  PP-APPRO f i n d s an a p p r o x i m a t e  using a greedy-like I n p u t : PP  solution  for  procedure.  problem.  Output: approximate  solution  f o r t h e PP  problem.  a  PP  problem  43  Generating Covering Various selecting current bound  Constraints  strategies  the  covering  CR p r o b l e m . on  the  can  be  used  constraints  Firstly,  in  that  i tis  CR-GENERATOR  a r e t o be a d d e d t o t h e  possible  to  set  number o f c o v e r i n g  constraints  that  w i l l attempt  t o add t o t h e c u r r e n t  CR p r o b l e m .  If  posynomial  constraints  are  violated,  a d v a n t a g e o u s t o add more t h a n one posynomial  constraint.  manner i n w h i c h t h e c o v e r i n g pool  1)  of constraints  add  at  least  one c o v e r i n g  constraint,  2)  the  cardinalities earlier  k  only  a  i t is  from  a  few often  violated  to vary the  are selected  covering  constraint  constraints  from t h e p o o l , where k i s  mentioned  posynomial  lower  CR-GENERATOR  i t i s possible  constraints  a  from  the  g e n e r a t e d by SOLVE-MC:  posynomial add  then  constraint  Secondly,  for  lower  bound  and  from each  with the  the  violated  the  smallest  maximum  of  the  number o f v i o l a t e d  constraints.  Some o t h e r p o s s i b i l i t i e s s u c h a s c h o o s i n g c o n s t r a i n t s  at  random  w e r e f o u n d t o be i n e f f e c t i v e . SOLVE-MC u s e s a f i x e d enumerating  the  branching  strategy  s o l u t i o n t r e e o f a MC p r o b l e m  manner.  SOLVE-MC c o l l e c t s t h e f i v e b e s t  Observe  that  i f the  first  for  in a depth-first  solutions  solution encountered  s o l u t i o n , t h e n no w o r s e s o l u t i o n c a n be c o l l e c t e d . of  the  variables  is  such  that  a  < k+l' a  k  implicitly  encountered. i s an  optimal  The  where  a  ordering k  i s the  44  coefficient a  k/l kl  t h e k t h term,  - k+l/l k+ll'  N  kth  of  a  where  N  search  of  Max =l i n the basic  Solving  enumerating manner.  a  fixed  is a  s  terminates  parameter  after Max  s  of  SOLVE-MC.  branching  strategy  for  implicitly  t h e s o l u t i o n t r e e o f a SC p r o b l e m i n a d e p t h - f i r s t  The o r d e r i n g  cost-coefficients. optimization SC-OPT  Max  tree  t h e SC P r o b l e m  SC-OPT u s e s  o f the variables i s determined No  surrogate  techniques  returns  constraints  (see f o rexample  the optimal  and f i r s t  by  or  their  subgradient  [1,5,18]) a r e employed.  feasible solutions f o r the  problem. A  lower  bound,  the optimal  solution there  from  supplied  solution. the previous  b y SC-APPRO, c u r t a i l s  Furthermore,  the solution tree before  relaxation  than  since  the first every  the search  the first  CR p r o b l e m s o l v e d  i s one, i s used as a s t a r t i n g node.  a f e a s i b l e completion,  not  that  algorithm.  s  in  such  i s the s e tof variables i n the  k  the solution  s o l u t i o n s have been found.  for  alternatively,  term. The  SC  N  or  feasible  to optimality, i f  No n o d e s  that  occur  f e a s i b l e s o l u t i o n c a n have CR  problem  each o f i t s predecessors,  is a  and w i l l ,  tighter  therefore,  have t o be e x a m i n e d . The  special  structure  o f the covering  used t o e x p l o i t t h e boolean operations language  level.  SC-OPT  constraints  available at the  represents  c o n s t r a i n t s by a two-dimensional integer  the s e t of array  i s not machine covering  containing  only  45  O's  and  l's.  (This  array occupies  s p a c e r e q u i r e d by t h e d a t a and  memory  space  techniques dependent  and  7.2  research  Problem  An  supply  reported  performance describes  word  are  [16]  are,  the  task  the  use  be  reduced used,  in this  CPU  of these  see  [16].  the kinds of  The  machine  techniques  algorithmic  aspects  the  status  thesis.  tool  class  of  of  the  for  the  analysis  i s a problem generator  of  problems  algorithm  be d e t e r m i n e d .  the generator  o f PP p r o b l e m s a n d  covering  which i s needed  reproducible can  the  for  which This  i s a measure of the  tightness of a c o n s t r a i n t  M i s t h e number o f  constraints  P i s t h e maximum number o f t e r m s i n a c o n s t r a i n t E i s t h e maximum number o f f a c t o r s i n a initializes  the  random number  term  generator  to the  section  i t s parameters.  N i s t h e number o f v a r i a b l e s  seed  of  implementor  PROBLEM PARAMETERS alpha  time  by an o r d e r  unfortunately, of  memory  Generation  algorithm  a  o f the  i s , therefore, inappropriate given  essential  relaxation  can  t h e a t t e n t i o n away f r o m t h e  o f t h e p r o b l e m and of the  in  Moreover,  to s h i f t  a  complicate  considerably. tends  in  described  60%  s t r u c t u r e s of the program.)  requirements  magnitude i f a l l b i t s  roughly  46  U n i f o r m ( s , t ) r e t u r n s an i n t e g e r  randomly  distributed  between s and t .  PP P R O B L E M G E N E R A T O R  ( s e e d , N, M, P, E , a l p h a )  i n t e g e r P, E ; i n t e g e r N , M, real  seed;  a l p h a , 0 < a l p h a < 1;  begin i n i t i a l i z e Uniform(seed); c  0  := 1;  f o r j : = l t o N d o CJ for  := C j _ ^ +  Uniform(0,10);  i : = l t o M do begin p(i)  := U n i f o r m ( l , P ) ;  for j : = l t o p ( i ) do begin a^j  :=  Uniform(l,20)  Nij  :=  0;  for  k:= 1 t o U n i f o r m ( 1 , E )  do  Nj[j := U n i o n ( N ^ j , { U n i f o r m ( l , n ) }) ; Nj^j i s t h e s e t o f v a r i a b l e s end n bj[ :=  J a i j ;  j=l end end.  i n term i j  47  7.3  Computational  The  major  modifications were  objective  of  in  of  improvements  chapter  the  5  covering  a r e m a i n l y due  p r o d u c e an o p t i m a l  Experimental  relaxation  solved  that  improved  approach.  reduction  to  s o l u t i o n t o a PP  the  relaxation algorithm  have s i g n i f i c a n t l y  t o a 70%  SC p r o b l e m s t h a t h a v e t o be  the  These  i n t h e number  optimality  in  order  of to  problem.  design  To e v a l u a t e described  t h i s s e c t i o n i s t o show t h a t  of the o r i g i n a l c o v e r i n g  presented  performance  results  the  shortly,  modifications, were  tested  various  f o r the  methods,  to  be  following c l a s s of  PP  problems:  The  N  M  30  30  (2,5,  ...  40  40  (2,5,  ...  choice  P  E  alpha  17,20)  (1,5,9)  0.5  17,20)  (1,5,9)  0.5  o f t h i s p a r t i c u l a r c l a s s was  d e t e r m i n e d by  a  number  of d i f f e r e n t factors: The  modifications  covering  covering  that  are  incorporated  relaxation algorithm  in  the  accelerated  were p r i m a r i l y d e v e l o p e d  t o r e d u c e t h e n u m b e r o f SC p r o b l e m s t h a t h a v e t o  be  optimality.  evaluate  It  is  necessary,  therefore,  to  solved  to their  e f f e c t i v e n e s s f o r PP p r o b l e m s f o r w h i c h a n o p t i m a l  solution  produced at the  optimality.  c o s t o f s o l v i n g m a n y SC p r o b l e m s t o  is  48  The e x t e n s i v e 1)  the  experiments performed  a v e r a g e number o f t e r m s  that  in a posynomial constraint i s  the dominant parameter  a f f e c t i n g t h e number o f  t h a t h a v e t o be s o l v e d  t o o p t i m a l i t y ; t h i s number a p p e a r s  increase 2) t h e  overall  CPU  time  dramatically  i s , o f c o u r s e , due the  required as N becomes  t o an e x p o n e n t i a l  to  solve large, increase  s o l u t i o n s p a c e s o f t h e SC p r o b l e m s  3) PP p r o b l e m s w i t h a l p h a = 0 . 5 Figure  SC  problems to  linearly with P  increases  a  (This  c a n be  problem increase  i n the s i z e of  are the most  difficult. PP  problems  i s b o u n d e d b y t h e d i f f i c u l t y o f t h e SC  following conclusions  PP  t o be s o l v e d . )  1. c l e a r l y s h o w s t h a t t h e s i z e o f t h e  c a n be s o l v e d The  i n [10 ] s h o w  that  problems.  drawn:  1) N i s a s e c o n d a r y f a c t o r i n t h e e v a l u a t i o n  of the  accelerated  algorithm. 2) P, h o w e v e r , i s a p r i m a r y f a c t o r . 3) T h e p e r f o r m a n c e o f t h e c o v e r i n g  relaxation algorithm  p r o b l e m s w i t h l a r g e N w i l l m a i n l y be i m p r o v e d  by e m p l o y i n g  m o r e s o p h i s t i c a t e d t e c h n i q u e f o r s o l v i n g t h e SC  Performance  for  PP a  problems.  indicators  The f o l l o w i n g  i n d i c a t o r s are used to a s s e s s the  of the  algorithm:  CPU  is the execution  time  (seconds) required  performance  to solve  a  PP  problem. The  time required  t o g e n e r a t e the p r o b l e m and t o  obtain  49  an  approximate  negligible  solution  amount  of  I/O  measurements were o b t a i n e d MTS u s i n g found  i s excluded time  is  vary  CPU.  included.  about  1%  compiler.  with  the  under  CPU  load  A The  o n a n AMDAHL 4 7 0 V / 6 - I I  t h e FORTRAN H o p t i m i z i n g  to  from  was  of the  installation. CR-CPU  i s the total  execution  time required  f o r s o l v i n g t h e SC  problems t o optimality. OPT  i s the  number  of  o p t i m a l i t y i n order  SC  problems  to solve  that  i s t h e number  o f SC p r o b l e m s s o l v e d  COVERS  i s t h e number  of covering  DENSITY  solved t o  a PP p r o b l e m .  HEUR  problem solved  were  approximately.  constraints  in  the  final  SC  to optimality.  i s t h e d e n s i t y o f t h e f i n a l SC p r o b l e m .  EFFECTIVENESS  is  value Ioptimal solved  Methods  the  average  value))100%  of  ((best  approximate  f o r a l lsC problems that  were  to optimality.  investigated  To e v a l u a t e were d i s c u s s e d  the various modifications i n chapters  and  strategies  that  5, 6 a n d 7 t h e f o l l o w i n g m e t h o d s  were  tested:  METHOD I  i s the basic covering in chapter  3.  relaxation algorithm  One c o v e r i n g  constraint  discussed  i s generated  from each v i o l a t e d posynomial c o n s t r a i n t and Max =l. s  METHOD I I  i s t h e same a s METHOD I e x c e p t  that modification  1  50  discussed  i n chapter  5 i s incorporated.  METHOD I I I i s t h e same a s METHOD I I e x c e p t t h a t m o d i f i c a t i o n discussed METHOD I V  i n chapter  5 i s also  incorporated.  i s t h e same a s METHOD I I I e x c e p t (1)  2  that  t h e terms i n a posynomial c o n s t r a i n t a r e ordered  s u c h t h a t afc-n/lN^.,.! | > a / | N | a n d k  k  (2) M a x = 5 , i . e . t h e e n u m e r a t i o n o f t h e MC p r o b l e m s s  terminates (See  after  5 s o l u t i o n s have been  s e c t i o n 7.1)  METHOD I V A i s t h e same a s METHOD I I I e x c e p t t h a t i.e.  encountered.  Max =infinity, s  t h e e n u m e r a t i o n o f t h e MC p r o b l e m s i s n o t  restricted. METHOD V  i s t h e same a s METHOD I V A e x c e p t t h a t t h e k constraints with selected.  the smallest  k i s s e t equal  posynomial constraints. METHOD V A  covering  cardinalities are  t o t h e number o f v i o l a t e d ( S e e s e c t i o n 7.1)  i s t h e same a s METHOD V e x c e p t t h a t  k i s set to  max{k (0.2M)}. f  METHOD V A A i s t h e same a s METHOD V A e x c e p t t h a t t h e  "weighting  f a c t o r " has been dropped from t h e approximate p r o c e d u r e s f o r t h e SC p r o b l e m t h a t w e r e d e s c r i b e d i n s e c t i o n 6.1.  Conclusions The figures entry  following conclusions  a r e drawn from t h e t a b l e s and t h e  that  a t the end o f t h i s chapter.  can  be  found  i n t h e s i x t a b l e s was o b t a i n e d  Each  by computing t h e average o f  51  ten  samples. Table  an  SC  I assesses  t h e improvements obtained  ( i i )using  g e n e r a t e CRQ  an  solved  (i.e. modification  1  reduces  modification  measured  2 ) . Table  the  number  I shows of  by  the  t h e number o f c o v e r i n g 2) a d d i t i o n a l  SC p r o b l e m s t o be  t h e number o f i t e r a t i o n s  number  SC  of  constraints  improvements  modification constraints  2; in  problems solved assesses  for generating shows  problems  the  final  approximately  and s e l e c t i n g  f o r METHOD I I ) a n d  realized  by  applying  number  of  covering  the  SC p r o b l e m a n d t h e number o f SC are reduced.  covering  strategies  constraints.  Table  II  that o f P, m o d i f i c a t i o n  3  reduces  CPU t i m e a n d t h e number o f SC p r o b l e m s s o l v e d 4) t h e p e r f o r m a n c e o f t h e a l g o r i t h m t h e MC p r o b l e m s t o o p t i m a l i t y longer  be  5) t h e d e n s i t y  I I I shows  the  (When P i s v e r y  overall  approximately  i s n o t improved by  solving  l a r g e t h i s may  true) o f t h e SC p r o b l e m s i s r e d u c e d , a s e x p e c t e d , by  selecting minimal c a r d i n a l i t y covering Table  to  i n t h e f i n a l SC p r o b l e m  are  explicitly,  solved  the effectiveness of the various  3) f o r l a r g e v a l u e s  no  that  1 increases  o p t i m a l i t y f o r METHOD I a n d a p p r o x i m a t e l y  II  1)  t o o p t i m a l i t y by 65% a n d t h e o v e r a l l CPU t i m e by 50%;  however, (as  solution  a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m t o  (i.e. modification  1) m o d i f i c a t i o n  Table  (i) solving  p r o b l e m t o o p t i m a l i t y o n l y when i t s a p p r o x i m a t e  i s f e a s i b l e t o t h e PP p r o b l e m t o b e s o l v e d and  by  that  constraints.  52  6) s u b s t a n t i a l i m p r o v e m e n t s .2M  minimal  explicitly,  a r e r e a l i z e d by g e n e r a t i n g  covering both  the  constraints number  of  at  SC  at least  each  problems  iteration; solved  to  o p t i m a l i t y a n d t h e o v e r a l l CPU t i m e a r e r e d u c e d . Table  I V shows  that  7) P P p r o b l e m s w i t h Table  V shows  8) t h e  SC  Table  problems  become  more  difficult  to solve  t o 30; h o w e v e r , t h e number o f SC  to  be  P.  that  "weighting  approximate  factor"  improves  procedures  significantly, covering  i fP i s  problems  t o o p t i m a l i t y a p p e a r s t o grow l i n e a r l y w i t h  V I shows  9) t h e  to solve.  that  increased solved  larger E are easier  for  the overall  in  the  the  effectiveness  SC  problem;  of more  performance o f the accelerated  relaxation algorithm  improvement  the  improves even i f only a  effectiveness  of  the  small  approximate  p r o c e d u r e s f o r t h e SC p r o b l e m i s o b t a i n e d .  In summary,  a l l three  performance o f the covering best  accelerated  70%  less  CPU  covering  modifications  relaxation approach.  relaxation  time and s o l v e s  method,  roughly  2. i l l u s t r a t e s  the  r e l a x a t i o n approach has been be  expected  employed  i f more  to solve  extent  improved.  effective  improved  the  METHOD V A , t h e  requires  roughly  70% f e w e r SC p r o b l e m s t o  o p t i m a l i t y t h a n METHOD I , t h e b a s i c c o v e r i n g Figure  have  to  relaxation which  Further  approximate  t h e SC p r o b l e m , s e e (9) a b o v e .  the  method. covering  improvements c a n procedures  are  Table I :  METHOD I  mxn  30x30  40x40  alpha = 0.5, E = 5.  2 5 8 11 14 17 20 2 5 8 11 14 17 20  CPU  OPT.  0.1 0.3 1.1 2.0 2.6 8.1 10.0 0.2 3.8 11.8 21.3 44.2 71.6 84.7  1 2 4 5 6 10 10.9  ~o~  3.2 5.0 5.9 8.5 10.3 11.5  HEUR.  METHOD I I COVERS  11.6 18.7 27.9 37.8 50.2 78.9 76.7 16.8 25.4 40.2 50.4 70.7 100.6 99.1  METHOD I I I  CPU  OPT.  HEUR.  COVERS  CPU  OPT.  HEUR.  0.1 0.3 0.9 1.2 1.8 5.5 6.2 0.3 3.2 6.8 9.7 27.0 38.1 45.3  1.0 1.1 1.6 1.5 1.6 3.1 3.2 1.0 1.1 1.6 1.6 3.2 3.5 4.0  1.0 2.6 5.1 6.0 7.0 12.3 12.0 1.0 3.5 6.0 7.4 9.6 13.2 14.6  11.6 19.1 28.4 38.4 52.0 78.6 78.7 16.8 25.8 41.9 51.8 76.8 109.9 106.1  0.1 0.3 0.7 1.0 1.6 5.3 5.4 0.3 2.0 4.4 6.6 18.7 38.0 41.5  1.0 1.1 1.3 1.1 1.7 2.8 2.9 1.1 1.0 1.3 1.4 2.5 3.5 3.8  1.0 2.0  1 2, 3, 5, 8. 11. 11.  COVERS 10.4 17.7 25.0 36.4 43.4 67.9 70.9 14.3 23.1 36.1 46.5 67.6 99.8 93.9  Table I I :  mxn  30x30  40x40  a l p h a = 0.5, E = 5.  P  CPU  METHOD III OPT. HEUR. COVERS DENSITY - CPU  METHOD IV OPT. HEUR. COVERS DENSITY  CPU  METHOD IV A OPT. HEUR. COVERS DENSITY  CPU  METHOD V OPT. HEUR. COVERS DENSITY  2 5 8 11 14 17 20 2 5 8 11 14 17 20  0.1 0.3 0.7 1.0 1.6 5.3 5.4 0.3 2.0 4.4 6.6 18.7 38.0 41.5  1.0 1.1 1.3 1.1 1.7 2.8 2.9 1.1 1.0 1.3 1.4 2.5 3.5 3.8  1.0 1.0 1.1 1.7 1.3 3.6 1.1 4.3 1.4 4.1 2.3 7.2 2.9 6.9 1.1 1.2 1.1 2.1 1.3 3.9 1.4 5.1 2.9 7.7 2.7 8.3 3.6 9.3  0.1 0.3 0.7 0.8 1.1 4.2 4.2 0.3 2.0 4.5 6.5 19.0 28.2 34.8  1.0 1.0 1.1 1.7 1.3 3.6 1.1 4.3 1.4 4.1 2.3 7.2 2.7 6.9 1.1 1.2 1.1 2.1 1.3 3.9 1.4 5.1 2.9 7.7 2.7 8.3 3.6 9.4  0.1 0.3 0.7 0.8 1.1 3.6 3.8 0.3 1.9 4.5 5.8 11.6 30.2 32.2  1.0 1.1 1.3 1.1 1.5 2.6 2.8 1.1 1.1 1.3 1.3 2.8 3.6 3.8  1.0 10.4 2.0 17.7 3.9 25.0 4.7 36.4 4.8 43.4 9.1 67.9 9.5 70.9 1.2 14.3 2.2 23.1 3.8 36.1 5.0 46.5 8.0 67.6 11.0 99.8 11.3 93.9  0.09 0.13 0.17 0.21 0.23 0.29 0.31 0.07 0.10 0.14 0.16 0.19 0.24 0.25  0.1 0.3 0.7 0.8 1.1 4.2 4.4 0.3 2.0 4.6 6.5 19.0 28.1 34.3  10.4 17.9 25.4 36.7 45.6 69.1 66.9 14.3 23.3 37.8 45.9 69.1 95.0 93.5  0.09 0.13 0.16 0.21 0.23 0.28 0.30 0.07 0.10 0.13 0.16 0.19 0.23 0.24  10.4 17.9 25.4 36.7 45.6 69.1 66.7 14.3 23.3 37.8 45.9 69.1 95.0 94.9  0.09 0.13 0.16 0.21 0.23 0.28 0.30 0.07 0.10 0.13 0.16 0.19 0.23 0.24  1.0 1.8 3.6 4.6 4.1 7.9 7.2 1.2 2.1 4.0 4.5 6.2 8.7 9.4  10.3 18.0 25.2 36.9 42.5 62.0 63.9 14.3 23.3 37.9 44.4 61.0 85.1 86.8  0.09 0.13 0.16 0.20 0.22 0.26 0 28 0.07 0.10 0.13 0.16 0.18 0.21 0.22  Table I I I : a l p h a = 0.5, E = 5.  METHOD V mxn  P  2 5 8 30x30 11 14 17 20 2 . 5 8 40x40 11 14 17 20  CPU  OPT.  0.1 0.3 0.7 0.8 1.1 3.6 3.8 0.3 1.9 4.5 5.8 11.6 30.2 32.2  1.0 1.1 1.3 1.1 1.5 2.6 2.8 1.1 1.1 1.3 1.3 2.8 3.6 3.8  HEUR 1 .0 1.8 3.6 4.6 4.1 7.9 7.2 1.2 2.1 4.0 4.5 6.2 8.7 9.4  COVERS 10.4 18.0 25.2 36.9 42.5 62.0 63.9 14.3 23.3 37.9 44.4 61 .0 85.1 86.8  METHOD V A DENSITY 0.09 0.13 0.16 0.20 0.22 0.26 0.28 0.07 0.10 0.13 0.16 0.18 0.21 0.22  CPU  OPT.  0.1 0.3 0.6 0.8 1.1 2.1 2 .6 0.3 2.0 4.8 7.2 13.6 24.0 25.8  1.0 1.1 1.1 1.1 1.3 2.4 2.2 1.1 1.1 1.3 1.5 2.4 2.9 3.0  HEUR.  COVERS  1.0 1.7 3.1 3.6 3.6 7.1 6.7 1.2 2.1 3.6 5.1 6.0 8.5 8.9  10.4 17.7 26.2 37.6 44.6 66.7 67.5 14.3 23.4 39.4 49.8 70.4 98.1 100.9  DENSITY 0.09 0.13 0.16 0.21 0.22 0.27 0.28 0.07 0.10 0.14 0.16 0.18 0.22 0.23  Table IV:  METHOD VA mxn  30x30  40x40  alpha = 0.5.  E = 1  METHOD VA  CPU  OPT.  HEUR.  5 8 11 14 17 20  0.2 0.4 0.9 5.6 8.7 22.9  1.1 1.2 1.3 2.9 3.6 3.8  1.6 2.5 4.0 9.4 12.5 19.5  11.9 24.9 48.2 88.8 111.8 174.2  0.07 0.09 0.11 0.13 0.14 0.16  5 8 11 14 17 20  0.3 1.4 6.4 24.1 52.7* +  1.0 1.2 1.3 2.0 4.3* +  1.4 2.7 4.4 8.5 12.8* +  17.3 36.6 63.7 119.6 164.3* +  0.05 0.06 0.08 0.10 0.12* +  P  COVERS  DENSITY  CPU  OPT.  HEUR.  COVERS  0.3 0.6 0.8 1.1 2.1 2.6  1.1 1.1 1.1 1.3 2.4 2.2  1.7 3.1 3.6 3.6 7.1 6.7  17.7 26.2 37.6 44.6 66.7 67.5  2.0 4.8 7.2 13.6 24.0 25.8  1.1 1.3 1.5 2.4 2.9 3.0  2.1 3.6 5.1 6.0 8.5 8.9  23.4 39.4 49.8 70.4 98.1 100.9  * In two o f the ten runs the optimal s o l u t i o n was not obtained a f t e r 150 seconds o f CPU time. + No attempt was made to s o l v e these problems.  E =5  METHOD VA DENSITY  The average  E = 9  CPU  OPT.  HEUR.  COVERS  DENSITY  0.13 0.16 0.21 0.22 0.27 0.28  0.2 0.3 0.4 0.5 0.7 0.8  1.2 1.0 1.2 1.3 1.4 1.4  1.8 2.0 3.0 3.3 3.3 4.0  16.8 19.6 26.3 28.6 31.2 40.8  0.17 0.22 0.26 0.30 0.31 0.37  0.10 0.14 0.16 0.18 0.22 0.23  0.5 1.1 2.3 1.7 3.2 2.7  1.1 1.3 1.4 1.3 2.3 2.1  1.8 2.5 3.5 4.0 4.4 5.5  19.8 26.7 35.6 39.1 46.5 60.1  0.14 0.17 0.21 0.25 0.27 0.32  i s o f the other e i g h t runs.  Table V:  mxn  P CPU  30x30  40x40  alpha = 0.5, E = 5.  2 5 8 11 14 17 20 23 26 30 2 5 8 11 14 17 20 23 26 30  0 .1 0 .3 0 .6 0 .8 1 .1 2 1 2 6 3 1 7 7 14 3 0. 3 2. 0 4. 8 7. 2 13. 6 24. 0 25. 8 31. 7 63. 8 64. 2  OPT. • 1.0 1.1 1.1 1.1 1.3 2.4 2.2 3.1 4.6 4.4 1.1 1.1 1.3 1.5 2.4 2.9 3.0 3.7 5.2 4.8  METHOD V A HEUR. COVERS " 1.0 1.7 3.1 3.6 3.6 7.1 6.7 8.5 11.2 13.1 1.2 2.1 3.6 5.1 6.0 8.5 8.9 10.3 13.2 14.7  10.4 17.7 26.2 37.6 44.6 66.7 67.5 70.7 95.5 103.0 14.3 23.4 39.4 49.8 70.4 98.1 100.9 108.0 148.6 142.6  DENSITY 0.09 0.13 0.16 0.21 0.22 0.27 0.28 0.29 0.32 0.36 0.07 0.10 0.14 0.16 0.18 0.22 0.23 0.25 0.27 + 0.31 +  + In one o f t h e t e n runs t h e o p t i m a l s o l u t i o n s was not o b t a i n e d a f t e r 200 seconds o f CPU time. The average i s o f t h e o t h e r n i n e runs.  Table  VI:  a l p h a = 0.5.  Method VA CPU  OPT.  HEUR.  2 5 8 11 14 17 20  0.1 0.3 0.6 0.8 1.1 2.1 2.6  1.0 1.1 1.1 1.1 1.3 2.4 2.2  1.0 1.7 3.1 3.6 3.6 7.1 6.7  10 17 26 37 44 66 67  2 5 8 11 14 17 20  0.3 2.0 4.8 7.2 13.6 24.0 25.8  1.1 1.1 1.3 1.5 2.4 2.9 3.0  1 .2 2 .1 3 6 5 1 6 0 8 5 8 9  14.3 23.4 39.4 49.8 70.4 98.1 100.9  mxn  30x30  40x40  COVERS .4 7 2 6 6 7 5  Method VAA EFFECTIVENESS  CPU  OPT.  99.5 99.5 98.5 98.7 98.7 98.5  0.1 0.3 0.7 0.8 1.1 2.2 2.6  1.0 1.1 1.4 1.3 1.6 2.5 2.5  1.0 1.9 3.4 3.7 3.8 7.6 7.2  10.4 18.0 26.8 36.5 46.9 69.0 68.6  99.8 99.7 98.7 98.9 98.3 98.7 98.8  0.3 2.1 4.8 9.0 20.6 25.9 33.9  1.1 1.1 1.4 1.7 3.4 3.0 3.4  1.2 2.4 4.1 4.5 7.3 9.3 10.6  14.3 23.8 40.8 48.2 72.9 98.1 110.0  99.9  HEUR.  COVERS  EFFECTIVENESS] 99.6 99.2 99.3 98.4 98.3 98.1  97.6 99, 99 98. 98. 98. 98. 98.  Figure  1.  CPU Time Use  60  F i g u r e 2. N = 40,  Method I  vs  Method VA  M =40, E = 5, a l p h a = 0.5.  10  S  5  Dots f o r Method I , P l u s s e s f o r Method VA. Data  o b t a i n e d from t a b l e s I and V.  P  61  8. B i b l i o g r a p h y 1. E . B a l a s a n d A . Ho, " S e t C o v e r i n g A l g o r i t h m s U s i n g C u t t i n g P l a n e s , H e u r i s t i c s and S u b g r a d i e n t O p t i m i z a t i o n : A C o m p u t a t i o n a l S t u d y " , WP No. 6 - 7 9 - 8 0 , G S I A , J u l y 1 9 7 9 . 2. E . B a l a s a n d R. J e r o s l o w , " C a n o n i c a l C u t s o n t h e U n i t H y p e r p l a n e " , MSR r e p o r t No. 1 9 6 ( R ) , C a r n e g i e M e l l o n U n i v e r s i t y , August-December 1969, r e v i s e d F e b r u a r y 1971. 3. E . B a l a s a n d C. H. M a r t i n , " P i v o t a n d C o m p l e m e n t - A H e u r i s t i c f o r 0-1 P r o g r a m m i n g " , MSR r e p o r t N o . 4 1 4 , C a r n e g i e M e l l o n U n i v e r s i t y , F e b r u a r y 1978. 4. H. P. C r o w d e r , R. S. Dembo a n d J . M. M u l v e y , " R e p o r t i n g Computational Experiments i n Mathematical Programming", M a t h e m a t i c a l P r o g r a m m i n g , V o l . 15 ( 1 9 7 8 ) , p p . 3 1 6 - 3 2 9 . 5. J . E t c h e b e r r y , " T h e S e t - C o v e r i n g P r o b l e m : A New I m p l i c i t E n u m e r a t i o n A l g o r i t h m " , O p e r a t i o n s R e s e a r c h , V o l . 25 (1977), pp. 760-772. 6. B. F a a l a n d a n d F . S. H i l l i e r , " I n t e r i o r P a t h M e t h o d s f o r H e u r i s t i c Integer Programming Procedures", O p e r a t i o n s R e s e a r c h , V o l . 27 ( 1 9 7 9 ) , p p . 1 0 6 9 - 1 0 8 7 . 7. R. S. G a r f i n k e l a n d G. L . N e m h a u s e r , W i l e y 1972.  Integer  Programming,  8. F . G l o v e r a n d E . W o o l s e y , " F u r t h e r R e d u c t i o n o f 0-1 P o l y n o m i a l P r o g r a m m i n g P r o b l e m s t o 0-1 L i n e a r P r o g r a m m i n g P r o b l e m s " , O p e r a t i o n s R e s e a r c h , V o l . 21 ( 1 9 7 3 ) , p p . 1 4 1 - 1 6 1 . 9. F . G l o v e r a n d E . W o o l s e y , " C o n v e r t i n g t h e 0-1 P r o g r a m m i n g P r o b l e m t o a 0-1 L i n e a r P r o g r a m " , R e s e a r c h , V o l . 22 ( 1 9 7 4 ) , p p . 1 8 0 - 1 8 2 .  Polynomial Operations  1 0 . D. G r a n o t , F . G r a n o t a n d J . K a l l b e r g , " C o v e r i n g R e l a x a t i o n f o r P o s i t i v e 0-1 P o l y n o m i a l P r o g r a m m i n g Problems", M a n a g e m e n t S c i e n c e V o l . 25, No. 3 ( 1 9 7 9 ) , p p . 264-273. 1 1 . D. G r a n o t a n d F . G r a n o t , " G e n e r a l i z e d C o v e r i n g R e l a x a t i o n i n 0-1 P r o g r a m m i n g " , WP No. 5 3 3 , F a c u l t y o f C o m m e r c e a n d Business A d m i n i s t r a t i o n , U n i v e r s i t y of B r i t i s h Columbia, December 1977. (Operations Research, forthcoming) 1 2 . D. G r a n o t a n d F . G r a n o t , "On U s i n g H e u r i s t i c s i n B e n d e r s P a r t i t i o n i n g P r o c e d u r e : I T h e L i n e a r C a s e " , WP No. 6 3 6 , F a c u l t y o f Commerce and B u s i n e s s A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h Columbia, A u g u s t 1979.  62 1 3 . F . G r a n o t , " E f f i c i e n t H e u r i s t i c A l g o r i t h m s f o r P o s i t i v e 0-1 P o l y n o m i a l p r o g r a m m i n g p r o b l e m s " , WP N o . 5 9 5 , F a c u l t y o f Commerce and B u s i n e s s A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h Columbia, August 1978. 14. F . G r a n o t a n d P. L . Hammer, "On t h e U s e o f B o o l e a n F u n c t i o n s i n 0-1 P r o g r a m m i n g " , M e t h o d s f o r O p e r a t i o n s R e s e a r c h , X I I (1977), p p . 154-184. 1 5 . F . G r a n o t a n d P. L . Hammer, "On t h e R o l e o f G e n e r a l i z e d C o v e r i n g Problems", C a h i e r s du Centre D'Etudes de Recherche O p e r a t i o n e l l e , V o l . 17 ( 1 9 7 5 ) , p p . 2 7 5 - 2 8 9 . 1 6 . J . S. G r a v e s , "On t h e S t o r a g e a n d H a n d l i n g o f B i n a r y D a t a U s i n g FORTRAN w i t h A p p l i c a t i o n s t o I n t e g e r P r o g r a m m i n g " , O p e r a t i o n s R e s e a r c h , V o l . 27 ( 1 9 7 9 ) , p p . 5 3 4 - 5 4 7 . 1 7 . P. L . Hammer a n d S. R u d e n e a n u , B o o l e a n M e t h o d s I n O p e r a t i o n s Research and R e l a t e d Areas, S p r i n g e r V e r l a g , 1967. 1 8 . M. H e l d , P. W o l f e a n d H. C r o w d e r , " V a l i d a t i o n o f S u b g r a d i e n t O p t i m i z a t i o n " , Mathematical Programming, V o l . 6 (1974), pp. 68-88. 1 9 . G.A. K o c k e n b e r g , B . A . M c c o i l a n d F . P. Wyman, "A H e u r i s t i c for General Integer Programming", D e c i s i o n S c i e n c e s , V o l . 5 (1974), p p . 26-44. 2 0 . R. L o u l o u a n d E . M i c h a e l i d e s , "New G r e e d y - l i k e H e u r i s t i c s f o r t h e M u l t i d i m e n s i o n a l 0-1 K n a p s a c k P r o b l e m " , O p e r a t i o n s R e s e a r c h , V o l . 27 ( 1 9 7 9 ) , p p . 1 1 0 1 - 1 1 1 4 . 2 1 . G. O r o n , " O p t i m i z i n g I r r i g a t i o n S y s t e m D e s i g n " , Ph.D. d i s s e r t a t i o n , A g . E n g . D e p t . , T e c h n i o n H a i f a ,  (1975).  2 2 . D. E . P e t e r s o n a n d D. L a u g h h u n n , " C a p i t a l E x p e n d i t u r e P r o g r a m m i n g a n d Some A l t e r n a t i v e A p p r o a c h e s t o R i s k " , M a n a g e m e n t S c i e n c e , V o l . 17 ( 1 9 7 1 ) , p p . 3 2 0 - 3 3 6 . 23. A. P r i t s k e r , L . J . W a t t e r s a n d F . W o l f e , " M u l t i p r o j e c t S c h e d u l i n g With L i m i t e d Resources: A Zero-One Programming A p p r o a c h " , M a n a g e m e n t S c i e n c e , V o l . 16 ( 1 9 6 9 ) , p p . 9 3 - 1 0 8 . 24. M. R. R a o , " C l u s t e r A n a l y s i s a n d M a t h e m a t i c a l P r o g r a m m i n g " , J o u r n a l o f t h e A m e r i c a n S t a t i s t i c a l A s s o c i a t i o n , V o l . 66 (1971), pp. 622-626. 2 5 . S. S e n j i u a n d Y. T o y o d a , "An A p p r o a c h t o L i n e a r P r o g r a m m i n g w i t h 0-1 V a r i a b l e s " , M a n a g e m e n t S c i e n c e , V o l . 15 ( 1 9 6 8 ) , p p . B196-207. 2 6 . H. A . T a h a , "A B a l a s i a n - B a s e d A l g o r i t h m f o r Z e r o - O n e p o l y n o m i a l p r o g r a m m i n g " , M a n a g e m e n t S c i e n c e , V o l . 18 pp. B398-343.  (1969),  63  27.  H. A. T a h a , " F u r t h e r I m p r o v e m e n t s i n t h e P o l y n o m i a l A l g o r i t h m " , M a n a g e m e n t S c i e n c e , V o l . 19 ( 1 9 7 2 ) , pp. B196-227.  Zero-One  28. Y. T o y o d a , "A S i m p l i f i e d a l g o r i t h m f o r O b t a i n i n g A p p r o x i m a t e S o l u t i o n s t o 0-1 P r o g r a m m i n g P r o b l e m s " , M a n a g e m e n t S c i e n c e , V o l . 21 ( 1 9 7 5 ) , p p . 1417-1427. 29.  L. J . W a t t e r s , " R e d u c t i o n o f I n t e g e r P o l y n o m i a l P r o b l e m s t o Zero-One L i n e a r Programming Problems", Operations Research, V o l . 15 ( 1 9 6 7 ) , p p . 1171-1174.  64  9. A p p e n d i x ; T h r e e B e n c h m a r k P P  This positive these  appendix  provides  0-1 p o l y n o m i a l  problems  will  complete  programming serve  as benchmarks  t h r e e p r o b l e m s were s o l v e d by Method  In  each  optimality. provided how  a  single  this  appendix.  faster  sophisticated  these  three  I s i s hoped  that  VA  (see  research.  section  7.3).  CR p r o b l e m h a d t o b e s o l v e d t o  I t would  CR  of  for future  T h e s p e c i f i c a t i o n s o f t h e s e CR  in  much  only  descriptions  problems.  All  case,  Problems  problems  problems  are  also  be v a l u a b l e t o d e t e r m i n e can  be  solved  by  a  a l g o r i t h m f o r t h e SC p r o b l e m .  Problem  Parameters  N  M  P  E  alpha  I  40  40  8  5  0.5  II  40  40  14  5  0.5  III  40  40  20  5  0.5  Performance CPU I  CR-CPU  OPT  1  HEUR C O V E R S D E N S I T Y  2.5  2.2  1  3  39  0.15  II  17.4  16.4  1  8  79  0.19  III  35.7  34.2  1  9  127  0.25  An e x a m p l e specifing  will  be u s e d t o d e m o n s t r a t e t h e n o t a t i o n e m p l o y e d f o r  t h e t h r e e benchmark  problems.  Consider  t h e f o l l o w i n g PP a n d CR p r o b l e m s :  Max  2xi + 5x  + 5x3 + 6x4 + IOX5  2  st 3x^ + 2 x x 2  2x l l x  Min  3  < 4  + 2x3X4 < 2  5  l 2 x  +  5 x  2yi + 5 y  4  +  2 x  5 -  + 5y  2  1 3  '  +6y4 + 1 0 x  3  5  st y i  + y  2  + y Y3  y  1  + Y  Yl +  2  +  Y  4  +  Y  4  Y2  +  SC  Constraints  2(2 3) < 4  2(5)  2(3 4) < 2  11(1  2) 5 ( 4 ) 2(5)  11100 00111 11010 11001  Y5 - !•  Function Coefficients  3(1)  Problem  1  be s p e c i f i e d a s f o l l o w s  2 5 5 6 10 Polynomial  Y5 ^  ^1 +  These problems w i l l  Objective  > 1  3  <  13  66  PROBLEM I Objective  Function  Coefficients  8 15 25 33 35 43 45 53 57 59 65 69 77 80 82 92 100 109 110 119 120 121 121 124 124 124 130 139 145 155 161 168 174 184 192 200 210 220 226 227 Polynomial  Constraints  19(24) 19(36 33) 15(40) 10(24 9 1) 5(6) 2(25 17)  <  35  15(38 3 2) 15(27 14 8 5) 15(2) 14(29 21 6) 10(21 17 16 4) 8(31 25 22) < 38 19(37  18) 17(15 14) 10(14) 9(8) 8(29 28 27 16)  <  31  19(11) 17(33 31 24 22) 12(29) 8(20 8 1) 6(38 19 10 8 1) 3(27 25 14 7) < 32 1(11 9 5)  <  0  19(21 11) 19(10 2) 16(22 16 9) 12(36 18 13 10) 11(39 35 17 7) 4(22 17) < 40 14(27  26 18 10 1)  <  7  17(32 10(37  23 18 13 8) 17(30 28) 14(40 7) 13(36 34 20 8) 28 16 15 13) 6(17 14 9) < 38  16(35  19 6) 1(11 8 2)  <  8  20(39 24 13) 17(36 10 6 1) 13(26 4 3) 11(31) 11(40 33 27) 3(33 14 8) 1(32 11) < 38 16(27 13 12 11 2) 15(22 17 14 2) 8(37 10) 8(39 26) 7(36 28 5) 5(36 29 27) < 29 16(28 27 5 2) 15(33 20 18 5 1) 14(36 20 15)  <  22  15(37 26 10) 12(37 25 24 21 4) 10(34) 5(5) 4(34 31 30 26) < 23 14(29 28 27) 14(9 2) 14(19 13 10 1) 13(23) 9(29 8 4) 6(36 30 28 18 5) 6(38) < 38 17(23) 11(39 31 26 21)  <  14  19(31 16 12) 17(24 15 10 3) 17(7) 16(35 33 21 20 17) 12(39 8) 10(19 17) 3(21 17 5) < 47 18(29 6) 15(18 12 11 7 1) 15(38 37 31 7 4) 13(34 32 3) 12(26 22 11) 10(33 15) 7(40 27 26 16) 2(29) < 46  67  17(27 26) 13(30 12 6) 11(9) 9(23 15 7) 1(40 28 22 17 16) <  25  18(23 11) 11(40 19 10 4 2) 9(32 3) 3(35 25 16 2)  <  20  11(32 28 23) < 5 19(34 28 20) 18(35 29 27 19 9) 10(32 22 4) 9(11) 4(36 28 24 9 6) 2(23 11) < 31 15(36 9 8) 6(9)  <  <  7  3  16(24) 16(40 35 23) 14(36 25 16 9) 13(36 14) 12(35 21 14) 12(39 35 10) 6(21 20 1) < 44 18(39 27 16)  <  8(32 23 15 12)  9 <  4  20(16) 16(35 32 28 26) 9(31 15 7) 3(12)  <  24  18 (31 25 19) 18(33 22 20 17 15) 17(40 26 16 3) 14(28 24 19 13) 13(33 2 1) 10(33 14 5) 8(27) 1(35) < 49 20(30) 12(34 33 30 19 14) 10(29 20 14 6) 3(33 17) 2(38 20 9) < 23 20(36 34 7) 1(12 11)  <  10  20(40 35 16 14 11) 20(28 1) 11(34 1) 9(29 20) 5(39 38 35 27 1) 4(13 8 4) 4(39 36 20) 1(34 27 12 10 2) < 37 20(32 3) 19(36 25 23 18 10) 19(18 17 14 1) 8(26 24 14 8) 3(34 30 29 2) 17(36 33)  <  <  <  29  5  8  17(18 17 3) 16(39 29 14 12) 9(7) 14(36 33 32 24 18) 11(17) 15(40 17) 11(25 23 1)  <  <  <  21  12  13  19(34 25 24) 12(39 34 23 13 7) 10(19) 7(33 15 10) 6(9) 5(27) 1(38 27 16 13 6) < 30 20(38 17) 18(34 26) 15(29) 10(30 27 18 7 1) 8(26 23 9) 4(36 27 23 12 4) 3(15 13 7) < 39 17 (27 26 25 14) 12(23 20) 11(33 28 23 20 3) 10 (33 16 5) 10(38 36 16 1) < 30  68  Solutions Approx. s o l u t i o n : 0010100100 1110100111 1100111111 1101111111 Value o f approximation: 3590 Optimal s o l u t i o n : 0010100100 1110100101 1101111111 1101111111 Value of o p t i m a l : 3604 F i n a l CR Problem Solved t o O p t i m a l i t y 1000000000 1000000100 0100100000 0100100000 0001000000 0000010000 0000010000 0000001000 0000001000 0000000001 0000000100 0000000100 0000000000 0000000000 0000000000 0000000100 0000000100 0000000000 0000000000 0000000000 0000000000 0000001000 0000001100 0000000001 0001100000 0000001000 0111000001 0000001000 1000000001 0000000000 0001000001 0000000000 0011000000 1000000001 1100100000 0100000001 0000100000 1100100000 1100000000  0000000001 1000000001 0000100001 1110000000 1000000001 0000000010 0100000000 0000000000 0000100000 0000000000 0001100000 0001000100 0001100100 0000010000 0000010000 0000010100 0010110001 0000001000 0000001000 0000000010 0000000000 0000110000 0100010000 0000100010 0000000000 0010110000 0000010010 0101000000 0000000100 1000000000 0000000000 0010000000 0010000000 0001000001 0000000101 1110000000 0011000010 0001000010 0010000010  0000000110 0000000010 0000001100 0000011100 0100000100 0000000000 0000011001 0000000000 0000010100 0000010000 0000000000 0000000000 0000000000 0000001000 0000010100 0000001110 0000000101 0000000000 0000010010 0001101000 0000000000 0000000000 0000000000 0001100000 1001100000 0000000101 0000100000 0000000010 0000011000 0101000000 1001110000 0001001000 0001010000 1001000000 0000001100 0000011000 0001101100 0000101000 0001101100  0001000000 0000000000 0000010000 0000010010 0101000000 0000100000 0000000000 0001010000 1100100000 0001001000 0000000000 0000001000 0000001000 0000000010 0100100000 0000001000 0001011000 0000000001 0001000100 0001000000 0010010000 1000000000 1000000010 0011000000 0001001000 0000001001 0100100001 0000000010 0000000000 1010000000 0000001000 1010000011 1000000010 0000100010 0010000000 0000001010 1010000000 1010100000 1010000000  69  PROBLEM I I Objective  Function  Coefficients  6 11 20 28 31 38 47 47 52 57 62 65 69 75 76 85 87 97 98 104 104 111 114 117 123 128 133 143 151 157 165 171 176 186 194 203 209 218 218 226 Polynomial  Constraints  17(35 16) 16(39 22 17 13 7) 13(23 17) 9(25 19 2)  <  27  15(25 23 19 9) 13(18 8 3) 8(27 1) 8(6) 5(9) 5(24 21 19 3) 4(30 29 2) 2(28 23 11 9) 2(5) 1(37 36 18 8) < 31 19(36 29 15 8 1) 19(22) 19(32 31 25 13 7) 17(28) 12(25 10) 11(38 17 16 6) 10(37 35 9 2) 5(40 36 21) 4(1) 4(22) 3(40 16 6 5) 3(25) 3(39 30) < 64 20(29) 20(36 21 15 4) 18(35 28 17) 13(32 9 6) 13(33) 11(38 22) 10(36 16 12 5 3) 9(34 15 3) 9(29) 6(35 28 26 21 10) 3(38) 3(30 25 22 15) 1(32 28 10 2) < 68 11(31 14 11 2) 5(37 31 19) 4(35 28 21 11 6)  <  10  20(14 11) 20(20 13 11 5) 18(20 16 13) 17(36 10 7 3) 12(39 34 30 26 19) 11(40 17 15) 9(35 11) 9(40 39 4 3) 8(25) 2(4) 2(38 35 33 26 4) 1(40 11 3 2) < 64 17(28) 15(35 19) 13(16 5) 10(5) 8(38 26 24 23 5) 2(40 36 24) 2(27) < 33 17(24) 14(39 22 10 6) 12(17 2) 11(26 12) 11(31 21 15) 10(18 1) 8(15 10) 8(39 36 33 26 6) 3(32 19 17 11) 2(9 2) 2(8 5) 1(35 28 16 12) < 49 18(34 12) 11(38 32 29 9 4) 11(9) 9(21 20 4 3) 6(29 4) 3(39 27 21 17 8) 2(35 24 23 13 6) 2(32 23 18 14 3) 2(37 31 25 23 7) 2(34 10) 1(39) < 33 20(17 8) 15(29 12 10 7 6) 13(37 29 26 13) 11(23 17 1) 8(19) 7(25 21 19 10) 7(10) 2(40 33 7) < 41 20(26 7) 10(32) 4(40 34 32 15 5)  <  17  16(16 8 5) 16(34 23 15 12) 14(33 22 17 12 1) 10(24) 10(29 15) 10(32 29 23 7) 10(37 25 15 12 6) 10(39 38 17 7) 9(28 17 6) 7(39) 4(27 26 8) < 58 17(40) 15(36 33 29 17) 12(38 32 31) 9(21 16 11) 3(40 28 26 17) 3(14 8 7) 2(35 11 7) < 30 11(38 28 19 11) 7(33 31 10 2) 3(33 24 22 19)  <  10  70  18(37 20 13) 17(7) 17(22) 13(37 31 30) 12(5) 11(12 11 6) 9(37) 7(35 19 11) 5(38 28) 4(33 24) 3(37 35 22 14) 3(38 16 15) 3(32 30 23 17 12) < 61 20(19) 18(38 36 34 33 16) 12(25) 4(23 16) 1(39 31 9)  <  27  14(30 21 12) 10(25 22 13 5 2) 6(39 36 12 7) 3(40 24 16 10 5) < 16 18(38 4) 16(40 27 25 17) 14(39 24 20 12 3) 12(39 13)  <  30  20(39) 17(39 32 28 21) 17(40 37 34) 15(40 39 28 2) 12(33 14 12 7) 10(32 29) 9(26 15) 5(32 29 10 9) 1(24 22) < 53 19(9) 19(39 37 33) 12(8 6) 2(34 30 29 22) 1(34 28 5 2 1) < 26 19(25 13 7) 12(19 18 9) 12(1) 2(30 24 5)  <  22  18(38 24) 16(40 15) 10(30 17 9) 6(36 32 19 6) 5(24 14) 5(26) 2(39 32 30 23 18) 1(23 22) < 31 18(36 31 20 19 18) 16(37 24 12) 11(39 33 19 3) 10(37) 9 (40 37 19 4 1) 7(38 35 24 20) 6(40) 4(38 30 24 8) 3(13 6) < 42 20(37 29 22 11) 20(13 7 6 4) 20(36 34 33 28 20) 18(20 16) 14(38 27 23 13 10) 11(36 2) 10(28 23 20) 9(32 11 1) 3(32 19 17 7 6) 1(36) < 63 20(9 6) 12(34) 11(28 10 9) 10(34 26 14 1) 7(9) 6(40 14) 4(40 29) 4(24) 1(24 6 3) 1(34 30 22 12) < 38 19(12) 19(36 28 15) 16(12 6 3) 12(35 34) 12(25 19 16 3) 9(40 39 36 8) 8(22 2) < 47 17(20 12) 16(40 24 16 3) 16(12) 16(19) 12(35 34 28 7) 10(40 27 26 11) 9(39) 8(34 6) 8(18 6 5) 2(37 36 30 24) 1(39 35 22 3) 1(39 22 14 8 4) < 58 9(33 21 19) 5(22 12)  <  7  20(31 29 28 16 11) 18(24) 17(20) 14(35 25 24 14 10) 13(38 36 12) 12(38 36 29 15) 12(32) 10(28 25 13) 10(29 14 6) 6(30) 2(28) 1(13) 1(6) 1(19 14) < 68 20(30 17 8 4) 19(26 13 8 4) 19(30 13) 18(20) 18(22) 16(18 16) 12(29 27 18 14) 12(32 31 25 13) 10(38 12) 8(38 30 12 4) 7(28) 7(23) 3(40 39 31 19) < 84 19(11) 3(32 31 27 5 4)  <  11  20(12) 15(33 13 7) 14(24) 8(39 36 5) 7(35 12) 7(33 30 27 3 1)  7(34  30 26 21 4) 4(35 25 9 6) 1(20)  <  41  19(27) 18(22) 17(38 25) 16(25 14) 16(31 30 29) 12(29) 11(28 23 21 5) 11(24) 8(24 5 1) 7(13) 5(33 10) 5(18 13 7) 4(39 27 26 19 15) 1(36 13 10) < 75 18(37 4) 16(28 8 2) 15(29) 14(18 12 1) 10(40 25 24 20 5) 9(29 27) 7(5) 1(29 21 10 7) < 45 19(35 11(33  31 25 19 12) 14(35 34 31 21 9) 12(30) 12(36 8 2) 32 28 27 11) 8(36 34 23 2) 4(34 29) 4(36 32 25) <  42  19(33 6) 14(37 34 27 13) 11(30 11 10) 11(24 19) 10(37) 5(30 18 7 6 3) 5(36 24 12 8 6) 3(19) < 39 18(25 20 18 5) 13(29) 13(36 26 22 1) 11(38 28 22 21) 7(13) 2(32 28) < 32 19(29 13(27  26 11) 19(36 16 14 7) 19(32 1) 17(38 37 35 28 27) 15 3 2) 4(6) 3(38 18 17 14 8) < 47  20(9) 18(20 19) 17(21 13 4 1) 12(30 21) 6(38 11) 2(38 23 12 2(39 23 16 14 4) < 38 18(31 19 8) 16(35 34 27 16 3) 13(31 26) 13(39 32 19) 11(37 18 16) 9(2) 8(31 30 9) 7(38 36 1) 2(35 22 14 2) 1(23 16 15 7) 1(36 32 30) < 49 Solutions Approx. s o l u t i o n : 001010010 1010110110 1111011100 11111111111 Value o f approximation: 3495 Optimal s o l u t i o n : 001010010 1010110110 1111011100 11111111111 Value o f o p t i m a l : 3495 F i n a l CR Problem Solved t o O p t i m a l i t y 1010100000 0100000100 0001000000 0001100000 0011000101 0000010100 0010010100 0010110000 0000010001 0000001000 0000001000 0000101000 0000001100 0000000010  0100000000 0100000000 0000001000 0100000000 0101001101 0000000000 0100000000 0100000101 0100100000 0000000000 0100000000 0000000000 0001000000 0000000000  0000001001 0100000000 0000101000 1000010001 1010001000 0000000000 0000000000 0100000000 1100010000 0000010000 1000000001 0100000001 0000000000 0000000000  0010110010 0001110011 0000000101 0001110010 0101000010 0010001010 0001110011 0001100010 1010010010 0000000000 0000010010 1000001000 1100000101 0010001010  0000000000 TTIIT00000 I O T O T O T I O O  0000000000 TTOTTOOTOO T O T O I O I I O O 0000000000 TOTOTOOTOO TOTOTOOTOO OOTOOOOOTO  OTOOOOOOOT  TOOOOOOOOO  OOIOOOTOOO OOIOOOTOOO OOIOOOTOOO OIOOOOTTOO  0000000000 0000000000 0000000000 OIIOIOOOOO OOOOOOTOOO  0000000000 0000000000 OIOOIOOOOO  OOIOTOOOIO TITOOTOOOO TOOOOIOITO 0000000000 OOOOTOOTOO OTOOOOOOOT OOOOIIOOIO OOOOOIIIOO OOIOTOOOIO TTOOOOOOOO TOOOOTIOIO OOOOTOOOOO IIOOOOOOTO OTTOOOOOOT 0000000000 OOOOOOOOTO OTOOOOOOTO OTTOTOOOOT OOOOOTOOOO 0000000000 OOTOOOOOOT TTOTOTOOOO OOOOOOTOOO 0000000000  OOOOTOOOOO 0010000000 OOOOOTOOTO OOOOTOOTOO 0000000000 OTOOOIOOOO TOTOOOOTOO OOOOOTOOOO 0001000000 OTOTOOOOOO 0000000000 OOOOOTTOOO  0000000000 0010000000 OOOOTOOOOO OOOOOTOOOO  TOOTIOOOOI 0000000000 TTTOOOOOOO 0000000000 TOOOIOOOIO TOTOTOOTOO 0000000000 TOTOTOOTTO TOOOOOOTOO  OOOOOOTOOT OOIOOOTOOO OOIOOOTOOO OOTOOOOOOO  OIOTOOOOIT OOIIOOOOOT TTOIOOTOIO  OOOOTOOOOO IOIOOOOOTO OTIOOOOOOO  OIIOIOOOOO  OTOOOOOOII TOOOTTOOOO  OOOOTOOOOO OOIOOOTOOO  OTOOOOOOOO  OOTOOOOOTO  OTOOOOOOOO OOTOTOTTOO 0000000000 OIOOIOOOOO OOOOOOOOOT OOOTOOOOOO OOOOTOOOOO  TTOIOOTOIO OTIOOOOOOO OIOOTOOOTO  0000000000 0000000000  0000000000 OOTOOOTOTO  TOOOOOOTOO 0000000000 0000000000 OOOOOOOOTO 0000000000 TOTOOOOTTO TOTOTOOTOO 0000000000  0000000000 0000000000  OOOOOOOTOO  OOOOOOOOOT  0000010000 OOIIOOOOOO OTOOOOOOOO TTOIOOTOIO OIOOIOOOOO OOOOOTOOOO OOTOOOOOOO OTOIOIOOTO OOOOOOTOOO IOOOTOOIOO OTOOOOOOOO OOOTOOOOOO  0000000000 0000000000 0000000000 0000000000  OOOTOOTOTO OOOOOOTOOO  OOOOOTOOOO OOOOOTOOOO  OOOTOOOOOO  0000000000  O O I T O I O O T T TOTOOOOTTO OOTOOOOOOO O O I I O I O T T T I O T O O O O O T I OOTOTOOOOO TTOIOOTOIO OOTOOOOOOT OOOOTIIOOO OOTOOOOOOO OOTOOOOOOO OOOIOITOTO OIOOIOOOOO OOOOOOTOOO TOTOOOOOOO OOOOOOTOOO OOOOOTOOOO OOOOOOTOOO  TTOITOOTOI OTOOOIOOOO 0000000100 0000000000  0000000000 0000000000 OOOOOTOOTO 0000000000 OOOOOOTOOO 0000000000 OOOOOOOOTO  OOOOOTOOOO  OOOOOTOOOO 0000000000 IOOOOOOOIO 0000000000  0000000000 TTTOOOOOOO OOOOOOOTOO 0000000010 OOOOOOOOOT IIOOOOOOTO OOOOOOOTOO OOOOOTOOOO OTOOOOOOOO 0000000000 OOTOTOTTOO OOOOOTOOOO OTOOOOOOOO 0000000000 OOOOOTOOOO OOOOOOOTOO OOOOTOOOOO 0000000000 OOOTTOOOOO 0000000000 0001000001 IOOOOOOOIO TOOOOOOTOO OOOOOTOOOO OOTOOOOOOO OOOTOTOOIO OOOOOOTTOO 0000000000  OIOOOOTOIO IIOOOOOOTO OIOOOOIOOO TOOOOOOOOO  OOOIOOOIOI IOOOTOOIOO OOOIOOOOOI TOOOIOOTIO  OOTTOOTOTO OOTTOIOOOO OOOTOOOOTO OOOTOIOOOO  OTTOOOOTOO OTOOOOOOOO TTTOOOOOOO OTOOOOOOOO  73  0000010000 0000000000 0011000000 0011000001 0001000000 0000100000 1000100001 0110000000 1110000000 0000000001 1000100000  0010000000 0000000000 0100000001 0100000001 0110000001 0000010000 0010000000 0000010100 0000010100 0010000000 0011000000  0000001000 0100101011 1000000010 1000000010 0100100001 0011011000 0001001011 0000011001 0000011000 0101101000 0001101000  0011001000 1000000100 0001000010 0001000000 1100000100 0000010101 1010000000 1101111000 1001111100 0010000100 0000000100  PROBLEM I I I Objective  Function  Coefficients  9 16 17 26 36 43 47 55 64 69 76 80 89 97 97 101 102 112 112 118 123 127 137 140 144 145 149 150 152 152 154 157 165 171 179 182 182 186 196 196 Polynomial  constraints  15(36) 14(34 30 27 25 20) 14(15) 13(35 18 11 8 7) 7(36 31 21) 4(36 10 7 4) 1(29 15) < 34 20(4 3) 20(34 31 22 20 8) 18(20 18 8) 18(37 36 12 10 6) 18(39 35 31 24) 17(37 34) 17(32 31 19 3 1) 16(27 1) 16(40 14 13) 13(15) 11(39 23 18) 7(34 22 21 9 3) 6(37 16) 4(3) 3(40 10 9) 2(31 22 21 20) < 103 13(19  15) 5(36 13 8)  <  9  19(31 30 22 20) 18(35 27 9 4) 6(36 30 9 1) 5(40 36 10 2) 1(40 27 19 17 12) < 24 19(32  12)  <  9  18(8) 15(28 27 22 21) 15(38 36 35 3) 14(40 32) 13(35) 10(9 8) 7(25 5) 6(11) 6(25 3) 4(20) 3(38 30 16) < 55 18(11) 17(22 12) 12(39 35 31) 12(34 32 30 8) 11(33 22 19) 10(10 4) 10(15) 10(32 25) 9(29 27) 7(28 15 2) 7(37 23) 6(29 19 12) 5(28) 5(24) 5(32 11 2) 4(12) 4(4) 3(20 8 1) 3(31 13 4 3) 1(37 2) < 79 20(39 33) 20(38 29 11 3) 19(19 7 6 5 2) 17(39) 16(37) 16 (33 17) 16 (36 19 11 10 8) 15(27 16) 15 (30 18) 14 (39 29) 14(33 16 8) 12(24 18 16) 12(27 1) 12(40 29 8) 10(28) 9(18) 9(40 31 23 7) 6(26 10) 5(39 24 2) < 128  74  20(38 22 12 5) 20(13) 15(29 18 11 3 2) 14(20) 11(21 20 18 12) 10(32 24 20 17 6) 6(40 26) 6(26 20 19 15 1) 5(38 36 30 5) 3(27) < 55 20(26 23) 20(12 9 2) 19(39) 17(31 16 12 3) 15(34 26 20 17 4) 11(21 17) 11(24 15) 8(40) 6(27 13) 5(38 34) 4(40 24 21 9 6) 2(36 21 18) 2(32 22 21 10 7) 1(11) < 70 19(24 20) 16(33 29 26 23 20) 15(28 25 17 6 2) 15(38 15) 14(39 33) 11(24) 6(9 1) < 48 19(28 18 17 3 1) 18(9) 18(31 29 28 11) 18(4) 15(36 18 14 5) 14(23 13) 13(25 18 4) 12(25) 12(19 14) 12(31) 9(37 22 17 14) 9(21 20) 7(39 4) 7(38 28 21 15 12) 6(11 8) 6(33 16 12 7 6) 2(39 36 17) < 98 20(36 33) 18(40 17 15) 17(37 34 24 2) 15(39 5) 14(31 9) 11(34 33) 10(39 33 26 15 7) 10(40 4) 8(20) 7(40 24 11) 6(36 31 26 13 8) 4(39 23 2) 1(12) 1(40 7) 1(33 20 13) < 13(40 30 15 1)  <  71  6  19(2) 18(21 17 16) 17(23 15 5) 16(32 14(32 21 1) 14(34 33 7 3) 13(12 9 2) 11(30 26 24 15 13) 11(17 14 8) 10(40 6(40 35 23 14 5) 5(39 37 12) 4(17 14 < 99 11(29 19 11) 10(36 11) 9(28 24 12)  13) 15(36 9 8 1) 12(38 31 27 17 2) 16) 9(18 15 13) 11 1) 3(32 13) 2(36) <  15  20(36 26 24 6) 19(22) 17(30 26 11 6) 13(31 25 21) 12(35) 12(11) 12(37 33) 11(40 18 16) 10(31 21 10) 9(34 13 9) 7(38 25 8 3) 6(23) 6(39 34 33 28) 3(30 26 14 11 2) 2(39 35 23 12) 2(13) < 80 12(20 6 3) 8(39 26 25 11) 1(29) 15(30 25 22 13 10) 5(23 11 9)  < <  10 10  19(19 6) 18(26 24 19 17) 16(27 23 13 6 2)  <  26  18(39 37) 15(36 20 16 7) 14(36 27 19 14) 12(38 17 1) 11(40 5) 11(33) 10(35 32 24 5) 10(13 12 11) 9(35 16 14 4) 4(35 32 26 19 9) 3(23 22 20) < 58 17(32 14 12 11) 10(36 18) 8(36 11) 6(35 15 4) 4(19 12 4 3) < 22 17(32 11) 16(23) 11(40 22) 10(39 36 11) 8(33 19 11 10 6) 6(33 21 20 11 4) < 34 16(40 33 26 1) 13(32 22 15) 4(37 8 7)  <  16  20(38 32 12 11 3) 15(39 37 3 1) 12(36 13) 9(23 17) 9(28 4)  75  7(16 7 6 3) 7(3) 5(38 29 19 17 6) 3(40 23)  <  43  20(32 19 17 16 14) 19(36 26 24) 18(17 14 13) 16(11 9 5 2) 16(6) 15(40 14 7 3) 15(19) 11(17 11 4 2) 10(28) 9(35 18 1) 9(36 32 18) 6(11) 5(38 36 24 15) 1(38 32 25 7) < 85 19(14 9) 17(8 5 3) 17(29 20) 15(37 35 21 14) 14(27 23 4) 14(34 22 14) 10(39 30 28 19) 10(39 36 35 20) 10(30 26) 9(33) 8(18 15) 5(36 34 2 1) 5(4) 3(22 17 6 5) 2(28 27 21 14) 2(12 4) 1(36) 1(31 21 12 5) < 81 20(20 8) 18(8) 17(37 22 5 3) 17(2) 16(31 23 5) 14(31 30 23) 13(8 2) 12(38 20) 12(35 30 19 13 11) 8(39 36 27 1) 8(25 9 6 5) 4(38 37 25) 3(10) < 81 16(32 28 23 1) 14(38 34 23 11) 12(13) 12(15 8) 10(35 6 5) 7(31 27 12) 3(23 18 15 10 6) 3(30 20 10 1) 2(39 35 2) 1(38 3) < 40 18(15) 17(29 4) 16(31 17 3) 15(4) 11(33 31 14 8) 10(38 28) 9(35 30 26 25 2) 6(39 34 21 2) 6(28) 5(38 5 3 1) 4(26 11) 2(39 37) < 59 18(37 10) 15(25 3) 15(40 33 21 9) 11(31 29 22 16 13) 10(38 35 28 19 3) 4(31 16 15) 2(30 10 9 7) < 37 19(33 24 14) 17(15 14 2) 12(39 33 24 14 4) 12(32-31 19 14 2) 12(9 7 2) 12(1) 11(35 31 14) 6(23 11) 5(22 18 14) 4(24 17) 4(38 37 29 26) 4(29 1) 2(32 24 23 11 10) < 60 19(40 32 28 22 8) 18(34 20 1) 17(37 34 24) 17(33 18 11 4) 14(35 32 31 29 7) 13(30) 10(39 32 26 16 6) 10(32) 7(22 17 16 6 1) 7(29 24 17) 7(18 11 3 1) 4(35 26 24 16 1) 1(36) < 72 20(35 5) 19(37 5) 18(35 19 10 8 3) 18(39 35 26 11 10) 14(37 29 13) 13(37 35 29 2) 11(37 25 7 4) 8(14) 8(40) 7(25 3 2) 7(30) 5(33 32 31 27 14) 5(40 31 16) 2(12) 1(20 19 15) < 78 20(35 13 11) 17(26 3) 17(38 22) 12(17) 12(37 33) 12(27 25 16 15 6) 12(36 33 2) 12(10) 10(37 35 27 25) 6(16 10) 5(36) 4(29 9) 3(37 36 29 18 2) 1(8) 1(18) < 72 20(27 18 16 9) 19(36 15) 17(35 26 15 11) 15(16 5 3) 14(38) 13(36 35 34 31) 13(16) 13(33 14) 10(39 36 13) 10(37 35 16 1) 8(18 3) 4(35 24 18 5) 3(33 31 11) 2(24 12 4) 2(28 19 17) 1(27 20 13 3) < 82 20(16 18(20 13(29 10(40 5(19)  2) 17 22 10 <  19(23 1) 19(33 26 20 13 12) 19(40 29 23 10) 18(30) 14) 18(38 37 12 3) 17(39 38 12) 17(33 31 26) 14(9) 19 4) 12(35) 12(22 21 17) 10(39 31 22 12) 4 3 2) 9(32 31 1) 8(35 9) 6(37 20) 6(37 27 20 9) 135  76  20(35 20 11 4) 6(26 22)  <  13  12(39  <  10  32 16 6) 9(31 16)  19(22 15 9 8) 19(37 32 26 17 5) 18(11) 17(38 37 16) 16(38) 14(27 1) 13(31 30) 13(34 19) 12(37 32 16 6 2) 10(19) 9(6) 7(40 30 16 9) 5(39 16) 5(9 2) 4(38 17) 3(36 31 13) 2(19 5 3) 1(37 29 19 16) 1(39 37 20 15) < 94 Solutions Approx. s o l u t i o n : 1000001010 0011000110 1111111111 1111111111 Value o f approximation: 3717 Optimal s o l u t i o n : 0000001010 0011011010 1111111111 1111111111 Value o f o p t i m a l : 3799 F i n a l CR Problem Solved t o O p t i m a l i t y 1100001010 1100000010 0010000010 0010000000 1010000010 0001000010 1001000000 0001000010 0001000010 0001000010 0000100000 0000100000 0000010000 0000010010 1000001100 0000000110 0000000110 0000000100 0000001100 1000001100 0000000001 0000000011 0000000000 0000000000 0000000000 1000000000 0000000010 1000000000 0000000000 0000000010 0000000000 1000000000 0000000000  0001000010 0001000010 0000000010 0000000000 0011000110 0011000110 0001000100 0001000000 0001000010 0001000010 0011000000 0001000010 0000000000 0010000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000100 0010000000 0010000000 1000000010 1000000000 1000000000 1010000000 1010000000 1001000100 0100000000 0110000000 0000100010 0000100000 0000100000  0001000000 1100010101 1000100100 1100001100 1111001000 0010100000 0101000010 1110011001 1110001101 1110011101 0000001011 0001001000 1111110000 1101110000 0000010000 1100001100 1100001100 1100001100 0101000111 0010001111 0100100001 1110100000 0000000010 0010000000 0110000000 0010000100 1110100000 0111010010 0000000000 1110100100 0000000000 0000000001 1000000000  1110100000 0011111010 0010100101 0100110101 1101101011 1000000000 1010100010 0011101000 0011101010 0001101010 1110101001 0110111011 1010111000 1011111000 0010001001 0000100000 0100000001 0100100001 1101101001 1010001011 0000000000 1011101000 0000010000 0100010010 0100000001 0101000100 1011101000 1010101100 0100000000 1011101010 0000000000 0000000001 1000010000  OOTTTOOTOO OOTTTOOTOO OOTIOOIOTI OIOIOOOIOO OTOTOOOIOO IOOIIOIIOI OIIIOOOIOI IOTOOIOOIO  0000000000 OTOOOOOOIO OTOOOOOOOT TOOTTOTTOO TOOTIOTTOO OOOTTTOIOO OOOIOOOOOT OTOOOOOTOO OTOOOTOTOT OOTOTTOOOO OTOOOOOOOT TTTOOOTOOO OTOOOOOOOO TTOOOOOOOO OOOOTTOOOO OOOIOOOOOT OOTTOOOOOT OOOOOOOOOT OOOIOOOOOT OOTOTOOOOO OOTOOOOTOO  OOOOTTOOOO OOTOTTOOOO OOOOTTOOOO TTOOTOOOOO OOOOOOOOOT  OTOOOOOOIO OTOOOOOOIO TOOOOOOOOO IIOTOOOOOO TIOIOOIOOO OOOOOOTOOO OIIOOOOOOO TOOOOOOOOO  ITOOOOOOTO TOOOOOOOTO OTOOTOOOTO OOTOOOOOOO  OOTTTOOOOO 0000000000  0000000000 OTOOOOTOTO  OOOOOOTOOO OOTOOOTOOO OOOOTOOOOO OIIOOOOOOO OOOOIOIOOO OIOTOOOOOO OOOOTOOOOO 0000000000 OOOOTOOOOO OOOOTOOOOO OTTOOTOOOO OOTOOOOOOT OTTOOOTOOO OOOOOOTOOO OOOTOTOOOO OOOOOOTOTO OOOOOOTOOO OOOTOTOOOT OOOOOOOOTO TOOOTOIOTO OOOOOOOOOT OOOOTOOOOO IOOOOTOOOO OOOOTTOOOO TTOTOOOIOO OOOOOOTOOO OOOTOTTOOO OTOTOOTOTO OOOOOOTOOO OOOTOTTOOO OOOOOOTOTO OOOTTOOOOO OOTOTTOOOT OTOOOOOOOO OOOOTOOTOO OOOOTOOOTO OTOOOOOTTO OOOOTOOTOO OOOOOOOOTO OTOOOOOOIO OOOOTOTTOO OOOOOTOOTT OTOOOOOOIO OOOOTOTTOO OOOOOTOOTO OTOOOOOOIO TOOOTOTTTO OOOOOOOOOT OOOOTOOOOO TOOOOOOTTO 0000000000 O O I O O I O I T O TOOOOTOTOO 0000000000 OOIOOTOOTO TOOOOTOTOO 0 0 0 0 0 0 0 0 0 0 OTTOTTOOTO OOOOOOOTIO 0000000000 T O T O O T O I I O OOOTOOOOOO OOTOTTOOOO OTOOOTOTOO OOOTOOOOOO OOTOTOTOOO OTOOOTOTOO 0000000000 OOIOOIOOOT OOTTOOOOOO  0000000000 0000000000 0 0 0 0 0 0 0 0 0 0 OOIOOIOOOT  OOOOOOOTIO OTOOOOOOOO  0 0 0 0 1 0 0 0 0 0 OOTOOOTOOO OOTOOOOOOO OTOTOITOOO OIOITTTOOO OTOTTTTTOO OOOTTTTOTT OOOOTOTOOT OOOOTOOOOT OTOOOOOTOO OTOOOOOTOO OTTTTTOTTO TTTOTOTOOO OIOIOOOIOO TOOTOTTTOT OTTOTTTTOT OOTTTTTTOT TTTTOOTOOT OIOIOOOIOO TTTOTOTOOO TOOOOOOTTO  OOOTOOOOOO OOTTOOOOOO OTOOTOOOOO OOTTTOOOOO  OIIOOOOOOO ITTOTOOOTT TTOOTOOOTT OTOOOOOOTT TTOOOOTOOO TOOTOTOOOT TOOOOOOOTO OTOOTOTTOO OOOOOOTOOO OOOTTOOOOO OOOTTOOTOT TTTTOOOOOO OOOOOTOTTT OOOTOOOOOO OOOTOOOOOO TOOTOOOOOO TIOIOOIOOO OOOTTOTTOT OOOOTOOOTO  OTTOOOOTOO OOOOOOTOOO  OOOOOOOOOT  0000000000  OOOTOTOOOO  OOOOOOTTOO  OOOOOOOOIT  0000000000  OOOOOTOOOO TTOOOOTOOO TOOOOOIOOO TOOOOOTOOO TOOOOOOOOO  OOOOOOTOOO OTOOOOOOOO OTOOOOOOOO OTOOOOOOOO OOOIOOOOOT  TOOOOOOOOO  0000000000  TOOOOOOOOO  OTOOOOOOOT  TOOOOOOOOO  0000000000  TOOOOOOOOO OTOTOOTOOO  OTOOOOOOOT OTOOOOOOOT  OOIIOOOTOO  0000000000  OOTTOOOOOO OOIOTOOIOO OOTOIOIIOO OOTOTOTOOO OTOOTOOOOO OOTOTOOOOO  OOOOOOOOOT OTOOOOOOOO OTOOOOOOOO OTOOOOOOOT OTOOOOOOOT OOOOOOOOOT  OOTOOTOTOO  0000000000  OOOOOTOOOO  OOOOOOOOOT  0100000001 0100001010 0100001000 0000001001 0000100000 0010100100 0010000001 0000100000 0000100000 0010000001 0010000001 0010000001 0010100100 0000100100 0100000101 0100000100 0100100100 0000000110 0000100110 0100100000 0000000000 1000100000 1000001000 1000001100 0100000001 0100000000 0000000001 0000000001 0000001000 0100001010 0100001010 0001000010 0001100010 0100100000 0101101000 0000100000 0000100010 0000101000 0001001000 0001101000  0000001000 0001001110 0000001100 0000001100 0110000001 0000000000 0000000010 0110000001 0110000101 0000001000 0000011000 0010010000 0000000000 0000000001 0000000001 0000000001 0000000001 0000000001 0000000000 0011000000 0011011110 0000011010 0001011011 0000000001 0000010000 0000010100 0000010100 0000010100 0000010100 0001000110 0001001010 0000000001 0001000110 0001010000 0001000000 0000011010 0000011010 0001010011 0001010011 0001010001  0100101000 0101000000 0011000111 0010010111 0100001000 0000100000 0000100100 0100010000 1100000000 0100010000 0100010000 0100100010 1100101100 1100101100 0000000000 0000100000 0010000000 0000000000 0000100000 0000000010 0001010100 0000011000 0000001000 0101000110 0100101000 0001001111 1110100000 0001011111 0011001111 0101010010 0001010010 0100001001 0000100000 0000000011 0000100010 0000010001 0000010001 0110001000 0110001000 0001000000  0010111100 1110100000 1010001011 1010001011 0000000100 0000110100 0000101100 0000000101 0000000100 0010011100 0010001100 1000001000 0000100000 0000100000 0000000100 0000001100 1000000000 0100100001 0100100001 0000101001 0100010000 0101001110 0000011110 1101101001 0010111100 0010001010 1010101001 0010001010 1010001011 1110101100 1110101100 1000100000 1000010000 1000101001 0000101001 1101001110 1101001101 0000011011 0000111010 0100111011  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

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>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051834/manifest

Comment

Related Items