UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

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

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

Item Metadata

Download

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

Full Text

c,/ COVERING RELAXATION METHODS FOR SOLVING THE ZERO-ONE P O S I T I V E POLYNOMIAL PROGRAMMING PROBLEM B . S c , U n i v e r s i t y o f B r i t i s h C o l u m b i a , 1978 A T H E S I S SUBMITTED IN P A R T I A L F U L F I L L M E N T OF THE REQUIREMENTS FOR THE DEGREE OF THE FACULTY OF GRADUATE STUDIES ( D e p a r t m e n t o f C o m p u t e r S c i e n c e ) 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 t o t h e r e q u i r e d s t a n d a r d . THE U N I V E R S I T Y OF B R I T I S H COLUMBIA A p r i l 30, 1980 (c ) W i l l e m V a e s s e n , 1980 MASTER OF S C I E N C E i n In presenting 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 the requirements f o r an advanced degree at the U n i v e r s i t y of 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 i t f r e e l y a v a i l a b l e f o r reference and study. I f u r t h e r agree that permission f o r extensive 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 granted by the Head of my Department or by h i s r e p r e s e n t a t i v e s . I t i s understood that copying or p u b l i c a t i o n of t h i s t h e s i s f o r f i n a n c i a l gain s h a l l not be allowed without my w r i t t e n permission. Department of The U n i v e r s i t y of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 D E - 6 B P 7 5 - 5 1 1 E ABSTRACT C o v e r i n g r e l a x a t i o n a l g o r i t h m s w e r e f i r s t d e v e l o p e d by G r a n o t e t a l f o r s o l v i n g p o s i t i v e 0-1 p o l y n o m i a l p r o g r a m m i n g (PP) p r o b l e m s w h i c h m a x i m i z e a l i n e a r o b j e c t i v e f u n c t i o n i n 0-1 v a r i a b l e s s u b j e c t t o a s e t o f p o l y n o m i a l i n e q u a l i t i e s c o n t a i n i n g o n l y p o s i t i v e c o e f f i c i e n t s [ " C o v e r i n g R e l a x a t i o n f o r P o s i t i v e 0-1 P o l y n o m i a l P r o g r a m s " , Management S c i e n c e , V o l . 25, ( 1 9 7 9 ) ] . The c o v e r i n g r e l a x a t i o n a p p r o a c h a p p e a r s t o c o p e s u c c e s s f u l l y w i t h t h e n o n - l i n e a r i t y o f t h e PP p r o b l e m and i s a b l e t o s o l v e m o d e s t s i z e (40 v a r i a b l e s a n d 40 c o n s t r a i n t s ) s p a r s e PP p r o b l e m s . T h i s t h e s i s d e v e l o p s a more s o p h i s t i c a t e d c o v e r i n g r e l a x a t i o n m e t h o d w h i c h a c c e l e r a t e s t h e p e r f o r m a n c e o f t h i s a p p r o a c h , e s p e c i a l l y when s o l v i n g PP p r o b l e m s w i t h many t e r m s i n a c o n s t r a i n t . B o t h t h e o r i g i n a l c o v e r i n g r e l a x a t i o n a l g o r i t h m a n d t h e n e w l y i n t r o d u c e d a c c e l e r a t e d a l g o r i t h m a r e c u t t i n g p l a n e a l g o r i t h m s i n w h i c h t h e r e l a x e d p r o b l e m i s t h e s e t c o v e r i n g p r o b l e m and t h e c u t t i n g p l a n e s a r e l i n e a r c o v e r i n g c o n s t r a i n t s . I n c o n t r a s t w i t h o t h e r c u t t i n g p l a n e m e t h o d s i n i n t e g e r p r o g r a m m i n g , t h e a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m d e v e l o p e d i n t h i s t h e s i s d o e s n o t s o l v e t h e r e l a x e d p r o b l e m t o o p t i m a l i t y a f t e r t h e i n t r o d u c t i o n o f t h e c u t t i n g p l a n e c o n s t r a i n t s . R a t h e r , t h e a u g m e n t e d r e l a x e d p r o b l e m i s f i r s t s o l v e d a p p r o x i m a t e l y a n d o n l y i f t h e a p p r o x i m a t e s o l u t i o n i s f e a s i b l e t o t h e PP p r o b l e m i s t h e r e l a x e d p r o b l e m s o l v e d t o o p t i m a l i t y . The p r o m i s e o f t h i s a p p r o a c h s t e m s f r o m t h e e x c e l l e n t p e r f o r m a n c e o f a p p r o x i m a t e p r o c e d u r e s f o r s o l v i n g i n t e g e r p r o g r a m m i n g p r o b l e m s . I n d e e d , t h e e x t e n s i v e c o m p u t a t i o n a l e x p e r i m e n t s t h a t w e r e p e r f o r m e d show t h a t t h e a c c e l e r a t e d a l g o r i t h m h a s r e d u c e d b o t h t h e number o f s e t c o v e r i n g p r o b l e m s t o be s o l v e d a n d t h e o v e r a l l t i m e r e q u i r e d t o s o l v e a PP p r o b l e m . The i m p r o v e m e n t s a r e p a r t i c u l a r l y s i g n i f i c a n t f o r PP p r o b l e m s w i t h many t e r m s i n a c o n s t r a i n t . i i i T A B L E OF CONTENTS 1. I n t r o d u c t i o n 1 2. M a t h e m a t i c a l P r e l i m i n a r i e s 7 3. The C o v e r i n g R e l a x a t i o n A p p r o a c h 12 4. E v a l u a t i o n o f t h e B a s i c C o v e r i n g R e l a x a t i o n A l g o r i t h m 19 5. M o d i f i c a t i o n s o f t h e C o v e r i n g R e l a x a t i o n A p p r o a c h 21 6. G r e e d y - l i k e A p p r o x i m a t e P r o c e d u r e s 32 6.1 G r e e d y - l i k e p r o c e d u r e s f o r t h e SC P r o b l e m 33 6.2 G r e e d y - l i k e p r o c e d u r e s f o r t h e MC P r o b l e m 37 7. E v a l u a t i o n o f t h e A c c e l e r a t e d C o v e r i n g R e l a x a t i o n A l g o r i t h m 39 7.1 A s p e c t s o f t h e I m p l e m e n t a t i o n 40 7.2 P r o b l e m G e n e r a t o r 45 7.3 C o m p u t a t i o n a l R e s u l t s 47 8. B i b l i o g r a p h y 61 9. A p p e n d i x : T h r e e B e n c h m a r k P r o b l e m s 64 LIST OF TABLES Table I 53 Table II 54 Table I I I 55 Table IV 56 Table V 57 Table VI 58 LIST OF FIGURES F i g u r e 1. CPU Time Use 59 F i g u r e 2. Method I vs Method VA 60 ACKNOWLE DGEMENT I w o u l d l i k e t o t h a n k p r o f e s s o r P a u l C. G i l m o r e f o r h i s a d v i c e a n d e n c o u r a g e m e n t ; my t h e s i s s u p e r v i s o r s , p r o f e s s o r s F r i e d a a n d D a n i e l G r a n o t , f o r t h e i r g u i d a n c e a n d f i n a n c i a l s u p p o r t ; a n d I h o r Gowda f o r t a k i n g an i n t e r e s t i n my w o r k . T h i s t h e s i s i s d e d i c a t e d t o Z e r o a n d One. 1 1. I n t r o d u c t i o n T h i s t h e s i s c o n s i d e r s a n d d e v e l o p s m e t h o d s f o r s o l v i n g t h e p o s i t i v e 0-1 p o l y n o m i a l p r o g r a m m i n g p r o b l e m (PP) w h i c h m a x i m i z e s a l i n e a r o b j e c t i v e f u n c t i o n i n 0-1 v a r i a b l e s t h a t i s c o n s t r a i n e d by a s e t o f p o l y n o m i a l i n e q u a l i t i e s c o n t a i n i n g o n l y p o s i t i v e c o e f f i c i e n t s . I t i s o f t h e f o r m : n MAX E C f t X h h = l s u b j e c t t o F.[ (x) < b i i = l , ... ,m (PP) x n € {0,1} h = l , ... ,n w h e r e f o r e a c h h , i and j P U ) F i ( x ) = > a i j TT x k ; j = l k S N i j a ^ j > 0; cjj > 0 a n d N ^ j i s a s u b s e t o f N = { l , 2 , ... ,n}. N ^ j i s t h e s e t o f v a r i a b l e s i n j t h t e r m o f t h e i t h c o n s t r a i n t . F i w i l l be r e f e r r e d t o a s a p o s y n o m i a l s i n c e i t i s a p o l y n o m i a l w i t h o n l y p o s i t i v e c o e f f i c i e n t s . G e n e r a l p o l y n o m i a l c o n s t r a i n t s i n 0-1 v a r i a b l e s w e r e f o u n d t o be u s e f u l f o r m o d e l i n g d i v e r s e p r o b l e m s i n b u s i n e s s a n d e n g i n e e r i n g . F o r e x a m p l e , t h e y a r e u s e d t o i n c o r p o r a t e r i s k i n t o c a p i t a l b u d g e t i n g [ 2 2 ] , t o p l a n i r r i g a t i o n s y s t e m s [ 2 1 ] , t o 2 p e r f o r m c l u s t e r a n a l y s i s [ 2 4 ] , a n d t o f o r m u l a t e v a r i o u s s c h e d u l i n g p r o b l e m s [ 1 7 , 2 3 ] . T h i s t h e s i s , h o w e v e r , f o c u s e s on t h e p o s i t i v e p o l y n o m i a l p r o b l e m . M e t h o d s o f S o l u t i o n T h e PP p r o b l e m , l i k e many o t h e r w e l l known m a t h e m a t i c a l o p t i m i z a t i o n p r o b l e m s , s u c h a s t h e t r a v e l l i n g s a l e s m a n o p t i m i z a t i o n p r o b l e m , i s a t l e a s t a s h a r d t o s o l v e a s a n y o n e o f t h e n o t o r i o u s l y d i f f i c u l t N P - c o m p l e t e p r o b l e m s . The m e t h o d s t h a t h a v e b e e n p r o p o s e d i n t h e l i t e r a t u r e f o r s o l v i n g t h e PP p r o b l e m e m p l o y a t some s t a g e an e n u m e r a t i o n t e c h n i q u e f o r s e a r c h i n g v e r y l a r g e s o l u t i o n s p a c e s . The two m a j o r m e t h o d s a r e t h e l i n e a r i z a t i o n a n d t h e b o o l e a n a l g e b r a a p p r o a c h e s . N e i t h e r a p p r o a c h t a c k l e s t h e n o n - l i n e a r i t y o f t h e PP p r o b l e m d i r e c t l y . B o t h a p p r o a c h e s s o l v e t h e PP p r o b l e m b y r e d u c i n g i t t o a l e s s c o m p l e x l i n e a r p r o b l e m . The l i n e a r i z a t i o n a p p r o a c h [ 8 , 9 , 2 9 ] t r a n s f o r m s t h e PP p r o b l e m i n t o an e q u i v a l e n t 0-1 l i n e a r p r o g r a m m i n g p r o b l e m . E a c h d i s t i n c t t e r m i n a PP p r o b l e m i s r e p l a c e d by a new v a r i a b l e a n d a d d i t i o n a l c o n s t r a i n t s a r e i n t r o d u c e d t o e n s u r e t h a t t h e v a l u e s o f t h e t e r m a n d t h e new v a r i a b l e c o i n c i d e . E x p l i c i t l y , l e t T j i = t/l X|<. T h e n T ^ J c a n be r e p l a c e d by a new 0-1 v a r i a b l e k S N i j y i j i n e v e r y c o n s t r a i n t i n w h i c h T ^ j o c c u r s i f t h e f o l l o w i n g two l i n e a r c o n s t r a i n t s , w h i c h a r e w r i t t e n i n t e r m s o f t h e o r i g i n a l 0-1 v a r i a b l e s x ^ a n d t h e new v a r i a b l e s Y i j , a r e s a t i s f i e d : 3 £ x k ± Y i j + | N i j | - 1 > x k > | N i j | y i j . k G N i j A s l i g h t l y more e f f i c i e n t t r a n s f o r m a t i o n t h a t r e d u c e s t h e number o f c o n s t r a i n t s i s p o s s i b l e , s e e [ 9 ] . B u t i t was f o u n d t o be l e s s e f f e c t i v e c o m p u t a t i o n a l l y . The number o f v a r i a b l e s i n t h e t r a n s f o r m e d 0-1 l i n e a r p r o g r a m m i n g p r o b l e m i s p o t e n t i a l l y v e r y l a r g e s i n c e t h e p o s s i b l e number o f p o s y n o m i a l t e r m s i n c r e a s e s e x p o n e n t i a l l y w i t h t h e number o f v a r i a b l e s i n t h e o r i g i n a l PP p r o b l e m . I n [ 2 6 , 2 7 ] an i m p l i c i t e n u m e r a t i o n a l g o r i t h m f o r s o l v i n g t h e t r a n s f o r m e d 0-1 l i n e a r p r o g r a m m i n g p r o b l e m h a s b e e n d e v e l o p e d i n w h i c h t h e a d d i t i o n a l c o n s t r a i n t s i n t r o d u c e d by t h e l i n e a r i z a t i o n p r o c e s s a r e o n l y c o n s i d e r e d i m p l i c i t l y . T h i s a p p r o a c h o b v i o u s l y s u f f e r s f r o m t h e same d r a w b a c k a s t h e s t a n d a r d l i n e a r i z a t i o n a p p r o a c h . The c o m p u t a t i o n a l r e s u l t s r e p o r t e d i n [ 2 6 , 2 7 ] u n d e r s c o r e t h i s c o n c l u s i o n . U s i n g b o o l e a n a l g e b r a t e c h n i q u e s , G r a n o t a n d Hammer [14] h a v e shown c o n s t r u c t i v e l y t h a t e v e r y PP p r o b l e m i s e q u i v a l e n t t o a l i n e a r s e t c o v e r i n g p r o b l e m i n t h e c o m p l e m e n t i n g v a r i a b l e s o f t h e o r i g i n a l PP p r o b l e m . T h e i r a t t e m p t t o s o l v e PP p r o b l e m s e m p l o y i n g t h i s t r a n s f o r m a t i o n f a i l e d b e c a u s e t h e number o f c o v e r i n g c o n s t r a i n t s i n t h e e q u i v a l e n t l i n e a r c o v e r i n g p r o b l e m i s o f t e n v e r y l a r g e . T h i s a t t e m p t i s , n e v e r t h e l e s s , o f t h e o r e t i c a l i m p o r t a n c e s i n c e t h e c o v e r i n g r e l a x a t i o n a p p r o a c h , d e v e l o p e d b y G r a n o t e t a l [ 1 0 ] , o v e r c o m e s i t s m a j o r d e f i c i e n c y . The c o v e r i n g 4 r e l a x a t i o n a p p r o a c h i s a c u t t i n g p l a n e t y p e a l g o r i t h m . I t p r o d u c e s a n o p t i m a l s o l u t i o n t o t h e PP p r o b l e m b y s o l v i n g e a c h o f a s e q u e n c e o f n e s t e d l i n e a r s e t c o v e r i n g p r o b l e m s t o o p t i m a l i t y . E a c h s e t c o v e r i n g p r o b l e m i s a r e l a x a t i o n o f t h e o r i g i n a l PP p r o b l e m an d u s u a l l y c o n t a i n s o n l y a s m a l l s u b s e t o f t h e c o n s t r a i n t s o f t h e e q u i v a l e n t s e t c o v e r i n g p r o b l e m . T h e c o m p u t a t i o n a l r e s u l t s r e p o r t e d i n [10] i n d i c a t e t h a t t h e c o v e r i n g r e l a x a t i o n a p p r o a c h i s a v i a b l e m e t h o d f o r s o l v i n g m o d e s t s i z e (40 v a r i a b l e s and 40 c o n s t r a i n t s ) s p a r s e p r o b l e m s . H o w e v e r , t h e p e r f o r m a n c e o f t h e m e t h o d d e t e r i o r a t e s r a p i d l y a s t h e number o f d i s t i n c t t e r m s i n t h e c o n s t r a i n t s o f a PP p r o b l e m i n c r e a s e s . U s i n g a s i m i l a r a p p r o a c h , D. G r a n o t and F. G r a n o t [11] h a v e d e v e l o p e d an a l g o r i t h m f o r s o l v i n g t h e g e n e r a l 0-1 p o l y n o m i a l p r o g r a m m i n g p r o b l e m . An O u t l i n e T h e p l a n o f t h i s t h e s i s i s a s f o l l o w s . C h a p t e r 2 r e v i e w s t h e t h e o r e t i c a l w o r k o f G r a n o t a n d Hammer [14] t h a t f o r m s t h e b a s i s o f t h e o r i g i n a l c o v e r i n g r e l a x a t i o n a p p r o a c h o f G r a n o t e t a l [ 1 0 ] , w h i c h w i l l be r e v i e w e d i n c h a p t e r 3. The c o v e r i n g r e l a x a t i o n a p p r o a c h i s e v a l u a t e d i n c h a p t e r 4. The m a j o r c o n t r i b u t i o n o f t h i s t h e s i s , t o be p r e s e n t e d i n c h a p t e r 5, i s an i m p r o v e d c o v e r i n g r e l a x a t i o n a l g o r i t h m . The t h r e e m o d i f i c a t i o n s i n c o r p o r a t e d i n t h e i m p r o v e d a l g o r i t h m a r e m o t i v a t e d by t h e s h o r t c o m i n g s o f t h e o r i g i n a l a l g o r i t h m d i s c u s s e d i n c h a p t e r 4. 5 The most i n t e r e s t i n g o f these m o d i f i c a t i o n s makes n o v e l use o f approximate p r o c e d u r e s f o r s o l v i n g the s e t c o v e r i n g problem t o reduce the number o f s e t c o v e r i n g problems t o have t o be s o l v e d t o o p t i m a l i t y . The improved a l g o r i t h m does not s o l v e a s e t c o v e r i n g problem t o o p t i m a l i t y a t e v e r y i t e r a t i o n . I n s t e a d , a s e t c o v e r i n g problem i s f i r s t s o l v e d a p p r o x i m a t e l y and w i l l be s o l v e d t o o p t i m a l i t y o n l y i f the approximate s o l u t i o n i s f e a s i b l e t o the o r i g i n a l PP problem. The second m o d i f i c a t i o n t h a t i s i n t r o d u c e d uses an approximate s o l u t i o n f o r the PP problem t o produce a b e t t e r i n i t i a l s e t c o v e r i n g problem. The t h i r d m o d i f i c a t i o n g e n e r a t e s t i g h t e r s e t c o v e r i n g c o n s t r a i n t s . The c o m p u t a t i o n a l r e s u l t s t o be r e p o r t e d i n c h a p t e r 7 show t h a t t h e s e m o d i f i c a t i o n s have s i g n i f i c a n t l y improved the performance o f the c o v e r i n g r e l a x a t i o n approach by r e d u c i n g the number, the s i z e and the d e n s i t y o f the s e t c o v e r i n g problems s o l v e d t o o p t i m a l i t y . Chapter 6 d e v e l o p s g r e e d y - l i k e approximate p r o c e d u r e s f o r the s e t c o v e r i n g problem. I t a l s o d i s c u s s e s s i m i l a r p r o c e d u r e s t h a t can be used t o produce t i g h t s e t c o v e r i n g c o n s t r a i n t s . Chapter 7 d i s c u s s e s the p e r t i n e n t a s p e c t s o f the i m p l e m e n t a t i o n o f the c o v e r i n g r e l a x a t i o n approach which has been a h e l p f u l and r e l i a b l e t o o l f o r the development approach. The i m p l e m e n t a t i o n employs a r u d i m e n t a r y i m p l i c i t e numeration a l g o r i t h m f o r s o l v i n g the s e t c o v e r i n g problem. The c o m p u t a t i o n a l r e s u l t s r e p o r t e d i n c h a p t e r 7 show t h a t i f the number of v a r i a b l e s and the d e n s i t y o f the s e t c o v e r i n g problems t o be s o l v e d t o o p t i m a l i t y i s l a r g e , then the CPU time r e q u i r e d f o r s o l v i n g a PP problem t o o p t i m a l i t y i s almost e n t i r e l y 6 d e v o t e d t o s o l v i n g t h e s e t c o v e r i n g p r o b l e m s . T h e p e r f o r m a n c e m e a s u r e s i n d i c a t e t h a t i f a more e f f i c i e n t 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 ( s e e f o r i n s t a n c e [ 1 , 5 ] ) i s i m p l e m e n t e d p r o p e r l y , t h e n t h e c o v e r i n g r e l a x a t i o n a p p r o a c h w i l l be a b l e t o s o l v e much l a r g e r PP p r o b l e m s . The a p p e n d i x c o n t a i n s t h r e e p s e u d o - r a n d o m l y g e n e r a t e d PP p r o b l e m s t h a t w e r e s o l v e d b y t h e a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m . The s e t c o v e r i n g p r o b l e m s t h a t w e r e s o l v e d t o o p t i m a l i t y a r e a l s o i n c l u d e d i n t h e a p p e n d i x . I t i s h o p e d t h a t t h e s e PP p r o b l e m s w i l l s e r v e a s b e n c h m a r k s f o r f u r t h e r r e s e a r c h . The new m a t e r i a l t h a t i s d e v e l o p e d i n t h i s t h e s i s i s c o l l e c t e d i n ["An A c c e l e r a t e d A l g o r i t h m f o r t h e P o s t i v e 0-1 P o l y n o m i a l P r o b l e m " , F a c u l t y o f Commerce a n d B u s i n e s s A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h C o l u m b i a , May 1980] b y F. G r a n o t , D. G r a n o t a n d W. V a e s s e n . 7 2. M a t h e m a t i c a l P r e l i m i n a r i e s T h i s c h a p t e r s u m m a r i z e s t h e t h e o r e t i c a l r e s u l t s a n d n o t i o n s o f [ 2 , 1 4 ] t h a t f o r m t h e b a s i s o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h t o be d i s c u s s e d i n c h a p t e r 3. G r a n o t a n d Hammer [14] u s e d b o o l e a n a l g e b r a t e c h n i q u e s t o show t h a t e v e r y p o s y n o m i a l i n e q u a l i t y c a n be r e p l a c e d by a n e q u i v a l e n t s e t o f l i n e a r c o v e r i n g i n e q u a l i t i e s . T o s e e how t h i s c a n be a c c o m p l i s h e d , c o n s i d e r , f i r s t o f a l l t h e l i n e a r i n e q u a l i t y o f t h e f o r m : n (1) >! a - i x i - b/ w h e r e a-pO, j = l , ... ,n. j = l D e f i n i t i o n 1 A s u b s e t U o f N, N = { l , 2 , ... ,n}, i s a c o v e r o f (1) i f j> a j > b . j e u D e f i n i t i o n 2 A c o v e r U i s p r i m e i f no p r o p e r s u b s e t o f U i s a c o v e r . D e f i n i t i o n 2a |u| i s t h e c a r d i n a l i t y o f t h e p r i m e c o v e r U. D e f i n i t i o n 2b The c a r d i n a l i t y o f a p r i m e c o v e r i s m i n i m a l i f i t i s s m a l l e r t h a n o r e q u a l t o t h e c a r d i n a l i t i e s o f a l l o t h e r p r i m e c o v e r s o f ( 1 ) . L e t C be t h e s e t o f a l l p r i m e c o v e r s o f ( 1 ) . T h e o r e m 1 A 0-1 v e c t o r x s a t i s f i e s (1) i f a n d o n l y i f T[ x-j = 0 f o r a l l U 6 C, j e u e q u i v a l e n t l y , i f a n d o n l y i f y , t h e c o m p l e m e n t o f x, s a t i s f i e s 8 (2) > y-; > 1 f o r a l l U 6 C, w h e r e y = l - x . j eu T h u s t h e l i n e a r i n e q u a l i t y (1) i n t h e 0-1 v e c t o r x c a n be r e d u c e d t o an e q u i v a l e n t s e t o f l i n e a r c o v e r i n g i n e q u a l i t i e s (2) i n t h e c o m p l e m e n t o f x. T h i s r e d u c t i o n c a n be a p p l i e d t o e v e r y c o n s t r a i n t o f a p o s i t i v e 0-1 l i n e a r p r o b l e m t o o b t a i n an e q u i v a l e n t l i n e a r c o v e r i n g p r o b l e m . A s i m i l a r r e s u l t was i n d e p e n d e n t l y o b t a i n e d by B a l a s a n d J e r o s l o w [2] u s i n g a c o m p l e t e l y d i f f e r e n t a p p r o a c h . The a b o v e r e s u l t s w e r e g e n e r a l i z e d i n [14] f o r p o s i t i v e 0-1 p o l y n o m i a l i n e q u a l i t i e s . C o n s i d e r t h e i n e q u a l i t y o f t h e f o r m : P (3) >. a k TT x-; < b, w h e r e a k > 0 , k = l , ... ,p a n d N k (2 N k = l j € N k A 0-1 v e c t o r x s a t i s f i e s (3) i f a n d o n l y i f t h e r e i s a 0-1 v e c t o r z s u c h t h a t x a n d z s a t i s f y : P _ (4) >. a^Zfc < b a n d z k = T| x-; f o r k = l , ... ,p. k = l j 6 N k L e t C be t h e s e t o f a l l p r i m e c o v e r s o f t h e i n e q u a l i t y o f ( 4 ) . T h e n (3) i s s a t i s f i e d i f a n d o n l y i f ]T z k = 0 f o r a l l U e C, kGU e q u i v a l e n t l y , i f a n d o n l y i f TT Tf X J = 0 f o r a l l U 6 C. kGU j 6 N k T h i s c o n d i t i o n c a n a l s o be r e w r i t t e n a s a s e t o f l i n e a r c o v e r i n g 9 i n e q u a l i t i e s i n t h e c o m p l e m e n t i n g v a r i a b l e s . T h e o r e m 2 A 0-1 v e c t o r x s a t i s f i e s (3) i f a n d o n l y i f y , t h e c o m p l e m e n t o f x, s a t i s f i e s (5) > y-; > 1 f o r a l l U 6 C, J S S ( U ) w h e r e y = l - x and S ( U ) i s t h e u n i o n o f N k f o r a l l kGU. T h u s , e v e r y c o n s t r a i n t i n a p o s i t i v e 0-1 p o l y n o m i a l p r o g r a m m i n g p r o b l e m c a n be r e d u c e d t o an e q u i v a l e n t s e t o f l i n e a r c o v e r i n g c o n s t r a i n t s t o o b t a i n a l i n e a r s e t c o v e r i n g (SC) p r o b l e m e q u i v a l e n t t o t h e o r i g i n a l 0-1 p o l y n o m i a l p r o b l e m . T o s i m p l i f y t h e s u b s e q u e n t d i s c u s s i o n o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h t h r e e r e l a t e d p r o p e r t i e s o f c o v e r i n g c o n s t r a i n t s n e e d t o be d e f i n e d . D e f i n i t i o n 3^  A c o v e r i n g c o n s t r a i n t (5) i s p r i m e i f t h e r e d o e s n o t e x i s t a s u b s e t R o f S ( U ) s u c h t h a t 3> y-; > 1 c a n a l s o be g e n e r a t e d f r o m ( 3 ) . J 6 R D e f i n i t i o n 3a The s i z e o f S ( U ) i s t h e c a r d i n a l i t y o f t h e c o v e r i n g c o n s t r a i n t , i . e . The number o f v a r i a b l e s o c c u r i n g i n t h e c o v e r i n g c o n s t r a i n t . D e f i n i t i o n 3b The c a r d i n a l i t y o f a c o v e r i n g c o n s t r a i n t (5) i s m i n i m a l i f i t i s s m a l l e r t h a n o r e q u a l t o t h e c a r d i n a l i t i e s o f a l l o t h e r c o v e r i n g c o n s t r a i n t s t h a t c a n be d e r i v e d f r o m ( 3 ) . 10 The r e a d e r who i s u n f a m i l i a r w i t h t h e a b o v e m a t e r i a l i s u r g e d t o e x a m i n e t h e f o l l o w i n g e x a m p l e : E x a m p l e 1. R e d u c i n g a P o s y n o m i a l C o n s t r a i n t t o an E q u i v a l e n t S e t o f C o v e r i n g C o n s t r a i n t s . 8x2X3 + 5 x 2 X 4 + 3x^x3X5 + 2 x 2 x g < 9 z l z 2 z 3 z 4 z l z 2 = u < = > X 2 X 3 X 4 = 0 <=> Y2+Y3+Y4 - 1 z l z 3 = 0 < = > X 1 X 2 X 3 X 5 = U <=> y i + Y 2 + y 3 + Y 5 - 1 z 1 z 4 = 0 <=> X 2 X 3 X 6 = 0 <=> Y2+Y3+Y6 - 1 z 2 z 3 z 4 = o < = > x 1 x 2 x 3 x 4 x 5 x 6 = o < = > y 1 + y 2 + y 3 + y 4 + y 5 + y 6 ^ 1 X i = l - y i f o r i = l , 2 , 3 , 4 , 5 , 6 . The f i r s t t h r e e c o v e r i n g c o n s t r a i n t s a r e p r i m e . T he c a r d i n a l i t i e s o f t h e f i r s t a nd s e c o n d c o n s t r a i n t a r e m i n i m a l . G r a n o t a n d Hammer [ 1 4 , 1 5 ] u s e d t h e a b o v e r e s u l t t o p r o p o s e an a l g o r i t h m f o r s o l v i n g t h e PP p r o b l e m t h a t f i r s t r e d u c e s t h e PP p r o b l e m t o an e q u i v a l e n t SC p r o b l e m w h i c h i s t h e n s o l v e d t o o p t i m a l i t y by a s t a n d a r d m e t h o d . T h i s a l g o r i t h m , h o w e v e r , i s n o t a t t r a c t i v e c o m p u t a t i o n a l l y b e c a u s e t h e number o f c o n s t r a i n t s i n t h e e q u i v a l e n t SC p r o b l e m i s o f t e n v e r y l a r g e , e v e n f o r f a i r l y s m a l l PP p r o b l e m s . F o r e x a m p l e , a c o n s t r a i n t o f t h e f o r m n j> x - i < T ( n / 2 ) , w h e r e T ( r ) d e n o t e s t h e i n t e g e r p a r t o f r , j = l 11 i s e q u i v a l e n t to C(n,T(n/2)+1) c o v e r i n g c o n s t r a i n t s . The next chapter d e s c r i b e s the c o v e r i n g r e l a x a t i o n approach which was developed by Granot et a l [10] to overcome the d e f i c i e n c y of employing the t r a n s f o r m a t i o n of the PP problem to the SC problem. The c o v e r i n g r e l a x a t i o n approach does not generate and s o l v e the e n t i r e e q u i v a l e n t SC problem but i n s t e a d , s o l v e s each of a nested sequence of much smal l e r SC problems, each of which i s a r e l a x a t i o n of the PP problem to be s o l v e d . 12 3. The Covering R e l a x a t i o n Approach The c o v e r i n g r e l a x a t i o n approach i s a c u t t i n g plane type a l g o r i t h m . C u t t i n g plane algorithms were f i r s t developed to s o l v e i n t e g e r l i n e a r programming (ILP) problems. See e.g. [7] f o r an in-depth treatment of t h i s technique. The b a s i c idea of the c u t t i n g plane algori t h m s f o r the ILP problems i s to s o l v e a sequence of s u c c e s s i v e l y t i g h t e r l i n e a r programming (LP) r e l a x a t i o n s of the o r i g i n a l ILP problem u n t i l the LP optimum s a t i s f i e s the i n t e g r a l i t y requirements of the ILP problem. A t i g h t e r LP r e l a x a t i o n i s obtained by adding one or more c o n s t r a i n t s to the c u r r e n t LP problem which cut o f f the c u r r e n t non-integer optimum but which do not remove any i n t e g e r p o i n t s from the f e a s i b l e r e g i o n of the ILP problem. Such c o n s t r a i n t s are c a l l e d c u t t i n g p l a n e s . The i n i t i a l r e l a x a t i o n i s the LP problem obtained by dropping the i n t e g r a l i t y requirements on the v a r i a b l e s from the ILP problem. The m o t i v a t i o n f o r the a p p l i c a t i o n of a c u t t i n g plane technique f o r s o l v i n g the PP problem i s the o f t e n unmanageable number of c o v e r i n g c o n s t r a i n t s i n the e q u i v a l e n t SC problem. Rather than s o l v i n g the e n t i r e e q u i v a l e n t SC problem, the c o v e r i n g r e l a x a t i o n approach s o l v e s each of a nested sequence of SC problems that are s u c c e s s i v e l y t i g h t e r r e l a x a t i o n s of the o r i g i n a l PP problem. The SC problems are r e f e r r e d to as c o v e r i n g r e l a x a t i o n (CR) problems. The i n i t i a l c o v e r i n g r e l a x a t i o n (CRg) problem c o n s i s t s of a s m a l l subset of the c o v e r i n g c o n s t r a i n t s of the e q u i v a l e n t SC 13 problem. Each CR problem i s obtained by augmenting the c o n s t r a i n t s et of i t s predecessor with c u t t i n g p l a n e s . These c u t t i n g planes are c o v e r i n g c o n s t r a i n t s generated from those terms i n the v i o l a t e d posynomial c o n s t r a i n t s of the o r i g i n a l problem that do not van i s h at the o p t i m a l s o l u t i o n f o r the c u r r e n t CR problem. They c u t - o f f s o l u t i o n s to the CR problems th a t are not f e a s i b l e to the o r i g i n a l problem. C l e a r l y , each CR problem i s a r e l a x a t i o n of the o r i g i n a l PP problem and i s t i g h t e r than a l l i t s p r e d e c e s s o r s . The b a s i c v e r s i o n of c o v e r i n g r e l a x a t i o n approach can now be s t a t e d i n an i n f o r m a l p r o c e d u r a l f a s h i o n . The d i s c u s s i o n of some aspects of the implementation i s d e f e r r e d u n t i l chapter 7. BASIC COVERING RELAXATION ALGORITHM f i n d a s t a r t i n g node; generate CRg with the s t a r t i n g node; repeat s o l v e the c u r r e n t CR problem to o p t i m a l i t y ; attempt to generate one or more a d d i t i o n a l c o v e r i n g c o n s t r a i n t s that cut o f f the o p t i m a l s o l u t i o n to the c u r r e n t CR problem; i f no cuts can be added then the o p t i m a l s o l u t i o n to the c u r r e n t CR problem i s a l s o f e a s i b l e to the o r i g i n a l PP problem; u n t i l the c u r r e n t o p t i m a l s o l u t i o n i s f e a s i b l e ; stop. 14 The a l g o r i t h m t e r m i n a t e s w i t h an o p t i m a l s o l u t i o n f o r t h e PP p r o b l e m i n a t m o s t 2 n i t e r a t i o n s . T e r m i n a t i o n o c c u r s i n f i n i t e l y many s t e p s b e c a u s e t h e s o l u t i o n s p a c e c o n t a i n s a t m o s t 2 n b i n a r y v e c t o r s a n d a t e a c h i t e r a t i o n t h e o p t i m a l s o l u t i o n t o t h e CR p r o b l e m i s d i s c a r d e d . (The e x p e r i m e n t a l r e s u l t s r e p o r t e d i n [10] show t h a t t h a t t h e a v e r a g e b e h a v i o u r o f t h e a l g o r i t h m i s s i g n i f i c a n t l y b e t t e r ! ) The s o l u t i o n on t e r m i n a t i o n i s o p t i m a l b e c a u s e e a c h CR p r o b l e m i s a r e l a x a t i o n o f t h e PP p r o b l e m t o be s o l v e d . A s i n g l e c o v e r i n g c o n s t r a i n t s u f f i c e s t o c u t o f f t h e o p t i m a l s o l u t i o n t o a CR p r o b l e m . I n g e n e r a l , h o w e v e r , more t h a n o n e p o s y n o m i a l c o n s t r a i n t i s v i o l a t e d . I n a d d i t i o n , more t h a n o n e c o v e r i n g c o n s t r a i n t c a n be g e n e r a t e d f r o m e a c h v i o l a t e d p o s y n o m i a l c o n s t r a i n t . T h i s f l e x i b i l i t y i s e x p l o i t e d i n t h e b a s i c a l g o r i t h m a n d t o a l a r g e r e x t e n t i n t h e a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m t o r e d u c e t h e number o f i t e r a t i o n s . See s e c t i o n 7.1 f o r d e t a i l s . I t i s o f t e n p o s s i b l e t o r e d u c e t h e d i m e n s i o n s o f t h e CR p r o b l e m by a p p l y i n g a s m a l l number o f s i m p l i f i c a t i o n r u l e s t h a t w i l l e l i m i n a t e d o m i n a t e d c o v e r i n g c o n s t r a i n t s a n d v a r i a b l e s w h o s e v a l u e s c a n be d e t e r m i n e d i n a d v a n c e , s e e f o r i n s t a n c e [ 7 ] . I f a t m o s t on e c o v e r i n g c o n s t r a i n t i s a d d e d a t e a c h i t e r a t i o n t o f o r m t h e a u g m e n t e d CR p r o b l e m , t h e n a c u t t i n g p l a n e t e c h n i q u e f o r s o l v i n g SC p r o b l e m s [7] c a n be e m p l o y e d t o o b t a i n t h e o p t i m a l s o l u t i o n f o r t h e a u g m e n t e d p r o b l e m . T h i s m e t h o d , h o w e v e r , i s u n l i k e l y t o be e f f e c t i v e b e c a u s e t h e number o f i t e r a t i o n s w i l l be l a r g e . 15 The s t a r t i n g n o d e u s e d by t h e b a s i c a l g o r i t h m i s ( 1 , 1 , ... , D . The b a s i c a l g o r i t h m g e n e r a t e s o n e c o v e r i n g c o n s t r a i n t f r o m e a c h v i o l a t e d p o s y n o m i a l c o n s t r a i n t . To s e e w h i c h c o v e r i n g c o n s t r a i n t i s g e n e r a t e d , c o n s i d e r t h e p o s y n o m i a l c o n s t r a i n t o f t h e f o r m : P >. a^Pfc < b , w h e r e P k d e n o t e s a p r o d u c t o f v a r i a b l e s . k = l T h e b a s i c a l g o r i t h m g e n e r a t e s t h e p r i m e c o v e r w h i c h f o r m s t h e c o v e r i n g c o n s t r a i n t i n t h e f o l l o w i n g m a n n e r : b e g i n o r d e r t h e t e r m s P k s u c h t h a t a k _ j > a k f o r k = 2,...,p; p r i m e - c o v e r := 0 l h s := 0; k := 1; r e p e a t l h s := l h s + a ^ ; p r i m e - c o v e r := p r i m e - c o v e r + U n i o n ( p r i m e - c o v e r , { k } ) ; k := k +1; u n t i l l h s > b o r k >p e n d T h e o r d e r i n g o f t h e t e r m s e n s u r e s t h a t t h e c a r d i n a l i t y o f t h e p r i m e c o v e r f o r m i n g t h e c o v e r i n g c o n s t r a i n t i s m i n i m a l . H o w e v e r , t h i s c o n d i t i o n d o e s n o t q u a r a n t e e t h a t t h e c o v e r i n g c o n s t r a i n t i s p r i m e . H e n c e , t h e c a r d i n a l i t y o f t h e c o v e r i n g c o n s t r a i n t g e n e r a t e d i n t h e a b o v e manner i s n o t m i n i m a l . 16 E x a m p l e 2. S o l v i n g a p o s i t i v e 0-1 p o l y n o m i a l p r o b l e m . S o l v e MAX 7X>L + 5 x 2 + 4 x 3 + 3 x 4 + 3 x 5 + 2 x g s . t . 1) 8 x ^ x 2 X 3 + 6x2X4 + 5x3 + 4x3X5 < 13 2) 7 x 2 X 3 X 5 + 2 x ^ x 6 < 6 3) 7 x 4 x 5 + 4 x]X 4 + 4 x 2 x 5 x 6 < 8 4) 5 x 2 x 3 + 5 x ^ 5 + 3 x 6 + 2 x 4 < 7 5) 3x2X4 +2x3X4 + 2x4X5 + 2x5X5 + x ^ x g < 5 X i 6 { 0 , l } f o r i = l , 2 , 3 , 4 , 5 , 6 . U s e ( 1 , 1 , ... ,1) t o g e n e r a t e o n e c o v e r i n g c o n s t r a i n t f r o m e a c h v i o l a t e d p o s y n o m i a l c o n s t r a i n t i n t h e manner d e s r i b e d a b o v e : f r o m 1) x^X2X3X4=0 2) x 1 x 2 x 3 X 5 X g = 0 3) x 1 x 4 x 5 = 0 4) x 1 x 2 x 3 x 5 = 0 5) x 2 x 3 x 4 X 5 = 0 The f o u r t h c o n s t r a i n t d o m i n a t e s t h e s e c o n d c o n s t r a i n t , w h i c h c a n t h e r e f o r e be d r o p p e d . T he f o u r r e m a i n i n g c o n s t r a i n t s a r e w r i t t e n a s c o v e r i n g c o n s t r a i n t s t o f o r m t h e i n i t i a l c o v e r i n g r e l a x a t i o n p r o b l e m . 17 I t e r a t i o n 1. S o l v e t h e i n i t i a l CR p r o b l e m : MIN 7 y i + 5 y 2 + 4 y 3 + 3 y 4 + 3 y 5 + 2 y 6 s . t . Y l + y 2 + y 3 + y 4 > 1 Y l + Y 4 + Y5 - 1 y i + y 2 + y 3 + y 5 > 1 y 2 + y 3 + y 4 + y 5 > 1 Y i e { 0 , l } f o r i = l , 2 , 3 , 4 , 5 , 6 . O b s e r v e t h a t t h e v a l u e o f y 2 c a n be f i x e d a p r i o r i a t 0 b e c a u s e y 3 c a n s a t i s f y t h e same c o n s t r a i n t s a t a l o w e r c o s t . The s o l u t i o n f o r t h e f i r s t CR p r o b l e m i s y i = y 2 = y 3 = y 6 = 0 i a n d y 4 = Y 5 = 1 • E q u i v a l e n t l y , x ^ = x 2 = x 3 = X g = l , a n d x 4 = x 5 = 0 . U s e x * = ( 1 , 1 , 1 , 0 , 0 , 1 ) t o g e n e r a t e a d d i t i o n a l c o v e r i n g c o n s t a i n t s : f r o m 1) x ^ x 2 x 3 x g = 0 4) x 2 x 3 x 6 = 0 O n l y t h e l a t t e r c o n s t r a i n t n e e d s t o be i n c l u d e d i n t h e a u g m e n t e d p r o b l e m s i n c e i t d o m i n a t e s t h e f o r m e r . I t e r a t i o n 2. S o l v e t h e a u g m e n t e d CR p r o b l e m : MIN 7 y ! + 5 y 2 + 4 y 3 + 3 y 4 + 3 y 5 + 2 y 6 s . t . Y l + Y2 + Y3 + y 4 > 1 Y l + y 4 + Y5 > 1 Y l + Y2 + Y3 + Y5 > 1 Y2 + Y3 + y 4 + Y5 > 1 Y2 + Y3 + Y6 ^ 1 yie{o, 1} : f o r i = l , 2,3,4,5,6. 18 Its solution i s yi =Y2 =Y5 =Y6 = (^' a n c^ Y3 =Y4 =1 • Use x*=(1,l f0,0,1,1) to generate additional covering constraints: from 4) x^x5xg=0 Iteration 3. Solve the augmented CR problem: + 5y 2 + 4y 3 + 3Y4 + 3y 5 + 2ye Y l + Y2 + V3 + Y4 > 1 Y l + Y4 + Y5 > 1 Y l + Y2 + Y3 + V5 > 1 Y2 + Y3 + Y4 + Y5 > 1 Y2 + Y3 + Y6 > 1 Y l + Y5 + Y6 > 1 yiS{0,l} for i=l,2,3,4,5,6. Its solution i s y1=y2=y4=yg=0, and Y3 =Y5 =1• Equivalently, x^=X2=X4=xg=l, and x 3=x 5=l. No covering constraint can be generated with x*=(l,1,0,1,0,1). In other words, i t i s feasible to the o r i g i n a l PP problem. Since x i s an optimal solution for a relaxation of the PP problem i t i s an optimal solution for the PP problem i t s e l f . Solving this problem by f i r s t transforming i t to a 0-1 linear problem requires 14 extra variables and at least 21 extra constraints. A considerable amount of computation i s required to reduce the equivalent SC problem to 9 covering constraints. This example w i l l be used in chapter 5 to i l l u s t r a t e the e f f e c t s of the modifications of the basic algorithm. 19 4. E v a l u a t i o n o f t h e B a s i c c o v e r i n g r e l a x a t i o n A l g o r i t h m T h e e x p e r i m e n t a l r e s u l t s r e p o r t e d i n [10] s h o w e d t h e c o v e r i n g r e l a x a t i o n a p p r o a c h t o be v e r y p r o m i s i n g . O v e r 200 r a n d o m l y g e n e r a t e d p r o b l e m s w i t h up t o 50 v a r i a b l e s a n d 50 c o n s t r a i n t s w e r e s o l v e d u s i n g t h e b a s i c a l g o r i t h m . The CPU t i m e r e q u i r e d t o s o l v e e a c h i n d i v i d u a l p r o b l e m was o f t e n l e s s t h a n 1 s e c o n d a n d e x c e e d e d 1 m i n u t e o n l y f o r t h r e e p r o b l e m s w i t h a r e l a t i v e l y l a r g e number o f t e r m s . ( T h e s e r e s u l t s w e r e o b t a i n e d o n an IBM 370/168.) The number o f c o v e r i n g c o n s t r a i n t s i n t h e f i n a l CR p r o b l e m u s u a l l y d i d n o t e x c e e d t h e number o f p o s y n o m i a l c o n s t r a i n t s i n t h e o r i g i n a l p r o b l e m . The number o f CR p r o b l e m s s o l v e d was t y p i c a l l y b e t w e e n 1 a n d 7. The s u c c e s s o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h c a n l a r g e l y be a t t r i b u t e d t o t h e f a c t t h a t no a d d i t i o n a l v a r i a b l e s a r e i n t r o d u c e d i n t h e s o l u t i o n p r o c e s s . I t i s w o r t h w h i l e t o n o t e t h a t t h e m a j o r s h o r t c o m i n g o f t h e p r o c e d u r e s t h a t l i n e a r i z e t h e p o s y n o m i a l c o n s t r a i n t s s t e m s f r o m t h e r a d i c a l i n c r e a s e i n t h e number o f v a r i a b l e s i n t h e l i n e a r i z e d p r o b l e m t o be s o l v e d . H o w e v e r , m o s t o f t h e p r o b l e m s s o l v e d i n [10] c o n t a i n e d on a v e r a g e o n l y 3 t e r m s p e r c o n s t r a i n t . I t was shown i n [10] t h a t a l l t h r e e p e r f o r m a n c e i n d i c a t o r s ( t h e CPU t i m e , t h e number o f i t e r a t i o n s , a n d t h e number o f c o v e r i n g c o n s t r a i n t s i n t h e f i n a l CR p r o b l e m ) d e t e r i o r a t e a s t h e a v e r a g e number o f t e r m s i n a c o n s t r a i n t b e c o m e s l a r g e r . The CPU t i m e showed t h e m o s t m a r k e d i n c r e a s e . T h i s i n c r e a s e i s d u e , i n p a r t , t o t h e much h i g h e r d e n s i t y o f t h e CR p r o b l e m s . The c o m p u t a t i o n a l r e s u l t s i n [10] 20 r e v e a l t h a t t h e d e n s i t y o f t h e CR p r o b l e m h a s a d r a m a t i c e f f e c t o n t h e CPU t i m e r e q u i r e d t o s o l v e t h e PP p r o b l e m . The a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m , w h i c h w i l l be d i s c u s s e d i n c h a p t e r 5, e m p l o y s t h r e e m o d i f i c a t i o n s t h a t a r e shown t o s u b s t a n t i a l l y i m p r o v e t h e e f f e c t i v e n e s s o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h f o r l e s s s p a r s e PP p r o b l e m s . 21 5. M o d i f i c a t i o n s o f t h e C o v e r i n g R e l a x a t i o n A p p r o a c h T h e a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m , w h i c h w i l l be p r e s e n t e d i n t h i s c h a p t e r , i s a more s o p h i s t i c a t e d v e r s i o n o f t h e b a s i c c o v e r i n g r e l a x a t i o n a l g o r i t h m . T h r e e a s p e c t s o f t h e b a s i c a l g o r i t h m h a v e b e e n m o d i f i e d t o i m p r o v e t h e e f f e c t i v e n e s s o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h . M o d i f i c a t i o n 1. The c o n c e p t u a l d i f f e r e n c e b e t w e e n t h e a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m a n d o t h e r c u t t i n g p l a n e m e t h o d s i n i n t e g e r p r o g r a m m i n g ( I P ) i s t h a t e a c h r e l a x e d p r o b l e m i s n o t n e c e s s a r i l y s o l v e d t o o p t i m a l i t y . The b a s i c i d e a o f m o d i f i c a t i o n 1 i s t o s o l v e t h e CR p r o b l e m s a p p r o x i m a t e l y a s l o n g a s t h e a p p r o x i m a t e s o l u t i o n a t e a c h i t e r a t i o n i s n o t f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m . C u t s c a n be g e n e r a t e d i n t h e u s u a l manner t o e l i m i n a t e t h e s u c c e s s i v e a p p r o x i m a t e s o l u t i o n s . An CR p r o b l e m i s s o l v e d t o o p t i m a l i t y o n l y when t h e a p p r o x i m a t e s o l u t i o n f o r t h i s p r o b l e m i s f e a s i b l e t o t h e o r i g i n a l p r o b l e m . The m o d i f i c a t i o n i s i m p l e m e n t e d by a d d i n g o n e e x t r a s t e p t o t h e b a s i c c o v e r i n g r e l a x a t i o n a l g o r i t h m t o c o m p u t e an a p p r o x i m a t e s o l u t i o n f o r t h e c u r r e n t CR p r o b l e m . T h e p r o m i s e o f t h i s m o d i f i c a t i o n s t e m s f r o m t h e e x c e l l e n t p e r f o r m a n c e o f t h e v a r i o u s a p p r o x i m a t e a l g o r i t h m s f o r s o l v i n g I P p r o b l e m s , s e e f o r e x a m p l e [ 3 , 6 , 1 9 , 2 5 , 2 8 ] . F o u r g r e e d y - l i k e a p p r o x i m a t e p r o c e d u r e s f o r t h e SC p r o b l e m a r e d e v e l o p e d i n s e c t i o n 6.1. T h e s e p r o c e d u r e s a r e f a s t a n d t h e v a l u e s o f t h e o p t i m a l s o l u t i o n s o b t a i n e d a r e o n a v e r a g e w i t h i n 2% o f 22 o p t i m a l i t y . O b s e r v e t h a t i f t h e a p p r o x i m a t e p r o c e d u r e s f o r s o l v i n g t h e SC p r o b l e m o b t a i n t h e o p t i m a l s o l u t i o n m o s t o f t h e t i m e , t h e n t h e number o f t i m e s t h a t a CR p r o b l e m w i l l n e e d t o be s o l v e d t o o p t i m a l i t y w i l l be v e r y c l o s e t o 1. I t i s p o s s i b l e t o e n s u r e t h a t o n l y a s i n g l e CR p r o b l e m i s s o l v e d t o o p t i m a l i t y . S u p p o s e t h a t a s l i g h t l y m o d i f i e d e n u m e r a t i o n t e c h n i q u e i s u s e d t h e c u r r e n t b e s t s o l u t i o n i s f o r s o l v i n g t h e CR p r o b l e m s . T h e e n u m e r a t i o n o f t h e c u r r e n t CR p r o b l e m w i l l be i n t e r u p t e d w h e n e v e r a s o l u t i o n b e t t e r t h a n t h e c u r r e n t b e s t s o l u t i o n i s e n c o u n t e r e d . I f t h i s s o l u t i o n i s f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m t h e n t h e e n u m e r a t i o n c o n t i n u e s ; o t h e r w i s e c o v e r i n g c o n s t r a i n t s a r e g e n e r a t e d t o e l i m i n a t e t h i s s o l u t i o n a n d t h e e n u m e r a t i o n o f t h e a u g m e n t e d CR p r o b l e m s t a r t s anew. I f t h e e n u m e r a t i o n o f t h e c u r r e n t CR p r o b l e m t e r m i n a t e s t h e n t h e c u r r e n t b e s t s o l u t i o n i s f e a s i b l e a n d o p t i m a l t o t h e o r i g i n a l PP p r o b l e m . T h e r e i s e v i d e n c e t h a t m o d i f i c a t i o n 1 c a n a l s o be a p p l i e d t o t h e c o v e r i n g r e l a x a t i o n a p p r o a c h f o r t h e g e n e r a l 0-1 p o l y n o m i a l p r o g r a m m i n g p r o b l e m . M o r e o v e r , D. G r a n o t a n d F . G r a n o t a r e c u r r e n t l y i n v e s t i g a t i n g t h e e f f e c t i v e n e s s o f a v e r y s i m i l a r i d e a f o r i m p r o v i n g B e n d e r s p a r t i t i o n i n g p r o c e d u r e f o r s o l v i n g m i x e d i n t e g e r p r o g r a m m i n g p r o b l e m s , s e e [12]. M o d i f i c a t i o n 2. An a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m i s e m p l o y e d t o o b t a i n an i n i t i a l CR p r o b l e m . T h i s CR p r o b l e m i s , i n a s e n s e , a c l o s e r a p p r o x i m a t i o n o f t h e PP p r o b l e m i n t h e n e i g h b o r h o o d o f i t s o p t i m a l s o l u t i o n t h a n t h e i n i t i a l CR p r o b l e m 23 g e n e r a t e d b y ( 1 , 1 , ... , 1 ) . M o d i f i c a t i o n 2 i s a l s o m o t i v a t e d by t h e e x c e l l e n t p e r f o r m a n c e o f t h e a p p r o x i m a t e p r o c e d u r e s f o r s o l v i n g I P p r o b l e m s . F. G r a n o t a n d W. V a e s s e n h a v e d e v e l o p e d , i m p l e m e n t e d a n d a n a l y z e d g r e e d y - l i k e a p p r o x i m a t e p r o c e d u r e s f o r t h e PP p r o b l e m , s e e F . G r a n o t [ 1 2 ] . The v a l u e s o f t h e a p p r o x i m a t e s o l u t i o n s f o u n d by t h e s e p r o c e d u r e s w e r e c o n s i s t e n t l y c l o s e t o t h e o p t i m a l v a l u e s a n d w e r e e q u a l t o t h e o p t i m a l v a l u e s i n o v e r 60% o f t h e p r o b l e m s t h a t w e r e s o l v e d . C R Q i s f o r m e d by g e n e r a t i n g c o v e r i n g c o n s t r a i n t s f r o m a number o f d i f f e r e n t s t a r t i n g n o d e s t h a t a r e d e r i v e d f r o m t h e a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m . E x p l i c i t l y , l e t X p p d e s i g n a t e an a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m . C R Q i s c o n s t r u c t e d i n t h e f o l l o w i n g m a n n e r : b e g i n C R := 0; Z e r o s := { v | x p p ( v ) = 0 } ; s t a r t i n g - n o d e := X p p ? f o r v 6 Z e r o s d o  b e g i n s t a r t i n g - n o d e ( v ) := 1; g e n e r a t e a u g m e n t e d C R w i t h s t a r t i n g - n o d e ; s t a r t i n g - n o d e ( v ) := 0; e n d C R Q := C R ; e n d 24 The a p p r o x i m a t e s o l u t i o n s p r o d u c e d by t h e m e t h o d s d e s c r i b e d i n [12] c a n n o t be i m p r o v e d by c h a n g i n g o n e o r more v a r i a b l e s f r o m 0 t o 1. T h i s p r o p e r t y o f X p p e n s u r e s t h a t a t l e a s t o n s t a r t i n g - n o d e w i l l be i n f e a s i b l e a n d h e n c e t h a t C R Q w i l l n o t be e m p t y . I t i s i n t u i t i v e l y c l e a r t h a t i f X p p i s e q u a l o r c l o s e t o t h e o p t i m a l s o l u t i o n o f t h e P P p r o b l e m , t h e n t h e s o l u t i o n o f C R Q f o r m e d i n t h e a b o v e manner i s l i k e l y t o be c l o s e r t o t h e s o l u t i o n o f t h e o r i g i n a l P P p r o b l e m t h a n t h e s o l u t i o n o f C R Q g e n e r a t e d b y ( 1 , 1 , ... , 1 ) . T h e o v e r a l l number o f i t e r a t i o n s a n d t h e number o f c o n s t r a i n t s i n t h e f i n a l C R p r o b l e m a r e , t h e r e f o r e , l i k e l y t o be s m a l l e r . The d e n s i t y o f C R Q g e n e r a t e d i n t h e a b o v e manner i s n o t n e c e s s a r i l y l o w e r . T h e v a l u e s o f t h e a p p r o x i m a t e s o l u t i o n s f o r t h e P P p r o b l e m a n d t h e CR p r o b l e m s c a n be u t i l i z e d a s l o w e r b o u n d s by t h e p r o c e d u r e s o l v i n g t h e CR p r o b l e m t o o p t i m a l i t y . M o d i f i c a t i o n 3. The q u a l i t y o f t h e c o v e r i n g c o n s t r a i n t s i s i m p r o v e d by i m p l i c i t l y e n u m e r a t i n g a l l o r m o s t o f t h e p r i m e c o v e r s t h a t c a n be g e n e r a t e d f r o m t h e v i o l a t e d p o s y n o m i a l c o n s t r a i n t s a n d s e l e c t i n g t h o s e p r i m e c o v e r s whose a s s o c i a t e d c o v e r i n g c o n s t r a i n t s h a v e m i n i m a l c a r d i n a l i t y . T h e o b j e c t i v e o f m o d i f i c a t i o n 3, w h i c h w i l l be j u s t i f i e d s h o r t l y , i s t o g e n e r a t e t i g h t e r c o v e r i n g c o n s t r a i n t s . L e t x ( c ) d e s i g n a t e e i t h e r an a p p r o x i m a t e o r o p t i m a l s o l u t i o n f o r t h e c u r r e n t CR p r o b l e m . C o n s i d e r t h e p o s y n o m i a l i n e q u a l i t y (3). L e t R = { i | v j 6 N i , X j ( c ) = l } . R r e p r e s e n t s t h e s e t 25 o f n o n - v a n i s h i n g t e r m s o f (3) a t x ( c ) . The p o s y n o m i a l i n e q u a l i t y f r o m w h i c h t h e t e r m s v a n i s h i n g a t x ( c ) h a v e b e e n d r o p p e d w i l l be o f t h e f o r m : (6) > a i TT XJ < b . i 6 R j G N i T h e c o v e r i n g c o n s t r a i n t s t h a t c a n be d e r i v e d f r o m (6) a r e o f t h e f o r m : 3> y j > 1, w h e r e S i s a s u b s e t o f N. j e s L e t be s u c h a c o v e r i n g c o n s t r a i n t w i t h S=S^. I f i s n o t p r i m e ( s e e d e f . 3) t h e n t h e r e e x i s t s a c o v e r i n g c o n s t r a i n t C 2 w i t h S=S2 s u c h t h a t S 2 i s a p r o p e r s u b s e t o f S]_. C l e a r l y , C 2 i s a b e t t e r c h o i c e t h a n C^ s i n c e i t d o m i n a t e s t h e c o n s t r a i n t a s s o c i a t e d w i t h S 2 . I f , o n t h e o t h e r h a n d , C^ i s p r i m e b u t n o t m i n i m a l ( s e e d e f . 3b) t h e n t h e r e e x i s t s a c o v e r i n g c o n s t r a i n t C 2 w i t h S = S 2 s u c h t h a t C 2 i s p r i m e a n d | S 2 | < |S-j_|. T he c h o i c e b e t w e e n C^ a n d C 2 i s n o t c l e a r - c u t i n t h i s c a s e . T h e p r o p e r t i e s o f c o v e r i n g c o n s t r a i n t s t h a t a r e d e f i n e d i n c h a p t e r 2 d o n o t s u f f i c e t o e v a l u a t e t h e r e l a t i v e m e r i t s o f C^ a n d C 2 s i n c e t h e y d o n o t t a k e i n t o a c c o u n t t h e p r o p e r t i e s and s t r u c t u r e o f t h e CR p r o b l e m t o be a u g m e n t e d . F o r l a c k o f i n s i g h t , C 2 i s c h o s e n b e c a u s e , f i r s t o f a l l , i t e l i m i n a t e s more 0-1 v e c t o r s f r o m t h e s o l u t i o n s p a c e o f c u r r e n t CR p r o b l e m a n d s e c o n d l y , t h e s o l u t i o n o f t h e a u g m e n t e d CR p r o b l e m i s more l i k e l y t o move c l o s e r t o t h e o p t i m a l s o l u t i o n s i n c e C j i s a t i g h t e r c o v e r i n g c o n s t r a i n t . The p r e v i o u s p a r a g r a p h m o t i v a t e s t h e s e a r c h f o r c o v e r i n g c o n s t r a i n t s w i t h m i n i m a l c a r d i n a l i t y . F o r m a l l y , t h e m i n i m a l c a r d i n a l i t y (MC) p r o b l e m c a n be s t a t e d a s f o l l o w s : 26 M i n i m i z e | U n i o n | S C R i e s (MC) s u b j e c t t o > a j > b j e s I f |R| i s n o t much l a r g e r t h a n |N|, we c a n e m p l o y an 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 f o r s o l v i n g t h e MC p r o b l e m . I f a f i x e d b r a n c h i n g m e t h o d i s u s e d , t h e n t h e c o v e r i n g c o n s t r a i n t p r o d u c e d b y t h e b a s i c a l g o r i t h m i s t h e f i r s t f e a s i b l e s o l u t i o n e n c o u n t e r e d i n a d e p t h - f i r s t s e a r c h o f t h e s o l u t i o n t r e e o f t h e MC p r o b l e m . N o t e t h a t i f (6) i s a l i n e a r i n e q u a l i t y , t h e n t h e f i r s t f e a s i b l e s o l u t i o n i s a l s o t h e o p t i m a l s o l u t i o n . I f , o n t h e o t h e r h a n d , |R| i s much l a r g e r t h a n |N|, t h e n a p p r o x i m a t e p r o c e d u r e s c a n be e m p l o y e d t o s o l v e t h e MC p r o b l e m . G r e e d y - l i k e a p p r o x i m a t e p r o c e d u r e s f o r t h e MC p r o b l e m a r e d e v e l o p e d i n s e c t i o n 6.2. The c o v e r i n g c o n s t r a i n t s g e n e r a t e d b y a r e s t r i c t e d e n u m e r a t i o n o f t h e s o l u t i o n t r e e o f t h e MC p r o b l e m o r by t h e g r e e d y - l i k e a p p r o x i m a t e p r o c e d u r e s t o be d i s c u s s e d , a r e n o t g u a r a n t e e d t o be p r i m e . E x p l i c i t l y , l e t 3> y ; > 1 be a c o v e r i n g c o n s t r a i n t p r o d u c e d f r o m (6) u s i n g j e v an a p p r o x i m a t e m e t h o d . T h e n i t i s p o s s i b l e t h a t a p r o p e r s u b s e t V o f V i s a l s o a c o v e r i n g c o n s t r a i n t f o r t h e same p o s y n o m i a l i n e q u a l i t y ( 6 ) . T h i s c o n d i t i o n c a n e a s i l y be d e t e c t e d . L e t x i ( v ' ) = l i f i S V a n d 0 o t h e r w i s e . T h e n V i s n o t p r i m e i f a n d o n l y i f t h e r e e x i s t s a p r o p e r s u b s e t V o f V s u c h t h a t (6) i s n o t v i o l a t e d by x ( v ' ) . 27 The a c c e l e r a t e d v e r s i o n o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h c a n now be s t a t e d i n an i n f o r m a l p r o c e d u r a l f a s h i o n . A C CELERATED COVERING RELAXATION ALGORITHM f i n d an a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m ; g e n e r a t e CRg u s i n g t h e a p p r o x i m a t e s o l u t i o n ; r e p e a t s o l v e t h e c u r r e n t CR p r o b l e m a p p r o x i m a t e l y ; a t t e m p t t o g e n e r a t e a d d i t i o n a l c u t s t o e l i m i n a t e t h e a p p r o x i m a t e s o l u t i o n ; i f t h e a p p r o x i m a t e s o l u t i o n i s f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m t h e n b e g i n s o l v e t h e c u r r e n t CR p r o b l e m t o o p t i m a l i t y ; a t t e m p t t o g e n e r a t e a d d i t i o n a l c u t s t o e l i m i n a t e t h e o p t i m a l s o l u t i o n ; i f no c u t s w e r e a d d e d t h e n t h e o p t i m a l s o l u t i o n t o t h e CR p r o b l e m i s f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m ; e n d u n t i l t h e c u r r e n t o p t i m a l s o l u t i o n i s f e a s i b l e ; s t o p . T he a l g o r i t h m t e r m i n a t e s w i t h an o p t i m a l s o l u t i o n f o r t h e PP p r o b l e m i n a t m o s t 2 n i t e r a t i o n s . T e r m i n a t i o n o c c u r s i n f i n i t e l y many s t e p s b e c a u s e t h e s o l u t i o n s p a c e c o n t a i n s a t m o s t 28 2 n b i n a r y v e c t o r s a n d a t e a c h i t e r a t i o n e i t h e r an a p p r o x i m a t e s o l u t i o n o r an o p t i m a l s o l u t i o n i s d i s c a r d e d . The s o l u t i o n o n t e r m i n a t i o n i s o p t i m a l t o t h e PP p r o b l e m b e c a u s e i t i s o p t i m a l t o t h e CR p r o b l e m w h i c h i s a r e l a x a t i o n o f t h e PP p r o b l e m . T h e a c c e l e r a t e d a l g o r i t h m d o e s n o t n e c e s s a r i l y g e n e r a t e o n e c o v e r i n g c o n s t r a i n t f r o m e a c h v i o l a t e d p o s y n o m i a l c o n s t r a i n t . I f t h e c a r d i n a l i t i e s o f t h e c o v e r i n g c o n s t r a i n t s t h a t c a n be g e n e r a t e d f r o m o n e p a r t i c u l a r p o s y n o m i a l c o n s t r a i n t a r e s m a l l e r t h a n t h o s e t h a t c a n be g e n e r a t e d f r o m a l l o t h e r p o s y n o m i a l c o n s t r a i n t s , t h e n t h e a c c e l e r a t e d a l g o r i t h m u s e s more t h a n o n e c o v e r i n g c o n s t r a i n t f r o m t h i s p o s y n o m i a l c o n s t r a i n t t o augment t h e CR p r o b l e m . F u r t h e r m o r e , i f o n l y a few p o s y n o m i a l c o n s t r a i n t s a r e v i o l a t e d t h e n t h e a c c e l e r a t e d a l g o r i t h m a t t e m p t s t o a d d more t h a n o n e c o v e r i n g c o n s t r a i n t f r o m t h o s e c o n s t r a i n t s t h a t a r e v i o l a t e d . See s e c t i o n 7.1 f o r f u r t h e r d e t a i l s . E x a m p l e 3. E x a m p l e 2 r e v i s i t e d . I n e x a m p l e 2 t h e f o l l o w i n g PP p r o b l e m was s o l v e d : MAX 7x1 + 5 x 2 + 4 x 3 + 3 x 4 + 3 x 5 + 2 x g s . t . 1) 8 x ^ X 2 X 3 + 6 x 2 x 4 + 5 x 3 + 4 x 3 x 6 < 13 2) 7 x 2 x 3 x 5 + 2X " LX 6 < 6 3) 7 x 4 x 5 + 4X]^x 4 + 4 x 2 x 5 x 6 < 8 4) 5X2 * 3 + 5 x i x 5 + 3 x 6 + 2 x 4 - 7 5) 3 x 2 x 4 + 2 x 3 x 4 + 2 x 4 x 5 + 2 x 5 x g + x - ^ g < 5 X i € { 0 , l } f o r i = l , 2 , 3 , 4 , 5 , 6 . '. 1 29 To i l l u s t r a t e m o d i f i c a t i o n 2 , x p p = ( 1 , 1 , 0 , 1 , 0 , 1 ) w i l l be u s e d t o g e n e r a t e C Rg. The f i r s t s t a r t i n g - n o d e ( 1 , 1 , 1 , 1 , 0 , 1 ) g e n e r a t e s f r o m 1) x ^ X 2 X 3 x 4 = 0 4) x 2 x 3 x 6 = 0 5) X 3 X 2 X 5 X 4 X 5 = 0 T h e s e c o n d s t a r t i n g - n o d e ( 1 , 1 , 0 , 1 , 1 , 1 ) g e n e r a t e s f r o m 3) x j X 4 X 5 = 0 4) x 1 x 5 x 6 = 0 5) X 2 X 4 X 5 x 6 = 0 T h e s e two s e t s o f c o n s t r a i n t s a r e s i m p l i f i e d a n d w r i t t e n a s a s e t o f c o v e r i n g c o n s t r a i n t s t o f o r m t h e i n i t i a l CR p r o b l e m . I t e r a t i o n 1 . S o l v e t h e i n i t i a l CR p r o b l e m : MIN 7 Y ! + 5 y 2 + 4 y 3 + 3 y 4 + 3 y 5 + 2 y 6 s . t . Y l + Y2 + Y2 + Y l Y l Y2 y i S { 0 , l } f o r i = l , 2 , 3 , 4 , 5 , 6 . I t s s o l u t i o n i s y 1 = y 2 = y 3 = y 5 = 0 , a n d y 4 = Y 6 = l . E q u i v a l e n t l y , x l = x 2 = x 3 = x 5 = l ' a n d x 4 = x g = 0 . U s e ( 1 , 1 , 1 , 0 , 1 , 0 ) t o g e n e r a t e a d d i t i o n a l c o v e r i n g c o n s t r a i n t s : f r o m 1) x ^ X 2 X 3 = 0 4) X l x 2 x 3 x 5 = 0 y 3 + y 4 > 1 y 3 + y 6 > 1 + Y 4 + Y5 ^ 1 + y 5 + y 6 ^ i + Y4 + Y5 + Y6 - 1 30 T h e f o r m e r c o n s t r a i n t d o m i n a t e s t h e l a t t e r c o n s t r a i n t w h i c h i s t h e r e f o r e n o t i n c l u d e d i n t h e a u g m e n t e d p r o b l e m . The f o r m e r c o n s t r a i n t a l s o e l i m i n a t e s t h e f i r s t c o n s t r a i n t i n t h e i n i t i a l CR p r o b l e m . I t e r a t i o n 2. S o l v e t h e a u g m e n t e d CR p r o b l e m : MIN l y ± + 5 y 2 + 4 y 3 + 3 y 4 + 3 y 5 + 2 y 6 s . t . y 2 + y 3 + y 4 > 1 y 2 + y 3 + y 6 > 1 Y l + Y4 + v 5 - 1 Y l + Y5 + v 6 - 1 Y2 + Y4 + Y5 + Ye - 1 y^e{0,l} f o r i = l , 2 , 3 , 4 , 5 , 6 . I t s s o l u t i o n i s y-j_=y 2=y 4=y 6 = 0, a n d y 3 = y 5 = l . E q u i v a l e n t l y , x 1 = x 2 = x 4 = x 6 = l , a n d x 3 = x 5 = 0 . x * = ( 1 , 1 , 0 , 1 , 0 , 1 ) i s f e a s i b l e a n d o p t i m a l t o t h e PP p r o b l e m . To i l l u s t r a t e m o d i f i c a t i o n 3, ( 1 , 1 , 1 , 1 , 1 , 1 ) w i l l be u s e d t o g e n e r a t e c o v e r i n g c o n s t r a i n t s w i t h m i n i m a l c a r d i n a l i t y : f r o m 1) x ^ x 2 x 3 = 0 5) x 1 x 2 x 3 x 5 x 6 = 0 3) x i x 4 x 5 = 0 4) x 2 x 3 x 6 = 0 5) x 2 x 3 x 4 x 5 = 0 T h i s s e t o f c o n s t r a i n t s i s s i m p l i f i e d a n d w r i t t e n a s a s a s e t o f c o v e r i n g c o n s t r a i n t s t o f o r m t h e i n i t i a l CR p r o b l e m . 31 I t e r a t i o n 1. S o l v e t h e i n i t i a l CR p r o b l e m : MIN 7yx + 5 y 2 + 4 y 3 + 3 y 4 + 3 y 5 + 2 y 6 s . t . y i + y 2 + y 3 > 1 Y l + Y4 • + Y5 - 1 y 2 + y 3 + y 6 > 1 Y 2 + Y 3 + Y 4 + Y5 - 1 Yie{0,l} f o r i = l , 2 , 3 , 4 , 5 , 6 . I t s s o l u t i o n i s Y l = Y 2 = Y 4 = Y 6 = 0 ' a n d Y 3 ~ Y s = 1 - E q u i v a l e n t l y , x i = x 2 = x 3 = x 5 = 0 , a n d x 4 = x g = l . x * = ( l , 1 , 0 , 1 , 0 , 1 ) i s f e a s i b l e a n d o p t i m a l t o t h e PP p r o b l e m . T h i s e x a m p l e i s p e r h a p s m i s l e a d i n g . I t i s n o t t o o d i f f i c u l t t o c o n s t r u c t an e x a m p l e f o r w h i c h t h e m o d i f i c a t i o n s a r e n o t a s s u c c e s s f u l . 32 6. G r e e d y - l i k e A p p r o x i m a t e P r o c e d u r e s  f o r t h e SC a n d MC P r o b l e m s T h i s c h a p t e r d e v e l o p s t h e g r e e d y - l i k e p r o c e d u r e s t h a t a r e u s e d by t h e a c c e l e r a t e d a l g o r i t h m t o o b t a i n g o o d s o l u t i o n s f o r t h e CR a n d MC p r o b l e m s a t p o l y n o m i a l c o s t . T he p r i m a l g r e e d y a p p r o a c h s t a r t s w i t h a f e a s i b l e s o l u t i o n , u s u a l l y ( l f l f ... ,1), a n d moves t o w a r d s a l o c a l o p t i m u m . I n i t i a l l y a l l v a r i a b l e s a r e f r e e . A t e a c h i t e r a t i o n t h e " p r o m i s e " o f e a c h f r e e v a r i a b l e i s c a l c u l a t e d t o d e t e r m i n e w h i c h v a r i a b l e w i l l be d r o p p e d f r o m t h e c u r r e n t s o l u t i o n . The p r o m i s e o f a v a r i a b l e i s t h e e x p e c t e d p a y - o f f o f f i x i n g t h e v a r i a b l e a t a p a r t i c u l a r v a l u e . Once a v a r i a b l e i s d r o p p e d , i t s v a l u e a n d p o s s i b l y t h e v a l u e o f o t h e r v a r i a b l e s a r e f i x e d . The p r i m a l a p p r o a c h i t e r a t e s u n t i l no more v a r i a b l e s c a n be d r o p p e d . T h e d u a l g r e e d y a p p r o a c h s t a r t s w i t h ( 0 , 0 , . . . ,0) a n d moves t o w a r d s a f e a s i b l e s o l u t i o n . I n i t i a l l y a l l v a r i a b l e s a r e f r e e . A t e a c h i t e r a t i o n t h e p r o m i s e o f e a c h f r e e v a r i a b l e i s c a l c u l a t e d t o d e t e r m i n e w h i c h v a r i a b l e w i l l be a d d e d t o t h e c u r r e n t s o l u t i o n . Once a v a r i a b l e i s a d d e d , i t s v a l u e i s f i x e d . T he d u a l a p p r o a c h i t e r a t e s u n t i l a l l c o v e r i n g c o n s t r a i n t s a r e s a t i s f i e d . An a p p r o x i m a t e s o l u t i o n o b t a i n e d by t h e d u a l p r o c e d u r e c a n o f t e n be i m p r o v e d by a p p l y i n g t h e p r i m a l p r o c e d u r e t o i t . The p r i m a l p r o c e d u r e w i l l d r o p t o 0 t h e v a r i a b l e s t h a t a r e no l o n g e r n e e d e d t o e n s u r e f e a s i b i l i t y . 33 6.1 G r e e d y - l i k e P r o c e d u r e s f o r t h e SC P r o b l e m Th e a p p r o x i m a t e p r o c e d u r e s f o r t h e SC p r o b l e m , t o be d e s c r i b e d s h o r t l y , a r e v a r i a n t s o f t h e b a s i c p r i m a l a n d d u a l a p p r o a c h e s . Two m o d i f i c a t i o n s h a v e b e e n i n t r o d u c e d . The f i r s t o f t h e s e c a l c u l a t e s a more a c c u r a t e p r o m i s e . T h e p r o m i s e o f a f r e e v a r i a b l e y ^ i s u s u a l l y c a l c u l a t e d a s t h e r a t i o o f C i , t h e c o s t - c o e f f i c i e n t a s s o c i a t e d w i t h y ^ , a n d |Cj_|, w h e r e 10-JL | i s t h e c a r d i n a l i t y o f t h e c o l u m n a s s o c i a t e d w i t h y ^ . H o w e v e r , i f t h e v a r i a b i l i t y o f t h e c a r d i n a l i t i e s o f t h e u n s a t i s f i e d c o n s t r a i n t s i s s u b s t a n t i a l , t h e n a more a c c u r a t e p r o m i s e i s c a l c u l a t e d by t a k i n g i n t o a c c o u n t t h e c a r d i n a l i t i e s o f t h e c o n s t r a i n t s i n w h i c h Yi o c c u r s . T h e c o m p u t a t i o n a l r e s u l t s t o be r e p o r t e d i n s e c t i o n 7.3 show t h a t t h e i n c l u s i o n o f t h i s w e i g h t i n g f a c t o r i n c a l c u l a t i n g p r o m i s e s i m p r o v e s t h e e f f e c t i v e n e s s o f t h e a p p r o x i m a t e p r o c e d u r e s . A s i m i l a r i d e a was i n d e p e n d e n t l y p r o p o s e d i n [20] f o r t h e m u l t i d i m e n s i o n a l k n a p s a c k p r o b l e m . The s e c o n d m o d i f i c a t i o n r e s t r i c t s t h e s e t o f f r e e v a r i a b l e s f o r w h i c h t h e p r o m i s e i s c a l c u l a t e d . The r e s t r i c t e d s e t c o n s i s t s o f t h e f r e e v a r i a b l e s t h a t o c c u r i n t h e t i g h t e s t c o n s t r a i n t s . The e f f e c t o f t h i s m o d i f i c a t i o n i s t h a t t h e v a l u e o f v a r i a b l e s o c c u r i n g i n t i g h t c o n s t r a i n t s a r e d e t e r m i n e d a t an e a r l y s t a g e . I t i s a s s u m e d t h a t t h e c a r d i n a l i t y o f e a c h c o n s t r a i n t i s s t r i c t l y g r e a t e r t h a n 1. 34 C o n s i d e r t h e SC p r o b l e m n (SC) MIN > c-jYj j = l s u b j e c t t o n >. a i j y - i > 1 f o r i = l , ,m j = l y j 6 { o f l } f o r j S N , w h e r e a i j 6 { o , l } f o r V i , j . D e f i n e - 1 i f y £ i s f r e e - 0 i f yj[ i s f i x e d t o e i t h e r 0 o r 1 F = { i | f i = l } f i = n h i ( y ) = - 0 i f > a j i y j > 1 j = l - 1 o t h e r w i s e H ( y ) = { i | h i ( y ) = 0 } f i . e . H ( y ) i s t h e s e t o f c o n s t r a i n t s t h a t a r e s a t i s f i e d b y a p a r t i c u l a r 0-1 v e c t o r y . Now, f o r a 0-1 v e c t o r y a n d a c o r r e s p o n d i n g v e c t o r f = ( f j _ ) l e t n R i ( f ) = E a-i-^f-; a n d l e t j = l T ( y ) = { j 6 F | 3 i ( a i j = l A v M i (1 < Rj ( f ) < R ^ f ) ) ) } , i . e . T ( y ) i s t h e s e t o f f r e e v a r i a b l e s o c c u r i n g i n t h e t i g h t e s t u n s a t i s f i e d c o v e r i n g c o n s t r a i n t s a t y . F u r t h e r l e t M = { l , 2 , ... ,m}; a n d l e t e a n d e r d e s i g n a t e s u i t a b l y s m a l l p o s i t i v e c o n s t a n t s . S u b s e q u e n t l y , h - j j y ) , H ( y ) , R i ( f ) a n d T ( y ) w i l l be d e n o t e d by h ^ , H, R^ a n d T r e s p e c t i v e l y . SC PRIMAL G R E E D Y - L I K E PROCEDURE i n i t i a l i z e H, R a n d T; y := 1; f := 1; r e p e a t i f s l o w - o p t i o n t h e n S := F e l s e S := T; m f o r j G S c o m p u t e p j = C j / ( >; j / ( ( R i ~ l ) h j [ + e r ) ) i = l k := MAX p i , i n c a s e o f a t i e MIN c ^ ; i e s i f p k > e t h e n  b e g i n y k := 0; f k := 0; f o r i : = l t o n i f R i = 1 t h e n b e g i n j := 0; r e p e a t j := j + 1 u n t i l ^ i j f j = 1; f j := 0 u p d a t e H; e n d u p d a t e R a n d T; e n d u n t i l p k < e o r F=0 o r H=M; s t o p . " R i - l " i s t h e w e i g h t i n g f a c t o r f o r t h e p r i m a l a p p r o a c h , 36 SC DUAL G R E E D Y - L I K E PROCEDURE i n i t i a l i z e T f H a n d R; y := 0; f := 1; r e p e a t i f s l o w - o p t i o n t h e n S := F e l s e S := T; m f o r j G S c o m p u t e p.; = c+/{ >_ a i - ; / ( R i h i + e r ) ) i = l k := MIN p j ^ , i n c a s e o f a t i e MIN c ^ ; i e s i f p k > e t h e n  b e g i n Yk : = 1> f k : = °' u p d a t e T a n d H; e n d u n t i l p k < e o r H=M; s t o p . " R i h i " i s t h e w e i g h t i n g f a c t o r f o r t h e d u a l a p p r o a c h . B o t h p r o c e d u r e s r u n i n O ( n ^ ) t i m e . T h e s e t i m e r e q u i r e m e n t s a r e an i n s i g n i f i c a n t o v e r h e a d i n t h e c o n t e x t o f s o l v i n g a PP p r o b l e m t o o p t i m a l i t y . A t e v e r y i t e r a t i o n t h e a c c e l e r a t e d a l g o r i t h m e m p l o y s b o t h o p t i o n s f o r t h e p r i m a l a n d f o r t h e d u a l p r o c e d u r e t o f i n d f o u r a p p r o x i m a t e s o l u t i o n s t o t h e c u r r e n t CR p r o b l e m . T h e s o l u t i o n w i t h t h e s m a l l e s t o b j e c t i v e f u n c t i o n v a l u e i s u s e d t o g e n e r a t e t h e c o v e r i n g c o n s t r a i n t s t h a t w i l l be a d d e d t o t h e c u r r e n t CR p r o b l e m . 37 6.2 G r e e d y - l i k e P r o c e d u r e s f o r t h e MC P r o b l e m T h e two a p p r o x i m a t e p r o c e d u r e s f o r t h e MC p r o b l e m a r e a g a i n a v a r i a t i o n o f t h e g r e e d y t h e me. T o s i m p l i f y t h e d i s c u s s i o n , c o n s i d e r a s l i g h t l y d i f f e r e n t f o r m u l a t i o n o f t h e MC p r o b l e m : M i n i m i z e | U ( y ) | s u b j e c t t o | a j y j > b y je{o,i}, w h e r e U ( y ) i s t h e u n i o n o f a l l N j f o r w h i c h y j = l . N j i s t h e s e t o f v a r i a b l e s i n t h e j t h t e r m , R i s t h e s e t o f n o n - v a n i s h i n g t e r m s d e f i n e d e a r l i e r , a s b e f o r e d e f i n e !- 1 i f yi i s f r e e 0 i f y i i s f i x e d t o e i t h e r 0 o r 1 F ( y ) = { i | f i = l } . f i = V ( y ) r e p r e s e n t s t h e s e t o f f r e e v a r i a b l e s i n t h e c u r r e n t p a r t i a l c o v e r i n g c o n s t r a i n t . 38 MC PRIMAL G R E E D Y - L I K E PROCEDURE V := U n i o n N j f o r V J 6 R ; y := 1; f := 1; r e p e a t f o r j 6 F i f a-j > > a i Y i ~ D t h e n f-i=0; i 6 F i f F?i0 t h e n  b e g i n f o r j 6 F c o m p u t e p j := ( | V | - | V / N j | ) / a j ; k := MAX p-;, i n c a s e o f a t i e MAX a j ; j S F y k := 0; f k := 0; V := V / N k ; e n d  u n t i l F=0 s t o p . MC DUAL G R E E D Y - L I K E PROCEDURE V := 0; y := 0; f := 1; r e p e a t f o r j S F c o m p u t e p j := ( | U n i o n ( V , N j ) | - | V | ) / a j ; k := MIN p-;, i n c a s e o f a t i e MAX a-;; j G F Yk : = 1 ' f k : = °' V := U n i o n ( V , N k ) ; u n t i l F=0 s t o p . 39 7. E v a l u a t i o n o f t h e A c c e l e r a t e d C o v e r i n g R e l a x a t i o n A l g o r i t h m T h e d e v e l o p m e n t o f an a l g o r i t h m f o r a m a t h e m a t i c a l o p t i m i z a t i o n p r o b l e m i s o f t e n an i t e r a t i v e p r o c e s s . O n c e an i n i t i a l a l g o r i t h m h a s b e e n d e v e l o p e d a c o r r e c t a n d r e l i a b l e i m p l e m e n t a t i o n i s r e q u i r e d t o i n v e s t i g a t e t h e a v e r a g e b e h a v i o u r o f t h e a l g o r i t h m . A n a l y t i c t e c h n i q u e s f o r d e t e r m i n i n g a v e r a g e a n d w o r s t - c a s e b e h a v i o u r t e n d t o f a i l b e c a u s e t h e a l g o r i t h m i s a l m o s t a l w a y s t o o c o m p l e x t o o b t a i n a n y v a l u a b l e r e s u l t s . I f t h e e x p e r i m e n t a l r e s u l t s show t h e i n i t i a l a l g o r i t h m t o be p r o m i s i n g , t h e n t h e d e v e l o p m e n t p r o c e s s c a n a d v a n c e t o t h e n e x t s t a g e i n o r d e r t o a s s e s s t h e e f f e c t i v e n e s s o f s t r a t e g i e s a n d c o m b i n a t i o n s o f s t r a t e g i e s t h a t c a n be i n c o r p o r a t e d t o i m p r o v e t h e p e r f o r m a n c e o f t h e a l g o r i t h m . T h i s s t a g e i s r e p e a t e d u n t i l e i t h e r t h e p e r f o r m a n c e o f t h e a l g o r i t h m b e c o m e s s a t i s f a c t o r y o r u n t i l t h e a l g o r i t h m d e s i g n e r s a b a n d o n t h e p r o j e c t f o r l a c k o f e f f e c t i v e s t r a t e g i e s . I f e m p i r i c a l t e c h n i q u e s a r e u s e d t o i n v e s t i g a t e t h e p r o p e r t i e s o f t h e a l g o r i t h m , t h e n t h e a l g o r i t h m ' s p e r f o r m a n c e w i l l d e p e n d o n t h e c l a s s o f p r o b l e m s on w h i c h t h e a l g o r i t h m i s t e s t e d . A v e r a g e b e h a v i o u r i s , t h e r e f o r e e x p r e s s e d w i t h r e s p e c t t o a p a r t i c u l a r c l a s s o f p r o b l e m s . T r u l y a v e r a g e b e h a v i o u r i s d i f f i c u l t t o d e t e r m i n e e m p i r i c a l l y b e c a u s e t h e c o n c e p t o f a r a n d o m p r o b l e m i s v a g u e . I d e a l l y , t h e c l a s s o f p r o b l e m s on w h i c h t h e a l g o r i t h m i s t e s t e d i s r e p r e s e n t a t i v e o f r e a l w o r l d p r o b l e m s . I n v i e w o f t h e s e o b s e r v a t i o n s , c a r e f u l d e s i g n a n d c o m p l e t e 40 a n d a c c u r a t e r e p o r t i n g o f c o m p u t a t i o n a l e x p e r i m e n t s a r e p a r t i c u l a r l y i m p o r t a n t a s p e c t s o f t h e d e v e l o p m e n t o f m a t h e m a t i c a l p r o g r a m m i n g a l g o r i t h m s a n d s o f t w a r e . C r o w d e r e t a l [4] h a v e recommended a s e t o f g u i d e l i n e s f o r d e s i g n i n g a n d p r e s e n t i n g c o m p u t a t i o n a l e x p e r i m e n t s . T h e i r s u r v e y o f t h e p r o f e s s i o n a l j o u r n a l s f o u n d t h e s t a n d a r d s i n t h i s a r e a t o be i n a d e q u a t e . T h i s t h e s i s a d h e r e s w h e r e p o s s i b l e t o t h e r e c o m m e n d a t i o n s o f [ 4 ] . 7.1 A s p e c t s o f t h e I m p l e m e n t a t i o n The f o l l o w i n g s e c t i o n s s u p p l y t h e p e r t i n e n t i n f o r m a t i o n a b o u t t h e i m p l e m e n t a t i o n o f t h e c o v e r i n g r e l a x a t i o n a l g o r i t h m f o r t h e PP p r o b l e m w h i c h w i l l a l l o w t h e r e a d e r t o c o r r e c t l y i n t e r p r e t t h e e x p e r i m e n t a l r e s u l t s t h a t w i l l be d i s c u s s e d i n s e c t i o n 7.3. I n k e e p i n g w i t h t h e t i m e - h o n o u r e d a n d w i d e s p r e a d c o n v e n t i o n i n t h i s f i e l d o f s c i e n t i f i c e n d e a v o u r , t h e p r o g r a m was w r i t t e n i n FORTRAN^. The r e a d e r w i l l p a r d o n t h e a u t h o r f o r o m i t t i n g t h e u s u a l j u s t i f i c a t i o n s . T he p r o g r a m c o n s i s t s o f more t h a n f i f t y f u n c t i o n s a n d s u b r o u t i n e s . T h e s o u r c e c o d e , i n c l u d i n g c omments, i s r o u g h l y 6000 l i n e s l o n g . D u r i n g t h e c o u r s e o f t h e e x p e r i m e n t s , o v e r 2000 r a n d o m l y g e n e r a t e d p r o b l e m s w e r e s o l v e d . A l l known b u g s h a v e b e e n r e m o v e d f r o m t h e p r o g r a m . 1 F o r p o r t a b i l i t y , ANSI FORTRAN was e m p l o y e d . T h e p r o g r a m h a s b e e n t e s t e d o n IBM a n d DEC m a c h i n e s . 41 T h e P u r p o s e a n d C a l l i n g H i e r a r c h y o f t h e M a j o r P r o c e d u r e s 1. PP-OPT s o l v e s a PP p r o b l e m t o o p t i m a l i t y . I n p u t s : PP p r o b l e m ; a p p r o x i m a t e s o l u t i o n ; v a l u e o f an a p p r o x i m a t e s o l u t i o n w h i c h c a n be u s e d a s a l o w e r b o u n d . O u t p u t : o p t i m a l s o l u t i o n f o r t h e PP p r o b l e m . 1.1 CR-GENERATOR g e n e r a t e s an a u g m e n t e d CR p r o b l e m i f t h e s o l u t i o n f o r t h e c u r r e n t CR p r o b l e m i s i n f e a s i b l e t o t h e o r i g i n a l PP p r o b l e m . C o v e r i n g c o n s t r a i n t s a r e s e l e c t e d f r o m a p o o l o f c o n s t r a i n t s w h i c h i s f o r m e d by r e p e a t e d l y i n v o k i n g SOLVE-MC. I n p u t : a p p r o x i m a t e o r o p t i m a l s o l u t i o n f o r t h e c u r r e n t CR p r o b l e m . O u t p u t s : l o g i c a l v a r i a b l e w h i c h i s t r u e i f t h e s o l u t i o n t o t h e c u r r e n t CR p r o b l e m i s f e a s i b l e t o t h e o r i g i n a l p r o b l e m ; a u g m e n t e d CR p r o b l e m . 1.1.1 SOLVE-MC c o l l e c t s a s m a l l s e t o f s o l u t i o n s f o r t h e MC p r o b l e m u s i n g an i m p l i c i t e n u m e r a t i o n . I n p u t s : p o s y n o m i a l c o n s t r a i n t ; i n t e g e r v a r i a b l e i n d i c a t i n g t h e maximum number o f s o l u t i o n s t h a t w i l l be e x a m i n e d . O u t p u t : s e t o f t h e k b e s t c o v e r i n g c o n s t r a i n t s f o u n d i n t h e s e a r c h o f t h e s o l u t i o n t r e e . k i s a c o n s t a n t . 42 1.1.2 ADD-CC a d d s a c o v e r i n g c o n s t r a i n t t o t h e CR p r o b l e m a n d r e m o v e s d o m i n a t e d c o n s t r a i n t s . I n p u t : c o v e r i n g c o n s t r a i n t . O u t p u t : u p d a t e d CR p r o b l e m . 1.1.3 E L C OLS f i n d s t h e v a r i a b l e s w hose v a l u e s c a n be d e t e r m i n e d i n a d v a n c e a n d e l i m i n a t e s t hem f r o m t h e CR p r o b l e m . I n p u t : CR p r o b l e m . O u t p u t : r e d u c e d CR p r o b l e m . 1.2 SC-APPRO f i n d s an a p p r o x i m a t e s o l u t i o n f o r a SC p r o b l e m u s i n g t h e g r e e d y - l i k e p r o c e d u r e s d e s c r i b e d e a r l i e r . I n p u t : CR p r o b l e m . O u t p u t : a p p r o x i m a t e s o l u t i o n f o r t h e CR p r o b l e m . 1.3 SC-OPT f i n d s an o p t i m a l s o l u t i o n f o r a SC p r o b l e m u s i n g a n i m p l i c i t e n u m e r a t i o n . I n p u t s : CR p r o b l e m ; l o w e r b o u n d ; s t a r t i n g n o d e . O u t p u t s : o p t i m a l s o l u t i o n f o r t h e CR p r o b l e m ; f i r s t f e a s i b l e s o l u t i o n . 2. PP-APPRO f i n d s an a p p r o x i m a t e s o l u t i o n f o r a PP p r o b l e m u s i n g a g r e e d y - l i k e p r o c e d u r e . I n p u t : PP p r o b l e m . O u t p u t : a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m . 43 G e n e r a t i n g C o v e r i n g C o n s t r a i n t s V a r i o u s s t r a t e g i e s c a n be u s e d i n CR-GENERATOR f o r s e l e c t i n g t h e c o v e r i n g c o n s t r a i n t s t h a t a r e t o be a d d e d t o t h e c u r r e n t CR p r o b l e m . F i r s t l y , i t i s p o s s i b l e t o s e t a l o w e r b o u n d o n t h e number o f c o v e r i n g c o n s t r a i n t s t h a t CR-GENERATOR w i l l a t t e m p t t o a d d t o t h e c u r r e n t CR p r o b l e m . I f o n l y a few p o s y n o m i a l c o n s t r a i n t s a r e v i o l a t e d , t h e n i t i s o f t e n a d v a n t a g e o u s t o a d d more t h a n o n e c o n s t r a i n t f r o m a v i o l a t e d p o s y n o m i a l c o n s t r a i n t . S e c o n d l y , i t i s p o s s i b l e t o v a r y t h e manner i n w h i c h t h e c o v e r i n g c o n s t r a i n t s a r e s e l e c t e d f r o m t h e p o o l o f c o n s t r a i n t s g e n e r a t e d b y SOLVE-MC: 1) a d d a t l e a s t o n e c o v e r i n g c o n s t r a i n t f r o m e a c h v i o l a t e d p o s y n o m i a l c o n s t r a i n t , 2) a d d t h e k c o v e r i n g c o n s t r a i n t s w i t h t h e s m a l l e s t c a r d i n a l i t i e s f r o m t h e p o o l , w h e r e k i s t h e maximum o f t h e e a r l i e r m e n t i o n e d l o w e r b o u n d a n d t h e number o f v i o l a t e d p o s y n o m i a l c o n s t r a i n t s . Some o t h e r p o s s i b i l i t i e s s u c h a s c h o o s i n g c o n s t r a i n t s a t r a n d o m w e r e f o u n d t o be i n e f f e c t i v e . SOLVE-MC u s e s a f i x e d b r a n c h i n g s t r a t e g y f o r i m p l i c i t l y e n u m e r a t i n g t h e s o l u t i o n t r e e o f a MC p r o b l e m i n a d e p t h - f i r s t m a n n e r . SOLVE-MC c o l l e c t s t h e f i v e b e s t s o l u t i o n s e n c o u n t e r e d . O b s e r v e t h a t i f t h e f i r s t s o l u t i o n e n c o u n t e r e d i s an o p t i m a l s o l u t i o n , t h e n no w o r s e s o l u t i o n c a n be c o l l e c t e d . T h e o r d e r i n g o f t h e v a r i a b l e s i s s u c h t h a t a k < a k + l ' w h e r e a k i s t h e 44 c o e f f i c i e n t o f t h e k t h t e r m , o r a l t e r n a t i v e l y , s u c h t h a t a k / l N k l - a k + l / l N k + l l ' w h e r e N k i s t h e s e t o f v a r i a b l e s i n t h e k t h t e r m . The s e a r c h o f t h e s o l u t i o n t r e e t e r m i n a t e s a f t e r M a x s s o l u t i o n s h a v e b e e n f o u n d . M a x s i s a p a r a m e t e r o f SOLVE-MC. M a x s = l i n t h e b a s i c a l g o r i t h m . S o l v i n g t h e SC P r o b l e m SC-OPT u s e s a f i x e d b r a n c h i n g s t r a t e g y f o r i m p l i c i t l y e n u m e r a t i n g t h e s o l u t i o n t r e e o f a SC p r o b l e m i n a d e p t h - f i r s t m a n n e r . The o r d e r i n g o f t h e v a r i a b l e s i s d e t e r m i n e d by t h e i r c o s t - c o e f f i c i e n t s . No s u r r o g a t e c o n s t r a i n t s o r s u b g r a d i e n t o p t i m i z a t i o n t e c h n i q u e s ( s e e f o r e x a m p l e [ 1 , 5 , 1 8 ] ) a r e e m p l o y e d . SC-OPT r e t u r n s t h e o p t i m a l a n d f i r s t f e a s i b l e s o l u t i o n s f o r t h e SC p r o b l e m . A l o w e r b o u n d , s u p p l i e d by SC-APPRO, c u r t a i l s t h e s e a r c h f o r t h e o p t i m a l s o l u t i o n . F u r t h e r m o r e , t h e f i r s t f e a s i b l e s o l u t i o n f r o m t h e p r e v i o u s CR p r o b l e m s o l v e d t o o p t i m a l i t y , i f t h e r e i s o n e , i s u s e d a s a s t a r t i n g n o d e . No n o d e s t h a t o c c u r i n t h e s o l u t i o n t r e e b e f o r e t h e f i r s t f e a s i b l e s o l u t i o n c a n h a v e a f e a s i b l e c o m p l e t i o n , s i n c e e v e r y CR p r o b l e m i s a t i g h t e r r e l a x a t i o n t h a n e a c h o f i t s p r e d e c e s s o r s , a n d w i l l , t h e r e f o r e , n o t h a v e t o be e x a m i n e d . Th e s p e c i a l s t r u c t u r e o f t h e c o v e r i n g c o n s t r a i n t s i s n o t u s e d t o e x p l o i t t h e b o o l e a n o p e r a t i o n s a v a i l a b l e a t t h e m a c h i n e l a n g u a g e l e v e l . SC-OPT r e p r e s e n t s t h e s e t o f c o v e r i n g c o n s t r a i n t s b y a t w o - d i m e n s i o n a l i n t e g e r a r r a y c o n t a i n i n g o n l y 45 O's a n d l ' s . ( T h i s a r r a y o c c u p i e s r o u g h l y 60% o f t h e memory s p a c e r e q u i r e d by t h e d a t a s t r u c t u r e s o f t h e p r o g r a m . ) CPU t i m e a n d memory s p a c e r e q u i r e m e n t s c a n be r e d u c e d by an o r d e r o f m a g n i t u d e i f a l l b i t s i n a w o r d a r e u s e d , s e e [ 1 6 ] . T h e t e c h n i q u e s d e s c r i b e d i n [16] a r e , u n f o r t u n a t e l y , m a c h i n e d e p e n d e n t and c o m p l i c a t e t h e t a s k o f t h e i m p l e m e n t o r c o n s i d e r a b l y . M o r e o v e r , t h e u s e o f t h e s e k i n d s o f t e c h n i q u e s t e n d s t o s h i f t t h e a t t e n t i o n away f r o m t h e a l g o r i t h m i c a s p e c t s o f t h e p r o b l e m and i s , t h e r e f o r e , i n a p p r o p r i a t e g i v e n t h e s t a t u s o f t h e r e s e a r c h r e p o r t e d i n t h i s t h e s i s . 7.2 P r o b l e m G e n e r a t i o n An e s s e n t i a l t o o l f o r t h e a n a l y s i s o f t h e c o v e r i n g r e l a x a t i o n a l g o r i t h m i s a p r o b l e m g e n e r a t o r w h i c h i s n e e d e d t o s u p p l y a c l a s s o f r e p r o d u c i b l e p r o b l e m s f o r w h i c h t h e p e r f o r m a n c e o f t h e a l g o r i t h m c a n be d e t e r m i n e d . T h i s s e c t i o n d e s c r i b e s t h e g e n e r a t o r o f PP p r o b l e m s and i t s p a r a m e t e r s . PROBLEM PARAMETERS a l p h a i s a m e a s u r e o f t h e t i g h t n e s s o f a c o n s t r a i n t N i s t h e number o f v a r i a b l e s M i s t h e number o f c o n s t r a i n t s P i s t h e maximum number o f t e r m s i n a c o n s t r a i n t E i s t h e maximum number o f f a c t o r s i n a t e r m s e e d i n i t i a l i z e s t h e r a n d o m number g e n e r a t o r 46 U n i f o r m ( s , t ) r e t u r n s an i n t e g e r r a n d o m l y d i s t r i b u t e d b e t w e e n s a n d t . PP PROBLEM GENERATOR ( s e e d , N, M, P, E , a l p h a ) i n t e g e r P, E ; i n t e g e r N, M, s e e d ; r e a l a l p h a , 0 < a l p h a < 1; b e g i n i n i t i a l i z e U n i f o r m ( s e e d ) ; c 0 := 1; f o r j : = l t o N d o CJ := C j _ ^ + U n i f o r m ( 0 , 1 0 ) ; f o r i : = l t o M d o  b e g i n p ( i ) := U n i f o r m ( l , P ) ; f o r j : = l t o p ( i ) d o  b e g i n a ^ j := U n i f o r m ( l , 2 0 ) N i j := 0; f o r k:= 1 t o U n i f o r m ( 1 , E ) d o Nj[j := U n i o n ( N ^ j , { U n i f o r m ( l , n ) }) ; Nj^j i s t h e s e t o f v a r i a b l e s i n t e r m i j e n d n bj[ := J a i j ; j = l e n d e n d . 47 7.3 C o m p u t a t i o n a l r e s u l t s T h e m a j o r o b j e c t i v e o f t h i s s e c t i o n i s t o show t h a t t h e m o d i f i c a t i o n s o f t h e o r i g i n a l c o v e r i n g r e l a x a t i o n a l g o r i t h m t h a t w e r e p r e s e n t e d i n c h a p t e r 5 h a v e s i g n i f i c a n t l y i m p r o v e d t h e p e r f o r m a n c e o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h . T h e s e i m p r o v e m e n t s a r e m a i n l y d u e t o a 70% r e d u c t i o n i n t h e number o f SC p r o b l e m s t h a t h a v e t o be s o l v e d t o o p t i m a l i t y i n o r d e r t o p r o d u c e an o p t i m a l s o l u t i o n t o a PP p r o b l e m . E x p e r i m e n t a l d e s i g n T o e v a l u a t e t h e m o d i f i c a t i o n s , v a r i o u s m e t h o d s , t o be d e s c r i b e d s h o r t l y , w e r e t e s t e d f o r t h e f o l l o w i n g c l a s s o f PP p r o b l e m s : N M P E a l p h a 30 30 ( 2 , 5 , ... 17,20) ( 1 , 5 , 9 ) 0.5 40 40 ( 2 , 5 , ... 17,20) ( 1 , 5 , 9 ) 0.5 The c h o i c e o f t h i s p a r t i c u l a r c l a s s was d e t e r m i n e d by a number o f d i f f e r e n t f a c t o r s : The m o d i f i c a t i o n s t h a t a r e i n c o r p o r a t e d i n t h e a c c e l e r a t e d c o v e r i n g c o v e r i n g r e l a x a t i o n a l g o r i t h m w e r e p r i m a r i l y d e v e l o p e d t o r e d u c e t h e number o f SC p r o b l e m s t h a t h a v e t o be s o l v e d t o o p t i m a l i t y . I t i s n e c e s s a r y , t h e r e f o r e , t o e v a l u a t e t h e i r e f f e c t i v e n e s s f o r PP p r o b l e m s f o r w h i c h an o p t i m a l s o l u t i o n i s p r o d u c e d a t t h e c o s t o f s o l v i n g many SC p r o b l e m s t o o p t i m a l i t y . 48 The e x t e n s i v e e x p e r i m e n t s p e r f o r m e d i n [10 ] show t h a t 1) t h e a v e r a g e number o f t e r m s i n a p o s y n o m i a l c o n s t r a i n t i s t h e d o m i n a n t p a r a m e t e r a f f e c t i n g t h e number o f SC p r o b l e m s t h a t h a v e t o be s o l v e d t o o p t i m a l i t y ; t h i s number a p p e a r s t o i n c r e a s e l i n e a r l y w i t h P 2) t h e o v e r a l l CPU t i m e r e q u i r e d t o s o l v e a PP p r o b l e m i n c r e a s e s d r a m a t i c a l l y a s N b e c o m e s l a r g e , ( T h i s i n c r e a s e i s , o f c o u r s e , d u e t o an e x p o n e n t i a l i n c r e a s e i n t h e s i z e o f t h e s o l u t i o n s p a c e s o f t h e SC p r o b l e m s t o be s o l v e d . ) 3) PP p r o b l e m s w i t h a l p h a = 0 . 5 a r e t h e m o s t d i f f i c u l t . F i g u r e 1. c l e a r l y shows t h a t t h e s i z e o f t h e PP p r o b l e m s t h a t c a n be s o l v e d i s b o u n d e d by t h e d i f f i c u l t y o f t h e SC p r o b l e m s . T h e f o l l o w i n g c o n c l u s i o n s c a n be d r a w n : 1) N i s a s e c o n d a r y f a c t o r i n t h e e v a l u a t i o n o f t h e a c c e l e r a t e d a l g o r i t h m . 2) P, h o w e v e r , i s a p r i m a r y f a c t o r . 3) The p e r f o r m a n c e o f t h e c o v e r i n g r e l a x a t i o n a l g o r i t h m f o r PP p r o b l e m s w i t h l a r g e N w i l l m a i n l y be i m p r o v e d by e m p l o y i n g a more s o p h i s t i c a t e d t e c h n i q u e f o r s o l v i n g t h e SC p r o b l e m s . P e r f o r m a n c e i n d i c a t o r s The f o l l o w i n g i n d i c a t o r s a r e u s e d t o a s s e s s t h e p e r f o r m a n c e o f t h e a l g o r i t h m : CPU i s t h e e x e c u t i o n t i m e ( s e c o n d s ) r e q u i r e d t o s o l v e a PP p r o b l e m . T h e t i m e r e q u i r e d t o g e n e r a t e t h e p r o b l e m a n d t o o b t a i n 49 an a p p r o x i m a t e s o l u t i o n i s e x c l u d e d f r o m CPU. A n e g l i g i b l e amount o f I/O t i m e i s i n c l u d e d . T he m e a s u r e m e n t s w e r e o b t a i n e d o n an AMDAHL 470 V / 6 - I I u n d e r MTS u s i n g t h e FORTRAN H o p t i m i z i n g c o m p i l e r . CPU was f o u n d t o v a r y a b o u t 1% w i t h t h e l o a d o f t h e i n s t a l l a t i o n . CR-CPU i s t h e t o t a l e x e c u t i o n t i m e r e q u i r e d f o r s o l v i n g t h e SC p r o b l e m s t o o p t i m a l i t y . OPT i s t h e number o f SC p r o b l e m s t h a t w e r e s o l v e d t o o p t i m a l i t y i n o r d e r t o s o l v e a PP p r o b l e m . HEUR i s t h e number o f SC p r o b l e m s s o l v e d a p p r o x i m a t e l y . COVERS i s t h e number o f c o v e r i n g c o n s t r a i n t s i n t h e f i n a l SC p r o b l e m s o l v e d t o o p t i m a l i t y . D E N S ITY i s t h e d e n s i t y o f t h e f i n a l SC p r o b l e m . E F F E C T I V E N E S S i s t h e a v e r a g e o f ( ( b e s t a p p r o x i m a t e v a l u e I o p t i m a l v a l u e ) ) 1 0 0 % f o r a l l s C p r o b l e m s t h a t w e r e s o l v e d t o o p t i m a l i t y . M e t h o d s i n v e s t i g a t e d T o e v a l u a t e t h e v a r i o u s m o d i f i c a t i o n s a n d s t r a t e g i e s t h a t w e r e d i s c u s s e d i n c h a p t e r s 5, 6 a n d 7 t h e f o l l o w i n g m e t h o d s w e r e t e s t e d : METHOD I i s t h e b a s i c c o v e r i n g r e l a x a t i o n a l g o r i t h m d i s c u s s e d i n c h a p t e r 3. One c o v e r i n g c o n s t r a i n t i s g e n e r a t e d f r o m e a c h v i o l a t e d p o s y n o m i a l c o n s t r a i n t a n d M a x s = l . METHOD I I i s t h e same a s METHOD I e x c e p t t h a t m o d i f i c a t i o n 1 50 d i s c u s s e d i n c h a p t e r 5 i s i n c o r p o r a t e d . METHOD I I I i s t h e same a s METHOD I I e x c e p t t h a t m o d i f i c a t i o n 2 d i s c u s s e d i n c h a p t e r 5 i s a l s o i n c o r p o r a t e d . METHOD I V i s t h e same a s METHOD I I I e x c e p t t h a t (1) t h e t e r m s i n a p o s y n o m i a l c o n s t r a i n t a r e o r d e r e d s u c h t h a t afc-n/lN^.,.! | > a k / | N k | a n d (2) M a x s = 5 , i . e . t h e e n u m e r a t i o n o f t h e MC p r o b l e m s t e r m i n a t e s a f t e r 5 s o l u t i o n s h a v e b e e n e n c o u n t e r e d . ( S e e s e c t i o n 7.1) METHOD IVA i s t h e same a s METHOD I I I e x c e p t t h a t M a x s = i n f i n i t y , i . e . t h e e n u m e r a t i o n o f t h e MC p r o b l e m s i s n o t r e s t r i c t e d . METHOD V i s t h e same a s METHOD IVA e x c e p t t h a t t h e k c o v e r i n g c o n s t r a i n t s w i t h t h e s m a l l e s t c a r d i n a l i t i e s a r e s e l e c t e d . k i s s e t e q u a l t o t h e number o f v i o l a t e d p o s y n o m i a l c o n s t r a i n t s . ( S e e s e c t i o n 7.1) METHOD VA i s t h e same a s METHOD V e x c e p t t h a t k i s s e t t o m a x { k f ( 0 . 2 M ) } . METHOD VAA i s t h e same a s METHOD VA e x c e p t t h a t t h e " w e i g h t i n g f a c t o r " h a s b e e n d r o p p e d f r o m t h e a p p r o x i m a t e p r o c e d u r e s f o r t h e SC p r o b l e m t h a t w e r e d e s c r i b e d i n s e c t i o n 6.1. C o n c l u s i o n s T h e f o l l o w i n g c o n c l u s i o n s a r e d r a w n f r o m t h e t a b l e s a n d t h e f i g u r e s t h a t c a n be f o u n d a t t h e e n d o f t h i s c h a p t e r . E a c h e n t r y i n t h e s i x t a b l e s was o b t a i n e d by c o m p u t i n g t h e a v e r a g e o f 51 t e n s a m p l e s . T a b l e I a s s e s s e s t h e i m p r o v e m e n t s o b t a i n e d by ( i ) s o l v i n g a n SC p r o b l e m t o o p t i m a l i t y o n l y when i t s a p p r o x i m a t e s o l u t i o n i s f e a s i b l e t o t h e PP p r o b l e m t o be s o l v e d ( i . e . m o d i f i c a t i o n 1) a n d ( i i ) u s i n g an a p p r o x i m a t e s o l u t i o n f o r t h e PP p r o b l e m t o g e n e r a t e CRQ ( i . e . m o d i f i c a t i o n 2 ) . T a b l e I shows t h a t 1) m o d i f i c a t i o n 1 r e d u c e s t h e number o f SC p r o b l e m s t o be s o l v e d t o o p t i m a l i t y b y 65% a n d t h e o v e r a l l CPU t i m e b y 5 0%; h o w e v e r , m o d i f i c a t i o n 1 i n c r e a s e s t h e number o f i t e r a t i o n s ( a s m e a s u r e d by t h e number o f SC p r o b l e m s s o l v e d t o o p t i m a l i t y f o r METHOD I a n d a p p r o x i m a t e l y f o r METHOD I I ) a n d t h e number o f c o v e r i n g c o n s t r a i n t s i n t h e f i n a l SC p r o b l e m 2) a d d i t i o n a l i m p r o v e m e n t s a r e r e a l i z e d b y a p p l y i n g m o d i f i c a t i o n 2; e x p l i c i t l y , t h e number o f c o v e r i n g c o n s t r a i n t s i n t h e f i n a l SC p r o b l e m a n d t h e number o f SC p r o b l e m s s o l v e d a p p r o x i m a t e l y a r e r e d u c e d . T a b l e I I a s s e s s e s t h e e f f e c t i v e n e s s o f t h e v a r i o u s s t r a t e g i e s f o r g e n e r a t i n g a n d s e l e c t i n g c o v e r i n g c o n s t r a i n t s . T a b l e I I shows t h a t 3) f o r l a r g e v a l u e s o f P, m o d i f i c a t i o n 3 r e d u c e s t h e o v e r a l l CPU t i m e a n d t h e number o f SC p r o b l e m s s o l v e d a p p r o x i m a t e l y 4) t h e p e r f o r m a n c e o f t h e a l g o r i t h m i s n o t i m p r o v e d b y s o l v i n g t h e MC p r o b l e m s t o o p t i m a l i t y (When P i s v e r y l a r g e t h i s may no l o n g e r be t r u e ) 5) t h e d e n s i t y o f t h e SC p r o b l e m s i s r e d u c e d , a s e x p e c t e d , b y s e l e c t i n g m i n i m a l c a r d i n a l i t y c o v e r i n g c o n s t r a i n t s . T a b l e I I I shows t h a t 52 6) s u b s t a n t i a l i m p r o v e m e n t s a r e r e a l i z e d by g e n e r a t i n g a t l e a s t .2M m i n i m a l c o v e r i n g c o n s t r a i n t s a t e a c h i t e r a t i o n ; e x p l i c i t l y , b o t h t h e number o f SC p r o b l e m s s o l v e d t o o p t i m a l i t y a n d t h e o v e r a l l CPU t i m e a r e r e d u c e d . T a b l e I V shows t h a t 7) PP p r o b l e m s w i t h l a r g e r E a r e e a s i e r t o s o l v e . T a b l e V shows t h a t 8) t h e SC p r o b l e m s become more d i f f i c u l t t o s o l v e i f P i s i n c r e a s e d t o 30; h o w e v e r , t h e number o f SC p r o b l e m s t o be s o l v e d t o o p t i m a l i t y a p p e a r s t o grow l i n e a r l y w i t h P. T a b l e V I shows t h a t 9) t h e " w e i g h t i n g f a c t o r " i m p r o v e s t h e e f f e c t i v e n e s s o f a p p r o x i m a t e p r o c e d u r e s f o r t h e SC p r o b l e m ; more s i g n i f i c a n t l y , t h e o v e r a l l p e r f o r m a n c e o f t h e a c c e l e r a t e d c o v e r i n g r e l a x a t i o n a l g o r i t h m i m p r o v e s e v e n i f o n l y a s m a l l i m p r o v e m e n t i n t h e e f f e c t i v e n e s s o f t h e a p p r o x i m a t e p r o c e d u r e s f o r t h e SC p r o b l e m i s o b t a i n e d . I n summary, a l l t h r e e m o d i f i c a t i o n s h a v e i m p r o v e d t h e p e r f o r m a n c e o f t h e c o v e r i n g r e l a x a t i o n a p p r o a c h . METHOD VA, t h e b e s t a c c e l e r a t e d c o v e r i n g r e l a x a t i o n m e t h o d , r e q u i r e s r o u g h l y 70% l e s s CPU t i m e a n d s o l v e s r o u g h l y 70% f e w e r SC p r o b l e m s t o o p t i m a l i t y t h a n METHOD I , t h e b a s i c c o v e r i n g r e l a x a t i o n m e t h o d . F i g u r e 2. i l l u s t r a t e s t h e e x t e n t t o w h i c h t h e c o v e r i n g r e l a x a t i o n a p p r o a c h h a s b e e n i m p r o v e d . F u r t h e r i m p r o v e m e n t s c a n be e x p e c t e d i f more e f f e c t i v e a p p r o x i m a t e p r o c e d u r e s a r e e m p l o y e d t o s o l v e t h e SC p r o b l e m , s e e (9) a b o v e . Table I : alpha = 0.5, E = 5. METHOD I mxn 30x30 40x40 2 5 8 11 14 17 20 2 5 8 11 14 17 20 CPU 0.1 0.3 1.1 2.0 2.6 8.1 10.0 0.2 3.8 11.8 21.3 44.2 71.6 84.7 OPT. 1 2 4 5 6 10 10.9 ~ o ~ 3.2 5.0 5.9 8.5 10.3 11.5 HEUR. COVERS 11.6 18.7 27.9 37.8 50.2 78.9 76.7 16.8 25.4 40.2 50.4 70.7 100.6 99.1 METHOD II CPU OPT. HEUR. 0.1 0.3 0.9 1.2 1.8 5.5 6.2 1.0 1.1 1.6 1.5 1.6 3.1 3.2 0.3 3.2 6.8 9.7 27.0 38.1 45.3 1.0 1.1 1.6 1.6 3.2 3.5 4.0 1.0 2.6 5.1 6.0 7.0 12.3 12.0 1.0 3.5 6.0 7.4 9.6 13.2 14.6 COVERS 11.6 19.1 28.4 38.4 52.0 78.6 78.7 16.8 25.8 41.9 51.8 76.8 109.9 106.1 METHOD I I I CPU OPT. HEUR. COVERS 0.1 0.3 0.7 1.0 1.6 5.3 5.4 1.0 1.1 1.3 1.1 1.7 2.8 2.9 1.0 2.0 0.3 2.0 4.4 6.6 18.7 38.0 41.5 1.1 1.0 1.3 1.4 2.5 3.5 3.8 1 2, 3, 5, 8. 11. 11. 10.4 17.7 25.0 36.4 43.4 67.9 70.9 14.3 23.1 36.1 46.5 67.6 99.8 93.9 Table I I : alpha = 0.5, E = 5. mxn P METHOD III METHOD IV METHOD IV A METHOD V CPU OPT. HEUR. COVERS DENSITY - CPU OPT. HEUR. COVERS DENSITY CPU OPT. HEUR. COVERS DENSITY CPU OPT. HEUR. COVERS DENSITY 30x30 2 5 8 11 14 17 20 0.1 1.0 1.0 10.4 0.09 0.3 1.1 2.0 17.7 0.13 0.7 1.3 3.9 25.0 0.17 1.0 1.1 4.7 36.4 0.21 1.6 1.7 4.8 43.4 0.23 5.3 2.8 9.1 67.9 0.29 5.4 2.9 9.5 70.9 0.31 0.1 1.0 1.0 10.4 0.09 0.3 1.1 1.7 17.9 0.13 0.7 1.3 3.6 25.4 0.16 0.8 1.1 4.3 36.7 0.21 1.1 1.4 4.1 45.6 0.23 4.2 2.3 7.2 69.1 0.28 4.4 2.9 6.9 66.9 0.30 0.1 1.0 1.0 10.4 0.09 0.3 1.1 1.7 17.9 0.13 0.7 1.3 3.6 25.4 0.16 0.8 1.1 4.3 36.7 0.21 1.1 1.4 4.1 45.6 0.23 4.2 2.3 7.2 69.1 0.28 4.2 2.7 6.9 66.7 0.30 0.1 1.0 1.0 10.3 0.09 0.3 1.1 1.8 18.0 0.13 0.7 1.3 3.6 25.2 0.16 0.8 1.1 4.6 36.9 0.20 1.1 1.5 4.1 42.5 0.22 3.6 2.6 7.9 62.0 0.26 3.8 2.8 7.2 63.9 0 28 40x40 2 5 8 11 14 17 20 0.3 1.1 1.2 14.3 0.07 2.0 1.0 2.2 23.1 0.10 4.4 1.3 3.8 36.1 0.14 6.6 1.4 5.0 46.5 0.16 18.7 2.5 8.0 67.6 0.19 38.0 3.5 11.0 99.8 0.24 41.5 3.8 11.3 93.9 0.25 0.3 1.1 1.2 14.3 0.07 2.0 1.1 2.1 23.3 0.10 4.6 1.3 3.9 37.8 0.13 6.5 1.4 5.1 45.9 0.16 19.0 2.9 7.7 69.1 0.19 28.1 2.7 8.3 95.0 0.23 34.3 3.6 9.3 93.5 0.24 0.3 1.1 1.2 14.3 0.07 2.0 1.1 2.1 23.3 0.10 4.5 1.3 3.9 37.8 0.13 6.5 1.4 5.1 45.9 0.16 19.0 2.9 7.7 69.1 0.19 28.2 2.7 8.3 95.0 0.23 34.8 3.6 9.4 94.9 0.24 0.3 1.1 1.2 14.3 0.07 1.9 1.1 2.1 23.3 0.10 4.5 1.3 4.0 37.9 0.13 5.8 1.3 4.5 44.4 0.16 11.6 2.8 6.2 61.0 0.18 30.2 3.6 8.7 85.1 0.21 32.2 3.8 9.4 86.8 0.22 Table I I I : alpha = 0.5, E = 5. METHOD V METHOD VA mxn P CPU OPT. HEUR COVERS DENSITY CPU OPT. HEUR. COVERS DENSITY 2 0.1 1.0 1 .0 10.4 0.09 0.1 1.0 1.0 10.4 0.09 5 0.3 1.1 1.8 18.0 0.13 0.3 1.1 1.7 17.7 0.13 8 0.7 1.3 3.6 25.2 0.16 0.6 1.1 3.1 26.2 0.16 30x30 11 0.8 1.1 4.6 36.9 0.20 0.8 1.1 3.6 37.6 0.21 14 1.1 1.5 4.1 42.5 0.22 1.1 1.3 3.6 44.6 0.22 17 3.6 2.6 7.9 62.0 0.26 2.1 2.4 7.1 66.7 0.27 20 3.8 2.8 7.2 63.9 0.28 2 .6 2.2 6.7 67.5 0.28 2 0.3 1.1 1.2 14.3 0.07 0.3 1.1 1.2 14.3 0.07 . 5 1.9 1.1 2.1 23.3 0.10 2.0 1.1 2.1 23.4 0.10 8 4.5 1.3 4.0 37.9 0.13 4.8 1.3 3.6 39.4 0.14 40x40 11 5.8 1.3 4.5 44.4 0.16 7.2 1.5 5.1 49.8 0.16 14 11.6 2.8 6.2 61 .0 0.18 13.6 2.4 6.0 70.4 0.18 17 30.2 3.6 8.7 85.1 0.21 24.0 2.9 8.5 98.1 0.22 20 32.2 3.8 9.4 86.8 0.22 25.8 3.0 8.9 100.9 0.23 Table IV: alpha = 0.5. METHOD VA E = 1 METHOD VA E = 5 METHOD VA E = 9 mxn P CPU OPT. HEUR. COVERS DENSITY CPU OPT. HEUR. COVERS DENSITY CPU OPT. HEUR. COVERS DENSITY 5 0.2 1.1 1.6 11.9 0.07 0.3 1.1 1.7 17.7 0.13 0.2 1.2 1.8 16.8 0.17 30x30 8 11 0.4 1.2 2.5 24.9 0.09 0.6 1.1 3.1 26.2 0.16 0.3 1.0 2.0 19.6 0.22 0.9 1.3 4.0 48.2 0.11 0.8 1.1 3.6 37.6 0.21 0.4 1.2 3.0 26.3 0.26 14 5.6 2.9 9.4 88.8 0.13 1.1 1.3 3.6 44.6 0.22 0.5 1.3 3.3 28.6 0.30 17 8.7 3.6 12.5 111.8 0.14 2.1 2.4 7.1 66.7 0.27 0.7 1.4 3.3 31.2 0.31 20 22.9 3.8 19.5 174.2 0.16 2.6 2.2 6.7 67.5 0.28 0.8 1.4 4.0 40.8 0.37 5 0.3 1.0 1.4 17.3 0.05 2.0 1.1 2.1 23.4 0.10 0.5 1.1 1.8 19.8 0.14 40x40 8 1.4 1.2 2.7 36.6 0.06 4.8 1.3 3.6 39.4 0.14 1.1 1.3 2.5 26.7 0.17 11 6.4 1.3 4.4 63.7 0.08 7.2 1.5 5.1 49.8 0.16 2.3 1.4 3.5 35.6 0.21 14 24.1 2.0 8.5 119.6 0.10 13.6 2.4 6.0 70.4 0.18 1.7 1.3 4.0 39.1 0.25 17 52.7* 4.3* 12.8* 164.3* 0.12* 24.0 2.9 8.5 98.1 0.22 3.2 2.3 4.4 46.5 0.27 20 + + + + + 25.8 3.0 8.9 100.9 0.23 2.7 2.1 5.5 60.1 0.32 * In two of the ten runs the optimal solution was not obtained after 150 seconds of CPU time. The average i s of the other eight runs. + No attempt was made to solve these problems. Table V: alpha = 0.5, E = 5. mxn P METHOD V A CPU OPT. HEUR. COVERS " DENSITY 2 0 .1 • 1.0 1.0 10.4 0.09 5 0 .3 1.1 1.7 17.7 0.13 8 0 .6 1.1 3.1 26.2 0.16 30x30 11 0 .8 1.1 3.6 37.6 0.21 14 1 .1 1.3 3.6 44.6 0.22 17 2 1 2.4 7.1 66.7 0.27 20 2 6 2.2 6.7 67.5 0.28 23 3 1 3.1 8.5 70.7 0.29 26 7 7 4.6 11.2 95.5 0.32 30 14 3 4.4 13.1 103.0 0.36 2 0. 3 1.1 1.2 14.3 0.07 5 2. 0 1.1 2.1 23.4 0.10 8 4. 8 1.3 3.6 39.4 0.14 11 7. 2 1.5 5.1 49.8 0.16 14 13. 6 2.4 6.0 70.4 0.18 40x40 17 24. 0 2.9 8.5 98.1 0.22 20 25. 8 3.0 8.9 100.9 0.23 23 31. 7 3.7 10.3 108.0 0.25 26 63. 8 5.2 13.2 148.6 0.27 + 30 64. 2 4.8 14.7 142.6 0.31 + + In one o f the ten runs the optimal s o l u t i o n s was not obtained a f t e r 200 seconds o f CPU time. The average i s o f the other nine runs. T a b l e V I : a l p h a = 0.5. mxn Method VA CPU OPT. HEUR. COVERS EFFECTIVENESS Method VAA CPU OPT. HEUR. COVERS EFFECTIVENESS] 30x30 40x40 2 0.1 1.0 1.0 10 .4 5 0 . 3 1.1 1.7 17 7 8 0 .6 1.1 3.1 26 2 11 0 . 8 1.1 3.6 37 6 14 1.1 1.3 3.6 44 6 17 2.1 2.4 7.1 66 7 20 2 .6 2 .2 6.7 67 5 2 0 .3 1.1 1 .2 14.3 5 2 .0 1.1 2 .1 23.4 8 4 . 8 1.3 3 6 39.4 11 7.2 1.5 5 1 49 .8 14 13.6 2.4 6 0 70.4 17 24.0 2.9 8 5 98.1 20 25.8 3.0 8 9 100.9 99.9 0.1 1.0 1.0 10.4 99.5 0 .3 1.1 1.9 18.0 99.5 0 .7 1.4 3.4 26.8 98.5 0 . 8 1.3 3.7 36.5 98.7 1.1 1.6 3.8 46.9 98.7 2.2 2.5 7.6 69.0 98.5 2.6 2.5 7.2 68.6 99.8 0 . 3 1.1 1.2 14.3 99.7 2.1 1.1 2.4 23.8 98.7 4 . 8 1.4 4.1 40.8 98.9 9 .0 1.7 4 .5 48.2 98.3 20.6 3.4 7.3 72.9 98.7 25.9 3.0 9 .3 98.1 98.8 33.9 3 .4 10.6 110.0 99.6 99.2 9 9 . 3 98.4 9 8 . 3 98.1 97.6 99, 99 98. 98. 98. 98. 98. Figure 1. CPU Time Use 60 F i g u r e 2. Method I vs Method VA N = 40, M =40, E = 5, a l p h a = 0.5. 10 S 5 Dots f o r Method I , P l u s s e s f o r Method VA. Data o b t a i n e d from t a b l e s I and V. P 61 8. B i b l i o g r a p h y 1. E . B a l a s a n d A. Ho, " S e t C o v e r i n g A l g o r i t h m s U s i n g C u t t i n g P l a n e s , H e u r i s t i c s a n d S u b g r a d i e n t O p t i m i z a t i o n : A C o m p u t a t i o n a l S t u d y " , WP No. 6-79-80, G S I A , J u l y 1 9 7 9 . 2. E . B a l a s a n d R. J e r o s l o w , " C a n o n i c a l C u t s o n t h e U n i t H y p e r p l a n e " , MSR r e p o r t No. 1 9 6 ( R ) , C a r n e g i e M e l l o n U n i v e r s i t y , A u g u s t - D e c e m b e r 1 9 6 9 , r e v i s e d F e b r u a r y 1 9 7 1 . 3. E . B a l a s a n d C. H. M a r t i n , " P i v o t a n d C o m p l e m e n t - A H e u r i s t i c f o r 0-1 P r o g r a m m i n g " , MSR r e p o r t No. 414, C a r n e g i e M e l l o n U n i v e r s i t y , F e b r u a r y 1 9 7 8 . 4. H. P. C r o w d e r , R. S. Dembo and J . M. M u l v e y , " R e p o r t i n g C o m p u t a t i o n a l E x p e r i m e n t s i n M a t h e m a t i c a l P r o g r a m m i n g " , M a t h e m a t i c a l P r o g r a m m i n g , V o l . 15 ( 1 9 7 8 ) , p p . 3 1 6 - 3 2 9 . 5. J . E t c h e b e r r y , "The S e t - C o v e r i n g P r o b l e m : A New I m p l i c i t E n u m e r a t i o n A l g o r i t h m " , O p e r a t i o n s R e s e a r c h , V o l . 25 ( 1 9 7 7 ) , p p . 7 6 0 - 7 7 2 . 6. B. F a a l a n d a n d F. S. H i l l i e r , " I n t e r i o r P a t h M e t h o d s f o r H e u r i s t i c I n t e g e r P r o g r a m m i n g P r o c e d u r e s " , O p e r a t i o n s  R e s e a r c h , V o l . 27 ( 1 9 7 9 ) , p p . 1 0 6 9 - 1 0 8 7 . 7. R. S. G a r f i n k e l a n d G. L . N e m h a u s e r , I n t e g e r P r o g r a m m i n g , W i l e y 1972. 8. F. G l o v e r a n d E . W o o l s e y , " F u r t h e r R e d u c t i o n o f 0-1 P o l y n o m i a l P r o g r a m m i n g P r o b l e m s t o 0-1 L i n e a r P r o g r a m m i n g P r o b l e m s " , O p e r a t i o n s R e s e a r c h , V o l . 21 ( 1 9 7 3 ) , p p . 1 4 1 - 1 6 1 . 9. F . G l o v e r a n d E . W o o l s e y , " C o n v e r t i n g t h e 0-1 P o l y n o m i a l P r o g r a m m i n g P r o b l e m t o a 0-1 L i n e a r P r o g r a m " , O p e r a t i o n s  R e s e a r c h , V o l . 22 ( 1 9 7 4 ) , p p . 1 8 0 - 1 8 2 . 10. D. G r a n o t , F . G r a n o t a n d J . K a l l b e r g , " C o v e r i n g R e l a x a t i o n f o r P o s i t i v e 0-1 P o l y n o m i a l P r o g r a m m i n g P r o b l e m s " , M a n a g e m e n t S c i e n c e V o l . 25, No. 3 ( 1 9 7 9 ) , p p . 2 6 4 - 2 7 3 . 1 1 . D. G r a n o t a n d F. G r a n o t , " G e n e r a l i z e d C o v e r i n g R e l a x a t i o n i n 0-1 P r o g r a m m i n g " , WP No. 533, F a c u l t y o f Commerce and B u s i n e s s A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h C o l u m b i a , D e c ember 1 9 7 7 . ( O p e r a t i o n s R e s e a r c h , f o r t h c o m i n g ) 12. D. G r a n o t a n d F . G r a n o t , "On U s i n g H e u r i s t i c s i n B e n d e r s P a r t i t i o n i n g P r o c e d u r e : I The L i n e a r C a s e " , WP No. 636, F a c u l t y o f Commerce and B u s i n e s s A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h C o l u m b i a , A u g u s t 1 9 7 9 . 62 13. F. G r a n o t , " E f f i c i e n t H e u r i s t i c A l g o r i t h m s f o r P o s i t i v e 0-1 P o l y n o m i a l p r o g r a m m i n g p r o b l e m s " , WP No. 595, F a c u l t y o f Commerce a n d B u s i n e s s A d m i n i s t r a t i o n , U n i v e r s i t y o f B r i t i s h C o l u m b i a , A u g u s t 1978. 14. F. G r a n o t a n d P. L. Hammer, "On t h e U s e o f B o o l e a n F u n c t i o n s i n 0-1 P r o g r a m m i n g " , M e t h o d s f o r O p e r a t i o n s R e s e a r c h , X I I ( 1 9 7 7 ) , p p . 1 5 4 - 1 8 4 . 15. F . G r a n o t a n d P. L. Hammer, "On t h e R o l e o f G e n e r a l i z e d C o v e r i n g P r o b l e m s " , C a h i e r s d u C e n t r e D ' E t u d e s d e R e c h e r c h e  O p e r a t i o n e l l e , V o l . 17 ( 1 9 7 5 ) , p p . 2 7 5 - 2 8 9 . 16. J . S. G r a v e s , "On t h e S t o r a g e a n d H a n d l i n g o f B i n a r y D a t a U s i n g FORTRAN w i t h A p p l i c a t i o n s t o I n t e g e r P r o g r a m m i n g " , O p e r a t i o n s R e s e a r c h , V o l . 27 ( 1 9 7 9 ) , p p . 5 3 4 - 5 4 7 . 17. P. L . Hammer a n d S. R u d e n e a n u , B o o l e a n M e t h o d s I n O p e r a t i o n s  R e s e a r c h a n d R e l a t e d A r e a s , S p r i n g e r V e r l a g , 1 9 6 7. 18. M. H e l d , P. W o l f e a n d H. C r o w d e r , " V a l i d a t i o n o f S u b g r a d i e n t O p t i m i z a t i o n " , M a t h e m a t i c a l P r o g r a m m i n g , V o l . 6 ( 1 9 7 4 ) , p p . 6 8 - 8 8 . 19. G.A. K o c k e n b e r g , B. A. M c c o i l a n d F . P. Wyman, "A H e u r i s t i c f o r G e n e r a l I n t e g e r P r o g r a m m i n g " , D e c i s i o n S c i e n c e s , V o l . 5 ( 1 9 7 4 ) , p p . 26-44. 20. R. L o u l o u a n d E . M i c h a e l i d e s , "New G r e e d y - l i k e H e u r i s t i c s f o r t h e M u l t i d i m e n s i o n a l 0-1 K n a p s a c k P r o b l e m " , O p e r a t i o n s  R e s e a r c h , V o l . 27 ( 1 9 7 9 ) , p p . 1 1 0 1 - 1 1 1 4 . 21. G. O r o n , " O p t i m i z i n g I r r i g a t i o n S y s t e m D e s i g n " , Ph.D. d i s s e r t a t i o n , A g . E n g . D e p t . , T e c h n i o n H a i f a , ( 1 9 7 5 ) . 22. D. E . P e t e r s o n a n d D. L a u g h h u n n , " C a p i t a l E x p e n d i t u r e P r o g r a m m i n g a n d Some A l t e r n a t i v e A p p r o a c h e s t o R i s k " , M a n a g e m e n t S c i e n c e , V o l . 17 ( 1 9 7 1 ) , p p . 3 2 0 - 3 3 6 . 23. A. P r i t s k e r , L . J . W a t t e r s a n d F. W o l f e , " M u l t i p r o j e c t S c h e d u l i n g W i t h L i m i t e d R e s o u r c e s : A Z e r o - O n e P r o g r a m m i n g A p p r o a c h " , M a n agement S c i e n c e , V o l . 16 ( 1 9 6 9 ) , p p . 9 3 - 1 0 8 . 24. M. R. Rao, " C l u s t e r A n a l y s i s a n d M a t h e m a t i c a l P r o g r a m m i n g " , J o u r n a l o f t h e A m e r i c a n S t a t i s t i c a l A s s o c i a t i o n , V o l . 66 ( 1 9 7 1 ) , p p . 6 2 2 - 6 2 6 . 25. S. S e n j i u a n d Y. T o y o d a , "An A p p r o a c h t o L i n e a r P r o g r a m m i n g w i t h 0-1 V a r i a b l e s " , Management S c i e n c e , V o l . 15 ( 1 9 6 8 ) , p p . B 1 9 6 - 2 0 7 . 26. H. A. T a h a , "A B a l a s i a n - B a s e d A l g o r i t h m f o r Z e r o - O n e p o l y n o m i a l p r o g r a m m i n g " , M anagement S c i e n c e , V o l . 18 ( 1 9 6 9 ) , p p . B 3 9 8 - 3 4 3 . 63 27. H. A. T a h a , " F u r t h e r I m p r o v e m e n t s i n t h e P o l y n o m i a l Z e r o - O n e A l g o r i t h m " , M anagement S c i e n c e , V o l . 19 ( 1 9 7 2 ) , p p . B 1 9 6 - 2 2 7 . 28. Y. T o y o d a , "A S i m p l i f i e d a l g o r i t h m f o r O b t a i n i n g A p p r o x i m a t e S o l u t i o n s t o 0-1 P r o g r a m m i n g P r o b l e m s " , M a n agement S c i e n c e , V o l . 21 ( 1 9 7 5 ) , p p . 1 4 1 7 - 1 4 2 7 . 29. L . J . W a t t e r s , " R e d u c t i o n o f I n t e g e r P o l y n o m i a l P r o b l e m s t o Z e r o - O n e L i n e a r P r o g r a m m i n g P r o b l e m s " , O p e r a t i o n s R e s e a r c h , V o l . 15 ( 1 9 6 7 ) , p p . 1 1 7 1 - 1 1 7 4 . 64 9. A p p e n d i x ; T h r e e B e n c h m a r k PP P r o b l e m s T h i s a p p e n d i x p r o v i d e s c o m p l e t e d e s c r i p t i o n s o f t h r e e p o s i t i v e 0-1 p o l y n o m i a l p r o g r a m m i n g p r o b l e m s . I s i s h o p e d t h a t t h e s e p r o b l e m s w i l l s e r v e a s b e n c h m a r k s f o r f u t u r e r e s e a r c h . A l l t h r e e p r o b l e m s w e r e s o l v e d by M e t h o d VA ( s e e s e c t i o n 7 . 3 ) . I n e a c h c a s e , o n l y a s i n g l e CR p r o b l e m h a d t o be s o l v e d t o o p t i m a l i t y . T he s p e c i f i c a t i o n s o f t h e s e CR p r o b l e m s a r e a l s o p r o v i d e d i n t h i s a p p e n d i x . I t w o u l d be v a l u a b l e t o d e t e r m i n e how much f a s t e r t h e s e CR p r o b l e m s c a n be s o l v e d by a s o p h i s t i c a t e d a l g o r i t h m f o r t h e SC p r o b l e m . P r o b l e m P a r a m e t e r s N M P E a l p h a I 40 40 8 5 0.5 I I 40 40 14 5 0.5 I I I 40 40 20 5 0.5 P e r f o r m a n c e CPU CR-CPU OPT 1 HEUR COVERS DENSITY I 2.5 2.2 1 3 39 0.15 I I 17.4 16.4 1 8 79 0.19 I I I 35.7 34.2 1 9 127 0.25 An e x a m p l e w i l l be u s e d t o d e m o n s t r a t e t h e n o t a t i o n e m p l o y e d f o r s p e c i f i n g t h e t h r e e b e n c h m a r k p r o b l e m s . C o n s i d e r t h e f o l l o w i n g PP a n d CR p r o b l e m s : Max 2 x i + 5 x 2 + 5x3 + 6x4 + IOX5 s t 3x^ + 2 x 2 x 3 < 4 2x 5 + 2x3X4 < 2 l l x l x 2 + 5 x 4 + 2 x 5 - 1 3 ' M i n 2yi + 5 y 2 + 5 y 3 +6y4 + 1 0 x 5 s t y i + y 2 + y 3 > 1 Y3 + Y 4 + Y5 ^ 1 y1 + Y2 + Y 4 ^ 1 Y l + Y2 + Y5 - !• T h e s e p r o b l e m s w i l l be s p e c i f i e d a s f o l l o w s O b j e c t i v e F u n c t i o n C o e f f i c i e n t s 2 5 5 6 10 P o l y n o m i a l C o n s t r a i n t s 3(1) 2(2 3) < 4 2(5) 2(3 4) < 2 11(1 2) 5(4) 2(5) < 13 SC P r o b l e m 11100 00111 11010 11001 66 PROBLEM I O b j e c t i v e F u n c t i o n C o e f f i c i e n t s 8 15 25 33 35 43 45 53 57 59 65 69 77 80 82 92 100 109 110 119 120 121 121 124 124 124 130 139 145 155 161 168 174 184 192 200 210 220 226 227 Polynomial C o n s t r a i n t s 19(24) 19(36 33) 15(40) 10(24 9 1) 5(6) 2(25 17) < 35 15(38 3 2) 15(27 14 8 5) 15(2) 14(29 21 6) 10(21 17 16 4) 8(31 25 22) < 38 19(37 18) 17(15 14) 10(14) 9(8) 8(29 28 27 16) < 31 19(11) 17(33 31 24 22) 12(29) 8(20 8 1) 6(38 19 10 8 1) 3(27 25 14 7) < 32 1(11 9 5) < 0 19(21 11) 19(10 2) 16(22 16 9) 12(36 18 13 10) 11(39 35 17 7) 4(22 17) < 40 14(27 26 18 10 1) < 7 17(32 23 18 13 8) 17(30 28) 14(40 7) 13(36 34 20 8) 10(37 28 16 15 13) 6(17 14 9) < 38 16(35 19 6) 1(11 8 2) < 8 20(39 24 13) 17(36 10 6 1) 13(26 4 3) 11(31) 11(40 33 27) 3(33 14 8) 1(32 11) < 38 16(27 13 12 11 2) 15(22 17 14 2) 8(37 10) 8(39 26) 7(36 28 5) 5(36 29 27) < 29 16(28 27 5 2) 15(33 20 18 5 1) 14(36 20 15) < 22 15(37 26 10) 12(37 25 24 21 4) 10(34) 5(5) 4(34 31 30 26) < 23 14(29 28 27) 14(9 2) 14(19 13 10 1) 13(23) 9(29 8 4) 6(36 30 28 18 5) 6(38) < 38 17(23) 11(39 31 26 21) < 14 19(31 16 12) 17(24 15 10 3) 17(7) 16(35 33 21 20 17) 12(39 8) 10(19 17) 3(21 17 5) < 47 18(29 6) 15(18 12 11 7 1) 15(38 37 31 7 4) 13(34 32 3) 12(26 22 11) 10(33 15) 7(40 27 26 16) 2(29) < 46 67 17(27 26) 13(30 12 6) 11(9) 9(23 15 7) 1(40 28 22 17 16) < 25 18(23 11) 11(40 19 10 4 2) 9(32 3) 3(35 25 16 2) < 20 11(32 28 23) < 5 19(34 28 20) 18(35 29 27 19 9) 10(32 22 4) 9(11) 4(36 28 24 9 6) 2(23 11) < 31 15(36 9 8) < 7 6(9) < 3 16(24) 16(40 35 23) 14(36 25 16 9) 13(36 14) 12(35 21 14) 12(39 35 10) 6(21 20 1) < 44 18(39 27 16) < 9 8(32 23 15 12) < 4 20(16) 16(35 32 28 26) 9(31 15 7) 3(12) < 24 18 (31 25 19) 18(33 22 20 17 15) 17(40 26 16 3) 14(28 24 19 13) 13(33 2 1) 10(33 14 5) 8(27) 1(35) < 49 20(30) 12(34 33 30 19 14) 10(29 20 14 6) 3(33 17) 2(38 20 9) < 23 20(36 34 7) 1(12 11) < 10 20(40 35 16 14 11) 20(28 1) 11(34 1) 9(29 20) 5(39 38 35 27 1) 4(13 8 4) 4(39 36 20) 1(34 27 12 10 2) < 37 20(32 3) 19(36 25 23 18 10) 19(18 17 14 1) < 29 8(26 24 14 8) 3(34 30 29 2) < 5 17(36 33) < 8 17(18 17 3) 16(39 29 14 12) 9(7) < 21 14(36 33 32 24 18) 11(17) < 12 15(40 17) 11(25 23 1) < 13 19(34 25 24) 12(39 34 23 13 7) 10(19) 7(33 15 10) 6(9) 5(27) 1(38 27 16 13 6) < 30 20(38 17) 18(34 26) 15(29) 10(30 27 18 7 1) 8(26 23 9) 4(36 27 23 12 4) 3(15 13 7) < 39 17 (27 26 25 14) 12(23 20) 11(33 28 23 20 3) 10 (33 16 5) 10(38 36 16 1) < 30 68 Solutions Approx. solu t i o n : 0010100100 1110100111 1100111111 1101111111 Value of approximation: 3590 Optimal solution: 0010100100 1110100101 1101111111 1101111111 Value of optimal: 3604 F i n a l CR Problem Solved to Optimality 1000000000 0000000001 0000000110 0001000000 1000000100 1000000001 0000000010 0000000000 0100100000 0000100001 0000001100 0000010000 0100100000 1110000000 0000011100 0000010010 0001000000 1000000001 0100000100 0101000000 0000010000 0000000010 0000000000 0000100000 0000010000 0100000000 0000011001 0000000000 0000001000 0000000000 0000000000 0001010000 0000001000 0000100000 0000010100 1100100000 0000000001 0000000000 0000010000 0001001000 0000000100 0001100000 0000000000 0000000000 0000000100 0001000100 0000000000 0000001000 0000000000 0001100100 0000000000 0000001000 0000000000 0000010000 0000001000 0000000010 0000000000 0000010000 0000010100 0100100000 0000000100 0000010100 0000001110 0000001000 0000000100 0010110001 0000000101 0001011000 0000000000 0000001000 0000000000 0000000001 0000000000 0000001000 0000010010 0001000100 0000000000 0000000010 0001101000 0001000000 0000000000 0000000000 0000000000 0010010000 0000001000 0000110000 0000000000 1000000000 0000001100 0100010000 0000000000 1000000010 0000000001 0000100010 0001100000 0011000000 0001100000 0000000000 1001100000 0001001000 0000001000 0010110000 0000000101 0000001001 0111000001 0000010010 0000100000 0100100001 0000001000 0101000000 0000000010 0000000010 1000000001 0000000100 0000011000 0000000000 0000000000 1000000000 0101000000 1010000000 0001000001 0000000000 1001110000 0000001000 0000000000 0010000000 0001001000 1010000011 0011000000 0010000000 0001010000 1000000010 1000000001 0001000001 1001000000 0000100010 1100100000 0000000101 0000001100 0010000000 0100000001 1110000000 0000011000 0000001010 0000100000 0011000010 0001101100 1010000000 1100100000 0001000010 0000101000 1010100000 1100000000 0010000010 0001101100 1010000000 69 PROBLEM I I O b j e c t i v e F u n c t i o n C o e f f i c i e n t s 6 11 20 28 31 38 47 47 52 57 62 65 69 75 76 85 87 97 98 104 104 111 114 117 123 128 133 143 151 157 165 171 176 186 194 203 209 218 218 226 P o l y n o m i a l C o n s t r a i n t s 17(35 16) 16(39 22 17 13 7) 13(23 17) 9(25 19 2) < 27 15(25 23 19 9) 13(18 8 3) 8(27 1) 8(6) 5(9) 5(24 21 19 3) 4(30 29 2) 2(28 23 11 9) 2(5) 1(37 36 18 8) < 31 19(36 29 15 8 1) 19(22) 19(32 31 25 13 7) 17(28) 12(25 10) 11(38 17 16 6) 10(37 35 9 2) 5(40 36 21) 4(1) 4(22) 3(40 16 6 5) 3(25) 3(39 30) < 64 20(29) 20(36 21 15 4) 18(35 28 17) 13(32 9 6) 13(33) 11(38 22) 10(36 16 12 5 3) 9(34 15 3) 9(29) 6(35 28 26 21 10) 3(38) 3(30 25 22 15) 1(32 28 10 2) < 68 11(31 14 11 2) 5(37 31 19) 4(35 28 21 11 6) < 10 20(14 11) 20(20 13 11 5) 18(20 16 13) 17(36 10 7 3) 12(39 34 30 26 19) 11(40 17 15) 9(35 11) 9(40 39 4 3) 8(25) 2(4) 2(38 35 33 26 4) 1(40 11 3 2) < 64 17(28) 15(35 19) 13(16 5) 10(5) 8(38 26 24 23 5) 2(40 36 24) 2(27) < 33 17(24) 14(39 22 10 6) 12(17 2) 11(26 12) 11(31 21 15) 10(18 1) 8(15 10) 8(39 36 33 26 6) 3(32 19 17 11) 2(9 2) 2(8 5) 1(35 28 16 12) < 49 18(34 12) 11(38 32 29 9 4) 11(9) 9(21 20 4 3) 6(29 4) 3(39 27 21 17 8) 2(35 24 23 13 6) 2(32 23 18 14 3) 2(37 31 25 23 7) 2(34 10) 1(39) < 33 20(17 8) 15(29 12 10 7 6) 13(37 29 26 13) 11(23 17 1) 8(19) 7(25 21 19 10) 7(10) 2(40 33 7) < 41 20(26 7) 10(32) 4(40 34 32 15 5) < 17 16(16 8 5) 16(34 23 15 12) 14(33 22 17 12 1) 10(24) 10(29 15) 10(32 29 23 7) 10(37 25 15 12 6) 10(39 38 17 7) 9(28 17 6) 7(39) 4(27 26 8) < 58 17(40) 15(36 33 29 17) 12(38 32 31) 9(21 16 11) 3(40 28 26 17) 3(14 8 7) 2(35 11 7) < 30 11(38 28 19 11) 7(33 31 10 2) 3(33 24 22 19) < 10 70 18(37 20 13) 17(7) 17(22) 13(37 31 30) 12(5) 11(12 11 6) 9(37) 7(35 19 11) 5(38 28) 4(33 24) 3(37 35 22 14) 3(38 16 15) 3(32 30 23 17 12) < 61 20(19) 18(38 36 34 33 16) 12(25) 4(23 16) 1(39 31 9) < 27 14(30 21 12) 10(25 22 13 5 2) 6(39 36 12 7) 3(40 24 16 10 5) < 16 18(38 4) 16(40 27 25 17) 14(39 24 20 12 3) 12(39 13) < 30 20(39) 17(39 32 28 21) 17(40 37 34) 15(40 39 28 2) 12(33 14 12 7) 10(32 29) 9(26 15) 5(32 29 10 9) 1(24 22) < 53 19(9) 19(39 37 33) 12(8 6) 2(34 30 29 22) 1(34 28 5 2 1) < 26 19(25 13 7) 12(19 18 9) 12(1) 2(30 24 5) < 22 18(38 24) 16(40 15) 10(30 17 9) 6(36 32 19 6) 5(24 14) 5(26) 2(39 32 30 23 18) 1(23 22) < 31 18(36 31 20 19 18) 16(37 24 12) 11(39 33 19 3) 10(37) 9 (40 37 19 4 1) 7(38 35 24 20) 6(40) 4(38 30 24 8) 3(13 6) < 42 20(37 29 22 11) 20(13 7 6 4) 20(36 34 33 28 20) 18(20 16) 14(38 27 23 13 10) 11(36 2) 10(28 23 20) 9(32 11 1) 3(32 19 17 7 6) 1(36) < 63 20(9 6) 12(34) 11(28 10 9) 10(34 26 14 1) 7(9) 6(40 14) 4(40 29) 4(24) 1(24 6 3) 1(34 30 22 12) < 38 19(12) 19(36 28 15) 16(12 6 3) 12(35 34) 12(25 19 16 3) 9(40 39 36 8) 8(22 2) < 47 17(20 12) 16(40 24 16 3) 16(12) 16(19) 12(35 34 28 7) 10(40 27 26 11) 9(39) 8(34 6) 8(18 6 5) 2(37 36 30 24) 1(39 35 22 3) 1(39 22 14 8 4) < 58 9(33 21 19) 5(22 12) < 7 20(31 29 28 16 11) 18(24) 17(20) 14(35 25 24 14 10) 13(38 36 12) 12(38 36 29 15) 12(32) 10(28 25 13) 10(29 14 6) 6(30) 2(28) 1(13) 1(6) 1(19 14) < 68 20(30 17 8 4) 19(26 13 8 4) 19(30 13) 18(20) 18(22) 16(18 16) 12(29 27 18 14) 12(32 31 25 13) 10(38 12) 8(38 30 12 4) 7(28) 7(23) 3(40 39 31 19) < 84 19(11) 3(32 31 27 5 4) < 11 20(12) 15(33 13 7) 14(24) 8(39 36 5) 7(35 12) 7(33 30 27 3 1) 7(34 30 26 21 4) 4(35 25 9 6) 1(20) < 41 19(27) 18(22) 17(38 25) 16(25 14) 16(31 30 29) 12(29) 11(28 23 21 5) 11(24) 8(24 5 1) 7(13) 5(33 10) 5(18 13 7) 4(39 27 26 19 15) 1(36 13 10) < 75 18(37 4) 16(28 8 2) 15(29) 14(18 12 1) 10(40 25 24 20 5) 9(29 27) 7(5) 1(29 21 10 7) < 45 19(35 31 25 19 12) 14(35 34 31 21 9) 12(30) 12(36 8 2) 11(33 32 28 27 11) 8(36 34 23 2) 4(34 29) 4(36 32 25) < 42 19(33 6) 14(37 34 27 13) 11(30 11 10) 11(24 19) 10(37) 5(30 18 7 6 3) 5(36 24 12 8 6) 3(19) < 39 18(25 20 18 5) 13(29) 13(36 26 22 1) 11(38 28 22 21) 7(13) 2(32 28) < 32 19(29 26 11) 19(36 16 14 7) 19(32 1) 17(38 37 35 28 27) 13(27 15 3 2) 4(6) 3(38 18 17 14 8) < 47 20(9) 18(20 19) 17(21 13 4 1) 12(30 21) 6(38 11) 2(38 23 12 2(39 23 16 14 4) < 38 18(31 19 8) 16(35 34 27 16 3) 13(31 26) 13(39 32 19) 11(37 18 16) 9(2) 8(31 30 9) 7(38 36 1) 2(35 22 14 2) 1(23 16 15 7) 1(36 32 30) < 49 Solutions Approx. solution: 001010010 1010110110 1111011100 11111111111 Value of approximation: 3495 Optimal solution: 001010010 1010110110 1111011100 11111111111 Value of optimal: 3495 F i n a l CR Problem Solved to Optimality 1010100000 0100000000 0000001001 0010110010 0100000100 0100000000 0100000000 0001110011 0001000000 0000001000 0000101000 0000000101 0001100000 0100000000 1000010001 0001110010 0011000101 0101001101 1010001000 0101000010 0000010100 0000000000 0000000000 0010001010 0010010100 0100000000 0000000000 0001110011 0010110000 0100000101 0100000000 0001100010 0000010001 0100100000 1100010000 1010010010 0000001000 0000000000 0000010000 0000000000 0000001000 0100000000 1000000001 0000010010 0000101000 0000000000 0100000001 1000001000 0000001100 0001000000 0000000000 1100000101 0000000010 0000000000 0000000000 0010001010 0000000000 TTIIT00000 0000000000 TTOTTOOTOO 0000000000 TOTOTOOTOO OOTOOOOOTO OTOOOOOOOT 0000000000 0000000000 OOOOOOTOOO 0000000000 OOIOTOOOIO TITOOTOOOO OOOOTOOTOO OTOOOOOOOT OOIOTOOOIO TTOOOOOOOO IIOOOOOOTO OTTOOOOOOT OTOOOOOOTO OTTOTOOOOT OOTOOOOOOT TTOTOTOOOO OOOOTOOOOO 0010000000 0000000000 OTOOOIOOOO 0001000000 OTOTOOOOOO 0000000000 0010000000 TOOTIOOOOI 0000000000 0000000000 TOOOIOOOIO 0000000000 TOTOTOOTTO OIOTOOOOIT OOOOTOOOOO OOIIOOOOOT IOIOOOOOTO TTOIOOTOIO OTIOOOOOOO 0000000000 TOTOOOOTTO OTOOOOOOII OOOOTOOOOO TOOOTTOOOO OOIOOOTOOO OOTOTOTTOO 0000000000 OOOOOOOOOT TTOIOOTOIO OOOTOOOOOO OTIOOOOOOO OOOOTOOOOO OIOOTOOOTO 0000010000 OOIIOOOOOO TTOIOOTOIO OIOOIOOOOO OOTOOOOOOO OTOIOIOOTO IOOOTOOIOO OTOOOOOOOO OOITOIOOTT TOTOOOOTTO OOTOOOOOOO OOI IOIOTTT IOTOOOOOTI OOTOTOOOOO TTOIOOTOIO OOTOOOOOOT OOOOTIIOOO OOTOOOOOOO OOTOOOOOOO OOOIOITOTO OIOOIOOOOO OOOOOOTOOO TOTOOOOOOO OOOOOOTOOO OOOOOTOOOO OOOOOOTOOO TTOITOOTOI 0000000000 OTOOOIOOOO 0000000010 0000000100 OOOOOOOOOT 0000000000 OOOOOTOOOO OOTOTOTTOO OOOOOTOOOO OOOOOTOOOO OOOOOOOTOO 0001000001 IOOOOOOOIO OOTOOOOOOO OOOTOTOOIO OIOOOOTOIO OOOIOOOIOI IIOOOOOOTO IOOOTOOIOO OIOOOOIOOO OOOIOOOOOI TOOOOOOOOO TOOOIOOTIO IOTOTOTIOO OOIOOOTOOO TOTOIOI IOO OOIOOOTOOO TOTOTOOTOO OOIOOOTOOO TOOOOOOOOO OIOOOOTTOO 0000000000 OIIOIOOOOO 0000000000 OIOOIOOOOO TOOOOIOITO 0000000000 OOOOIIOOIO OOOOOIIIOO TOOOOTIOIO OOOOTOOOOO 0000000000 OOOOOOOOTO OOOOOTOOOO 0000000000 OOOOOOTOOO 0000000000 OOOOOTOOTO OOOOTOOTOO TOTOOOOTOO OOOOOTOOOO 0000000000 OOOOOTTOOO OOOOTOOOOO OOOOOTOOOO TTTOOOOOOO OOOOOOTOOT TOTOTOOTOO OOIOOOTOOO TOOOOOOTOO OOIOOOTOOO OIIOIOOOOO OOTOOOOOOO TOOOOOOTOO 0000000000 0000000000 OOOOOOOOTO TOTOTOOTOO 0000000000 OTOOOOOOOO OOTOOOOOTO OTOOOOOOOO 0000000000 OIOOIOOOOO 0000000000 0000000000 0000000000 0000000000 OOTOOOTOTO OOOOOOOTOO OOOOOOOOOT OTOOOOOOOO 0000000000 OOOOOTOOOO 0000000000 OOOOOOTOOO 0000000000 OOOTOOOOOO 0000000000 OOOTOOTOTO OOOOOTOOOO OOOOOOTOOO OOOOOTOOOO OOOTOOOOOO 0000000000 0000000000 0000000000 OOOOOTOOTO 0000000000 OOOOOOTOOO 0000000000 OOOOOOOOTO OOOOOTOOOO OOOOOTOOOO 0000000000 IOOOOOOOIO 0000000000 TTTOOOOOOO OOOOOOOTOO IIOOOOOOTO OOOOOOOTOO OTOOOOOOOO 0000000000 OTOOOOOOOO 0000000000 OOOOTOOOOO 0000000000 OOOTTOOOOO 0000000000 TOOOOOOTOO OOOOOTOOOO OOOOOOTTOO 0000000000 OOTTOOTOTO OTTOOOOTOO OOTTOIOOOO OTOOOOOOOO OOOTOOOOTO TTTOOOOOOO OOOTOIOOOO OTOOOOOOOO 73 0000010000 0010000000 0000001000 0011001000 0000000000 0000000000 0100101011 1000000100 0011000000 0100000001 1000000010 0001000010 0011000001 0100000001 1000000010 0001000000 0001000000 0110000001 0100100001 1100000100 0000100000 0000010000 0011011000 0000010101 1000100001 0010000000 0001001011 1010000000 0110000000 0000010100 0000011001 1101111000 1110000000 0000010100 0000011000 1001111100 0000000001 0010000000 0101101000 0010000100 1000100000 0011000000 0001101000 0000000100 PROBLEM I I I O b j e c t i v e F u n c t i o n C o e f f i c i e n t s 9 16 17 26 36 43 47 55 64 69 76 80 89 97 97 101 102 112 112 118 123 127 137 140 144 145 149 150 152 152 154 157 165 171 179 182 182 186 196 196 Polynomial c o n s t r a i n t s 15(36) 14(34 30 27 25 20) 14(15) 13(35 18 11 8 7) 7(36 31 21) 4(36 10 7 4) 1(29 15) < 34 20(4 3) 20(34 31 22 20 8) 18(20 18 8) 18(37 36 12 10 6) 18(39 35 31 24) 17(37 34) 17(32 31 19 3 1) 16(27 1) 16(40 14 13) 13(15) 11(39 23 18) 7(34 22 21 9 3) 6(37 16) 4(3) 3(40 10 9) 2(31 22 21 20) < 103 13(19 15) 5(36 13 8) < 9 19(31 30 22 20) 18(35 27 9 4) 6(36 30 9 1) 5(40 36 10 2) 1(40 27 19 17 12) < 24 19(32 12) < 9 18(8) 15(28 27 22 21) 15(38 36 35 3) 14(40 32) 13(35) 10(9 8) 7(25 5) 6(11) 6(25 3) 4(20) 3(38 30 16) < 55 18(11) 17(22 12) 12(39 35 31) 12(34 32 30 8) 11(33 22 19) 10(10 4) 10(15) 10(32 25) 9(29 27) 7(28 15 2) 7(37 23) 6(29 19 12) 5(28) 5(24) 5(32 11 2) 4(12) 4(4) 3(20 8 1) 3(31 13 4 3) 1(37 2) < 79 20(39 33) 20(38 29 11 3) 19(19 7 6 5 2) 17(39) 16(37) 16 (33 17) 16 (36 19 11 10 8) 15(27 16) 15 (30 18) 14 (39 29) 14(33 16 8) 12(24 18 16) 12(27 1) 12(40 29 8) 10(28) 9(18) 9(40 31 23 7) 6(26 10) 5(39 24 2) < 128 74 20(38 22 12 5) 20(13) 15(29 18 11 3 2) 14(20) 11(21 20 18 12) 10(32 24 20 17 6) 6(40 26) 6(26 20 19 15 1) 5(38 36 30 5) 3(27) < 55 20(26 23) 20(12 9 2) 19(39) 17(31 16 12 3) 15(34 26 20 17 4) 11(21 17) 11(24 15) 8(40) 6(27 13) 5(38 34) 4(40 24 21 9 6) 2(36 21 18) 2(32 22 21 10 7) 1(11) < 70 19(24 20) 16(33 29 26 23 20) 15(28 25 17 6 2) 15(38 15) 14(39 33) 11(24) 6(9 1) < 48 19(28 18 17 3 1) 18(9) 18(31 29 28 11) 18(4) 15(36 18 14 5) 14(23 13) 13(25 18 4) 12(25) 12(19 14) 12(31) 9(37 22 17 14) 9(21 20) 7(39 4) 7(38 28 21 15 12) 6(11 8) 6(33 16 12 7 6) 2(39 36 17) < 98 20(36 33) 18(40 17 15) 17(37 34 24 2) 15(39 5) 14(31 9) 11(34 33) 10(39 33 26 15 7) 10(40 4) 8(20) 7(40 24 11) 6(36 31 26 13 8) 4(39 23 2) 1(12) 1(40 7) 1(33 20 13) < 71 13(40 30 15 1) < 6 19(2) 18(21 17 16) 17(23 15 5) 16(32 13) 15(36 9 8 1) 14(32 21 1) 14(34 33 7 3) 13(12 9 2) 12(38 31 27 17 2) 11(30 26 24 15 13) 11(17 14 8) 10(40 16) 9(18 15 13) 6(40 35 23 14 5) 5(39 37 12) 4(17 14 11 1) 3(32 13) 2(36) < 99 11(29 19 11) 10(36 11) 9(28 24 12) < 15 20(36 26 24 6) 19(22) 17(30 26 11 6) 13(31 25 21) 12(35) 12(11) 12(37 33) 11(40 18 16) 10(31 21 10) 9(34 13 9) 7(38 25 8 3) 6(23) 6(39 34 33 28) 3(30 26 14 11 2) 2(39 35 23 12) 2(13) < 80 12(20 6 3) 8(39 26 25 11) 1(29) < 10 15(30 25 22 13 10) 5(23 11 9) < 10 19(19 6) 18(26 24 19 17) 16(27 23 13 6 2) < 26 18(39 37) 15(36 20 16 7) 14(36 27 19 14) 12(38 17 1) 11(40 5) 11(33) 10(35 32 24 5) 10(13 12 11) 9(35 16 14 4) 4(35 32 26 19 9) 3(23 22 20) < 58 17(32 14 12 11) 10(36 18) 8(36 11) 6(35 15 4) 4(19 12 4 3) < 22 17(32 11) 16(23) 11(40 22) 10(39 36 11) 8(33 19 11 10 6) 6(33 21 20 11 4) < 34 16(40 33 26 1) 13(32 22 15) 4(37 8 7) < 16 20(38 32 12 11 3) 15(39 37 3 1) 12(36 13) 9(23 17) 9(28 4) 75 7(16 7 6 3) 7(3) 5(38 29 19 17 6) 3(40 23) < 43 20(32 19 17 16 14) 19(36 26 24) 18(17 14 13) 16(11 9 5 2) 16(6) 15(40 14 7 3) 15(19) 11(17 11 4 2) 10(28) 9(35 18 1) 9(36 32 18) 6(11) 5(38 36 24 15) 1(38 32 25 7) < 85 19(14 9) 17(8 5 3) 17(29 20) 15(37 35 21 14) 14(27 23 4) 14(34 22 14) 10(39 30 28 19) 10(39 36 35 20) 10(30 26) 9(33) 8(18 15) 5(36 34 2 1) 5(4) 3(22 17 6 5) 2(28 27 21 14) 2(12 4) 1(36) 1(31 21 12 5) < 81 20(20 8) 18(8) 17(37 22 5 3) 17(2) 16(31 23 5) 14(31 30 23) 13(8 2) 12(38 20) 12(35 30 19 13 11) 8(39 36 27 1) 8(25 9 6 5) 4(38 37 25) 3(10) < 81 16(32 28 23 1) 14(38 34 23 11) 12(13) 12(15 8) 10(35 6 5) 7(31 27 12) 3(23 18 15 10 6) 3(30 20 10 1) 2(39 35 2) 1(38 3) < 40 18(15) 17(29 4) 16(31 17 3) 15(4) 11(33 31 14 8) 10(38 28) 9(35 30 26 25 2) 6(39 34 21 2) 6(28) 5(38 5 3 1) 4(26 11) 2(39 37) < 59 18(37 10) 15(25 3) 15(40 33 21 9) 11(31 29 22 16 13) 10(38 35 28 19 3) 4(31 16 15) 2(30 10 9 7) < 37 19(33 24 14) 17(15 14 2) 12(39 33 24 14 4) 12(32-31 19 14 2) 12(9 7 2) 12(1) 11(35 31 14) 6(23 11) 5(22 18 14) 4(24 17) 4(38 37 29 26) 4(29 1) 2(32 24 23 11 10) < 60 19(40 32 28 22 8) 18(34 20 1) 17(37 34 24) 17(33 18 11 4) 14(35 32 31 29 7) 13(30) 10(39 32 26 16 6) 10(32) 7(22 17 16 6 1) 7(29 24 17) 7(18 11 3 1) 4(35 26 24 16 1) 1(36) < 72 20(35 5) 19(37 5) 18(35 19 10 8 3) 18(39 35 26 11 10) 14(37 29 13) 13(37 35 29 2) 11(37 25 7 4) 8(14) 8(40) 7(25 3 2) 7(30) 5(33 32 31 27 14) 5(40 31 16) 2(12) 1(20 19 15) < 78 20(35 13 11) 17(26 3) 17(38 22) 12(17) 12(37 33) 12(27 25 16 15 6) 12(36 33 2) 12(10) 10(37 35 27 25) 6(16 10) 5(36) 4(29 9) 3(37 36 29 18 2) 1(8) 1(18) < 72 20(27 18 16 9) 19(36 15) 17(35 26 15 11) 15(16 5 3) 14(38) 13(36 35 34 31) 13(16) 13(33 14) 10(39 36 13) 10(37 35 16 1) 8(18 3) 4(35 24 18 5) 3(33 31 11) 2(24 12 4) 2(28 19 17) 1(27 20 13 3) < 82 20(16 2) 19(23 1) 19(33 26 20 13 12) 19(40 29 23 10) 18(30) 18(20 17 14) 18(38 37 12 3) 17(39 38 12) 17(33 31 26) 14(9) 13(29 22 19 4) 12(35) 12(22 21 17) 10(39 31 22 12) 10(40 10 4 3 2) 9(32 31 1) 8(35 9) 6(37 20) 6(37 27 20 9) 5(19) < 135 76 20(35 20 11 4) 6(26 22) < 13 12(39 32 16 6) 9(31 16) < 10 19(22 15 9 8) 19(37 32 26 17 5) 18(11) 17(38 37 16) 16(38) 14(27 1) 13(31 30) 13(34 19) 12(37 32 16 6 2) 10(19) 9(6) 7(40 30 16 9) 5(39 16) 5(9 2) 4(38 17) 3(36 31 13) 2(19 5 3) 1(37 29 19 16) 1(39 37 20 15) < 94 Solutions Approx. solution: 1000001010 0011000110 1111111111 1111111111 Value of approximation: 3717 Optimal solu t i o n : 0000001010 0011011010 1111111111 1111111111 Value of optimal: 3799 F i n a l CR Problem Solved to Optimality 1100001010 0001000010 0001000000 1110100000 1100000010 0001000010 1100010101 0011111010 0010000010 0000000010 1000100100 0010100101 0010000000 0000000000 1100001100 0100110101 1010000010 0011000110 1111001000 1101101011 0001000010 0011000110 0010100000 1000000000 1001000000 0001000100 0101000010 1010100010 0001000010 0001000000 1110011001 0011101000 0001000010 0001000010 1110001101 0011101010 0001000010 0001000010 1110011101 0001101010 0000100000 0011000000 0000001011 1110101001 0000100000 0001000010 0001001000 0110111011 0000010000 0000000000 1111110000 1010111000 0000010010 0010000000 1101110000 1011111000 1000001100 0000000000 0000010000 0010001001 0000000110 0000000000 1100001100 0000100000 0000000110 0000000000 1100001100 0100000001 0000000100 0000000000 1100001100 0100100001 0000001100 0000000000 0101000111 1101101001 1000001100 0000000100 0010001111 1010001011 0000000001 0010000000 0100100001 0000000000 0000000011 0010000000 1110100000 1011101000 0000000000 1000000010 0000000010 0000010000 0000000000 1000000000 0010000000 0100010010 0000000000 1000000000 0110000000 0100000001 1000000000 1010000000 0010000100 0101000100 0000000010 1010000000 1110100000 1011101000 1000000000 1001000100 0111010010 1010101100 0000000000 0100000000 0000000000 0100000000 0000000010 0110000000 1110100100 1011101010 0000000000 0000100010 0000000000 0000000000 1000000000 0000100000 0000000001 0000000001 0000000000 0000100000 1000000000 1000010000 OOTTTOOTOO OTOOOOOOIO OOTTTOOTOO OTOOOOOOIO OOTIOOIOTI TOOOOOOOOO OIOIOOOIOO IIOTOOOOOO OTOTOOOIOO TIOIOOIOOO IOO I IO I IO I OOOOOOTOOO OI I IOOOIOI OIIOOOOOOO IOTOOIOOIO TOOOOOOOOO 0000000000 OOOOIOIOOO OTOOOOOOIO 0000000000 OTOOOOOOOT OTTOOTOOOO TOOTTOTTOO OOOOOOTOOO TOOTIOTTOO OOOOOOTOOO OOOTTTOIOO TOOOTOIOTO OOOIOOOOOT IOOOOTOOOO OTOOOOOTOO OOOOOOTOOO OTOOOTOTOT OOOOOOTOOO OOTOTTOOOO OOOTTOOOOO OTOOOOOOOT OOOOTOOTOO TTTOOOTOOO OOOOTOOTOO OTOOOOOOOO OOOOTOTTOO TTOOOOOOOO OOOOTOTTOO OOOOTTOOOO TOOOTOTTTO OOOIOOOOOT TOOOOOOTTO OOTTOOOOOT TOOOOTOTOO OOOOOOOOOT TOOOOTOTOO OOOIOOOOOT OOOOOOOTIO OOTOTOOOOO OOOTOOOOOO OOTOOOOTOO OOOTOOOOOO OOOOTTOOOO 0000000000 OOTOTTOOOO 0000000000 OOOOTTOOOO 0000000000 TTOOTOOOOO OOOOOOOTIO OOOOOOOOOT OTOOOOOOOO 0000100000 OOTOOOTOOO OOTOOOOOOO OIIOOOOOOO OTOTOITOOO ITTOTOOOTT OIOITTTOOO TTOOTOOOTT OTOTTTTTOO OTOOOOOOTT OOOTTTTOTT TTOOOOTOOO OOOOTOTOOT TOOTOTOOOT OOOOTOOOOT TOOOOOOOTO OTOOOOOTOO OTOOTOTTOO OTOOOOOTOO OOOOOOTOOO OTTTTTOTTO OOOTTOOOOO TTTOTOTOOO OOOTTOOTOT OIOIOOOIOO TTTTOOOOOO TOOTOTTTOT OOOOOTOTTT OTTOTTTTOT OOOTOOOOOO OOTTTTTTOT OOOTOOOOOO TTTTOOTOOT TOOTOOOOOO OIOIOOOIOO TIOIOOIOOO TTTOTOTOOO OOOTTOTTOT TOOOOOOTTO OOOOTOOOTO OOOTOOOOOO ITOOOOOOTO OOTTOOOOOO TOOOOOOOTO OTOOTOOOOO OTOOTOOOTO OOTTTOOOOO OOTOOOOOOO OOTTTOOOOO 0000000000 0000000000 OTOOOOTOTO OOOOOOTOOO OOTOOOTOOO OOOOTOOOOO OIIOOOOOOO OIOTOOOOOO OOOOTOOOOO OOOOTOOOOO OOOOTOOOOO OOTOOOOOOT OTTOOOTOOO OOOTOTOOOO OOOOOOTOTO OOOTOTOOOT OOOOOOOOTO OOOOOOOOOT OOOOTOOOOO OOOOTTOOOO TTOTOOOIOO OOOTOTTOOO OTOTOOTOTO OOOTOTTOOO OOOOOOTOTO OOTOTTOOOT OTOOOOOOOO OOOOTOOOTO OTOOOOOTTO OOOOOOOOTO OTOOOOOOIO OOOOOTOOTT OTOOOOOOIO OOOOOTOOTO OTOOOOOOIO OOOOOOOOOT OOOOTOOOOO 0000000000 OOIOOIOITO 0000000000 OOIOOTOOTO 0000000000 OTTOTTOOTO 0000000000 TOTOOTOIIO OOTOTTOOOO OTOOOTOTOO OOTOTOTOOO OTOOOTOTOO OOIOOIOOOT OOTTOOOOOO 0000000000 OTTOOOOTOO OOIOOIOOOT OOOOOOTOOO OOOOOOOOOT 0000000000 OOOTOTOOOO OOOOOOTTOO OOOOOOOOIT 0000000000 OOOOOTOOOO OOOOOOTOOO TTOOOOTOOO OTOOOOOOOO TOOOOOIOOO OTOOOOOOOO TOOOOOTOOO OTOOOOOOOO TOOOOOOOOO OOOIOOOOOT TOOOOOOOOO 0000000000 TOOOOOOOOO OTOOOOOOOT TOOOOOOOOO 0000000000 TOOOOOOOOO OTOOOOOOOT OTOTOOTOOO OTOOOOOOOT OOIIOOOTOO 0000000000 OOTTOOOOOO OOOOOOOOOT OOIOTOOIOO OTOOOOOOOO OOTOIOIIOO OTOOOOOOOO OOTOTOTOOO OTOOOOOOOT OTOOTOOOOO OTOOOOOOOT OOTOTOOOOO OOOOOOOOOT OOTOOTOTOO 0000000000 OOOOOTOOOO OOOOOOOOOT 0100000001 0100001010 0100001000 0000001001 0000100000 0010100100 0010000001 0000100000 0000100000 0010000001 0010000001 0010000001 0010100100 0000100100 0100000101 0100000100 0100100100 0000000110 0000100110 0100100000 0000000000 1000100000 1000001000 1000001100 0100000001 0100000000 0000000001 0000000001 0000001000 0100001010 0100001010 0001000010 0001100010 0100100000 0101101000 0000100000 0000100010 0000101000 0001001000 0001101000 0000001000 0001001110 0000001100 0000001100 0110000001 0000000000 0000000010 0110000001 0110000101 0000001000 0000011000 0010010000 0000000000 0000000001 0000000001 0000000001 0000000001 0000000001 0000000000 0011000000 0011011110 0000011010 0001011011 0000000001 0000010000 0000010100 0000010100 0000010100 0000010100 0001000110 0001001010 0000000001 0001000110 0001010000 0001000000 0000011010 0000011010 0001010011 0001010011 0001010001 0100101000 0101000000 0011000111 0010010111 0100001000 0000100000 0000100100 0100010000 1100000000 0100010000 0100010000 0100100010 1100101100 1100101100 0000000000 0000100000 0010000000 0000000000 0000100000 0000000010 0001010100 0000011000 0000001000 0101000110 0100101000 0001001111 1110100000 0001011111 0011001111 0101010010 0001010010 0100001001 0000100000 0000000011 0000100010 0000010001 0000010001 0110001000 0110001000 0001000000 0010111100 1110100000 1010001011 1010001011 0000000100 0000110100 0000101100 0000000101 0000000100 0010011100 0010001100 1000001000 0000100000 0000100000 0000000100 0000001100 1000000000 0100100001 0100100001 0000101001 0100010000 0101001110 0000011110 1101101001 0010111100 0010001010 1010101001 0010001010 1010001011 1110101100 1110101100 1000100000 1000010000 1000101001 0000101001 1101001110 1101001101 0000011011 0000111010 0100111011 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051834/manifest

Comment

Related Items