Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Algorithms and hardware for the solution of set partitioning problems Saxton, Timothy Howard 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_1982_A7 S39.pdf [ 4.6MB ]
Metadata
JSON: 831-1.0065574.json
JSON-LD: 831-1.0065574-ld.json
RDF/XML (Pretty): 831-1.0065574-rdf.xml
RDF/JSON: 831-1.0065574-rdf.json
Turtle: 831-1.0065574-turtle.txt
N-Triples: 831-1.0065574-rdf-ntriples.txt
Original Record: 831-1.0065574-source.json
Full Text
831-1.0065574-fulltext.txt
Citation
831-1.0065574.ris

Full Text

ALGORITHMS AND HARDWARE FOR THE SOLUTION OF SET PARTITIONING PROBLEMS by TIMOTHY HOWARD SAXTON B.E.,  University  o f S a s k a t c h e w a n , 1979  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE ( Department  of E l e c t r i c a l  STUDIES Engineering }  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.  THE UNIVERSITY OF BRITISH COLUMBIA December,  ©  1981  T i m o t h y Howard S a x t o n ,  198 1  In p r e s e n t i n g  t h i s t h e s i s i n p a r t i a l f u l f i l m e n t of  requirements f o r an advanced degree a t the  the  University  o f B r i t i s h Columbia, I agree t h a t the L i b r a r y s h a l l make it  f r e e l y a v a i l a b l e for reference  and  study.  I  further  agree t h a t p e r m i s s i o n f o r e x t e n s i v e copying of t h i s t h e s i s f o r s c h o l a r l y purposes may  be  department or by h i s o r her  granted by  the head of  representatives.  my  It i s  understood t h a t c o p y i n g or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain  s h a l l not  be  allowed without my  permission.  Department of The U n i v e r s i t y of B r i t i s h 2075 Wesbrook P l a c e Vancouver, Canada V6T 1W5 Date  nF-fi  (2/79)  fly.  IS  / tfftf  Columbia  written  i i  Abstract  This  thesis  problem,  called  m i n i m i z e cx, column  i s c o n c e r n e d w i t h an  subject  of  and  simple  applications,  however,  so  difficult  and  amount o f The that  c  binary  that  such  thesis.  They a r e  procedure. uses  vector.  the  first  is a  has  There are  many  set p a r t i t i o n i n g problem  of  be  solved  in a  is  reasonable  partitioning  Two are  new  be  one  problem  developed  algorithms,  presented they  and use  to  one  suggests  solve  these  that  could  evaluated the  in  same  bounding  i s a branch-and-bound a l g o r i t h m ,  of  the  indicates  better that  [16]  branching  new  and  the  strategy.  set p a r t i t i o n i n g  the  this  algorithms  algorithms  perform  better.  Heuristic investigated.  the  more s o p h i s t i c a t e d A*  with  significantly  versions The  to  the  h e u r i s t i c algorithms  very  formed  of  by  large  A*  p r o m i s e good  partitioning  combining  the  algorithm  A*  problems. algorithm  branch-and-bound  algorithm  i s shown t o y i e l d  to  i n minimal  time.  large  e  set p a r t i t i o n i n g problem  i t cannot  s i m i l a r in that  literature  algorithm  matrix,  its  hardware c o u l d  hardware,  The  Comparisons  solutions  problem i s :  Despite  f o r which the  structure  exploit  the  i s a binary  cost  the  The  i n many d i f f e r e n t a r e a s .  p r o b l e m s more e f f i c i e n t l y .  in  a  programming  time.  special digital  second  is  structure,  applications  large  linear  set p a r t i t i o n i n g problem. t o Ax=e, where A  ones,  particularly practical  the  integer  problems  optimal  are  also  sub-optimal A with  hybrid the  solutions  To  solve p a r t i t i o n i n g  microprocessor is  based system, supplemented with  investigated.  peripheral cost  device  effective  partitioning  large  in  Such  a  attached  because  areas  problems.  would  to the host allow  be  special  computer.  the s o l u t i o n  that  should  be  of  of  a  hardware,  organized  using the expensive  Such a s y s t e m  application  partitioning  system  i t would  problems without  mainframe computer. those  problems the g e n e r a l i z e d design  as  a  I t would  be  of very  large  resources of a interest  r e q u i r e the s o l u t i o n  to  o f many  iv  Table  of  Contents  Abstract Table  i i  of  Contents  List  of  Figures  List  of  Tables  ..  vi  vii  Acknowledgements  1.  iv  viii  Introduction  and  Applications  1  1.1  Introduction  1  1.2  Applications  4  1.3  A Look Ahead  8  2.  Review and  Survey  10  2.1  NP-Complete P r o b l e m s  11  2.2  The  12  2.3  B r a n c h - a n d - B o u n d and  2.4  Linear  Search Tree Enumerative Algorithms  Programming  2.4.1  Basic  2.4.2  Involutory  2.4.3  Extreme P o i n t  2.6  The  2.7  A Survey  2.8  The  G a r f i n k l e and  2.9  The  Pierce  Set  18  Properties  of  the  SPP  19 20  Covering of  16  Bases  Reductions  14 16  Solutions  2.5  ......  Greedy H e u r i s t i c  Existing  and  Algorithms  Nemhauser A l g o r i t h m  Lasky A l g o r i t h m  23 24 27 30  V  3.  New A l g o r i t h m s 3.1  Bounding Algorithms  . . . . . . 38 38  Bounding A l g o r i t h m  I  39  3.1.2  Bounding A l g o r i t h m  II  43  Two New A l g o r i t h m s  f o r t h e SPP  3.2.1  A Branch-and-Bound  3.2.2  An I m p l i c i t  46  Algorithm  46  Enumeration Algorithm  3.3  Some I m p l e m e n t a t i o n D e t a i l s  3.4  A New A l g o r i t h m  3.5  Test  Problems  3.6  Test  Results  and C o m p a r i n g  48 54  f o r the Set Covering  Problem  Results  Set P a r t i t i o n i n g  3.6.2  Set Covering  Test  Test  Results  58  63  Results  70  Summary  Special  . . . . . 56  61  3.6.1  3.7  5.  Problem  3.1.1  3.2  4.  f o r the Set P a r t i t i o n i n g  74  Hardware  f o r the Solution  o f SPPs  77  4.1  Some C o n s i d e r a t i o n s  78  4.2  Special  80  4.3  A Few D e t a i l s  Hardware .  85  Summary a n d C o n c l u s i o n s  88  5. 1  Summary  88  5.2  Conclusions  92  Bibliography  94  Appendix  A:  A Program  Appendix  B:  Input  Data  for Generating  f o r the Test  Test  Problems  Problems  97  100  vi  List  of  Figures  2.1  A simple  tree  13  2.2  Constraints  2.3  Convex  2.4  (3 (u) f o r p r o b l e m  2.5  Search tree  3.1  SPPBB s o l u t i o n  tree  47  3.2  SPPA* s o l u t i o n  tree  50  4.1  A system  4.2  Flowchart  4.3  Special  4.4  A row o f t h e s p e c i a l h a r d w a r e  i n block  function  format  28  (3(u)  0  33  i n Table  f o r problem  2.2  33  i n Table  2.2  f o r s o l v i n g p a r t i t i o n i n g problems of Bounding A l g o r i t h m  hardware  I  36  81 82 83 83  vii  List 2.1  An example SPP  2.2  Example SPP f o r m a t t e d  3.1  Example problem  3.2  Partitioning  3.3  SPPHA* p e r f o r m a n c e  3.4  SCPA* c o m p u t a t i o n a l  3.5  Computational  3.6  of T a b l e s 31  into  formatted  test  into  ascending  31 CPRs  results r e l a t i v e t o SPPA* results  results  SCPHA* p e r f o r m a n c e  blocks  u s i n g SCPA* a n d Etcheberry*s algorithm  r e l a t i v e t o SCPA*  42 64 68 72  . . . . . . . . . 73 73  VI 1 1  Acknowledgements  I would his  like  assistance  Cameron  t o t h a n k my  supervisor, Dr.  and s u p p o r t .  f o r the  many  ideas  Mabo R.  I would a l s o l i k e he  offered  during  Ito,  t o thank our  for  Robert  frequent  conversations.  Financial Sciences  and  Scholarship,  support  for this  Engineering  work was p r o v i d e d Research  Council  a n d by t h e U n i v e r s i t y o f B r i t i s h  by  a  Natural  Postgraduate  Columbia.  1  CHAPTER 1 Introduction  1 .1  thesis  optimization The  is  problems  mathematical mathematical  faced the  Applications  Introduction  This  the  and  by  those  massive  adequately required  notation  who  these  using  is  necessarily problems.  the  solve  the  Rather,  the  economical  them.  optimization  the  excessive  for  solving  algorithms  tasks.  Such  The  as  related  by  time  is  difficulty to  practical  problems cannot  define The  is  to  and  be  resources  introduce  partitioning  introduced a  it  system  p u r p o s e of  host  computer  algorithms  and  will  new  be  utilizing  solve  on the  and  problems.  these  shown special  such a system  h a r d w a r e makes p o s s i b l e  the  (SPPs).  problems.  system which c o u l d  leaving  integer  i s simple,  generated  work  SPP.  of  SPPs i s g e n e r a l l y  this  to  class  to o u t p e r f o r m a mainframe computer  problems while normal  of  possible  hardware t o s o l v e  defines  problems  large  a  these problems  important  algorithms  Furthermore,  simple,  of .  objective  it  of  to  with  set p a r t i t i o n i n g problems  that  attempt  Many  solve  efficient  that  structure  h a n d l e d b e c a u s e of  to  The  known a s  size  applications.  concerned  is  not  types  of  design  of  a  large p a r t i t i o n i n g  free hardware  to  perform should  be  its of  2  interest  t o those  who  have  to  solve  many  large  partitioning  problems. The  set  partitioning  mathematically  problem  z = 0  Ip  t  Cj Xj  i j i , ajj Xj = 1  , i=  Xj = 0,1  where a,j = 0,1.  In t e r s e m a t r i x  min SPP  z = 0  Ax  1 x n  Closely (SCP),  related  ,n  becomes:  cx  0,1  the o b j e c t i v e  function  (1,1,...,1). to  the  SPP  expressed as:  0  SCP  Ax > e = 0 ,1  the set packing  ,m  n o t a t i o n the problem  minz =cx  and  , j= 1 , —  cost vector defining  e i s the m vector  1,—  = e  Xj =  and  expressed  as:  min  where c i s a  c a n be  problem  i s the s e t c o v e r i n g  problem  3  max  z = cx 0  Ax £ e  0, 1 .  xj = An their as  alternate  collection  {A A ,...,A of  2  of  L e t 1=  sets.  }, s u c h t h a t  AjSl  J , say J ' , such t h a t U ^ A  defines  a partition  relaxed,  a covering  Set  problems mainly  i n pure in  problems.  the  = I and A j f l A = k  I f the l a s t  problem,  integer past  form  subset  0 f o r j^k and k t J ' ,  restriction,  0,  Aj(lA = k  problems, along  the  programming.  fifteen  tools  to  linear  years,  in linear  research  programming  as  a  three  is  these  many of  studied, important  these  three  problems  programming  the  important  been  because a s one  with  most  They have  investigate  programming  and o p e r a t i o n s  linear  A  of I i s defined.  a s new t e c h n i q u e s  success  {l,2,...,n}.  f o r jeJ=  p r o b l e m s c a n be f o r m u l a t e d The  available  science  of I .  salesman  optimization  of  receive  {l,...,m}, a n d A be t h e s e t  p a r t i t i o n i n g and s e t c o v e r i n g  traveling  The  from w h i c h t h e p r o b l e m s  ' s e t ' p r e f i x , comes from t h e i n t e r p r e t a t i o n o f t h e p r o b l e m  a 1 f  definition,  became  were a d v a n c e d .  had i n t h e f i e l d s  o f management  l e d n a t u r a l l y t o the a p p l i c a t i o n tool  for solving integer  linear  problems. The than  s e t p a r t i t i o n i n g problem  the s e t c o v e r i n g  problem.  general  problem  suitable  transformation  t  i n that  i s a more c o n s t r a i n e d  In  fact  the  SCP  is  problem a  more  any SPP c a n be e x p r e s s e d a s a SCP by a  of t h e c o s t  = I^j a,| a n d c h o o s e any L s u c h t h a t  vector. L t  For  l ] ^ Cj .  instance, Then:  let  4  Theorem If SCP  1  [14]  a  SPP  defined  optimal  defined  by  A and  to  covering  SPP  can  only  be  solved  1,...,n  problems.  However,  of  exactly  o n c e ) make p o s s i b l e  structure  partitioning  more  1.2  justify  a  f  has  one  the  same s e t  might c o n s i d e r  algorithms  the of  solution  the  exclusive  ( e a c h row  t h a n SCP  it  f o r the  i t i s known t h a t  algorithms  i s of  special  SCP,  constraints  efficiently  p a r t i t i o n i n g problem to  as  develop e f f i c i e n t  nature  right  a partition solution,  solutions.  necessary  the  c has  C j = C j + L t j , j=  A and  S i n c e any  of  by  must be  covered  which e x p l o i t the  special  algorithms.  enough  Furthermore,  importance  in  its  own  some  of  the  attention.  Applications  The  following  applications primarily problem  of  is also  so  be  possible  partitioning  brief and  with  the  included  closely related to  a  SPPs  concerned  are  later  is  replace  problem.  have a p p l i c a t i o n s  Although  of  this  p a r t i t i o n i n g problem, applications.  depending  a covering  Also, to  SCPs.  i n the  that,  description  some o f  SCPs.  on  the  The  thesis  the two  the  covering problems  appliction, i t  p r o b l e m w i t h an r e s u l t s t o be  is  may  equivalent presented  5  Political  To  Districting  establish  establish  towns,  t h e n Aj  satisfies  boundaries composed  etc.).  (Aj£l) d e f i n e s  If there  unacceptability the  cities,  requirements  compactness.  with  electoral  electoral districts  counties, units,  [13]  of  are  requirement  district  set  in  Xj = K  gives  (eg.  population  providing  and  partition the  to  it  contiguity,  required  the  units  of  A  population,  j , then  necessary  of p o p u l a t i o n  K districts  district  is  I f I i s the  a  of  it  Cj  and  is  solution  optimal  the along  districting  plan.  Airline  Crew S c h e d u l i n g  • The or  optimal  'legs'  is  scheduling a  set  economic  optimization  feasible  flight  personnel certain  and  regulations,  while  the  A  airline in  The  last  points  is a  to,  their  computer  generating mentioned  crews to  The  round  operation.  flight  schedule  trip  home b a s e . feasible  To cabin  to  the  obtain and  timetable  a  flight over  a  must  satisfy  certain  regulations  include  safety  company  requirement as  segments  important  must a s s i g n  These  serve  flight  problem  their  reguirements,  returning  previously  flight  airline's  restrictions.  previous  rotation  an  period.  union  considerations.  of  flight  planning  of  partitioning  s c h e d u l e an  to every  regulations  [1]  i s the  the  p o l i c y and objective  economic function,  constraints.  flown  by  a  crew  from,  and  Problem g e n e r a t i o n  begins with  rotations  satisfy  requirements.  A  that  solution  i s defined  a  the by  the  6  subset in  of r o t a t i o n s which cover  which  a  flight  'deadheading'. passenger flight  i n order  l e g , or  to  them  l e g once.  more t h a n  crew  to position  return  i s permitted  flight  i s covered  T h i s means a f l i g h t  seats  deadheading  leg  each  is  once  their  case  i s known a s  allowed  themselves  to  The  to  occupy  for their  home  next  base.  If  i n t h e model a s e t c o v e r i n g p r o b l e m i s  defined. Since and  there  many  to  feasible delivery location  of  flight  problem  Thus, a i r l i n e s  a  are  it  generated  is  usually  manageable s i z e often  with  restricted  to  [5]  routes  is  problems.  crew used  to  a set partitioning  m  locations  problem  C j i s the c o s t of route  Cost  i i s on r o u t e  be  legs,  to  p r o b l e m o f making d e l i v e r i e s  airline  would  the  r o t a t i o n s c a n be  solutions.  Deliveries The  the  reduce  techniques.  sub-optimal  Truck  of l e g a l  c a n be s e v e r a l h u n d r e d  necessary heuristic  thousands  j . Problem  typical  if  be s i m i l a r t o  different  f o r the f o r m u l i z a t i o n , generation,  n  o f many  j , and ay = 1  structure will  s c h e d u l i n g problem although  along  criteria  and r e d u c t i o n  the problem.  Information  Retrieval [ 9 ]  Suppose each  file  included  that  an  information  j having  l e n g t h Cj .  in  j i f ay= 1.  file  A  system c o n s i s t s of n  unit  of  The o p t i m a l  information, cover  files, i , is  i s t h e minimum  7  total  size  of  information  Coloring  solution  be  files  i n the  requires  areas a  which  includes a l l m  information  of  units  of  system.  known m a t h e m a t i c a l  c o l o r i n g of a map  same c o l o r .  I ; t h e n Aj  to adjacent  optimal  i s a well the  have t h e  subset  correspond the  contained  of  c o l o r i n g problem  adjacent Aj  subset  Problem  The The  the  areas.  partition  Let  i s in A  I be i f no  a  such t h a t  no  two  s e t of a r e a s  and  two  If a l l costs are  represents  the  minimum  problem.  e l e m e n t s o f Aj of  unit  value  number o f  colors  required.  Optimal  Switching  Networks, O p t i m i z a t i o n  of  Boolean  Formulas [8,25,26]  Consider digital  the  problem  i s to design  has  single  possible  a circuit  binary  inputs.  AND-gate  output  Often  these  components  qualification, the  designing  computer, a t e l e p h o n e  problem a  of  function  or  finding  requires  the the  a switching  network  for a  c e n t r a l or a c o n t r o l system.  The  which a c c e p t s  and  which circuits  OR-gate cheapest  k binary  is  a  are  designed  inputs  f u n c t i o n of  only  With  this  which w i l l  s o l u t i o n of a c o v e r i n g  2  using  components. circuit  the  implement  problem. •  Closely a  r e l a t e d to designing  l o g i c i a n ' s problem  functions. Boolean  The  of m i n i m i z i n g  logician  optimal the  d e s i r e s the  v a r i a b l e s i n t o a given  switching  networks  representation  Boolean  truth table.  formula  of  logical  which  Generally  is  there  maps are  8  many  functions  one  is  w h i c h h a v e t h e same t r u t h t a b l e , b u t t h e s i m p l e s t  desired.  This  switching  networks s i n c e  'false'  to  disjunction  1.3  have  of  practical  scheduling  variables are  often  measured  Typical take  i n integer problems  to  'high',  and-gate,  times  a and  limits.  constantly  reads  any  algorithm  that  that uses  a group of r e l a t e d  on  the  large  difficult  [4],  These  airline  and 2500-4000  much s m a l l e r  problems  time l i m i t s a r e  mainframe  integer  computers.  a s 50x100 c a n  problems,  entirely  When l o o k i n g  i t .  among  computers.  proved  linear  being  notoriously  problems as s m a l l  for solving  SCPs a n d S P P s .  them  but o f t e n  s e c o n d s on m a i n f r a m e  SCPs a n d SPPs  programming,  300-500 c o n s t r a i n t s  for test  methods  that  t o B a l a s and Padberg  i n t e n s o f CPU m i n u t e s  one  introduce  an  section  linear  time  p r o g r a m m i n g , have n o t  applied  to  a  However, d e s p i t e  make  According  i n reasonable  Traditional linear  applications.  problems with  execution  several  to  optimal  or-gate.  a r e sometimes s o l v e d ,  unsolvable  (pAq)  from t h e p r e v i o u s  problems  problems t o s o l v e . crew  problem as w i t h  corresponds  conjunction  many p r a c t i c a l  size  same  Ahead  i s apparent  simplest  the  a 'true'  (pVq) t o an  A Look  It  the  'low',  is  successful  through  programming  b a s e d on when  the l i t e r a t u r e  i s a bottleneck  Consequently,  branch-and-bound  Chapter algorithms  in  2 will that  9  have  a minimal  results  with  methods.  these  introduce  The  3  Computational  discuss additional  move  from  the  from  2  Chapter  t h e same s e t o f t e s t  defined  simple  partitioning  problems.  Chapter  hardware.  controlled  test  the  for  4 will It  one  results  of  the  obtained  3 , makes p o s s i b l e  the  purpose  with the  of solving  the newly definition  partitioning  i n t r o d u c e and e x p l a i n t h e f u n c t i o n will  hardware  investigate in  an  the  economical  feasibility  of of  microprocessor  system.  Chapter suggestions  by c o m p a r i n g  i s presented.  with  b i n a r y s t r u c t u r e o f SPPs, c o u p l e d  hardware  incorporating  compared  problem.  problems.  a l g o r i t h m s of Chapter  simple  are  background  introductory material to  f o r the set  algorithms  other  problems.  a new a l g o r i t h m f o r t h e s e t c o v e r i n g p r o b l e m  The  such  also  to set partitioning  will  partitioning  using  will  two new a l g o r i t h m s  algorithms  of  2  related  Chapter  programming.  a l g o r i t h m s have compared f a v o r a b l y w i t h  Chapter  information  Also,  d e p e n d e n c e on l i n e a r  5 will  summarize  for further  the  research w i l l  results. be made.  Conclusions  and  10  CHAPTER 2 Review and S u r v e y  This  chapter  important  background  covering of of  problems.  the important the  of  discussed is  discussed integer  of the  relevant  to  hindering  in  the reader's  2.3 b e c a u s e a d i s t i n c t i o n  the  next  chapter.  problems. i n Section  examined  further  because  algorithms  introduced  or l o g i c a l  AjU  A  and  o f some not a l l  new  results  2.4.2  through  understanding  of  brief  2.7.  of  between  Linear  the  two  programming  is  role  in  solving  survey  o f SPP and SCP  Two o f t h e s e  algorithms are  their  similarity  to  the  new  3.  the  constraint  on t h e c o l u m n s c a n be  notation.  i s equivalent  A  i n Chapter  columns  operations  set  and  thesis.  i s given  the  the  sections  b r i e f l y because of i t s t r a d i t i o n a l  Since  partitioning  and a s a r e s u l t  In p a r t i c u l a r ,  algorithms  k  to  terminology  branch-and-bound and e n u m e r a t i v e a l g o r i t h m s a r e  programming  vectors,  the  t o be a b r i e f .survey  field,  directly  without  i n Section  important  in this  thesis.  of  related  I t i s intended  c a n be o m i t t e d  Generalized  some  material  is  in this  the remainder  review  details  material  presented 2.5  will  For instance,  to the l o g i c a l  matrix  expressed  the union  are binary in  either  o f two c o l u m n s  ' o r ' o f two b i n a r y  vectors,  11  AjV A .  To a v o i d c o n f u s i o n  k  kept  notational equivalence  should  be  i n mind.  2.1  NP-Complete  Set  Problems  partitioning  integer  and s e t c o v e r i n g p r o b l e m s ,  programming  NP-complete  respect  intuitively  obvious  points,  problems,  means t h a t  bound w i t h  of  this  the  size  of  s i n c e a SPP w i t h  a  the  problems.  i s not p o l y n o m i a l  problem.  This  n v a r i a b l e s has 2  in i t s solution  programming  almost a l l  NP-complete  the problem complexity  to  or s o l u t i o n s ,  linear  are  like  feasible  space.  is  possible  n  In the terminology  solution  i s a solution for  which a l l the c o n s t r a i n t s a r e s a t i s f i e d .  An o p t i m a l  the  value  of the o b j e c t i v e  types  o f problems have  feasible  solution  with  the  best  solution i s  function.  Being no  simple  NP-complete analytical  based  on  some  points  i n the space.  explicitly  The are  i m p l i e s that these  solution.  type  of search  that  An e f f i c i e n t  examine t h e f e w e s t  algorithms  Rather,  implicitly  branch-and-bound  literature algorithms  most  be o f i n t e r e s t  and  implicit  are  and  algorithms in fact  draws a d i s t i n c t i o n ,  be n  in  general,  enumeration  enumerative called  to this discussion  make no  work w i l l  algorithms. distinction  algorithms.  implicit  branch-and-bound a l g o r i t h m s .  and t h i s  must  examines a l l 2  algorithm w i l l ,  S p i e l b e r g ' [ 3 1 ] p o i n t s o u t t h a t most a u t h o r s between  solution  points.  which w i l l  branch-and-bound,  the  do l i k e w i s e .  In t h e  enumeration Spielberg  12  2  •  The S e a r c h  2  A convenient search of  tree.  Tree  way  to represent  A search  the search  through node  tree  a search  i s a map  the problem.  representing  The  each  space.  Nodes c a n a l t e r n a t e l y be c a l l e d problems.  the  (eg.  search  node  is  general, binary  The r o o t  the descendant  a trial  Except  like  is  vector  SPPs,  a  solutions,  the i n i t i a l  node  many  can  path  composed  f o r the root  of  a.  of  i n the s o l u t i o n  partial  o f a s i n g l e node c a l l e d  a node c a n be t h e t h e p a r e n t problems  tree  node d e f i n e s  x={0,...,0}).  i s with  showing t h e s e q u e n t i a l  nodes,  candidate  algorithm  s t a t e of  node,  every  i t s parent. nodes  have  at  or  In  but  for  most  two  descendants.  Figure adjacent  2.1  A  positive  index  A negative  other  are  be  the  numbers  solution vector  tree.  The  numbers  i n w h i c h t h e nodes were  adjacent  to  an  edge i s t h e  t o 1 i n the p a r t i a l a t 0.  Thus a t node  x = { x , , x , . . . x „ } has x =1, 2  solution.  2  x =0 and 5  variables free.  because  no f e a s i b l e  there  of a small  indicates a variable fixed  A f a t h o m e d node may  example  of a v a r i a b l e f i x e d  number  4 the p a r t i a l all  an  t o t h e nodes i n d i c a t e t h e o r d e r  generated. variable  is  i s a node w h i c h h a s no  t h e node d e f i n e s a f e a s i b l e s o l u t i o n s from t h e node, o r  descendants. s o l u t i o n , or i t  is  This there  known  that  i s no s o l u t i o n f r o m t h e node w h i c h h a s a b e t t e r c o s t  current  optimal  solution.  A  unfathomed  node.  Figure  n o d e s 0 and  1 have been e x p l o r e d  2.1  live could  node  then,  represent  defines  a partial  and n o d e s 2, 3 and 4  than  have  an  tree; yet  13  Figure  2.1:  A Simple  Tree  14  to  be  fathomed.  The  when t h e r e a r e no l i v e  tree nodes  i s complete (eg.  the  and t h e s o l u t i o n entire  tree  found  has  been  LIFO  (last  fathomed).  2.3  B r a n c h - a n d - B o u n d and E n u m e r a t i v e  Branch-and-bound in,  first  search  (BB) a l g o r i t h m s a r e a l s o  out) or 'single  strategy  algorithms  generalised  procedure.  Generalized  BB A l g o r i t h m  Let  branch'  S denote  the p a r t i a l  1.  (Initialize)  2.  (Forward to  3.  (Check cost,  5.  +  S i s a solution  the l a s t  z(S)=z-c , k  i s not l e s s goto  variable 2.  following  S ={j|xj=1,jeS}, +  the  current  best  z = c*>. 0  node c h o o s e S =S +{k}, 4  +  f o r the cost  a variable,  k,  z(S)=z+c . k  of completion,  node.  6.  I f S*={0] g o t o  goto  the  A l l  respectively.  f o r f e a s i b i l i t y and. a s o l u t i o n ) z(S)+LBC(S),  indicates the  generated. to  are  S* = {0},  bound  node  vector,  0  cost,  solution.  O b t a i n a lower  o f t h e new  (Backstep) of  S = {0},  0  s t e p ) From t h e c u r r e n t  (Bounding)  if  z= 0 ,  add t o the p a r t i a l  LBC(S), 4.  and a s s o c i a t e d  x ,z  called LIFO  similar  solution  S S  solution  live  are  S" = { j |xj = 0 , j e S } , a n d z ( S ) = I j * C j . feasible  methods.  explores the l a t e s t  branch-and-bound  Algorithms  added  than  z , goto 0  Otherwise, 7. to  I f the  goto  Otherwise, S . +  5.  lower  bound  Otherwise,  2.  l e t k be t h e i n d e x  S*=S*-{k),  S"=S"+{k}, ,  15  6.  (Save  7.  (Termination) is  solution) x =x(S), 0  the  that  and  steps  t h e method  characteristics from  vector  and  z  2 and  i s no  i s the  0  3 are  which d i s t i n g u i s h  one  Otherwise,  optimal  vague.  for calculating  enumerative  algorithm  the  cost.  The lower  x  0  Stop.  forward  branch  bound a r e  branch-and-bound  t o be  from a branch-and-bound a l g o r i t h m successors candidate  to  node  2 refer i s taken  lower  bound  satisfies  The  new  to the t o be  few  t o examine  procedure  node on  the  algorithm  always  fewer  algorithm  node p l a c e d  the  In program  next  that  and  on  the  node t o be  general,  the  is  algorithms  are  problem.  Enumerative  both  by  forward  the  i s reguired to  S,=So {k},  and  +  parent step  list  any by  node,  the  with  list  by  a more  list. BB  current the  best  strategy  other  a  and  algorithm is  branching complicated  insure that  candidate  candidate  the  branching  than  both  on  bounding  penalized  the  places  candidate  nodes  differs  generates  to the  this  the  best  In c o n t r a s t , algorithm  is  explored.  branch-and-bound  debug.  a  later,  it  defined  Providing  i s always a v a i l a b l e from last  then  On  conditions,  bookkeeping  that  0 subscript refers  the  The  node  node,  descendants.  strategy.  introduced  in  nodes a r e  estimate. a  guaranteed  current  where t h e  =  1 and  the  list.  2 SS+{k},  the  solution.  another.  The  s  5.  0  there  0  solution  Notice strategy  I f z = ex>  z = z ( S ) , goto  However,  as  algorithms  easier  problem complexity  more s u s c e p t i b l e t o t h e algorithms  are  exponential  tend  t o be  grows  nature  'smarter'  of but  to BB the as  16  Spielberg simpler  [31]  schemes  justification originator implicit  of  such  A  this  But  will  occur  is  a l l the  The  canonical  a  few  also  columns.  has  and  With  a new  The  to  and  BB  stay  the  t o be this  with  burden  of  b o r n e by  the  i n mind a  new  algorithm  discuss  SPPs.  This  Section  canonical  f o r m can  addition  of  will  2.7.  will  be  a  redundant cover.  standard  programming  help  Also,  frequently  clarify  be  i f there A  artificial  expressed  variables,  of  introduced.  a constraint  has  >  0.  A problem  in  form  slack  no  equation  except  in standard called  rest  cover  a l l inequality constraints.  a l w a y s be  the  to  i s a column j '  prime  equations,  some  references  throughout  form of  c o n s t r a i n t s e x p r e s s e d as f o r m has  linear  more d e f i n i t i o n s w i l l  i s s a i d t o be  J'-{j'}  redundant  to of  first  cover J'  point  survey  programming  such that  s t r u c t u r e s has  structure."  relationship  work.  structure)  to  Programming  p o i n t s made i n t h e  this  always been  3.  i s u s e f u l at  its  linear  a  i n Chapter  has  i n t e r m s of  f o r more complex  Linear  It and  (simple  trend  enumeration a l g o r i t h m  presented  2.4  s t a t e s : "The  or  Xj  by  the  surplus  variables.  2.4.1  Basic  Solutions  Consider  a linear  columns of Ax=b c a n  be  A are  problem  in standard  p a r t i t i o n e d i n t o two  written  as:  such  f o r m and that  suppose  A=(B,N).  the Then  17  Bx +Nx =b B  The vector  m*m of  vector  B matrix basic  matrix.  multiplying  i s c a l l e d the basis  variables.  of a s s o c i a t e d  (det^O)  (1)  N  m a t r i x and x  N i s m*(n-m) m a t r i x ,  non-basic  variables*  Therefore,  we  can  B  is  solve  for  feasible solution  of ( 1 ) .  s o l u t i o n t o (2) i s f o u n d by s e t t i n g x =0.  (3)  1  x  B  > 0, (3) d e f i n e s  any of t h e b a s i c  a basic  variables  are equal  a r e a maximum  solution.  linear  programming;  a  optimal  solution.  requires  f i n d i n g t h e one b a s i s ,  basic  problem  objective Standard  for  the simplex  This  o f (£,) b a s e s , one o f w h i c h d e f i n e s t h e  optimal  on  to zero the s o l u t i o n i s  t o be d e g e n e r a t e .  There  the  x  (2)  N  B  said  nonsingular i n ( 1 ) by  x = B ~ b , x„ =0  If  i s the  B  1  If  a  H  1  B  basic  and x  by B " .  x =B"'b-B" Nx  The  i s the  B  the optimal  fundamental  theorems  in  s o l u t i o n t o a l i n e a r problem i s  Thus,  the  solution  of  o f many, w h i c h  a  linear  optimizes  function. methods  for solving  algorithm.  finding the optimal  feasible  i s one o f t h e  solution.  variable  enters  objective  function  the l i n e a r problem a r e based  The s i m p l e x solution  During  each  and a v a r i a b l e i s improved.  algorithm  isa  procedure  s t a r t i n g f r o m an i n i t i a l  iteration leaves  of  the  the b a s i s ,  The s i m p l e x  basic  algorithm such  algorithm,  a  that the however,  18  has  difficulties  degenerate sequence That the  solutions of  i t  degenerate  i s , the simplex  is  does  algorithm  occur  However, t h i s  that  there  i t e r a t i o n s that  will  cycle  solutions.  precautions  For  highly  linear  in  the  solution  i s not the case  so  must  This  solution  i s that  the  indefinitely  through  i s known a s c y c l i n g .  data  that  against  cycling.  2.4.2  Involutory  Consider  2  linear  problems.  integer  problem,  precautions  cases.  obtaining  due t o t h e e x t r e m e required  to  guard  Bases  a SCP.  If  cycling  c y c l i n g i n these  much more d i f f i c u l t  necessary  a  a cycle.  of a p p l i e d  to prevent  be  define  f o r the relaxed  be t a k e n  will  d e g e n e r a t e p r o b l e m s s u c h a s SCPs a n d SPPs,  degeneracy and  point  In the presence of  i s known f r o m a w e a l t h o f e m p i r i c a l  not  Theorem  solutions.  possible  simplex  same s e t o f d e g e n e r a t e  It  a  with degenerate  Then:  J'={j|xj=l}  is  a prime cover,  x' i s an e x t r e m e  i n t h e s p a c e o f f e a s i b l e s o l u t i o n s o f t h e SCP. The  satisfy columns  proof  is  simple.  Each  a t l e a s t one c o n s t r a i n t of  J'  are  linearly  column  s p e c i f i e d by J ' must  a s an e q u a l i t y . independent  Therefore  the  a n d x' i s an e x t r e m e  po i n t .  Bellmore problem  and  has b a s i c  involutory  basis  Ratliff  optimal is  one  [6]  prove  solutions with for  that  the  involutory  w h i c h B~ =B. 1  set covering basis.  Thus i n (3) i t  An is  19  unnecessary  to  computationally J',  the b a s i s  invert  the  expensive  matrix  rows and c o l u m n s  basis  exercise.  obtained  matrix,  normally  Given a f e a s i b l e  by a s u i t a b l e  a  solution,  interchange  of  the  i s of the form:  1 , 0 B = P  where  I  is  2  variables  2.4.3  identity  i n the s o l u t i o n .  Extreme P o i n t As  is  the  with  "12  matrix  associated  Note t h a t  Properties  the  surplus  =1.  o f t h e SPP  t h e SCP, any s o l u t i o n  an e x t r e m e p o i n t  B-B  with  t o the p a r t i t i o n i n g problem  i n t h e space of f e a s i b l e  solutions  to  the  SPP. The of  adjacent  excactly  Theorem SPP  next  solutions  i n t h e SPP.  into  Adjacent  the  relationship  solutions  differ  by  one c o l u m n .  3 [4]  and  solution  t h e o r e m o f f e r s some i n s i g h t  L e t x, be an i n t e g e r  l e t B, be t h e a s s o c i a t e d t o t h e SPP w i t h  adjacent  bases  the basis  B , B , . ..,B 10  n  non-optimal basis.  B  2  such  1 p  If x  there that  solution 2  to  an  i s the optimal  e x i s t s a sequence of B^B,  and  B =B . 1p  2  Furthermore: (i)  the  intermediate  solutions  defined  i=0,1,...,p a r e a l l f e a s i b l e and ( ii )  cx  10  > cx „ > . . . >  cx  1 p  .  integer.  by  x =B^-e, u  20  p = | J i f l Q | , where J ! i s the index  (iii)  algorithm  of  non-basic  a s s o c i a t e d w i t h B,, and -Q = {J€N|xj-j = 1}.  variables  An  set  2  2  o u t l i n e d i n s e c t i o n 2.7 uses t h i s p r o p e r t y t o  s o l v e the SPP.  2.5  Reductions It  i s o f t e n p o s s i b l e t o e l i m i n a t e columns and rows from the  c o n s t r a i n t m a t r i x before problem s o l u t i o n b e g i n s . this  can  problem The  significantly  the time r e q u i r e d t o s o l v e t h e  ( e s p e c i a l l y with problems c o n t a i n i n g s p e c i a l s t r u c t u r e ) .  following  list  which problems they  Reduction  1  describes  This reduction  the  possible reductions  and t o  apply.  (SCP,SPP)  n u l l v e c t o r , there  any  reduce  In some c a s e s  I f there e x i s t s a row, rj , which i s a  i s no f e a s i b l e s o l u t i o n . i s obvious s i n c e row i cannot be covered  by  solution.  Reduction 2  (SCP,SPP)  If  i s the kth u n i t v e c t o r ,  then  feasible  K  s o l u t i o n , and A  f o r some i and k, r^=e , where e K  x =1 k  must  may be d e l e t e d .  be  included  K  i n any  A l s o any row t , with  t e A , must a l s o be d e l e t e d . k  A^  i s the only column which can cover r .  The i n c l u s i o n of  21  x„  i n the s o l u t i o n covers  removed  if i<^ = a  = 1  r  2a o  n  p  3  that  r o w s must  be  cover  3  3a  a l l columns  column k has been  If r  with  2a w o u l d  included i n the  'overcover'  a  row  there  exists  a row r  t  such  that  may be d e l e t e d .  t  follows  (SPP)  tk  p<  from  the fact  Following  that  a cover  o f row p  to  overcover  row t .  Reduction  4  c o l u m n k, Uj  cover  some c o l u m n q  row p..  (SCP)(SPP) feS  £S  Cj  f o r a subset  the  a, =a =1  must  be  o f c o l u m n s S,  and  a  ^ c , c o l u m n k may be d e l e t e d . k  column k i s i n c l u d e d i n cover  with  Thus t h e s e l e c t i o n o f c o l u m n k w o u l d  If  A,- =Aj. a n d I|  S  r e d u c t i o n 3, a l l columns k such  must be d e l e t e d .  f o l l o w s because  selected  If  2  row t .  a =1 a n d a =0 This  reduction  included in the s o l u t i o n .  f o r some p , t h e n  Reduction  if  (SCP)(SPP)  Reduction will  since  ajj Xj > 1) i f  lj  £ r  Following  t h e n any column s a t i s f y i n g  Reduction t  (SPP)  follows  solution,  r  K  some t must be d e l e t e d .  r  This  (eg.  i n A , so these  from the s o l u t i o n .  Reduction a  a l l rows  same  any  solution  columns  in  rows  with  solution  c a n be o b t a i n e d by r e p l a c i n g x = 1 w i t h K  then  less  since  cost,  a  Xj=1,jeS.  the  better  22  Redution  4a  (SCP)  k, U [ A j 2 k  column  K  The argument relax  f o r a subset  and IjesCj ^ c ,  K  65  If  6  To i l l u s t r a t e problem.  cost  k may  f o r 4a i s s i m i l a r  t h e r e q u i r e m e n t Uj sAj =A  of c o l u m n s S and a column  to that  to permit  k  be  t h e above r e d u c t i o n s  deleted. o f 4, e x c e p t  consider  the  row  A=  1 1 0 0 0 0 0  1 0 0 0 1 0 0  i s reduced as  r =e„, delete  (2a)  Delete  (3)  r >  (4)  A UA =  A ,  (2)  r,=e,,  delete  Which  5  1  leaves  0 0 1 1 0 0 0  0 0 1 0 0 0 1  0 1 0 0 0 1 0  1 2 3 4 5 6 7  follows.  (2)  2  0 1 0 0 0 1 1  1 2 3 4 5 6 7 8  columnThe SPP  0 0 1 0 0 0 0  A , 3  x«='1 .  3  6  6  5  x = 0.  r , delete 2  r,,r ;  r .  ,  2  c +c < c , delete 1  2  6  r„, x , = 1 .  the reduced problem:  we  overcovering.  = ( 3 4 8 7 9 9 8 7 )  0 0 0 1 0 0 0  that  A ; 6  x =0. 6  following  23  cost  = ( 4 9 8 7 )  row A =  10 10 0 10 1 0 1 1 0  column-  2 5 7 8  Clearly An is  the solution  interesting  made p o s s i b l e  Reduction  4b  exclusive Ejes'Cj  subsets  sub-optimal  feasible  practically  solve  set  heuristic very  the  review,  introduced  If  1  S  be  partitioning  problem  4b  S ,  index  would  SS  1  set  remove  necessarily  Uj 'A =Uj *A  2  not i n S  2  not  may be d e l e t e d . of  the  optimal  a l l columns  A reduction of t h i s  problem.  and  SS  But o f c o u r s e ,  type  in  would  to obtain the  s o l v e the problem.  covering  Greedy problem  problems.  The  d e s c r i b e d by C h v a t a l and because i n Chapter  0  two,  and  1  the  solutions. the  z =23.  5  for  Heuristic is  techniques a r e important  large  heuristic  4  t h e i d e a i n r e d u c t i o n 4.  columns,  reduction  one must  1  2  t h e columns of S  The S e t C o v e r i n g The  of  1  s u p p o s e we l e t S Then  2.6  i s : x =x =x =x =1,  way o f l o o k i n g a t t h e  of  l C  set S  7  (SCP)(SPP)  solution.  index  6  by e x t e n d i n g  ^ £ j « j > then Now  3  3.  a  NP-complete  problem  f o r the sub-optimal  Greedy [7],  i s i s related  Heuristic  is  I t i s presented  so  solution a  simple  as part of  t o a SCP a l g o r i t h m  to  be  24  Let where  T  partial  SCP  Pj be t h e number o f rows is  the  2.  (Choose  next  column,  k, w i t h t h e minimum C P R j .  4.  (Forward  variable)  Cutting  Planes  j=1,...,n.  Find the  G o t o 3.  +  i s a c o v e r and z i s t h e c o s t .  Koncal  generates  the c o v e r i n g problem. encountered  I f T={0}  k  g o t o 2.  of E x i s t i n g  and  [27,28,29] t h a t  integer  CPRj,  +  Otherwise,  (Termination) S  is  Calculate  K  4.  Salkin  +  +  A Survey  one  i n the  S e t S ={0}, T=e, z=0 a n d g o t o 2.  s t e p ) S =S +{k}, T=T-(A AT) and z=z+c .  2.7  of  |AjAT|,  Heuristic  (Initialization)  goto  Pj =  L e t CPRj =Cj/Pj .  1.  3.  Aj ,  v e c t o r o f rows r e m a i n i n g t o be c o v e r e d  solution.  Greedy  c o v e r e d _ by  Algorithms  describe  an  a l l integer  strong cutting When a p i v o t  during  planes  a dual simplex  coefficient  i n that  This  all  integer  solution.  for  both c o v e r i n g and p a r t i t i o n i n g  other  iteration, pivots  i n s u r e s an i n t e g e r  Computational  algorithm  f o r the s o l u t i o n  on an. e l e m e n t  c u t [15] i s added and t h e a l g o r i t h m row.  Stop.  on  a Gomory a  unit  t a b l e a u and an  r e s u l t s a r e given  problems.  than  i n [29]  25  Branch  and  Linear  Lemke,  Salkin  branch-and-bound compute a integer  lower  Subqradient  than  for  alternate  solve  each  the  set  the  covering  solution  optimization  rows the  every  problem,  to obtain  an  Computational  a  the  obtain  algorithm  iterative  was  used  linear  non-negative in  to  a  lower  E t c h e b e r r y [10,11] u s e d  an  [17,18],  constraint  = min  i s the v e c t o r  r e m a i n i n g t o be s e t of  satisfies solution. 1  to  the  designed  approach, to  an to  called  calculate  an  problem.  Subgradient  Lagrangian  multiplier,  candidate  problem.  The  problem i s :  For  u .  programming  Heuristic  problem  solution,  to  associates  L(u)  where u  a  solution.  In a branch-and-bound  approximate  bounding  describe  given.  linear  partial  method.  with  are  linear  Greedy  linear  problems  optimization  ,  t h e SCP  the  subgradient  u  uses  [19]  Optimization  Rather  solve  from  Spielberg which  bound, and  for covering  Bound  and  algorithm  solution  results  bound  Programming  After  free  a l l  {l  j f i T  J  c o v e r e d by  U R  U f ( l-Ij^ajj-Xj )}  where z*  iterative (4), u  vectors  u,  i s the c o s t  procedure is  R  (4)  i s the s e t of  the c a n d i d a t e problem,  at the p a r t i a l  non-negative  solving  c -Xj+I  of L a g r a n g i a n m u l t i p l i e r s ,  variables  L ( u ) < z*, The  X j  by  J is  to  (4)  solution.  the  solution  of the o p t i m a l  begins with a  updated  and  u * B  1 =  initial  u'+  t-v',  linear vector where  26  = I  i e R  uj,-(1-EjeR ajj-Xj ) ,  constant L(u)  guaranteed  to  good e s t i m a t e s  Etcheberry more e f f i c i e n t However, with  he  other  than  from t h i s  Vertex  Path  3.6.2  30  iterations.  approach  i s computationally  programming  based  methods.  compare c o m p u t a t i o n a l  a  of z*.  i n about  to  make  limited  a n d some o f  Algorithm  an  results accurate  comparison  the  results  i s made stemming  (Theorem linear  3) c a n be u s e d  problem.  Due  degeneracy  t o massive  a p p r o a c h would  of  the  (1)  P i e r c e and Lasky  algorithms constraints  take  there  has  e f f e c t i v e n e s s of t h i s  seem t o be c o m p u t a t i o n a l l y  of the  been  no  approach.  problems,  this  expensive.  P r o p e r t i e s o f t h e SPP  Garfinkel  which w i l l and  be i n c l u d e d  Nemhauser  [ 2 4 ] , a n d (3) M a r s t e n  [12],  [20].  advantage of the e x c l u s i v e nature  to define blocks  properties  pivoting  i n t h e SPP, a n d c y c l i n g  are three algorithms  classification:  to control  However,  on t h e C o m b i n a t o r i a l  There  f o r t h e SPP  [ 3 ] d e s c r i b e how t h e a d j a c e n c y  measure  [23],  linear  results  computational  Based  this  value  z * a s y m p t o t i c a l l y and i n  so i t i s d i f f i c u l t  Section  and Padberg  SPP  associated  BB  to  and t i s a  thesis.  Balas the  that  counter,  w i s an e s t i m a t e d  not e x p l i c i t l y  approaches, In  iteration  converge  similar  between E t c h e b e r r y ' s  of  the  are achieved  claims  does  comparison.  Adjacent  is  p r o p o r t i o n a l t o L(u)-w.  is  practice  1  of columns a c c o r d i n g  in  this  (2) P i e r c e  These  three  of the problem to  the  rows  27  they  have  most one This  in  common.  column  results  columns  from  in a simple the  partial  are  significantly limited  in i t s  comparisons  problems, problems  while  the  algorithms be  compared  they  are discussed  2.8  The Begin  Figure into  In B , r  rll  >r  Let subset  the  S  be  the  at  solution.  for eliminating  two  ratio  total  of v a r i a b l e s f i x e d  on  b e t t e r on  of  the of  t o be i n the  the that  into  low  density M's  two  Lasky  i n Chapter  3,  sections.  [12]  ' b l o c k s ' as  f o r a l l kc  some b l o c k s may  partial  in  Because  P i e r c e and  presented  to  Only  density  higher  columns of A a r e  according  differs  the m a t r i x ) .  next  two  algorithms.  number o f  shown  partitioned  B ,  a =  be  empty.  r  in  rk  1,  and  Within  increasing cost.  s e t of  the  at  A l s o , l e t T be  1.  first  three  better  size  columns  ordered  index  the  Nemhauser A l g o r i t h m  that  algorithms  strategy.  Nemhauser, and  words,  Notice  on  perform  algorithms  other  these The  bounding  made  i n some d e t a i l  blocks are  procedure  perform  r=1,...,m s u c h  a =0 f o r k e U i B i . a column  t o the  r e o r d e r i n g the  2.2.  blocks  to  to the  G a r f i n k l e and by  been  other  to the  i n c l u d e d i n any  algorithms.  and  of G a r f i n k l e and  will  overcovered,  while Marsten's algorithm  branching  (density refers  c o n s t r a i n t matrix  be  r e s u l t s with  SPP  similar  seems  the  be  will  solutions.  have  the  row  powerful  other  very  Marsten's algorithm  but  computational  superior to  algorithms  t h a t no  from each b l o c k can  In g e n e r a l , t h e have been  So  solution the  and  S  +  vector  the of  B-  B  1 row  B  B,  111... 1 0  2  111 ... 1  3  1 11 ... 1  ....  0 or 1  m  Figure  2.2:  Constraints  in block  format  29  rows  remaining  , feasible  to  solution  be  covered,  let x  and z , t h e a s s o c i a t e d 0  be  0  the current  best  cost.  A l g o r i thm 1.  (Initialize)  Establish  T=e, a n d z = c o .  Goto  0  2.  (Select the  3.  next  first  (Find  such  column  pointer  Let r=min{i|ieT}.  in B .  forward step)  Set a pointer t o  Examine, b e g i n n i n g a t t h e r  ai = 0  I f a column  f o r a l l i£T, and z + c < z ,  K  +  G o t o 3.  r  t h e columns i n b l o c k B .  that  S ={0},  2.  block)  a feasible  pointer,  t h e b l o c k s , Bj , 1=1,...,m.  K  t o k+1 a n d g o t o  4.  0  k  is  found  then update t h e  I f t h e r e i s no s u c h column  goto  5. 4.  (Forward (eg.  Step)  +  solution),  K  z = z , x ( j ) = {1 | j e S } , +  0  0  T={0}  g o t o 5.  g o t o 2.  (Backstep)  If  S ={0]  ( e g . a l l columns of b l o c k  +  been e x a m i n e d ) g o t o say  If  +  k  a partition  Otherwise, 5.  L e t S =S +{k}, z=z+c , T=T-A .  6.  Otherwise  k, from S ; S = S - { k } . +  +  +  remove  the  Set the p o i n t e r  last  1 have index,  t o k+1 and g o t o  3. 6.  (Termination) Otherwise,  x , z 0  If 0  z =°o 0  define  there  i s no f e a s i b l e  the optimal solution.  solution.  Stop.  30  2.9  The  Pierce  Garfinkle define  the  block, by  and  and  and  first so  Lasky  Algorithm  Nemhauser a r b i t r a r i l y block  (Figure  2.2),  on.  A more e f f i c i e n t  the  columns  ordering  in  ratio  (CPR), where t h e  number  rows  a column c o v e r s .  such that  C P R ( j ) < CPR(J + 1 ) ,  P( j ) = | A j 1=1-?! a.j. block in  1.  B,  and  in  in B ,  3  B,,  is  2  If this  3  A  A  2  then  procedure  in  A  B , 2  i s t r u e add  else place  i f A,AA AA #0 2  3  add  3  continues  A  until  2 to d e f i n e  ordering  row  2  second  is possible.  Begin  order  of  the  cost  is defined  i s , reorder  the  to block  2.  Assuming  A  3  t o B,. 3  t o B,,  3  all  by  i f A,  first  and  e l s e put  columns  A  3  to  2  t h a t A,  Otherwise,  Now  A  a  is positioned  A  Cj/P(j),  I f A,AA #0 add  3  the  columns  1.  A  to  as  to block  in B .  to  the  performance That  first  j = 1 , . . . , n - 1 ; where C P R ( j ) =  A,  Otherwise, assign  A,AA ^0.  place  Assign  row  ascending  performance of  chose the  checking  if A  2  is  A AA TFO 2  were  in B .  3  both This  2  have been a s s i g n e d  to  blocks.  Table previous  of with  the  ordering  i t places search.  a l o w e r CPR  optimal  The Notice  shows  the  problem  in Table  2.1  ordered  by  the  rules.  This because  2.2  i s more e f f e c t i v e t h a n an  the  ' b e t t e r ' columns c l o s e r t o  Here has  a r b i t r a r y ordering  a  better  r e f e r s t o the  greater  probability  the  fact of  that being  beginning a  column in  the  solution.  improved that  the  ordering  a l s o makes a b o u n d i n g  Garfinkle  and  Nemhauser  test  algorithm  possible. had  no  Cost  =(  3  4  5 6  0  0  0  0  0  1  0  1  1  1  0  1  0  0  0  0  1  1  1  1  1  0  0  0  1  0  0  1  0  1  0  0  0  1  1  0  1  0  1  0  0  0  1  0  0  1  0  0  0  1  Table  A =  column  -  7  2.1:  9 1 1 1 3 1 5 1 8 )  An example  3  7 13  18  0  0  1  1  0  0  0  1  1  1  1  1  0  1  0  11  Table  SPP  1 1  9  5  6  1  0  1  0  0  1  1  1  0  0  0  1  0  0  0  0  0  0  0  0  0  1 .1  0  0  1  0  0  1  0  0  0  1  1  0  2  3  4  5  6  7  8  9  10  2.2:  4 15  Example  SPP  formatted  into  blocks  32  bounding simple to  be  test  test  except  z+m .v ^ z , s  covered  went  z c  ^ z .  +  k  stage  S,  and  introducing  knapsack problem  Pierce  0  where m  0  at  further,  relaxed  for  [22]  i s t h e number o f  s  u =minj,< CPR( j ) .  d e f i n e d by  test  adding  rows  based up  on  a l l  the  remaining  P i e r c e and  s  a dominance  added  La sky-  solving the  the  problem  constraints.  Suppose assigned. cost  that We  at  stage  wish  of c o m p l e t i n g  to  S t h e v a l u e s x, , x , . .. ,x _, 2  calculate  the problem.  LBC(S),  The  have  s  a lower  been  bound on  knapsack problem  the  at stage  S  is:  min  F.jl q-yj = L B C ( S ) 5  E£ Pj-yj = m s  (5)  s  Yj = 0,1,  Define 6 =h -C . K  in  k  h = k  F i g u r e 2.3,  number  of  compute  a  0 ^ yj  ^  lower  bound  feasible  K  lower  1 ) , one  be  covered  by  bound  (5)  to  2.4  and  simply  solution  Figure  R  t  to  s  on  the  j3(u) c a n c  € B  s  the  l(>  relaxed  6,  ).  ^ 6  2  | Pj-yj ^ n , pS  g i v e s (3(u) f o r the  defined  k  initial  and shown  i ^ q , where q  i s the  solution.  To  (5)  (eg.  {3(m ) i s a  valid  ^ 6cj, and  for a  version That ^  }, as  partial  s  Ij  be  Vi=E| . 6 ;  c a l c u l a t e s (3(m  f o l l o w s from (5),  K  k  function  where n- = Ejj. h  rows t o  C = min {CPR( j ) | j eB  max{Pj | j e B } ,  Then a c o n v e x  K  j =S,S+1,...,n.  . • .  of s  f o r a l l k<q.  problem  in Table  2.2.  1  n  Figure  2.3:  1  1  n 2  1  Convex F u n c t i o n  n  3  ...  (3(u)  u  Figure  2.4:  |3o( ) u  f°  r  the  problem  in Table  2.2  34  Algorithm 1.  (Initialize)  Group t h e elements  previously. Let  next  r  a  pointer, be  update  such  k  (eg.  +  is a  S =S -{k},  goto  (Backstep)  If  +  Step value  4.  in B .  S*={0},  I f t h e r e i s no  t o the f i r s t  column  5.  beginning at the  I f no c o l u m n ,  r  Otherwise,  S ={0}  s  K  solution),  goto  +  (3(m ),  T=T-A .  k  Otherwise,  5.  Otherwise, m =|T-A |. s  If  T={0}  x ( j ) = {1|jeS*},  Otherwise,  remove t h e l a s t  0  0  g o t o 2.  6.  Set the pointer  z =cothere  no  +  K  z = z,  S ; S =S -{k}. +  k, c a n  g o t o 3.  z=z+c ,  +  partition  s a y k, f r o m  +  to  k+1  g o t o 3.  Figure  If  x , z 0  0  Each  define  numbered  the a l g o r i t h m .  3, z + c + (3(m ), k  has  0  2.5 i l l u s t r a t e s  2.2.  in  point  t o k+1 a n d c a l c u l a t e  s t e p ) L e t S =S + {k},  Otherwise,  4)  Bj .  a ^ =0 f o r a l l i ^ T , g o t o  goto  0  (Termination)  Table  Otherwise,  remaining  that  s  S  index,  6.  to  f o r w a r d s t e p ) Examine,  t h e columns  z + c + (3(m ) < z ,  and  5.  the pointer  (Forward  5.  goto  feasible  found  +  common  k=1,...,m.  a n d g o t o 3.  (Find  4.  K  b l o c k ) L e t r=min{11b„A Tj = 0}.  block,  B  If  and 6 ,  k  described  0  such  3.  as  and z = o o .  (Select  in  blocks  the values of h  b{ , 1=1.,...,m, be t h e r o w ( s )  T=e,  2.  Determine  into  5  been  is  feasible  the optimal s o l u t i o n .  the solution  node  tree  represents a forward  rounded  to the  left  of  up t o t h e n e a r e s t  Stop.  f o r the problem i n  The v a l u e o f t h e lower  i s shown  solution.  step  (step  bound e s t i m a t e o f the  integer  node. value.  This The  35  number  to  the  nodes  were g e n e r a t e d .  the  variables  The  optimal  and  important  the  order  numbers a d j a c e n t  t o the  1 by  or  0 or  were t h e  rows  of  b  , summed, and  vector,  r e s u l t a n t problem  optimal  solution  the  as  to  for  SPP  edges  denote  backward  step.  make  use  multiplied  by  r e s u l t s subtracted  using  of  another  o t h e r s ) b a s e d on  are  the  the  o  [4]  a  i n which  z =20.  first  (see  constants,  same  forward  0  improvement  the  a  i s x =(2,5,8),  Lasky  I f the  node i n d i c a t e s t h e  The  f i x e d at  solution  Pierce  costs.  r i g h t of  the  arbitrary  from t h e  'reduced' c o s t s  original  reduced  problem.  cost  has  That  the  is  the  problem:  min  z = E]l Cj x 0  1  Ax=e  (5)  x =0,1;  where c ' = C j - 1 ^ bj-aij , has p r o b l e m , and  z =  they  should  solve. with This  To c'^  choice  constants  be  chosen end  we  Thus, a tends  coefficients  same  solution  as  the  original  0  the  this 0.  the  z -EjI'i b[ .  0  Although  j=1,...,n  and  to  can  so  that  restrict lower  be  selected (5)  our  enhances the  the  i s the  z  0  relative  to  i s 0,  fixed cost  they  e a s i e s t problem  attention  bound on  eliminate  arbitrarily,  those  and  on  cost  to  problems z ,  in  E ^ b^ .  0  the  difference  cost  between  coefficients.  One choice  can  that  now  argue  maximizes the  that amount  the  best  s e l e c t i o n of  of  reduction,  E£  t  b^ .  b  is  the  Or  in  36  Figure  2.5:  Search  tree  f o r problem  in Table  2.2  37  other  words,  t h e l o w e r bound on z , 0  good s e l e c t i o n of t h e c o n s t a n t s linear  E(? b^ , i s m a x i m i z e d .  Thus  t  i s given  by t h e s o l u t i o n o f  a  the  problem:  max  ll?! b  t  bA < c b- £ 0; v  This  i s the dual  linear  i=1,...,m.  problem of the o r i g i n a l  set p a r t i t i o n i n g  problem.  Intuitively be  effective.  one c a n s e e why  The c o l u m n s i n c l u d e d  solution  will  The  ordering  new  first  examine  certainly  experience  t h o s e columns since  good p r o b a b i l i t y of b e i n g  the  linear  the  SPP  i n t h e SPP  solved.  Since  integer  s o l u t i o n s one o f t e n  solving  the l i n e a r  problem.  does  of the  cost t h e BB  would optimal  reduction. search  solution.  i n the l i n e a r  This  will is  s o l u t i o n has a  solution.  the reduced problem i s that i f  s o l u t i o n t o t h e p r o b l e m i s an  has been  that  linear  a column  advantage of s o l v i n g  relative  insure  i n the  reductions  i n the basis  the g r e a t e s t  of columns w i l l  desirable  Another  t h e above c o s t  integer  the l i n e a r not  have  SPP to  solution,  often  then  has  natural  proceed  beyond  38  CHAPTER 3 New  Algorithms  This chapter this  thesis.  results  problems  introduce  otherwise  algorithms  for  are  presented.  One  and  the  other for  the  presented.  3.1  will  algorithms.  .Test  used  i n these  end  of the chapter,  of  this  3.1  original  is  a  set  of s e t p a r t i t i o n i n g  branch-and-bound type  covering  algorithm.  problem  is  d e s c r i b e the bounding results are  f o l l o w e d by a b r i e f  type  given  An also  procedure  towards  the  summary o f t h e c o n t e n t s  Algorithms  essential  bounding and  represents  chapter.  Bounding  An  the solution  i s an e n u m e r a t i v e  enumerative algorithm Section  chapter  contained i n  referenced.  new  algorithm  Problem  t h e new a l g o r i t h m s  A l l material in this  unless  Two  will  f o r the Set P a r t i t i o n i n g  procedure.  Lasky,  that  bound  i s time  tree  sufficiently  calculate  i n g r e d i e n t i n any s e a r c h  well  the  I t i s often the case, any  time  spent. to  bound.  spent  A good  justify  algorithm  as observed  calculating  lower  by P i e r c e  a stronger  bound r e d u c e s  the a d d i t i o n a l  Traditional  i s a strong  time  approaches  lower  the search required to  to  integer  39  programming linear  problems,  problem  defined  T h i s method y i e l d s problem [11]  claims  linear  to  techniques  similar, based  of  solving  relaxed  SPP.  3.1.1  Bounding  A  Algorithm  of t h i s  this  simple  cost  partial follows.  only  in  i t adds  and  to  the  the  linear  combinatorial  Lasky a l g o r i t h m i s  simple  bounding  test  from t h e  will  be i n t r o d u c e d .  Bounding  now  procedure  used  chapter.  Thus  by  the  algorithms  i t represents  and  relative  i s largely  a major  strength  responsible  of  f o r the  algorithms.  i s t o d e t e r m i n e a l o w e r bound on t h e feasible  The a l g o r i t h m  associate  avoid the  a  subgradient  problem d e r i v e d  procedure  row  using  knapsack  The e f f i c i e n c y  the best  For every  subproblem,  this  problem  s o l u t i o n S.  Pierce  Etcheberry  solutions  Nemhauser  SPP  I  o f t h e new  bounding  results  considering  The  because  bounding  of o b t a i n i n g  and  algorithm  thesis.  performance  The  approximate  Algorithm  later  part  good  to obtain  I i s the bounding  introduced  constraints.  and c y c l i n g .  good  the l i n e a r  new b o u n d i n g  integer  obtained  SPP.  but s u p e r i o r ,  on  the  [ 1 9 ] , solve the  l o w e r bound b u t s o l v i n g t h e l i n e a r  by  the  Lemke, e t a l .  relaxing  Garfinkle  altogether  properties  as  due t o d e g e n e r a c y  have  problem.  problem  by  a good  is difficult  optimization  such  that the  solution  c a n be d e s c r i b e d  remains value  from  to of  be  the  the  current  i n words a s  covered minimum  in  the  cost  to  40  performance the  ratio  partition  (CPRj = C j / E -  lW  constraints.  row  i , t h e lower  the  u's.  bound c o s t  and  1.  2.  the proof that  (LBC) i s s i m p l y o b t a i n e d by  f o r the bounding  LBC i s a l o w e r  (Initialization)  bound  R=Vj vAj ,  procedure  p a s s e d by t h e c a l l i n g  so t h a t  CPR(j)  (Find  j,  j>k,  the best that  LBC=0,  routine.  i s g i v e n below  feasible  satisfies  goto  4.  Otherwise,  and check  T =T-(AjAT).  Otherwise,  goto  completing  pointer  variables  LBC  t h e subproblem  k i n s t e p 1 i s used fixed  be made c l e a r  prove  columns  2.  column) F i n d  the  first  constraints,  I f t h e r e i s no s u c h  g o t o 3.  ( T e r m i n a t i o n ) I f T£{0] t h e LBC=oo.  Goto  l e t k be a  the  the p a r t i t i o n  f o r completion)  I f T={0],  and  Order  j=1,...,n-1.  < CPR(J+1),  and i n c l u d e  (Update  To  summing  follows.  T=e-R,  e  pointer  column  The  with  = Ep, u[ .  AjAR=0, a n d c o v e r s a row i n T, A j A T / 0 .  4.  satisfies  Algorithm I  column  3.  which  That i s :  formal d e f i n i t i o n  Bounding  column  I f u' i s t h e v a l u e a s s o c i a t e d  LBC  The  aij ) o f a  4.  LBC=LBC+|Aj A T|•CPRj Otherwise,  subproblem i s a lower  S . +  to  S  +  bound  k=j, is  and  g o t o 2. unfeasible,  f o r t h e c o s t of  Stop.  exclude  at zero i n the p a r t i a l  from  solution.  consideration I t s use w i l l  later.  LBC i s a l o w e r  bound  i ti ssufficient  t o show  that  41  LBC  i s less  than the c o s t  subproblem.  of t h e l i n e a r  I f the l i n e a r  solution  to  the  same  subproblem i s :  min  z = cx 0  Ax  > e  (1)  x > 0 then  the dual problem i s : max  v  =  0  uA  | u | = Ei ut < c  (2)  u > 0  where  u  linear  programming  dual  i s the dual  problem  ^ z  0  states  (2) have  from Bounding LBC  solution  the c o n s t r a i t s  of  A fundamental theorem i n  the p r i m a l  problem  t h e same o p t i m a l c o s t ;  Algorithm  and LBC  that  vector.  I satisfies  z =v . 0  0  the c o n s t r a i n t s  i s a l o w e r bound. (2)  (1),  Substituting  and  the  Thus, of  i n u'  i f u'  ( 2 ) , then for u in  gives:  E ^ u { a i j = Ei min{CPR |ai5 = 1 , 1=1 , ... ,n}- a j t  8  ;  < Ei CPRj • asj = E =  thus  E^jU'i -aq ^ C j and  As an below  example,  the proof  consider  shows t h e s e l e c t e d  (Cj / 1 Aj ] ).a,j  C j  i s complete.  the problem  columns  L  and  the r e s u l t a n t  values.  (0) R={0],  i n T a b l e 3.1.  T=e  The  list  assignment  of  Cost  = ( 3  CPR  =(  7  4 1 3  9 1 8  3  3.5  44.33 4.54.5  0  0  0  1  1  0  0  1  1  1  1  0  0  1  0  0  5 1 5 1 1 5  5  5.5  6  1  0  1  0  0  0  1  0  1  1  0  1  0  1  0  0  0  0  0  0  0  0  0  1  1  1  0  0  1  1  1  0  0  0  column  Table  3.1:  6 ) )  10  Example problem  formatted  into  ascending  CPRs  43  and  LBC = I i u t = 1 9 . 3 3 .  one  sees that  obtained  j=1, u = 3  (2)  j=2, uj=3.5  (3)  j = 3,  u =4  (4)  j = 4,  u',=4.33  (5)  j = 5 , u|=4.5  3  a good e s t i m a t e  has  I  will  always y i e l d  s  for  low d e n s i t y  not  a sufficiently  special tree  that  The  bound  f o r t h e same  p r o b l e m s h a v i n g many strong  success  bound.  with  to the point  o  initial  Bounding  higher  I  obtained.  feasible  density  In  s  problems  reductions It  i s strong  fact,  solutions (3(m ) i s  reduce the s i z e  be e f f e c t i v e .  Algoritm  is  a s good a s  The P i e r c e and L a s k y  where any f u r t h e r  function w i l l  a bound a t l e a s t  bound  c o n s t r a i n t s on t h e p r o b l e m  bounding  z =20,  obtained.  and Lasky a l g o r i t h m  p ( m ) , b u t u s u a l l y a much b e t t e r  better  been  cost  16 ( F i g u r e 2 . 5 ) .  Algorithm  has  2  C o m p a r i n g LBC t o t h e o p t i m a l  by t h e P i e r c e  p r o b l e m was  (1)  will  algorithm where t h e  of the search  due t o t h e be  shown  simple later  enough t o be e f f e c t i v e a t  lower d e n s i t i e s .  3.1.2  At  Bounding A l g o r i t h m  II  this  stronger  introduced. principle i,  point It  an even is  similar  d i f f e r e n c e being  t h e CPRs a r e u p d a t e d b y :  bounding  to the previous  that  o n c e u\  algorithm  can  be  procedure with the  h a s been a s s i g n e d  t o row  44  CPR ( j ) = (c ( j ) where,  as  ajj-u [ ) / | Aj AT |  (3)  b e f o r e , T i s t h e s e t of rows r e m a i n i n g t o be c o v e r e d  by  the bounding  is  just  algorithm.  The  term  t h e number o f rows i n Aj  i n the denominator  f o r which  of  (3)  v a l u e s o f u- have n o t  been a s s i g n e d .  Bounding  A l g o r i t h m , II  1.  (Initialization)  2.  (Find  the  CPR(j), value  CPR(j)  Otherwise, (Update  goto  and  (Termination) LBC=t>o. for  (2) a r e a l w a y s  Applying gives:  goto  T={0]  O t h e r w i s e , LBC  i s never  the  partition  such column, goto  f o r a s o l u t i o n ) LBC=LBC+| Aj AT j • CPRj  T={0}, If  similar  calculate  w i t h t h e minimum  satisfies  I f t h e r e i s no  4.  the  Otherwise, subproblem  i s the lower  t h i s procedure y i e l d s  an argument  of  which  (3),  j  column  the c o m p l e t i o n of the subproblem.  That  Ziu[aij  and  the  Using  2.  4.  3.  check If  column)  Find  AjAR=0.  T=T-(Aj A T ) . 4.  feasible  j=1,...,n. of  Goto  es  best  constraints,  3.  R=Vj -Aj , T=e-R, LBC=0.  to that  a lower  for  S  +  bound  2.  is unfeasible, cost  estimate  Stop.  bound c a n  Algorithm  a l l o w e d to exceed  goto  and  I.  be p r o v e n The  Cj , t h u s t h e d u a l  value  with of  constraints  satisfied.  Algorithm  II to the  initial  problem  in Table  3.1  45  (0) R = { 0 } ,  and  LBC=  E£Ui=20.  the  optimal  requires  the  finding  the  initial  will  reduce  over  the  a SCP  uj=4  (3)  j=3,  u =4  (4)  j = 5,  u =uj = 4.5  this  2  ,  1  small problem A l g o r i t h m  feasible  yet  At  of  the  CPRs.  For  t o be  time the  this  be  I I has  found  using  the  t h e CPRs on  a b e t t e r bound each  iteration.  i s more d i f f i c u l t columns  these  u s e f u l i n a SCP so  though,  r e q u i r e d t o compute search  calculate  change  because  with  reasons,  the  Bounding  tested.  time  bounding  i t i s not the  clear  The  SCP  to  is  procedures that  bounds w i t h A l g o r i t h m  using Algorithm  latter  program.  stronger  tree s u f f i c i e n t l y  e q u i v a l e n t program  3.6.2.  of  column  c o n s t r a i n e d problem,  program  Section  the  II might  important.  additional  best  of  Algorithm  are  j=2,  ordering  I I has  loosely  (2)  3  recalculation  the  recalculation  a  u =3  second a l g o r i t h m w i l l  the  Also,  Algorithm  (1 ) j = 1,  cost.  Although it  For  T=e.  the II  improve  performance  I.  results  for  given  .in  Test  bounding procedure  are  46  3.2  Two New  3.2.1  A Branch-and-Bound A l g o r i t h m Using  branching The  A l g o r i t h m s f o r t h e SPP  Bounding strategy  ordering  Algorithm  to define  I  needs  a BB a l g o r i t h m  of columns d e f i n e d  the d e f i n i t i o n  one  only  to  define  solve  by t h e b o u n d i n g  the  algorithm  a  SPP. makes  s i m p l e and c o n v e n i e n t .  SPPBB A l g o r i t h m 1.  (Initialization) columns so t h a t  2.  (Forward  such column, goto 3.  (Bounding)  Determine I..  (eg.  partition  4.  (Backstep)  Let  R=R-A .  4.  solution), Otherwise,  k be t h e l a s t  I f S ={0], goto +  k  (Termination)  If  z =°o 0  Otherwise,  x , z  Figure  illustrates  solution format  3.1  tree  i s used  0  0  define  there  j ,  4.  that  S =S*+{k}, +  by  Bounding  Otherwise,  if  then z =z, x ( j ) = { l | j e 0  goto  +  2.  index v a l u e i n S ,  S =S -{k}  +  Otherwise, is  R=e S },  0  no  goto  i n T a b l e 3.1.  +  by  +  3.  partition  t h e SPPBB a l g o r i t h m  2.5.  3.  If there i s K  defined  the  j>k,  k = j , R=RVA ,  the optimal s o l u t i o n .  f o r the problem as i n F i g u r e  5.  Goto  AjAR = 0.  as  goto  0  goto  +  column,  Otherwise,  If z+LBC(S)^z ,  S =S -{k},  and 5.  a  first  LBC(S)  Order  j=1,...,n-1.  constraints,  4.  z=z+c , goto  +  the  k=0.  R = { 0 } ,  0  < CPR(J+1),  Find  Algorithm  z =~,  = { 0 } ,  the p a r t i t i o n  k  3.  +  CPR(j)  step)  satisfies no  S  solution.  Stop.  showing  The same  the  labeling  20  Figure  3.1:  n  SPPBB s o l u t i o n  tree  48  Notice  that  implicitly where  k  node 2  h a n d l e d by t h e p o i n t e r is  in  free.  variables  3.1  That  a t 0, a r e  i s , S"={j|j<k,  jeS*}  i n d e x v a l u e i n S* o r S " . F o r e x a m p l e , S*={1,3},  has  S"={2}  6 h a s S = { 1 ] , S~={2,3},  Node  An I m p l i c i t  next  algorithms belongs  k.  fixed  and  a l l other  and a l l o t h e r a r e  +  are free.  The  brief  the l a r g e s t  Figure  variables  3.2.2  t h e v a l u e s o f S~, t h e v a r i a b l e s  algorithm  called  to  Algorithm  t o be i n t r o d u c e d  Heuristic  group  called  to these generalized  introducing  belongs  to a class of  P a t h A l g o r i t h m s (HPA) [ 2 4 ] ,  a more s p e c i f i c  introduction  made by f i r s t  Enumeration  A* a l g o r i t h m s [ 1 6 ] . A  a l g o r i t h m s can  the p a r t i c u l a r  It also  algorithm  of  best  be  interest.  SPPA* A l g o r i t h m 1.  (Initialization) that  2.  CPR(j)  (Select no find  0  goto goto 3.  < CPR(J+1),  a subproblem  subproblems  on  t h e subproblem  minimum S .  S Q = [ 0 ] ,  lower  S 5 = { 0 } .  j=1,...,n-1.  from  6.  Remove  ZLBC(S). on  If there 5.  which  has  this  the  candidate  from  the candidate l i s t  Otherwise,  goto  3. to the current  such  are  Otherwise,  Call  0  (Generate the descendants  columns  3.  goto  the candidate l i s t  bound c o s t ,  S  Goto  the candidate l i s t from  the  the candidate l i s t )  I f t h e r e a r e no s u b p r o b l e m s 5.  Order  the  subproblem, list,  and i f V j c ^ A j = e , £  n o d e ) L e t 1 be t h e  49  largest that  two  i s no  2  0  i n So  or  SQ.  the p a r t i t i o n  such  S  r  and  S  F i n d the column  constraints,  column goto  descendants  S =S ,  2.  k>l,  A A(Vj s*Aj ) = 0. k  6  Otherwise,  d e f i n e d by  2  k,  S}=S  generate {k},  + 0  If the  ST =S5  and  Si=Sa+{k}.  (Bounding) ZLBC(S)=  Calculate  LBC(S)  for  E j ^ C j +LBC(S) f o r b o t h  the c a n d i d a t e 5.  value  satisfies  there  4.  index  iist.  Goto  both  S,  nodes, then  and  S .  Let  2  store  them  on  2.  ( U n f e a s i b l e t e r m i n a t i o n ) There  is  no  partition  solution.  Stop. 6.  (Termination) solution  The  and  current  subproblem  z = ZLBC(S )= 0  0  EjesjCj  S  is  is the  the  optimal  optimal cost.  Stop.  Figure Table  3.2  illustrates  SPPA* a l g o r i t h m  is,  given  a  list  find  the  one  with  generate  and  bound  candidate  list.  If  solution  t r e e f o r the  problem i n  3.1. The  from  the  SPPA*  g(x)  in  The  for  evaluation  f(x)  example of a HPA  of c a n d i d a t e the  g e n e r a l i z e d HPA  the p a r t i a l  cost  of  (1-w(x))•g(x)  bound  nodes and  That  algorithm  will  estimate,  then  p l a c e them on  a l g o r i t h m , however,  the  differs  function,  w(x),  i s introduced.  solution  a t x,  and  completing  function f(x) i s given  =  lower  successor  that a weighting  the  algorithm.  p r o b l e m s t h e HPA  minimum  the  is.-the c o s t o f  estimate  i s an  the  h(x)  problem,  i s an  then  by:  +w(x)-h(x),  0<  w(x)  <1.  (4)  the  Figure  3.2:  SPPA* s o l u t i o n  tree  51  Notice bound.  that  i s an  Consequently,  g u a r a n t e e an  The bound  h(x)  optimal  the  estimate  generalized  solution,  algorithm  known  as  s i n c e the  an  A*  equivalent  algorithm Raphael the  was  bounding  this  more t e s t .  For  the  can  equal  of  are  t  optimal  that  nodes w i t h then  soluton  examining  value. only  This  those  algorithms solution).  the  would  nodes  This  insure  find  situation  A*  generalized  A*  Hart,  algorithm  find  ZLBC(S) that by one  the the  Nilson  and  fewer nodes t h a n any  other  procedure.  test  can  d o e s not cost  for a  This  say  the  be  one  expressd  as  strictly  satisfy  successor  as  the  optimal find  However, t o do  greater  solution  than  SPPBB a l g o r i t h m  the  before optimal  would  examine  algorithm  (e.g.  feasible  solution,  the  The  so  the  the  A*  seldom o c c u r s .  node  i f there  SPPBB, m i g h t  optimal  To  satisfy  implies that  ZLBC(S)  t fewer n o d e s . to  A*  find  of  algorithm,  have  examined  would  node.  same v a l u e  a node w i t h  lower  will  this  estimated  i n a t most would  the  SPPA*  parent  another  SPPB a l g o r i t h m ever  the  a  SPPA* i s an  b o u n d i n g p r o c e d u r e must  2  s i n c e the  The  bounding  SPPA* a l g o r i t h m  requirement  not  (5)  s t u d i e d by  same  ZLBC(So) < Z L B C ( S , ) , Z L B C ( S ) .  solution,  and  exploring  the  this  Clearly  w(x)=0.5.  the  property,  t o be  J6S  introduced  using  does  'heuristic'.  Z .Cj +LBC(S)  by  lower  function  when  solution  algorithm  i s required  T h i s work showed t h a t  procedure  guarantee  (4)  first  [16].  optimal  search  to  h(x)  necessarily a  name  algorithm.  ZLBC(S)=  is  not  HPA  hence the  c a s e when w(x)=0.5 and  is  and  SPPA*  both optimal  algorithm  52  will  typically  examine s i g n i f i c a n t l y  fewer  nodes than  t h e SPPBB  algorithm.  the  As  one  would e x p e c t ,  A*  algorithm  branch-and-bound  t o examine t h e  requires  more  strategy.  A  maintained  and  some k i n d  of  track  the  current  best  of  results  show t h a t  However, large,  as w i l l  Since problem  optimal  set  expect  solution.  employed  to  solutions.  it  This  w  although  is  a l w a y s be to  the  the  candidate  the  stack.  i s well  nodes  simpler  list  procedure  must  must  be  keep  Computational  worth  these  good is  problem  large  find,  problems  and  prove,  easily  the  list  an  price.  grows  too  that  one  to  Ej *Cj + w- LB.C(S) ,. £S  factor  has  (6) been  has  cannot  found  the  methods must  be  S i n c e SPPA* i s a obtain  a weighting  factor.  NP-complete  f o r w h i c h one  solutions.  modified  adding  weighting  weighting  is  problems h e u r i s t i c  sub-optimal  i s done by  the  than  when t h e c a n d i d a t e  partitioning  ZLBC(S)=  where  node on  number o f  later.  For  find  algorithm  large  bookkeeping  arise  seen  there w i l l  reasonably  HPA  be  the  overhead  the e x t r a overhead  difficulties  fewest  heuristic  factor  to (5).  w>1  is  (6)  the  same a s  expressed  (4)  slightly  di f ferently.  The  weighting  factor  compensating  for  the  example,  the  test  in  will  in general  underestimated problems  reduce  value  examined  the  of later,  search  LBC(S). LBC(S)  by For was  53  typically  about  underestimate. give  a  will  and  at  n o d e s on Let  S  be  1  Z =100  algorithm  is  heuristic 410, choose  a  w h i c h was  o f w=1.1  in  Furthermore,  those  feasible  nodes  also  (6) a  an  will  weighting  which  solution.  define can  be  This  i n t h e SPPA* s e a r c h t h e r e a r e  two  example.  point  list,  both  the  S  the  first  and  2  LBC(S )=100 1  free  to  choose  be and  LBC(S ) =  with  of  to  1=  SS  The  2  either  equal  I f z r j . C j =300  second.  SPPA*  the nodes f i r s t .  ZLBC(SM  100+300 • ( 1 . 1 ) = 430,  2  ZLBCs  LBC(S )=300.  SPPHA*, c a l c u l a t e s  The  = 300+1.1•(100) =  so t h e h e u r i s t i c  will  S . 1  Intuitively, a  ZLBC(S).  the c a n d i d a t e  version,  and  solution,  factor  penalize  some  then  2  linear  of  from  w i t h an  Suppose  400.  to  'far'  illustrated  the  estimate  tend  subproblems  of  Thus, a w e i g h t i n g  closer  factor  'best'  90%  feasible  added  solution  to  estimates solution  larger  S'  to  that  by  as  One  S  S ,  1  i n the  sense  the  time  would expect  S  cost  that  c o u l d be  2  choice since  that  f a t h o m t h e node.  it will  1  value  i s the b e t t e r  is  fewer S  2  as  more t h a n  close  that  will  found.  upper  sub-optimal optimal  solution.  cost,  then  can If z  Zo/z  0  <  put 0  an  i s very the  the  (6)  feasible  important.  s e a r c h but  a sub-optimal bound on  i s the h e u r i s t i c w.  to  be  1  to reduce  i n c r e a s e s the p r o b a b i l i t y One  have t o  to  S .  same t i m e be  variables  i s p e n a l i z e d because  the c h o i c e of w  expected  i t is closer  cost  at  the  solution  the cost and  A  z  0  of a the  54  Section giving  3.6.1  test  will  investigate  results  for  the  several  SPPHA*  values  algorithm  of  the  by  weighting  function.  3.3  Some I m p l e m e n t a t i o n D e t a i l s  This been are  section includes a collection  explicitly significant  stated to the  i n the  of d e t a i l s  algorithm  implementation  t h a t have  definitions  and  but  performance  not  which  of  the  algorithms."  Step 3 feasible the  successor was  A  i s the  the  the  value  inclusion  and  S ,  than list  and  to the  2  by  the  for  e x c l u s i o n of  parent  the x  node S .  However,  0  That  I u s e s t o compute  k twice,  with  next  defines  k  bounding a l g o r i t h m .  calculating along  index easy.  of  Thus,  subproblem  two  The  searches  the  i t should  original  be  is the  saved  information  node.  particularily  In  algorithm  column Bounding A l g o r i t h m  rather  Saving  +  k  candidate  defining  j£S }.  A .  node, S,  first So  the  the  SPPA*  p r e v i o u s l y determined  bound.  is  the  column  k  on  of  S on  step  descendant  the  4 of  k  Consider  k for a l l  value  the the  the  parent  list  node  definition  i s k,  calculated.  S , 0  S*  the  and  of  node S.  then  required  SPPA* a l g o r i t h m ,  nodes a r e  the  subproblem a t  information  candidate  the  makes  to  If  k  0  S~={j|j<k , 0  define  the  ZLBC(S).  l o w e r bounds f o r  LBC(S,) i s  S"  calculated  the as  55  described  but  Remember x ,  that  has  K  set  there  S  differs  2  been  fixed  of f e a s i b l e  will  be  a  shortcut  from S  only  0  to 0 in S .  same e x c e p t  I i s modified  T=A  i n that a  for A ,  S  LBC(S ). 2  variable,  h a v e t h e same  2  bounding  rows i n A .  procedure  So i f B o u n d i n g  k  1 , one  i n step  K  free  and S  0  the  k  f o r those  by  when c a l c u l a t i n g  Since  2  columns except  the  Algorithm  is  can  calculate  Z L B C ( S ) by 2  ZLBC(S )=ZLBC(S )-c +LBC(S ). 2  Notice  that  there  0  b o u n d i n g c a n be s i g n i f i c a n t l y  in  the  tree.  S .descendant 2  Large Physically, the  bit  j =1  S*  extra  problem as  i f jeS ) +  interest  can  of  binary  compresses  to  the  The a  the  information.  This  data  c a n be s t o r e d a s a b i n a r y  s t a c k , i n memory.  As a new  node  size  In the  problems. the s t a t e of  of .the  problem.  i n m a c h i n e words ( e . g .  significantly. i t  list  by a  In  the  i s d e s i r a b l e t o add in  information  covered  e a s i e s t way t o implement  to define  stored  candidate  £S  latter  candidate  the  efficiency  z = E j i C j , and t h e rows a l r e a d y The  many  on  vector  computational  information  recalculating  a  nodes  node.  generate  depends  so  i s t h e same a s c a l c u l a t i n g  t h e number o f words r e q u i r e d  candidate  Treating  s p e e d e d up f o r h a l f t h e  a backstep  to the parent  SPPs  a few rows i n A  The same i d e a a p p l i e s t o SPPBB.  b r a n c h a n d bound a l g o r i t h m the  2  are generally only  the  search  K  order  to  avoid  i s the f i x e d  cost,  subproblem  (Vj *Aj ) . SS  vector.  t h e SPPA* c a n d i d a t e i s generated,  i t is  list  i s as  added  to  56  the  top  of  the  successors. search  save  the  the  this  live  value  of  the  z,  S  and  +  nodes  3.4  "A  New  this  the  dead S  0  parent  nodes i n  the  2t+1  l e a v i n g t+1  node on live  S  2  live  necessary  A convenient  remain unchanged.  list  two  i t i s only  stack.  d e f i n i n g the  way  the  to  do  candidate  descendant.  Only the  to  The  values  of  k  T h i s m i n i m i z e s t h e memory r e q u i r e d  since only  t h a t a SCP  ordering  Set  information pertaining  of  be  Furthermore,  every  addition  S . +  Covering  Problem  to  (SCP)  t h e s i s i s p r i m a r i l y concerned with  algorithm,  from  the  partition  columns  by  the  more  the  SPP,  modifying  be  SPPA*  introduced.  version mainly  i n SPPA* i s not  recalculated node on  algorithm  SCPA*, s h o u l d  bounding procedure  must  to  f o r the  o f d e f i n i n g a SCP  T h i s makes t h e CPRs  the  Algorithm  SCPA* d i f f e r s fixed  are  node i n t o  is retained.  simplicity  suggests  Therefore,  updated.  candidate  Although the  list.  Vj«*Aj  there  t have been e x p l o r e d ,  information  2  live  t iterations  nodes on  over  L B C ( S ) must be save the  SPPA* e x p a n d s a p a r e n t  these,  candidate  i s to write with  to  Of  t+1  list  and  Thus a f t e r  tree.  n o d e s on  stack.  in that  the  a v a i l a b l e t o SCPA*.  difficult  and  sorted  candidate  list  at must  because every  the node.  s t o r e S~,  in  SCPA* A l g o r i t h m 1.  (Initialization)  2.  ( S e l e c t a subproblem from the c a n d i d a t e  list)  no  g o t o 5.  subproblems  on t h e c a n d i d a t e  minimum  lower  node S ,  and  bound  cost,  remove  g o t o 6.  it  rows  i n Aj  the  goto  that  has  minimum  goto  2.  and If  S  Otherwise,  generate  Otherwise,  Call this  current  the K  has  list.  node) is  Find  t h e number o f the  column  s a t i s f i e s the  there  is  no  (Bounding)  Calculate  LBC(S)  n o d e s on t h e c a n d i d a t e (Unfeasible  for  both  for both nodes, list.  termination)  column,  t h e two d e s c e n d a n t s S, 2  Goto  There  S,  then  and store  k  partition  such  Sl=S5 and S = S 5 , Si=Ss+{k}.  +LBC(S)  If  Calculate  S}=So+(k],  F-jesrCj  the  subproblem  defined by:  ZLBC(S)=  are  3.  r e m a i n t o be c o v e r e d .  A A(Vj s*Aj ) = 0 .  there  which  j = 1 , . . . , n ; where P ( j )  CPR  If  candidate  that  constraints,  5.  from  Otherwise,  = c(j)/P(j),  list  ZLBC(S).  (Generate the descendants to the CPR(j)  3.  list,  s u b p r o b l e m on t h e c a n d i d a t e  Vjes»Aj=e,  4.  Goto  o  f i n d the  0  3.  S ={0}, S5={0}.  and Goto  S  2  4.  S .  Let  the  new  2  2. is  no  cover  solution.  Stop. 6.  (Termination) solution  and  The c u r r e n t  subproblem  z = ZLBC(S )= 0  SCPA*  algorithm  0  is  the  optimal  is  the  optimal cost.  cannot  use  many  Ijss'Cj  0  S  Stop.  Although features still  that  appears  the  make SPPA* an e f f i c i e n t t o be  comparable  to  algorithm its  other  of  the  performance  algorithms  for  the  58  limited  test  covering  results  version easily  performance examined  3.5  examined.  of  both  Test  with  the  to a h e u r i s t i c  the h e u r i s t i c  Comparing  t h e p e r f o r m a n c e of  undertaking.  A  two  good  on  the  influence  same m a c h i n e , w i t h operating  the  implementation  The  v e r s i o n , SCPHA*, a r e  computational  executed as  algorithm.  algorithms  i f t h e p r o g r a m s r e p r e s e n t a t i v e of  such  the  Results  possible  the  SPPA* a l g o r i t h m ,  3.6.2.  P r o b l e m s and  Comparing difficult  converts  SCPA* and  in Section  As  system  comparison. give  one  the  algorithm  often  comparison  the  algorithms  same i n p u t d a t a .  should Nor  is  not  be  should an  is are  Factors  permitted  to  language  of  the  unfair  a  advantage  over  another.  Often  i t i s not  conditions. with  results  the  program  not  be  results results must  i n s t a n c e , i f one  published from  available. from  the  take  difficult  into But  an  i n the  to s a t i s f y  literature,  However, a c o m p a r i s o n same s e t o f on  account accurate  to determine  test  different the figure  the  w i s h e s t o compare new as w i l l  which the p u b l i s h e d r e s u l t s  were o b t a i n e d  computers. be  For  p o s s i b l e or p r a c t i c a l  is  relative  results  done  later,  were o b t a i n e d possible  problems are  computers  be  above  then  if  known. the  test  If  the  comparison  performance  for relative  may  of  the  performance  can  s i n c e i t d e p e n d s on many f a c t o r s  (e.g.  59  operating  systems,  There  are  difficult.  An  operations complete  annoying  it  problems problem  of  the  often  not  especially  large  ones,  a r e not p o s s i b l e  One  possible  standardized  much  unreproducible  of  area.  Such  i n the  been  programmed and  This permits  a in  literature  for  comparison  and  2.7.  of  As  time.  the  The  algorithm  It  a set  space  list  accurate  problems of  a r e not sets  of the  of  test  of  problems  problems  would  from a p r o l i f e r a t i o n  problems  of  i s not  available,  Lasky  algorithm  and  a s a benchmark  one  of  the  which  also  refers  best  has  permits  a  algorithms been  i n the  qualitative  was  chosen  because  algorithms  the a l g o r i t h m s i n the in Pierce  and  program.  to [23].  partitioning  test  to G a r f i n k l e i s shown  to  But  definition  comparison  algorithm  bounding  paper.  the P i e r c e  with  proof consider  makes i t s u p e r i o r latter  thesis  Lasky's  one  literature. Section  some  a  implemented  w i t h t h e work w h i c h  Pierce represents  this  Due  to e x p l i c i t l y  borne  test  "side-by-side"  introduced  without a  literature.  f o r the reasons mentioned,  [ 2 3 ] has  throughout  results  problems.  the  comparison  up  are representative  S i n c e a s e t of s t a n d a r d i z e d and  of t e s t  in  the c o n f u s i o n  results  shows  feasible  is  which  i n each a p p l i c a t i o n  eliminate  that  i f the exact t e s t  solution  problems  etc.).  w h i c h can make a  test  is  comparisons  used,  i s the p u b l i c a t i o n  definition  problems,  found  additional  research  limitations  known.  benchmark p r o g r a m s  and  Lasky's  Nemhauser's  i n [29] t o be  superior  it  i n the  survey  of  algorithm  algorithm.  The  t o t h e Lemke e t  60  al.  [19] and K o n c a l  two  algorithms  applied on  et a l .  are  set  [27,28,29]  covering  to the s e t p a r t i t i o n i n g  linear  using  a  input  data  listed  i n Appendix  using  a  random  constraint  B o t h have a  program  number  matrix.  the t e s t  listed B.  This  results  results  Randomness  generator  Column c o s t s  random number g e n e r a t o r  equivalent  1's  minimuim  test  cardinality  scheduling  problem.  locations  to  that  route  were  make  more  The  deliveries  proportional  increase  more  in cost. equal  problems  many  in  a  truck  The  equal,  t o s o l v e than the cardinality  practical  column  lacking  scheduling  Consider  a  truck  represent  the  w o u l d make d e l i v e r i e s i f A larger truck  As a r e s u l t f o r a l l the  program  are reproducible  their  additional  Minimum  locations  the problem g e n e r a t i n g  by  I's i n t h e  small  some s t r u c t u r e .  rows  obtained  and t h e r e f o r e  i n the schedule. to  CPRs t o be a p p r o x i m a t e l y  the  to  which a p a r t i c u l a r included  is  the  cj=1, f o r j=1,...,n.  problems, randomly g e n e r a t e d similar  randomly  approximately  problem.  problems with  structure, are  were  i n the column.  i s then used t o add a  problems which u s u a l l y c o n t a i n  A,  been  a r e c a l c u l a t e d by l e t t i n g  i n a l l t h e CPRs b e i n g  problems are c o v e r i n g  Since  have  dependence  t o randomly p l a c e  t h u s t h e r e s u l t a n t p r o b l e m s a r e more d i f f i c u l t  special  last  i n A p p e n d i x A, and u s i n g  be p r o p o r t i o n a l t o t h e number o f  The  that  The  programming.  generated  cost.  algorithms  problem.  The p r o b l e m s u s e d t o o b t a i n  values  algorithms.  but one  at  a  would  would roughly  expect  the  routes.  is listed  t o anyone  having  in  Appendix  access  to a  61  computer.  This  explicitly  listing  a  i s a much more c o n v e n i e n t  s e t of standard  by  the adoption  Future  the t e s t  problems.  and  parameters  to  used.  idea a l s o a p p l i e s to other  operations structure agreed  [30]. all  just  standard  of The  3.6  as  with  that  the  the  most  were w r i t t e n  instructions  may  to l i s t  the  the t e s t  also  input  problems  have  program  A.  in  special  can  be  an  results.  32  the  random number  i s portable  Fortran generator  i n the sense that  b i t signed  integers  will  SPPA*,  and  numbers.  is, the  t o implement  Since  most  a r e many l o g i c a l  efficient  compresses  met  o p t i m i z a t i o n problems  A uses a p o r t a b l e  represent  be  Results  there  That  have  generating  reproducible  can  to  i n Appendix  the problems are r e p r o d u c i b l e ,  SCPA* a l g o r i t h m s . since  listed  define  problems  t h e same s e q u e n c e o f random  and  only  fully  random number g e n e r a t o r  Test  words.  then  to  Test  Appendix  Programs the  that  machines  generate  program  so l o n g  insure  program  the  research.  upon  To  p a p e r s would  previously could  t h e one  SCP  This  SPP  like  compared  F u r t h e r m o r e , t h e need f o r  problems as d i s c u s s e d of a p r o g r a m  strategy  way  to store  bit j  of word  data  and  t o implement  the  SPPBB,  of the problem data  operations  in  the  the problem data  i i s set  permits the l o g i c a l  to  the  1  if  binary  algorithms, i s i n machine ajj = 1.  use o f l o g i c a l  operations  is  in  This machine  parallel.  62  The  degree  of p a r a l l e l i s m  d e p e n d s on  t h e word s i z e  of the h o s t  machine.  Fortran data  and  programs,  logical  algorithms. t o be  operations,  Other  performed  implemented  in  obvious  reason  accessed  and  development  with  high  special could  level  directly.  the  used  ease  the  with  for  there  exists  support routines  that  c a n be e a s i l y  An  a s s e m b l e r program  will  be more e f f i c i e n t  possible of  d e s i g n of s p e c i a l  some  of  programmer most  the  some i n s i g h t  a  program  in  Lastly,  t h e new  are  simple  relative  linear  to  i s n o t an  Program using  algorithms  the  University  control  Thus,  an a s s e m b l e r  unmanageable  development, facilities  of B r i t i s h  task  testing,  offered Columbia.  library  large  assembler. of s i z e  discuss  the  and  and the  performance  program  gives  the  will  be  Also,  an  development  the s p e c i a l  hardware.  simple,  at  approaches  least  based  implementation  f o r the  be  a  hardware  relatively  can  An  program  algorithm.  future  been  assembler  will  t h e more s o p h i s t i c a t e d  programming.  algorithm  the  serves to simplify would  4  special  up  m i c r o p r o c e s s o r which  data  assembler program  a s t o where speeding  have  i n terms  t o improve  An  operations  a c c e s s e d from  Chapter  hardware  algorithms.  beneficial  assembler for  Furthermore,  the  reasons.  binary  i s that  binary  implement  several  which  Another  s u p p o r t e d and  time.  to  programs  of  execution  to handle  languages permit these  language  manipulated.  i s well  be  However  assembler is  routines  of  on the  programmer.  evaluation  was  by  t h e Computing  The  Centre operates  performed  Centre at  the  an ' Amdahl  63 J  470  V/8  computer  operating  under  (MTS), w h i c h p r o v i d e s an o n - l i n e ,  3.6.1  Set P a r t i t i o n i n g  As  mentioned  implemented accurate,  a  3.2  required  examined associated  For  implemented  the  listed.  with  CPU  original  costs are replaced  SPPA* p r o g r a m  the  size  of  the problems words.  naturally, words. on  the  on  results  and  the  operating  The  Therefore,  upon  completion  large  enough  i n memory.  to store  list  the stack  of problem.  But t h e r e the a l l  for  range  number  I/O  of  the e x e c u t i o n of  nodes  t i m e and a l l t i m e  system. t o P7,  Problems  PR1  except that  nodes  the  For  on a  candidate  difficult  problems  has been  the l i s t  For problem  P5,  were  live  live  Obviously  it  live  the stack To  to  depends,  n o d e s c a n be  13152/2=6576  nodes.  to save.  restricted  a node.on  problem. the  a  c a n become t o o l a r g e  a maximum o f 5,713  list. of  3.2  comparisons  the reduced c o s t s .  space to d e f i n e  the s i z e  the candidate  with  candidate  in Table  make  was  i n assembler language.  s t o r e s a l l the l i v e  implemented as a s t a c k  80,000  To  a r e t h e same p r o b l e m s a s P1  list  For  and L a s k y a l g o r i t h m  time excludes  the time-shared  PR7  system.  of t h e t h r e e p r o g r a m s problem  through  The  Pierce  algorithm.  each  System  Results  shows t h e c o m p u t a t i o n a l  to solve  is  time-shared  the  benchmark  problems.  time  before,  t h e p r o g r a m was  Table test  as  Test  the M i c h i g a n Terminal  handle  is  14  stored nodes i s not this  Problem  P1  Size  Density  Optimal solution cost  15, 120  .205  287  PR 1 P2  15.90  .205  .071  1038.7 30,120  .073  878.S 30,200  .072  1018.6 30,400  .07 1  PR7  703.33 40,400  .070  .207  . 146  nodes  CPU(sec)  436  .062  488  .045  523  .070  312  .044  1469  . 113  279  .034  68  .010  .013  322  .040  98  .015  >60  3800  .694  1328  .242  1.644  1093  . 189  84  .018  >70  1 2006  1.132  2408  21 1  23172  23791  > 1 10  24777  6.732  2.468  T a b l e 3.2:  CPU(sec)  . 137  731 730.15  nodes  SPPA*  1223  .272  . 292  SPPBB  . 281  704  PRS P7  1 19  CPU(sec)  1025  PR5 PG  nodes  880  PR4 P5  P i e r c e and Lasky  1039  PR3 P4  . 155  389 376.78  30,120  Time to solve linear problem ( s e c )  3695 284 . 18  PR2 P3  Linear solution cost  P a r t i t i o n i n g test results  1.918 . 382  5563 282  1 . 156 .051  46807  7.265  13152*  13925  2.155  3170  17975  3.604  8324*  3749  2.687  1222  61753  15.357  17590**  5.517  13601  2.992  5744*  1.294  2.762 .546 2.130 .222  65  situation, the  nodes  full  from  beginning of  a  of  candidate l i s t  the  the  variables  list.  list  into  less  further  research,  an  but  Naturally,  optimal  solution  partial pruning  this  cannot  that  a sub-optimal  solution  was  Clearly  reduced  cost  that  problems the  linear with  to solve.  reduced  problem. a  was  333  from  solved  partition  problem  includes  from  Using For  the  When to  reduced  time the  since  the  i t was  problem,  A  worth easily  been  pruned  "*"  in  the  the candidate  list  found.  "**"  means  and  by  solving  linear  based The  from  Section the  problem  on  the  relaxed  are  the  time  time  2.9  associated was  solved  MINIT a l g o r i t h m  covering  problem,  computationally easier The  the  to solve  to c a l u l a t e  than  the  the  linear  the  reduced  solution.  costs easy  to solve reduced  Ax=e.  time  has  are  and  i n T a b l e 3.2  remember  are c a l c u l a t e d  algorithm  I/O  problems  will  t h e CACM).  linear  relatively  the  solve  the  One  was  are  found.  In T a b l e 3.2,  relaxed  costs  cost  primal-dual  (Algorithm Ax>e,  the o p t i m a l s o l u t i o n  number  are  fast  of the  There  that  guaranteed. that  from  therefore  methods is  20%  fewest  solutions.  indicates  pruned  the  and  scheme  be  was  easier  that  removing  once t h e c a n d i d a t e l i s t  SPPA n o d e s c o l u m n o f T a b l e 3.2 but  by  nodes where t a k e n  solution,  promising  more s o p h i s t i c a t e d  pruned  t h e s e nodes have t h e  the  certainly  implemented.  pruned  because  fixed  statistically  The  was  i s most p r o f i t a b l e problems the  P1  linear  problem  it  and  P2  problem is  for larger  problems.  the g a i n s are i s added  apparent  modest.  t o the  that  one  time is  66  sometimes problems  better  off  however,  solving  reduced c o s t s  time.  For  seconds  b u t PR4 was s o l v e d  faster.  instance,  The  solution  Pierce  reason  .1%.  often  very close  solution  i n the s o l u t i o n  favorably  algorithm.  On  in  ratio  favors  factor  more  than  of  difficult  Apparently,  introduced  problem  ratio in this  examined  less  than  the  thesis, the  problems,  the integer by  less  solutions are  the  SPPBB and SPPA*,  Pierce  dramatic  by  a  f o rthe still  a  and Lasky a l g o r i t h m .  and  increasingly  Lasky  sometimes  a l t h o u g h PR5 was  Pierce  and  P3 t h r o u g h P7, t h e  algorithms,  become l a r g e r  more favor  SPPA* e n u m e r a t i v e  SPPBB  difficult, the  the  algorithms  algorithm,  a l g o r i t h m outperforms  although  the  optimal  half  a s many n o d e s on a v e r a g e ,  greater  problem.  The d i f f e r e n c e  P5,  times  thesis.  slightly  spent  new  for  60  i n cost  and i n t e g e r  The g a i n s were l e s s  will  branch-and-bound guarantee  i s that  differ  to  reduced problems,  expected,  always  the  n o t s o l v e P4 i n 70  space.  comparison  50.  as problems  performance  the  cost  difficult  As  usually  larger  solution  more t h a n  improvement  t h e more d i f f i c u l t  performance  very  this  On  reduce  could  algorithms introduced in this  performed  less  and L a s k y  In o t h e r words, t h e l i n e a r  The  problem.  significantly  i n 1.13 s e c o n d s ,  for  and t h e l i n e a r  than  the o r i g i n a l  fraction  of  solution  time  not SPPA*  and r e q u i r e d a  that  to  solve the  i n due  to  the  by SPPA* m a i n t a i n i n g t h e c a n d i d a t e l i s t .  P6, and P7 t h e c a n d i d a t e l i s t  could  a s SPPBB c o u l d .  than  i n t h e two r a t i o s  it  time  Notice that f o r  became t o o l a r g e  to save.  For  67  these  cases  optimal  the h e u r i s t i c  solution  Table heuristic factor  3.3  f o r t h r e e of f o u r  problems.  illustrates  performance  z'/z  SPPHA* t o  the  Similarily,  is  to  N'/N  about  within of  ratio  of a  w.  problems  of s e a r c h  problem  to problem.  (e.g.  SPPBB  have  P3 and P 4 ) .  examines  type  test  approach  problem  also  be  o f z'/z=1  solution.  than  t h e upper  used factor  in  examining  would  this  appears  to  which  is  a solution  less  Thus,  t h a t 3%  for large  guarantee  i s a NP-complete  a l g o r i t h m s can v a r y  significantly  a good  3.2.  good  time.  problems w i t h different  nodes.  feasible  The  extent  t h e same  execution  behavior  on how  solution.  problem,  significantly  b e h a v e more p r e d i c t a b l y  depends t o a g r e a t  the a l g o r i t h m t o f i n d  by  (candidate  A value  problems  while  In f a c t ,  SPPA* w i l l  Table  can  z'/z i s w e l l l e s s  solution  t h e minimuim number o f  algorithm  the optimal  the  c o s t found  in  N'/N  t h e CPU t i m e s .  the  i n minimal  SPPHA*,  of the weighting  SPPA*  of t h e r a t i o  ratio  this  found t h e  o f t h e number o f nodes  found  the p a r t i t i o n i n g  d e n s i t y may  by  by t h e o p t i m a l a l g o r i t h m .  performance  from  found  T h i s g i v e s , on a v e r a g e ,  solutions  Because the  of  For  of the o p t i m a l  difficult  heuristic  of  of the s o l u t i o n  good c h o i c e o f t h e w e i g h t i n g  w=1.063. 1%  the  t h e nodes examined  and  and  The v a l u e  a l l cases value  ratio  i s the r a t i o  the  investigation be  the  cost  that the h e u r i s t i c  In bound  be  the  optimal  problems) examined.  implies  described e a r l i e r  v e r s i o n s o f SPPA*, f o r v a r i o u s v a l u e s  w.  taken  technique  long  The  size times  since i t of  the  i t takes  earlier  a  68  w=1.016 Problem  z'/z  N'/N  w=1.031 z'/z  w=1.063  N'/N  z*/z  w-1.125  N'/N  z*/z  N'/N  P4  1  .241  1  .153  1.006  .050  1.005  .027  P5  1  .335  1.001  .101  1.010  .016  1.038  .016  P6  1.001  .068  1.007  .019  1.013  .007  1.016  .007  P7  1.001  .067  1.001  .027  1.001  .026  1.026  .005  Table  3.3:  SPPHA* p e r f o r m a n c e  relative  t o SPPA*  69  good  solution  prune  i s found the e a r l i e r  branches  known  to  solution  the  SPPBB  examine  stage  solution  take  advantage  a  of  the  best  version  is  t o SPPBB, w h i c h  to  find  examine c l o s e  list  l a r g e problems. Appendix the  B  problem  because  i n minimal solves  upper  which  in  5  seconds  using  i n 5.6 s e c o n d s  The process.  to solve  SPPA*  SPPA*,  the  partial  solution  modified  is  examine t h e algorithm  s u g g e s t s a two which  to obtain  This  upper  would  a  good  bound  Notice  that  cost SPPBB  the  not m a i n t a i n the l a r g e  algorithm  problem  the unreduced  was p r u n e d  so u n w i e l d y on  denoted costs.  could  by  not  11 t i m e s .  an  upper  be  solved assured  U s i n g SPPBB a n d  bound c o s t ,  can  was  found  SPPBB t o o k  be o p t i m i z e d f o r t h i s  a l o w e r bound c o s t logic  SPPA* a l g o r i t h m  in  127  problem.  algorithm  vectors  P8  SPPA*  f r o m SPPA*, t h e o p t i m a l s o l u t i o n  t h e same  program  This  the problem.  but o p t i m a l i t y  Without  Since only  only  cost  o f b o t h SPPBB and SPPA*.  time.  makes t h e SPPA  was s o l v e d  seconds.  optimal  problems  but i t does  For instance,  bound c o s t  be a b l e t o  t o t h e minimum number o f nodes g u a r a n t e e d  the candidate l i s t  the  large  features  will  i s , t h e SPPBB  o f SPPA* i s u s e d  the optimal s o l u t i o n ,  candidate  the  i t would  That  process for solving  t o the problem  now  then  by SPPA*.  solution  will  If  minimum number o f n o d e s .  the h e u r i s t i c  passed  tree.  algorithm,  s p a c e examined  would  First,  i n the s o l u t i o n  the algorithm  and  estimate i s desired  stack  i s not r e q u i r e d . more  efficient.  two s t a g e  space This  from  used t o save t h e would  make  a  70  3.6.2  Set C o v e r i n g  Table results E5  3.5  cardinality according  problems  problems.  Amdahl 470 V/8  IBM  360/67.  the  performance  perform  iterations SCPA*,  The  the  through minimum reduced  time  for  It includes reducing  the  faster  than  time.  40  times  in Table  comparable  3.5 i n d i c a t e s to  that  of  d e n s i t y p r o b l e m s , E1 a n d E 4 ,  algorithm  can  be  expected  to  d e n s i t y problems because t h e  ( S e c t i o n 2.7) w o u l d  of the bounding  procedure  most c o v e r i n g  algorithms,  to obtain performs  r e q u i r e more  a given  accuracy.  b e t t e r on  higher  problems.  optimal  partition. SPPA* o b t a i n s nodes.  partitioning solution  is  on h i g h e r  o p t i m i z a t i o n method  like  density  SCPA  For higher  poor  CPU  spent  a l l I/O  o f CPU t i m e s  Etcheberry's  relatively  subgradient  of  generated  2.5.  time  i s approximately  algorithm.  i s superior.  the  excludes  The r a t i o  with  P r o b l e m s E1  t o solve the problem.  excludes  SCPA* CPU t i m e  Etcheberry's  1138  but  time  SCPA*  c o s t s ) w h i c h have been  t o the r u l e s o u t l i n e d i n S e c t i o n  time  SCPA*  of  i n [10,11],  (e.g. unit  some i n p u t  that  performance  i n [ 1 0 ] , These a r e a l l randomly  i s the t o t a l  the  the  by E t c h e b e r r y  Etcheberry  The  Results  compares  obtained  are l i s t e d  Test  covering  Thus  solution  C1  turns  SCPA* and. SPPA* have t h e same  the s o l u t i o n This  t o C1  illustrates  v e r s i o n o f A*.  13 t i m e s  to  faster  than  The  out  solution  i n 0.215 s e c o n d s the r e l a t i v e partition  the c o v e r i n g  to  by  version.  a  to C l .  examining  efficiency  version  be  of t h e  found  the  71  Table test  3.4  gives  the computational  p r o b l e m s g e n e r a t e d by  t h r o u g h MC7 C.1 t o C7. easier  Clearly  t h e minimum  solving  et  al.  covering  in  SCPA* w o u l d  the problem. probably  Table  versions  A.  MC1  of the problems  problems  are  The  last  much  ratios  case of T a b l e value  two  the  fact  that  descendant branching  to the  w i t h w>>1,  obtain  SPPHA*  as w i t h  The  problems  that  an a b s o l u t e  have  based  those  nature programs  problems.  of  SCPHA*,  the  of the weighting  t h e same meaning  3.6, w>>1,  as i n  i s equivalent to  2.6) t o  the  t h e same s o l u t i o n is  forced  tree,  the Greedy  generated  z" i s t h e c o s t  programming  (Section  node down t h e s e a r c h strategy  to  3.3.  of w i n T a b l e  will  Salkin,  NP-complete  for various values  solution  heuristics  [18],  results,  performance  z ' / z a n d N'/N  approaches  However one w o u l d e x p e c t  on l a r g e r  the  o f SCPA*,  the Greedy H e u r i s t i c the  and 3.5.  illustrates  The  the p a r t i t i o n  3.4  computational  Consequently, l i n e a r  factor.  based  ( e . g . Lemke, e t a l .  be more e f f e c t i v e  3.6  programming  be more s u s c e p t i b l e  versions  where  linear  problems  Tables  heuristic  such  Appendix  cardinality  [ 2 9 ] ) have c o m p a r a b l e  illustrated  would  of  f o r a number o f  to solve.  to  of  program  a r e t h e minimum c a r d i n a l i t y  The more c o n v e n t i o n a l  that  the  results  which  to  That  follows  follow  results  from  the  S,  i n t h e same  Heuristic.  by  the program  u p p e r bound  on t h e v a l u e  of the worst  SCP.  feasible  i n Appendix A a r e o f z"/z i s  solution,  1.50,  a n d z, t h e  Size m,n  density  Cl MC 1  30,90 n  . 1 1 ti  C2 MC2  30,90  C3 MC3  Problem  t o t a l no. o f candidate p r o b l e m s (N)  Cost CPU t i m e ( z ) (msec)  2169 121  558 8  2620 145  .21 n  913 415  457 5  1016 440  30,90 ft  .31  855 331  398 4  851 298  C4 MC4  50,90 n  .21 n  81 17 329  643 6  9954 3790  C5 MC5  40,90  .21 ti  1675 435  525  1873 480  C6 MC6  30,50  .21 n  1797 49  624 5  1  C7 MC7  30,70 ti  .21 ti  1307 237  500 5  1 1 30 203  II  «  IF  Table  3.4:  SCPA* c o m p u t a t i o n a l  5  results  149 34  CPU t i m e  Problem  Size m,n  Density  Etcheberry IBM 360/67  (sec.) SCPA* Amdahl 470  r a t i o of CPU t i m e s  El  10,13  .30  0.72  .004  180  E2  30,43  .10  2.55  .084  30  E3  30,59  .10  4.80  .100  48  E4  50,100  .21  352.01  0.534  659  E5  50,75  .07  46.05  1.711  27  Table  3.5:  Computational  w=1.031 Problem  z'/z  N'/N  results  u s i n g SCPA* a n d E t c h e b e r r y ' s algorithm  w=1.063 z'/z  w=1.125  N'/N  z'/z  N'/N  w »  1  z'/z  C1  1.013  .194  1.036  .102  1.063  .041  1.11  C2  1  .461  1.059  .181  1.059  .071  1.14  C3  1  .392  1  .219  1  .095  1.06  C4  1  .216  1  .067  1  .016  1.03  C5  1  .251  1  .099  1  .026  1.38  C6  1  .289  1  .132  1  .042  1.12  C7  1  .279  1  .094  1  .034  1.14  Table  3.6:  SCPKA*  performance  relative  t o SCPA*  74  best.  With  Greedy the  this  figure  Heuristic  heuristic  solutions.  are  must  However,  by e x a m i n i n g  optimal  version.  w=1.l25, a s e a r c h  bound  A  tree  For  in  much  was r e d u c e d  3.7  Summary  example, 5%  with of  worst  found  search a  the  feasible  the optimal  tree  than  weighting size  the  f o r p r o b l e m C5,  the  cases  z ' / z was l e s s  performance  by a b o u t  chapter  partitioning Evaluation results  algorithm.  most  of  smaller  increase  v a l u e s of the w e i g h t i n g  This  one  by  of  the  f a c t o r of  the  optimal  s o u t i o n was f o u n d i n than  the  predicted  o f w.  solution.  shown  a  In a l l c a s e s ,  optimal  test  SCPHA  t r e e about  significant  smaller  found  obtained  In f a c t  was e x a m i n e d a n d y e t t h e o p t i m a l  5 of 7 cases. upper  results  not impressive.  have  solution  algorithm  i n mind, t h e  factor.  70%, a n d 6 o f  also  recorded  and  one  for  of the p a r t i t i o n i n g those  obtained  P i e r c e and L a s k y ' s  the  7  cases  set  obtained  the l i t e r a t u r e .  Also  of  u s i n g a s m a l l program  the  f o r the set  covering  problem.  a l g o r i t h m s was made by c o m p a r i n g using  the  Pierce  a l g o r i t h m was c h o s e n  i n S e c t i o n 3.5, i t r e p r e s e n t s one o f t h e  in  for  W i t h w=1.031 t h e s e a r c h  h a s i n t r o d u c e d two new a l g o r i t h m s  problem  with  is  introduced to generate  in this  best  chapter  random t e s t  and  Lasky  because, as algorithms was t h e i d e a  problems.  This  75  makes  the  test  problems  program and a l i s t unattractive  more  portable  because only a small  of input parameters has t o be s p e c i f i e d .  a l t e r n a t i v e would be t o e x p l i c i t l y  list  The  many l a r g e  problems. The  new  Algorithm bound  much  have  one  common  feature,  I . T h i s new bounding procedure c a l c u l a t e s  cost  solution  algorithms  of  the  i t i s simple  stronger  than  linear  subproblem,  and e f f i c i e n t that  from  The  first  The bound  This  type a l g o r i t h m .  described  approach. on  (SPPA*) It  is  search  smarter  than  The  A*  because, f o r a given branching  minimum number of candidate Test  results  show  algorithms the  ratio  The  that  perfomance  conventional s t r a t e g y based  conducts  an  optimal  s t r a t e g y , i t examines the  the  ratio  new p a r t i t i o n i n g to  the  Pierce  algorithms and  Lasky  i n c r e a s i n g l y favored the new  as the problems became more d i f f i c u l t . exceeded 50.  they  problems.  perform e x c e p t i o n a l l y w e l l compared algorithm.  because  more  branching  algorithm  i n the  However, the second  the  uses a more c o m p l i c a t e d  the A* a l g o r i t h m .  is  is a  Most search a l g o r i t h m s  w e l l understood and easy to implement.  algorithm  fact  (SPPBB)  l i t e r a t u r e tend t o be branch-and-bound a l g o r i t h m s are  is  results.  p a r t i t i o n i n g algorithm  branch-and-bound  lower  the r e l a x e d knapsack  problem used i n the P i e r c e and Lasky a l g o r i t h m . i l l u s t r a t e d by the t e s t  the  but u n l i k e the l i n e a r  t o implement.  obtained  Bounding  . In some cases  In comparing the new a l g o r i t h m s ,  g e n e r a l l y performed much b e t t e r than  SPPBB.  However,  SPPA*  optimal  76  results medium  from size  SPPA*  could  problems.  For  entire  candidate  results  were s o m e t i m e s  Heuristic very  Algorithm  obtained search  by  tree.  part  of  SPPA*  i s used  optimal  tree.  This  strengths  A  showed  medium  algorithms  good  Thus  only  a  small  find  This  algorithm  cost  procedure  is  an  proposed  of  SPPA*  in this  t o t h e SPPBB  a  near  excellent  way  of  to  be  The main a d v a n t a g e o f SCPA* case,  to h e u r i s t i c  the  algorithm  minimal  search  of combining the  in this  and i t s p e r f o r m a n c e on s m a l l  appears  existing searches.  solutions could  comparable  to  i s i t s HPA  covering Test  is  chapter.  introduced  SCPA*, was a l s o  be  of the o p t i m a l  algorithm,  sub-optimal  Path  could  algorithms.  problems  good  results  t h e A* and b r a n c h - a n d - b o u n d  I t i s an A* a l g o r i t h m  that  Heuristic  version  i s passed  examining  themselves  a  very  themselves  an u p p e r bound on t h e c o s t  by  lend  problems a r e  of s o l v i n g  fraction  the h e u r i s t i c  two s t a g e  the p a r t i t i o n i n g  the  sub-optimal  not lend  sub-optimal  the problem  size  problems  naturally suited to this application.  that  to quickly  do  However, SPPA* i s  Furthermore,  of both  algorithms.  difficult  for solving partitioning  is  examining  covering  chapter.  Like  and  solution.  solves  more  obtained.  application.  a unique  which  the  f o r the s m a l l and  was t o l a r g e t o s a v e .  Existing  (HPA)  results  be g u a r a n t e e d  because of t h e extreme d i f f i c u l t y  problems.  towards t h i s  Test  list  procedures  important  large  only  other  character.  algorithms results  be -found u s i n g  to  do n o t  indicate  SCPA*.  77  CHAPTER 4 Special  This of The  chapter  a hardware  the  will  required  because  elapse  for solving  to solve CPU t i m e  large  time  than the t o t a l  based  system,  be  partitioning computer. handling  simple.  problems Such  a  many l a r g e  feasiblility  most  resource.  applications  that  system problems.  the  would  same  be a c o s t  here  as  effective  isa  s h o u l d be  should a  be  hardware,  hardware  the system time  i s usually  time can  the system  the s p e c i a l  To be e f f i c i e n t , i n about  around  with s p e c i a l  To be p r a c t i c a l  mainframe  Furthermore,  t o be examined  supplemented  problem.  from t h e t i m e and  SPPs on a t i m e - s h a r e d  alternative  economical, implying  relatively  For  CPU t i m e , so t u r n  microprocessor  relatively  and  on a t i m e - s h a r e d machine  The  these problems.  Problems  partitioning  arises  SPPs.  i s a valuable  long.  solve  the design  the set  large  prohibitively  to  of P a r t i t i o n  investigation  to solve  solution  much l o n g e r  investigate  for this  i s impractical  computer  f o r the S o l u t i o n  system  motivation  resources it  Hardware  should solve  mainframe method o f  78  4.1  Some C o n s i d e r a t i o n s  The a  a l g o r i t h m s of C h a p t e r  s y s t e m as p r e v i o u s l y  algorithm  will  implemented.  type  avoiding  the  floating  point  (in  conventional  and  the  a  the  microcoded fact, time  for  would  This  the  too  used,  arise be  an  with  p o s s i b l e to 470  V/8  is . certainly  b e c a u s e of  s e t of  the  s m a l l e r word s i z e binary  data  an  order  slow  the  an  slower  microprocessor  would d e c r e a s e could  microprocessor  be  of m a g n i t u d e  the  handled.  system  could  slower  f o r the c o m p u t a t i o n a l  microprocessor  a larger  a  design  I t w o u l d be  word  instructions  intensive  microcode.  being  be  than  bound  job  here.  bit-slice  time,  system.  more t h a n  system,  easily  l a n g u a g e ) i n t o p r o g r a m s aimed a t a  conventional  p r e v i o u s problems.  cycle  more  can  of  SPPBB  arithmetic is  that it  instruction  the  which  to perform  considered  Thus  is  the  algorithm,  i t is inefficient  smaller  with  mainframe  A  but  Furthermore,  a  it  Integer  instabilities  assembler  cycle  Consequently,  simple  [2],  microprocessor  parallelism  particular,  t h e p r o g r a m s w r i t t e n f o r t h e Amdahl  approach,  expected  since  calculations.  economical  system.  considered  numerical  360/370  time  In  algorithm  translate  IBM  described.  SPPBB i s a r e l a t i v e l y  "additive"  directly  be  3 make p o s s i b l e t h e d e f i n i t i o n  size  would  dedicated routines  faster  c o u l d be further  system could  such be  would overcome due  the  c o n s t r u c t e d , and improve  as  to  the  one  some of shorter special  efficiency. considered  implemented  entirely  In here, in  79  A more p o w e r f u l a r c h i t e c t u r e is  added t o the  suggested  by  manipulated partition as  few  in  can  several  32  instruction  the bounding due  in several  where  the  vast  overall  effect.  in  number o f  rows bits  i s an  easily  is  will  the  Furthermore,  t h e word s i z e  manipulated For  larger  time  required  problems  small  algorithm.  bounding  data  This  a word o f d a t a .  awkward c o m p u t a t i o n , handled  with s p e c i a l  but  On  most  fewer  efficiently (m >  in 32),  of  have  but  the  columns  procedure  i s manipulated, the  time  so  greatest  consuming  i n v o l v e s c o u n t i n g the  i n a column, or a t the machine l e v e l in  have  to manipulate  I t i s i n the  in  of the host  consume a g r e a t e r p r e c e n t a g e  enhancements t h e r e w i l l  SPPBB  problems  i s , most p r o b l e m s  observation concerns a  exercise  '1'  data  observation i s  test  bound.  m a j o r i t y of the problem  performance  Another  a lower  That  d a t a words.  clearly  be  V/8.  Another  f o r the  s m a l l e r than  to the bookkeeping  stored  that  rows.  operations.  procedure  the  partitioning  hundred  rows, t h u s p r o b l e m  single  time  470  in  large  spent computing  t h e Amdahl  columns  Remember  was  are  the  data i s  t h e column i n  3.2  3.2  most p r o b l e m  is  store  of the e x e c u t i o n time  of T a b l e  to  strategy  d a t a word would  75%  machine,  this  A large  i f s i m p l e hardware  design  First,  corresponding  possible.  have  This  about  problems  of  design.  observations•.  units  words as  Table  than  several  problem.  problems that  bit-slice  is possible  the  number  a g e n e r a l purpose  machine  i t i s a computation  hardware.  that  can  80  4.2  Special  Fiqure  Hardware  4.1  microprocessor could  be  is  design,  used  numeric  as  the  -Vje*Aj f o r e v e r y S  in  the data  hardware that  data  single  as  f o r every  value  variable.  The bus between  other  memory  has  been  is  organized  the  algorithm  the  cost  Binary vector  and data,  and t h e v a l u e of  search,  is  stored  memory a n d t h e s p e c i a l width.  Notice  bus i s n o t s h a r e d  w i t h any  word  between  hardware  Secondly,  I (page 4 0 ) .  R i s a binary vector  hardware  is  manipulation  the  two  units  S  is  indicating  the  efficient  current  partial  t h e rows c o v e r e d  by t h e b o u n d i n g  summation,  the  of data  F i g u r e 4.2 i s a f l o w c h a r t  is illustrated  the  First,  of l a r g e u n i t s  by S,  procedure.  i n F i g u r e 4.3.  two p a r t s , one c o n t a i n i n g  performing  two-fold.  i t permits  of the bounding procedure.  into  that  t o implement.  the e f f i c i e n t  special  of  matrix  data  T h i s makes t h e i n t e r f a c e  instructions.  been d i v i d e d  hardware,  memory  the  bit-slice  problem using the  data  of the branch-and-bound  T i s t h e rows t o be c o v e r e d  The  the  level  Bounding A l g o r i t h m  solution, and  Program  f u n c t i o n of the s p e c i a l  execution of  and  columns of t h e c o n s t r a i n t  simple  facilitates  with  memory  such  ratio  memory.  devices.  The  special  i s v e r y w i d e , a s wide a s t h e d a t a  relatively  it  Program  t h e d a t a memory/special hardware  other  for a  and c o n t a i n s a l l t h e code d e f i n i n g  cost-performance such  diagram  supplemented with  separated.  conventionally plus  block  t o solve the set p a r t i t i o n i n g  SPPBB a l g o r i t h m . physically  a  special  I t has  logic  and  E ^ a ^ - T ; ) , i n d i c a t e d by  81  D a t a Memory  BUS  ^Special  Hardware  -control -control statusJL Program  Memory  <C  BUS  ~p  pP  Controller  IT external interface signals  host  Figure  4.1:  computer  A system f o r s o l v i n g  interface  p a r t i t i o n i n g problems  Begin  Given: S*=  j Xj  { j  =  R=Vj * Aj , 6S  Initialize: LBC(S)=0 T=  1 } k  e-R  yes i  yes ,  LBC(S)=oo  Return  Fiqure  4.2:  Flowchart  of  Bounding A l g o r i t h m  I  83  R T registers Logic  load A R  update R  ([  BUS  y  |A AT k  - encoded sum  Co  T  w  JJP i n t e r f a c e s i g n a l s  F i g u r e 4.3:  row  Special  Hardware  i ^ ) - f  F i g u r e 4.4:  A row o f t h e s p e c i a l h a r d w a r e  (A  f c l  AT  t  )  84  |A AT|  i n F i g u r e 4.2.  K  corresponding in  the  logic  component. 16  build of  generated  computing  the  with  load'  'R  similar  the  of  the  signal  of  from  the  a  bit-slice  special  the R r e g i s t e r  to  handle  the  to size  the c o n t r o l l e r . v a l u e of  and  then  must p e r f o r m  indicate  if  4.3.  rectangular  boxes  The  last  logic.  remainder  A  implemented  C„  logic,  using  the  is  Consider  is illustrated  represents  true,  cell  logic,  as p a r t of  that  load' 4.2.  It  the  of  counting  must  update  T  logic  i n F i g u r e 4.4. i  (=1)  'T  operations.  lc  loaded  LBC(S) i s  four  A AR=0  in a  true  shown i n F i g u r e  K  the  was  is  by  latched  i s loaded  k  three o p e r a t i o n s are performed of  loaded  as  R=(A V R ) .  This  is  the T r e g i s t e r  updated  continues  u p d a t e R by  in Figure  is  hardware i n  i n d a t a memory, and  register  k  be  T  controlled  i n p u t width  the T  register.  could  w i t h an  the counter  |A AT | ,  The  and  u n i t s c o u l d be c a s c a d e d  i s f e t c h e d from  k  logic  the  R,  designed  |A AT|  special  of  c o u l d be  If signal  flow  i  registers  are  is  the R r e g i s t e r .  Program  row  4.3  as  signal.  K  unit  First,  initial  and  T=T-(A AT),  unit  function  bound.  updated,  compute  Figure  individual  identical  The  same t i m e  The  registers  appropriate location  manner.  value  three  microprocessor.  i s , a single  lower  the  the  in  now  addressing the  to  bus.  Consider  at  illustrated  functionally  the data  These the  That  access  k  by  rows o f d a t a , and  a  has  of t h e b i n a r y v e c t o r s A ,  procedure.  signals  The  logic  the values  bounding  through  say,  to  The  the  by  for Each  labeled  -by t h e  given  E^ .(a,- -), l  the p r e v i o u s l y d e s c r i b e d  K  logic,  85  but  i s more e a s i l y  implemented  the hardware c o u l d  be  built  using available  logic.  using encoders  and  be d i s c u s s e d .  Because  That  s i m p l e ROM  is,  lookup  tables.  4.3  A Few  A  few  intention  detail  are  to  thesis  CPU  has  typically  hardwired  the c o n t r o l  signals  be  in  System performance wide  data  problem. times  bus Bus  that  computers. width the  of  special  have t o be  of  the a l g o r i t h m . 250  execute  efficiently  nsec.  faster  than  controlled  by  i s improved the  by  the  using  so the  Also,  construction  inherent  parallelism  b i t word u s e d problems,  d a t a bus,  designed  is,  the  implementing  the  hardware.  That  every microsecond,  i m p l y i n g d a t a word w i d t h , c o u l d  large  CPUs  microcode.  exploit  32  microcoded  Bit-slice  width,  For the  to  be  microprocessor.  of a s t a n d a r d m i c r o c p r o c e s s o r .  hardware can  will  trade-offs  of s p e c i a l  are executed  r o u t i n e s can  instructions  t h e use  times around  instructions  simple microcoded  as a b i t - s l i c e  by  implement  operate with c y c l e  microcoded  hardware, d e t a i l s  the  design.  throughput  to  any  i t i s not  f o r the v a r i o u s performance  been d e s c r i b e d  c h o i c e improves  proposed  to b u i l d  account  macroinstructions  four  now  i n h e r e n t i n any  The This  will  of t h i s  generalized that  Details  For  by most  large  be  general  of  a  i n the several purpose  t h o s e h a v i n g more rows t h a n  the  d a t a w o u l d have t o be m u l t i p l e x e d i n t o this  to handle  case,  the  special  the m u l t i p l e x e d d a t a  logic word.  would  86  The  bit-slice  except  for  signals  to the s p e c i a l  data  word  the  processor  is  extended  ALU i s a component  be  handled  integer SPPBB  bit  For  instance,  relatively  small  Custom build.  The costs  could  sufficient  the  d a t a a 24 b i t Thus a 24  design.  Arithmetic  because  simple unsigned  and m u l t i p l i c a t i o n  is  can  be  always  i s used  handled  small,  say  circuits hardware  are  because  generally  described  low d e v e l o p m e n t  be k e p t low u s i n g  i n the  an  8 bit  a s an 8x24 |A |  is  k  a  problems.  expensive  in this  gates coupled with three  implies  can  efficiently  k  for large  design  the c o n t r o l  accuracy.  w i t h a 24 b i t r e s u l t ,  of l o g i c  simplicity  implement  |A /vT|- CPR(k) c a n be t r e a t e d  integrated  array  to  microcode  number, even  However  conventional  F o r the numeric  Multiplication  multiplication,  simple  in  one o f t h e o p e r a n d s  number.  a  i n the b i t - s l i c e  subtraction,  algorithm.  because  to insure  adequately  addition,  be  microcode  hardware.  needed  bit  would  semi-custom,  chapter i s a  data  costs.  to  registers.  Implementation  perhaps  gate  array,  technology.  The that 650  proposed  the  maximum  Kbytes  by t h e s p a c e  largest  sufficient. prices  problem  o f d a t a memory  dominated the  s y s t e m must h a n d l e  problem.  required  Program  to contain  memory  problems.  Suppose  be rn=500, n=lO,000.  i s required.  Semiconductor  affect  will  F o r t h e above  continue to f a l l .  seriously  size  large  case  100  of  t h e economy o f t h e s y s t e m .  will  the numeric Kbytes  is relatively  Thus t h e p r i c e  memory  Then, be  data f o r  should  be  i n e x p e n s i v e and  memory  should  not  87  The  hardware  described develop  should  costs  not  for  exceed  a  system  $15,000.  a p r o t o t y p e s y s t e m would  the  system.  fiqures build. a  two months would  With  large  that  mainframe,  than  s y s t e m would difficult  one  required  to  systems  t o debug  advantage  the be  larger a  cost  partitioning  anyone s o l v i n g  the  from t h e p r e v i o u s  be r e l a t i v e l y  many  proposed  close system.  two  inexpensive t o  way  and  to that  should  orders  Clearly  effective problems  system  to  design.  and e v a l u a t e  t h e throughput of t h e system comparable  price-performance better  the  4 t o 6 man-months f o r  t o be i n f e r r e d  t h e system would  to  time  of d i g i t a l  be r e q u i r e d  The i m p o r t a n t f a c t  is  The  be a b o u t  an e n g i n e e r e x p e r i e n c e d i n t h e a r e a An.additional  similar  of  of  enjoy  a  magnitude  then, the proposed  to  solve  large  and  s h o u l d be o f i n t e r e s t t o  of these types of problems.  88  CHAPTER Summary  This Chapters  chapter 3 and 4.  will  5  and C o n c l u s i o n s  summarize  Suggestions  for  the  results  further  obtained  research  in  will  be  made.  5.1  Summary  Chapter the  set  3 i n t r o d u c e d two new a l g o r i t h m s partitioning  branch-and-bound enumerative,  algorithm.  heuristic  relatively  simple,  programming  based  the  additional generated. large by  than  logic  first,  second, algorithm  algorithms  examining  strategy  is  SPPA*, (HPA).  guaranteed  t h e minimum  (Bounding  was  a  was  an  Both  are  to  linear  to  find  the  number o f nodes f o r  Algorithm  I).  It is  more  the branch-and-bound a l g o r i t h m because of the  r e q u i r e d t o handle  the  a t which p o i n t h e u r i s t i c  the  SPPBB,  compared  large  For l a r g e problems the candidate  to store,  pruning  path  compact  by  bounding  sophisticated  The  a HPA a l g o r i t h m ,  solution  given  The  algorithms.  SPPA*, b e i n g optimal  problem.  f o r the s o l u t i o n of  candidate  list.  candidate  list  c a n become t o o  solutions  Experience  list  were o b t a i n e d  shows t h a t  such  89  heuristic  techniques  often  sophisticated  pruning  of  optimal  finding  an  yield  heuristics  optimal  would  solution.  solutions.  increase  This  the  remains  More  probability  an  area  for  further investigation.  SPPA* r e p r e s e n t s in  integer  application may  a departure  linear  programming.  suggests  that other  b e n e f i t by  adopting  an  A*  Performance e v a l u a t i o n comparing Lasky's  test  results  branch-and-bound  algorithm  was  i t was  available  generated data  using  listed  the  i n Appendix  those  which  wishing  Test algorithm new  aids  Lasky In  some c a s e s  new  algorithms,  less  than  half  i n A p p e n d i x A,  have of  and  Lasky's to the  problems and  the  u s e d so  to  the  Pierce  new  partitioning  Test  SPPBB, SPPA*, and 3.6.1.  significantly  particularily  be  test  SPPA* f o u n d  ratio  the  t i m e of  better  were input  that  the  explicitly problems  P i e r c e and  for  Lasky  show  that  the  the  Pierce  and  than  more d i f f i c u l t  exceeded  optimal  the  the  Results  f o r the  performance  the  better  a p p r o a c h was  by  and  similarity  the  portability  in Section  perform  the  its  made  results.  using  listed  algorithm,  This  algorithms  the  Pierce  of  particular  was  using  literature.  listed  B.  i n the  t o compare  algorithms  algorithms  p r o b l e m s w o u l d not  results are  the  program  numerous l a r g e t e s t listed,  in  one  in this  seen  strategy.  obtained  of  algorithms  programming  algorithm.  because  algorithms  new  those  because  and  integer  the  chosen  algorithms,  I t s success  branching  of  with  from p r e v i o u s  50.  Comparing  s o l u t i o n , on  SPPBB a l g o r i t h m .  problems.  average,  the in  However, f o r  90  the  larger  problems  solution,  although  only  SPPBB  could  SPPA* d i d f i n d  guarantee  the optimal  an  optimal  solution  i n most  cases.  The  heuristic  behavior  algorithm  was  bounding  function.  stage  approach  partitioning obtain  a  solution the  good  a weighting very  the optimal  During  sub-optimal  a  without  solution  which then  solution stage  in  search  finds  bound.  cost.  the  Thus,  to  to  a two large  time.  This  I t i s passed  optimal than  very  the  SPPA* i s used t o  minimal  t r e e much s m a l l e r  an u p p e r  factor  good, s u g g e s t i n g  the f i r s t  branch-and-bound a l g o r i t h m s  solution  the search  to by  tree  t h e s t r e n g t h s o f t h e A*  have been c o m b i n e d  i n t o a unique  algorithm.  Pierce modified  and  Lasky  to obtain  optimal  constraints solution the  were  SPPA* a l g o r i t h m as a HPA  i s an u p p e r bound on t h e o p t i m a l  generated  the  Results  for finding  SPP a l g o r i t h m ,  hybrid  the  i n v e s t i g a t e d by a d d i n g  problems.  investigating  and  of  describe  the k-best  solution.  is  the  best  their  solutions,  This  a r e not e x p l i c i t l y  how  rather  approach built  solution  a l g o r i t h m c o u l d be  is  into  than  useful  t h e SPP.  from t h e k - b e s t  the when  The  just side  optimal  which  satisfies  side constraints.  SPPA*  c a n be e a s i l y  That  i s , the f i r s t  the  k-best  algorithm  increasingly  favor  to find  k solutions discovered  solutions. compared  modified  to  Furthermore,  the k-best by t h e  algorithm  are  p e r f o r m a n c e o f t h e SPPA*  branch-and-bound  SPPA* a s k i n c r e a s e d .  solutions.  algorithms  The ' k - b e s t '  would  idea a l s o  91  applies  to the  solutions,  the  Increasing  yet  the  best  k would  solution optimal  heuristic  would search  versions  solution  increase  be  t r e e may  studied  in  Test  results  confirmed  even  the  bottleneck.  computational a good s u b - o p t i m a l  could  discussed  i n the  values  the  of  Bounding  [10,11], than  area  for  To  linear  further  solve  algorithm  problems  the  a  k-best  solution.  the  optimal  fraction  These  reduced  of  ideas  linear  most SPP  costs  problem  the have  From S e c t i o n  solution  to  using  Section  2.7.  This  one For  improved  methods  investigated  to s o l v e  the  costs could linear  would  the  instance,  I I , then  reduced  could  be  be  problem.  that  estimated  the  using  iterative  by  Etcheberry  obtained This  be  methods  obtained  using  a  i t is clear  suggests  of  the  i s often  SPP  I  or  to obtain  2.9  the  reduced c o s t s .  reduced  for solving  algorithms,  variables  in  less  remains  an  research.  set c o v e r i n g SCPA*, was  suggests  that  p e r f o r m a n c e of  problems, a modified introduced. for the  small  version  A limited and  algorithm  SCP  algorithms.  H e u r i s t i c SCPA* s o l u t i o n s  and  results  good.  were  that  dual  good  i t takes  SPPA* a l g o r i t h m , the  of  optimization Thus,  time  linear  be  survey  Algorithm  subgradient  by  c a l c u l a t e the  bottleneck  of  s o l v i n g the  major  the  optimal  though o n l y  use  shared  to  the  the  detail.  Nevertheless,  sufficient  Of  probability  reduced c o s t s , a step  that  be  have been e x a m i n e d .  t o be  SPP.  SPPA*.  may  the  found,  of  of  evaluation  intermediate  i s comparable were  the  also  to  of  size other  examined  92  The  advantage  traditional  linear  simplicity  and  linear  numbers.  data  as  new  programming  efficient  system  values  i s used  Chapter  based a l g o r i t h m s  usage  design  for cost  could  exploit  the  w o u l d be  organized  be  parallelism  The  as  data  example,  as  floating  word,  constraint  and  integer  microprocessor  t o s o l v e the p a r t i t i o n i n g  in  bus, the  and  in  about  using  the  based  problem.  hardware,  attached  cost e f f e c t i v e  problems without  special  SPPBB a l g o r i t h m .  a p e r i p h e r a l device  but  data  relative  For  manipulates  inexpensive  s y s t e m w o u l d be  mainframe computer, a mainframe  resources. problem  in  is its  the  calculations.  used  large partitioning  5.2  a l l  i n c l u d e s a wide d a t a  computer.  of  packed  4 i n t r o d u c e d an  that  set c o v e r i n g a l g o r i t h m over  However, SCPA* s t o r e s and  binary  arithmetic  solve  the  programming m a n i p u l a t e s  point  The  of  The  to  the  same  expensive  system  the  because  to  host  i t could time  as  resources  of  computer.  Conclusions In c o n c l u s i o n , t h i s  partitioning algorithms important  algorithms currently  because  applications computers. particular promises  thesis  two  yet  a  introduced  represent literature.  partitioning can  take  algorithms  advantages.  t o be  i n the  large  and The  that  has  an  hours  Such  to  i n t r o d u c e d each  technique  for  efficient  improvement  problems  A hybrid algorithm  strong  two  upon  improvements have  mainframe their  own  t h a t combines the handling  are  important  s o l v e on have  set  very  two  large  93  problems. developed  The are  strong  heuristic  important  due  techniques  to the  that  NP-complete  have  nature  of  been the  problem.  The these  microprocessor  problems  expensive  This  can  chapter stemming  in  thesis  be  be  developed  has from  system  solved  r e s o u r c e s of a l a r g e  research this  based  made this  efficiently  showed  without  using  that the  computer.  several  work.  i t is possible  introduced  that  to solve p a r t i t i o n i n g  Using even  suggestions the  results  for  further  presented  stronger techniques  problems.  can  94  Biblioqraphy  1.  Arabeyre, J . P., F e a r n l e y , J . , S t e i g e r , F. C, Teather, W., "The A i r l i n e Crew S c h e d u l i n g P r o b l e m : A S u r v e y , " Transportation Science, V o l . 3, No. 2, 1969, pp. 140-163.  2.  B a l a s , E . , "An A d d i t i v e A l g o r i t h m f o r S o l v i n g L i n e a r P r o g r a m s w i t h Zero-One V a r i a b l e s " , O p e r a t i o n s R e s e a r c h , Vol. 13, 1965, pp. 517-546.  3.  B a l a s , E . , P a d b e r g , M. W., "On t h e S e t C o v e r i n g P r o b l e m , II. An A l g o r i t h m f o r S e t P a r t i t i o n i n g , " O p e r a t i o n s Research, V o l . 23, 1975, pp. 74-90.  4.  B a l a s , E . , P a d b e r g , M. W., "Set P a r t i t i o n i n g : SIAM R e v i e w , V o l . 1 8 , No. 4, O c t o b e r 1976, pp.  5.  B a l i n s k i , M. L., Quandt, R. E . , "On an I n t e g e r P r o g r a m for a D e l i v e r y Problem," O p e r a t i o n s Research, V o l . 12, 1964, pp.300-304.  6.  B e l l m o r e , M., R a t l i f f , K. D., " S e t C o v e r i n g and I n v o l u t o r y B a s e s " , Management S c i e n c e s , V o l . 18, No. 3, November 1971, pp. 194-206.  7.  C h v a t a l , V., "A G r e e d y H e u r i s t i c f o r t h e S e t - C o v e r i n g P r o b l e m , " M a t h e m a t i c s of O p e r a t i o n s R e s e a r c h , V o l . 14, No.3, A u g u s t 1979, pp. 233-235.  8.  Cobham, A., N o r t h , J . H., " E x t e n s i o n s of t h e I n t e g e r L i n e a r Programming A p p r o a c h t o t h e M i n i m i z a t i o n o f B o o l e a n F u n c t i o n s , " Res. Rep. RC-915, IBM, 1963.  9.  Day, R. H., "On O p t i m a l E x t r a c t i n g from a M u l t i p l e D a t a S t o r a g e S y s t e m : An A p p l i c a t i o n of I n t e g e r Programming," O p e r a t i o n s R e s e a r c h , V o l . 13, 1965, pp. 482-494.  10.  Etcheberry, J . , "The S e t R e p r e s e n t a t i o n P r o b l e m , " t h e s i s , The U n i v e r s i t y of M i c h i g a n , A u g u s t 1974.  11.  E t c h e b e r r y , J . , "The S e t - C o v e r i n g P r o b l e m : A New Implicit Enumeration A l g o r i t h m , " O p e r a t i o n s Research, V o l . 25, 1977, pp. 760-772.  12.  G a r f i n k l e , R. S., Nemhauser, G. L., "The S e t - P a r t i t i o n i n g Problem: Set C o v e r i n g w i t h E q u a l i t y C o n s t r a i n t s , " Operations Research, V o l . 17, 1969, pp. 848-856.  A Survey," 710-761.  File  Ph.D.  95  13.  G a r f i n k l e , R. S., Nemhauser, G. L., "Optimal P o l i t i c a l D i s t r i c t i n g by I m p l i c i t E n u m e r a t i o n T e c h n i q u e s , " Management S c i e n c e , V o l . 16, 1970, pp. B495-B508.  14.  G a r f i n k l e , R. S., Nemhauser, J o h n W i l e y , New Y o r k , 1972.  15.  Gomory, R. Res. Rep. Industrial  16.  H a r t , P., N i l s o n , P. N., R a p h a e l , B., "A F o r m a l B a s i s f o r t h e H e u r i s t i c D e t e r m i n a t i o n o f Minimum C o s t P a t h s , " I E E E Trans. Sys. S c i . and C y b e r . , V o l . SSC-4, No. 2, 1968, pp.100-107.  17.  H e l d , M., K a r p , R. M., "The T r a v e l i n g - S a l e s m a n Minimum S p a n n i n g T r e e s : P a r t I I , " M a t h e m a t i c a l Programming 1, 1971, pp. 6-25.  18.  H e l d , M., W o l f e , P., C r o w d e r , H., " V a l i d a t i o n of S u b g r a d i e n t O p t i m i z a t i o n , " M a t h e m a t i c a l Programming 1974, pp. 62-68.  G.  L., I n t e g e r  Programming,  E . , "An A l l - I n t e g e r Programming A l g o r i t h m , " IBM RC-189, J a n u a r y 1960; also S c h e d u l i n g , P r e n t i c e - H a l l , 1963, pp. 193-206.  P r o b l e m and  6,  19.  Lemke, C. E . , S a l k i n , H. M., S p i e l b e r g K., " S e t C o v e r i n g by S i n g l e B r a n c h E n u m e r a t i o n w i t h L i n e a r Programming S u b 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 . 19, 1971, pp. 998-1022.  20.  M a r s t e n , R. E . , "An A l g o r i t h m f o r L a r g e S e t P r o b l e m s , " Management S c i e n c e , V o l . 20, No. pp. 774-787.  21.  P a d b e r g , M. W., " C o v e r i n g , P a c k i n g , and K n a p s a c k P r o b l e m s , " A n n a l s of D i s c r e t e M a t h e m a t i c s 4, 1979, pp. 265-287.  22.  P i e r c e , J . F., " A p p l i c a t i o n of C o m b i n i t o r i a l Programming t o a C l a s s o f A l l - Z e r o - O n e I n t e g e r Programming P r o b l e m s , " Management S c i e n c e , V o l . 15, No. 3, 1968, pp. 191-209.  23.  P i e r c e , J . F., L a s k y , J . S., "Improved C o m b i n a t o r i a l Programming A l g o r i t h m s f o r a C l a s s o f A l l - Z e r o - O n e I n t e g e r Programming P r o b l e m s , " Management S c i e n c e , V o l . 19, No. 3, 1973, pp. 528-543.  24.  P o h l , I . , " P r a c t i c a l and T h e o r e t i c a l C o n s i d e r a t i o n s i n H e u r i s t i c S e a r c h A l g o r i t h m s , " M a c h i n e I n t e l l i g e n c e 8, 1977, pp. 55-72.  25.  Pyne, I . Implicant  Partitioning 5, 1974.  B., McClusikey, E . J . , "An E s s a y on P r i m e T a b l e s , " SIAM J . , V o l . 9, 1961, pp. 604-631.  96  26.  Q u i n e , W. V., "A Way o f S i m p l i f y i n g T r u t h F u n c t i o n s , " Am. Math. Mon., V o l . 62, 1955, p p . 627-631.  27.  S a l k i n , H. M., K o n c a l , R. D., "A P s e u d o - D u a l A l l - I n t e g e r A l g o r i t h m f o r t h e S e t Covering Problem," Dept. of Oper. Res. Tech. Memo. 204, Case W e s t e r n U., C l e v e l a n d , O h i o , Nov. 1970.  28.  S a l k i n , H. M., K o n c a l , R. D., "A D u a l A l l - I n t e g e r A l g o r i t h m ( i n r e v i s e d s i m p l e x form) f o r t h e S e t C o v e r i n g Problem," Dept. of Oper. Res. Tech. Memo. 250, Case W e s t e r n R e s e r v e U., C l e v e l a n d , O h i o , A u g . 1971.  29.  S a l k i n , H. M., K o n c a l , R. D., " S e t C o v e r i n g Integer Algorithm: Computational Experience," 2 0 ( 2 ) , A p r i l 1973, pp.189-193.  30.  S c h r a n g e , L . , "A More P o r t a b l e F o r t r a n Random Number G e n e r a t o r , " ACM T r a n s . Math. Software, V o l . 5 ( 2 ) , June 1979, p p . 132-138.  31.  S p i e l b e r g , K., " E n u m e r a t i v e Methods i n I n t e g e r P r o g r a m m i n g , " A n n a l s o f D i s c r e t e M a t h e m a t i c s 5, 1979, pp. 139-183.  by an A l l J . ACM, V o l .  97  APPENDIX A A Program  f o r Generating  The p r o g r a m GENTEST g e n e r a t e s test  problems  reproducible  using  through  and  27  input/output  1 2 3 4. 5 c 7 8 9 10 1 1 12 13 1 4 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35  C C C C C  r \—  c  used  in  this  the input data 65  through  Test  the p a r t i t i o n i n g thesis. given  106  Problems  can  The  and c o v e r i n g problems  i n A p p e n d i x B. be  Lines  f o r m a t d e s i r e d by t h e u s e r .  P r o g r a m GENTEST - T h i s p r o g r a m g e n e r a t e s random b u t r e p r o d u c i b l e p a r t i t i o n i n g problems a c c o r d i n g to the input d a t a s u p p l i e d by t h e u s e r . INTEGER P ( 7 6 8 ) / 7 6 8 * 1 / , C 0 S T ( 7 6 8 ) / 7 6 8 * 1 / INTEGER L I S T ( 1 ) / ' * ' / , E L I N E ( 7 6 8 ) , P M A X , F X INTEGER EINDEX(128)/128*0/,MAXIX/2147483647/ INTEGER*2 E ( 1 2 8 , 1 5 0 )  c  c  10 20 30 40  c c c  Input s i z e seed v a l u e PRINT10 READ(5,LI PRINT20 READ(5,LI PRINT30 READ(5,LI PRINT4 0 READ(5,LI  and d e n s i t y o f c o n s t r a i n t m a t r i x , f o r random number g e n e r a t o r .  and  ST) N ST) M ST) D ST) IX  FORMAT('-','INPUT N: ) FORMAT(' ','INPUT M: ') FORMAT(' ','INPUT D e n s i t y : ' ) FORMAT(' ','INPUT Seed v a l u e : ' ) 1  P l a c e a '1' i n e v e r y c o l u m n t r i v i a l zero columns.  (-  DO 50 J=1,N CALL RAND(IX) I=(IX/(MAXIX/M))+1 EINDEX(I)=EINDEX(I)+1  15  changed t o s u i t the  \~  C C  are  to ensure there  a r e no  98  36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89  50 C C C C C  60 C  70 C C C C  80 C C C  90 100  J1=EINDEX(l) E(I,J1)=J P l a c e '1's a t random i n m a t r i x . E I N D E X ( I ) r e c o r d s no. o f '1's i n row. P ( J ) r e c o r d s no. o f '1's i n c o l u m n . NONES=D*N*M-N DO 60 K=1,NONES CALL RAND(IX) I=(IX/(MAXIX/M))+1 CALL RAND(IX) J=(IX/(MAXIX/N))+1 EINDEX(I)=EINDEX(I)+1 J1=EINDEX(I) E(I,J1)=J P(J)=P(J)+1 PMAX=max{P(J)} PMAX=1 DO 70 J=1,N I F ( P ( J ) . G T . P M A X ) PMAX=P(J) Calculate cost vector. proportional to P ( J ) .  COST(J)  i s roughly  DO 80 J=1,N CALL RAND(IX) K=(IX/(MAXIX/41)) C0ST(J)=(P(J)*2*(100+K-20))/PMAX Print  c o s t s , 25 v a l u e s  per  line.  KL=1 KH=25 NT=(N/25) IF(NT.EQ.O) GOTO 100 DO 90 L=1,NT WRITE(7,110) ( C O S T ( J 1 ) , J 1 = K L , K H ) KL=KL+25 KH=KH+25 I F ( K L . G T . N ) GOTO 120 WRITE(7,110) ( C O S T ( J 1 ) , J 1 = K L , N ) FORMAT(' ' , 2 5 1 4 ) ';' d e l i m i t s t h e c o s t s from t h e c o n s t r a i n t s WRITE(7,130) FORMATC;')  110 C 120 130 C C PRINT m a x t r i x E ( i , j ) i n e x p l i c i t 0,1 b i n a r y f o r m a t . C I f N>128, p r i n t e a c h row i n c o n s e c u t i v e l i n e s C o f 128 c h a r a c t e r s maximum l e n g t h . C NT=NT/128 DO 190 1=1,M DO 150 J=1,N  99  90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 1 18 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134  150  160 C  170 180 190 200  C C C C C C  ELINE(J)=0 NR0W=EINDEX(I) DO 160 J1=1,NROW J=E(I,J1) ELINE(J)=1 KL=1 KH=128 IF(NT.EQ.O) GOTO 180 DO 170 L=1,NT WRITE(7,200) (ELINE(J1 ) , J1=KL,KH) KL=KL+128 KH=KH+128 I F ( K L . G T . N ) GOTO 190 WRITE(7,200) ( E L I N E ( J 1 ) , J 1 = K L , N ) CONTINUE FORMAT(' ',12811) STOP END  RAND i s a p o r t a b l e no. g e n e r a t o r d e s c r i b e d by S c h r a n g e i n "ACM T r a n s a c t i o n s on M a t h e m a t i c a l S o f t w a r e , " V o l . 5, No. 2, June 1979. SUBROUTINE RAND(IX) INTEGER A,P,IX,B15,B16,XHI,XALO,LEFTLO,FHI,K DATA A/16807/,B15/32768/,B16/65536/,P/2147483647/  C C C C C C C C  G e t 15 h i g h o r d e r b i t s o f IX XHI=IX/B16 G e t 16 low o r d e r b i t s a n d f o r m low p r o d u c t XAL0=(IX-XHI*B16)*A G e t 15 h i g h o r d e r b i t s o f low p r o d u c t LEFTLO=XALO/B16 Form t h e 31 h i g h e s t b i t s o f f u l l p r o d u c t FHI=XHI*A+LEFTLO Get o v e r f l o past 31st b i t of f u l l product K=FHI/B15 A s s e m b l e a l l t h e p a r t s and p r e s u b t r a c t P IX=(((XAL0-LEFTL0*B16)-P)+(FHI-K*B15)*B16)+K Add P back i n i f n e c e s s a r y I F ( I X . L T . O ) IX=IX+P RETURN END  100  APPENDIX B Input Data  The generates  following  is a list  the problems used  Problem  f o r the Test  Problems  of the input  in this  data  t o GENTEST w h i c h  thesis.  N  M  Density  Seed V a l u e  C1  90  30  .110  15  C2  90  30  .235  2  C3  90  30  .37  17  C4  90  50  .235  7  C5  90  40  .235  12  CG  50  30  .235  1 1  C7  70  30  .235  14  P1  1 20  15  .23  8  P2  90  15  .23  22  P3  1 20  30  .075  1  P4  1 20  30  .074  29  P5  200  30  .074  10  P6  400  30  .074  1  P7  400  40  .073  15  P8  400  50  .073  3  

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-0065574/manifest

Comment

Related Items