D:\User\sbornik_38_pdf\17.DVI


Mathematical Problems of Computer Science 38, 38{41, 2012.

Advanced Combinator ial Optimization

L . A s la n ya n

Institute for Informatics and Automation Problems
of the National Academy of Sciences

Laboratory of Discrete modelling, analysis and recognition

hasmik@ipia.sci.am

Th e r e s e a r c h a im s a t c o n s t r u c t in g e ± c ie n t a lg o r it h m s a n d a p p r o xim a t io n s fo r h a r d , o p e n
a n d n o ve l c o m b in a t o r ia l o p t im iz a t io n p r o b le m s wit h e m p h a s is o n t h e p r a c t ic a l a p p lic a b ilit y
o f r e s u lt s . B o o le a n m in im iz a t io n ( h a r d ) , Is o p e r im e t r y a n d t o m o g r a p h y ( o p e n ) , d e c e n t r a liz e d
a n d s t r e a m a n a lys is ( n o ve l) a lg o r it h m s a r e c o n s id e r e d . Co m b in a t o r ia l r e d u c t io n is a n o t h e r
t a r g e t , b e in g r e la t e d wit h t wo s e t s o f p r o b le m in s t a n c e s , t o g e t h e r wit h a s t r u c t u r e o f r e -
d u c t io n . Th is t r ip le t is s t u d ie d t o r e c o ve r t h e t r a c t a b ilit y a n d a p p r o xim a t io n b o u n d a r ie s .
Th e c o n c e p t o f o p t im a lit y t h a t is n o t ye t c le a r fo r c o m p le x s ys t e m s wit h c o n ° ic t in g g o a ls
is a d d r e s s e d in t e r m s o f h e u r is t ic s , s t a b ilit y a n d e qu ilib r ia . Th e s e is s u e s p la y a ke y-r o le t o
t h e e m e r g e n c e o f a m a jo r r e s e a r c h p o le in t h e a r e a o f c o m b in a t o r ia l o p t im iz a t io n , h ig h ly
r e s p o n s ive t o t h e in d u s t r y n e e d s a n d t ig h t ly lin ke d t o d i®e r e n t r e s e a r c h a r e a s wit h d e s ig n ,
a n a lys is a n d m a n a g e m e n t o f c o m p le x s ys t e m s . A p p lie d a r e a s a d d r e s s e d in c lu d e P o p u la t io n
Ge n o m ic s a n d W ir e le s s S e n s o r N e t wo r ks .

Resear ch pr oblem
Fo r s e ve r a l ye a r s s c ie n t ī c r e s e a r c h we n t t h r o u g h a n im p o r t a n t t r a n s fo r m a t io n p r o c e s s a n d
r e s e a r c h p e r s p e c t ive s s t a r t e d s u p p o r t in g in t e r e s t s t h a t we r e n o t o n ly a n d e xc lu s ive ly t h e
p u r e ly c o g n it ive a s p e c t s , b u t a ls o - t h e n e e d s o f s o c ie t y. Co m p le xit y Th e o r y a n d Co m b in a -
t o r ia l Op t im iz a t io n m a n ife s t t h e m s e lve s a s a n e w kin d o f r e la t io n b e t we e n t h e o r e t ic a l a n d
a p p lie d s c ie n c e , a n d t h e s e d is c ip lin e s m e e t n e e d s o f s o c ie t y t h r o u g h a n in t e r d is c ip lin a r y a p -
p r o a c h . S u c h a n a p p r o a c h h a s t o m o d e l h a r d a n d c o m p le x s ys t e m s ( complex system is
c o m p o s e d o f in t e r c o n n e c t e d p a r t s / a g e n t s t h a t a s a wh o le e xh ib it p r o p e r t ie s n o t o b vio u s fr o m
t h e p r o p e r t ie s o f t h e in d ivid u a l p a r t s ) , a n d t o fa c e h a r d m a t h e m a t ic a l p r o b le m s a r is in g fr o m
t h is m o d e lin g . Th e o r g a n iz a t io n o f c o m p le x s ys t e m s t o g e t h e r wit h t h e ir p o s s ib le a p p lic a t io n s
in a va r ie t y o f in d u s t r ia l s e c t o r s r e p r e s e n t s a g r e a t c h a lle n g e t o t h e s e d is c ip lin e s .
Ma t h e m a t ic a l m o d e ls fo r a lm o s t a n y r e a l-wo r ld p r o b le m a r is in g in va r io u s a r e a s s u c h a s
g e n o m ic s , in fo r m a t io n t e c h n o lo g y ( s o ft wa r e a n d h a r d wa r e in c lu d in g ) , c o m m u n ic a t io n n e t -
wo r ks , a n d ( r a d io a c t ive a n d o t h e r ) wa s t e m a n a g e m e n t , g ive r is e t o c o m b in a t o r ia l p r o b le m s
t h a t c a n b e c h a r a c t e r iz e d a s har d ones, in t h e s e n s e t h a t a n y o p t im a l s o lu t io n p r o c e s s fo r
la r g e s c a le in s t a n c e s o f t h e m t a ke s u n a c c e p t a b ly lo n g c o m p u t a t io n t im e . Mo s t c o m b in a t o r ia l
o p t im iz a t io n p r o b le m s o f g r e a t p r a c t ic a l r e le va n c e a r e , in d e e d , c o m p u t a t io n a lly in t r a c t a b le
in t h e a b o ve s e n s e . In fo r m a l t e r m s , t h e y a r e c la s s i¯ e d a s N P -h a r d o p t im iz a t io n p r o b le m s
[1 ]. D e s p it e m a n y ye a r s o f r e s e a r c h it h a s n o t b e e n fo r m a lly p r o ve d t h a t N P -h a r d p r o b le m s

3 8



L. Aslanyan 3 9

c a n n o t b e s o lve d b y m e a n s o f a lg o r it h m s r u n n in g in p o lyn o m ia l t im e 1. N e ve r t h e le s s , t h e r e
is ve r y s t r o n g t h e o r e t ic a l a n d p r a c t ic a l e vid e n c e t h a t s u c h a lg o r it h m s m a y n o t e xis t a n d we
h a ve t o m a ke u s e o f a p p r o xim a t io n a lg o r it h m s .
P / N P t h e o r y u s e s t h e p r o b le m r e d u c t io n t e c h n iqu e . A n in d ivid u a l p r o b le m { S A T, TS P ,
3 D M, e t c . in c lu d e t h e wh o le s e t o f in d ivid u a l in s t a n c e s [2 ]. R e d u c t io n is r e qu ir e d t o b e p o ly-
n o m ia l a n d it s d e g r e e is n o t a c r it ic a l fa c t o r . Th is fr a m e wo r k, va lid in t h e o r y is t o b e fu r t h e r
in ve s t ig a t e d fr o m a p r a c t ic a l p o in t o f vie w. W e in t e n d t o c o n s t r u c t t h e m in im a l c o m p le xit y
r e d u c t io n s , s u b -p r o b le m s o f in d ivid u a l p r o b le m s will b e c o n s id e r e d , a n d fo r -a p p r o xim a t io n
r e d u c t io n s will b e c o m p o s e d . Th is a p p r o a c h will t r a n s fe r t h e s o lva b le in s t a n c e s fr o m o n e
p r o b le m t o t h e o t h e r , a n d t r a n s it ive ly will c o m p o s e t h e la r g e r t r a c t a b le s u b s e t s o f p r o b le m
in s t a n c e s . A p p r o xim a t io n r e d u c t io n s will fo r m t h e kn o wle d g e o n a p p r o xim a b ilit y b o u n d -
a r ie s . Th e r e fo r e , t h e p r a c t ic a l c o u n t e r p a r t o f p r o b le m r e d u c t io n s t h e o r y will b e s e t u p a n d
a p p lie d t o c o m p le x s ys t e m s t a s ks .
In d e e d , a n e w c o n c e p t u a l fr a m e wo r k is n e e d e d fo r d e a lin g wit h o p t im a lit y is s u e s in c o m p le x
s ys t e m s . Fir s t o f a ll, o n e h a s t o t a ke in t o a c c o u n t t h e p r e s e n c e o f c o n ° ic t in g o r jo in t in -
t e r e s t s o f t h e a g e n t s in vo lve d in t h e s e s ys t e m s , a s we ll a s t h e a b s e n c e o f a n y a u t h o r it y a b le
t o c e n t r a liz e in fo r m a t io n a n d t o im p o s e optimal ( in fa c t , a n y kin d o f ) d e c is io n s c o n c e r n in g
t h e a g e n t s ' b e h a vio r . S u c h a s p e c t s d o in d u c e m a jo r d i®e r e n c e s b e t we e n c la s s ic o p t im iz a t io n
a n d t h e a g e n t n e t wo r k c o n t e xt .

B e s id e s t h e t h e o r y we a d d r e s s e d t wo b a s ic a p p lic a t io n s wit h c o m p le x s ys t e m s in s id e {
o n e in P o p u la t io n Ge n o m ic s ( P G) a n d t h e s e c o n d in W ir e le s s S e n s o r N e t wo r ks ( W S N ) .
a ) W ir e le s s S e n s o r N e t wo r ks ( W S N ) s e r ve s m a n y p o t e n t ia l a p p lic a t io n a r e a s : fr o m e n vir o n -
m e n t m o n it o r in g t o h e a lt h , a n d fr o m d e fe n s e m o d e ls t o s o c ia l n e t wo r ks . W S N a r e m a d e o f
la r g e n u m b e r o f a lm o s t id e n t ic a l s m a ll s e n s o r n o d e s t h a t a r e in t e g r a t e d o n b a s e o f d is t r ib u t e d
p r o t o c o ls a n d a lg o r it h m s o f d a t a c o m m u n ic a t io n a n d d a t a a n a lys is .
W S N h a s n o p r e d e ¯ n e d in fr a s t r u c t u r e , i.e ., n o d e s d o n o t h a ve a n y a p r io r i kn o wle d g e a b o u t
t h e r e s t o f t h e n e t wo r k. H e n c e a W S N m u s t b e a b le t o s e lf-o r g a n iz e . N o d e s c o o p e r a t e fo r
t h is s e lf-o r g a n iz a t io n a n d it is ve r y b a s ic t o t h is p r o p o s a l t h a t t h is c o o p e r a t io n is in it s n a t u r e
lo c a l { n e ig h b o r h o o d b a s e d . Cu r r e n t W S N m o d e ls d e a l wit h t h is lo c a l a n a lys is in a h id d e n
m o d e , wh ic h d o e s n 't h e lp t o a c h ie ve t h e b e s t p e r fo r m a n c e .
b ) P o p u la t io n g e n e t ic s is t h e s t u d y o f a lle le fr e qu e n c y d is t r ib u t io n a n d c h a n g e u n d e r t h e
in ° u e n c e o f t h e fo u r m a in e vo lu t io n a r y p r o c e s s e s : n a t u r a l s e le c t io n , g e n e t ic d r ift , m u t a -
t io n a n d g e n e ° o w. H e r e t h e p u r e p a r s im o n y p r o b le m is t o in fe r a m a xim a lly p a r s im o n io u s
c o lle c t io n o f g e n e t ic d o n a t io n s t h a t c a n c o m b in e t o fo r m a n e w p o p u la t io n 's d ive r s it y o ve r
p o r t io n s o f t h e c h r o m o s o m e [8 ]. W e p a r t ia lly o r d e r a c o lle c t io n o f g e n o t yp e s s o t h a t we c a n
r e p r e s e n t t h e p r o b le m o f in fe r r in g t h e le a s t n u m b e r o f h a p lo t yp e s in t e r m s o f s u b s t r u c t u r e s
kn o wn a s g -la t t ic e s . Th is r e p r e s e n t a t io n a llo ws p r o vin g t h a t if t h e g e n o t yp e s p a r t it io n in t o
c h a in s wit h c e r t a in s t r u c t u r e , a n d t h e n t h e N P -H a r d p r o b le m c a n b e s o lve d e ± c ie n t ly. E ve n
wit h o u t t h e s p e c i¯ e d s t r u c t u r e , t h e d e c o m p o s it io n s h o ws h o w t o s e p a r a t e t h e u n d e r lyin g
in t e g e r p r o g r a m m in g m o d e l in t o s m a lle r m o d e ls .

I mplementation
A n a lys is o f p r o b le m r e d u c t io n s / h a r d n e s s a n d a p p r o xim a t io n / .
A 'g a d g e t ' is a ¯ n it e c o m b in a t o r ia l o p t im is a t io n p r o b le m , wh ic h t r a n s la t e s c o n s t r a in t s o f o n e
o p t im iz a t io n p r o b le m in t o a s e t o f c o n s t r a in t s o f a s e c o n d o p t im iz a t io n p r o b le m . P r o b le m

1here is the link to the latest attempt in solving this problem
http://michaelnielsen.org/polymath1/index.php?title =Deolalikar P vs NP paper)



4 0 Advanced Combinatorial Optimization

h a r d n e s s m a y m e a n t h e e xis t e n c e o f a h a r d CP I ( c la s s e s o f p r o b le m in s t a n c e s ) o n ly. Is it
la r g e o r n o t ? Ma y we d e t e r m in e t h is a r e a ? A d d it io n a lly, in d i®e r e n t p r o b le m s t h e r e a r e
kn o wn e ®e c t ive ly s o lva b le CP I. In IP s u c h kn o wn a r e a is t h e in s t a n c e s b a s e d o n u n im o d u la r
m a t r ic e s . Th e r e fo r it is n o ve l t h e s t r u c t u r e , wh ic h t r a n s la t e s c o n s t r a in t s o f o n e o p t im iz a t io n
p r o b le m in t o a s e t o f c o n s t r a in t s o f a s e c o n d o p t im iz a t io n p r o b le m [7 ]. P o lyn o m ia l r e d u c -
t io n s u s e d in N P a r e a a r e b a s e d o n p le n t y o f g a d g e t s . P r a c t ic a lly, c o m p u t a t io n a lly s im p le r
g a d g e t s p r o vid e u s wit h m o r e e ± c ie n t r e d u c t io n o f p r o b le m s o r s p e c i¯ c CP I. Two n o t io n s
a r e s p e c ī c a lly im p o r t a n t . Th e n o t io n o f p r o m is in g t o ¯ n d o u t d i®e r e n t p o lyn o m ia l CP I in
h a r d o p t im is a t io n t a s ks , - u s e t h e m in p r o b le m r e d u c t io n s , a n d e n la r g e in t h is wa y t h e a r e a s
o f e ®e c t ive ly s o lva b le in s t a n c e s . Th is s t u d y r e qu ir e d c o n s t r u c t in g n e w g a d g e t s a n d s p e c ia l
g a d g e t s will b e c o n s id e r e d fo r r e d u c t io n o f a p p r o xim a t e s o lu t io n s .
Op t im a lit y c r it e r ia in c o m p le x s ys t e m s .
Th e s p e c i¯ c g o a l o f t h is t a s k is in d e e p a n a lys is o f lo c a l a lg o r it h m s a s t h e b a s is o f a ll W S N
t a s ks - t o u n d e r s t a n d h o w we ll t h e y s e r ve t h e a lg o r it h m ic n e e d s o f W S N : s u c h a s c o ve r a g e ,
c o n n e c t ivit y, s e c u r it y, e t c . S t a r t p o in t is t h e b a s ic r e s e a r c h [6 ], wh ic h e n a b le d d is c o ve r in g
p r o b le m s ir r e s o lva b le b y m e a n s o f lo c a l a lg o r it h m s . Th e n t h e N P c o m p le t e t a s ks b y lo c a l
a lg o r it h m s will b e in ve s t ig a t e d . Th is s e r ie s will s h o w t h e wa y n o t t o g o in W S N d e s ig n .
A lt h o u g h h a r d n e s s o f N P c o m p le t e p r o b le m s is we ll r e c o g n iz e d , a t t h is p o in t le s s a t t e n t io n
is p a id t o N P h a r d n e s s a n d ir r e s o lva b le p r o b le m s b e c a u s e o f lim it a t io n s t o t h e c la s s e s o f
lo c a l a lg o r it h m s . Th is is d u e t o m ix o f u s e a n d c o m p le xit y e s t im a t e s o f o r d in a r y o p t im iz a -
t io n t a s ks wit h o n e s o b lig e d t o u s e t h e lo c a l a lg o r it h m s . In fa c t , t h e t a s k will d e ve lo p lo c a l
c r it e r ia in t e r m s o f c u r r e n t s t a t e a n d b e h a vio r , a n d will m o d e l t h e g lo b a l o p t im iz a t io n c r i-
t e r ia in t h e s e t e r m s . W S N s im u la t io n will u s e t h e fr e e , o p e n s o u r c e s o ft wa r e p r o je c t n s -3
h t t p :/ / www.n s n a m .o r g , kn o wn a s a d is c r e t e -e ve n t n e t wo r k s im u la t o r fo r In t e r n e t s ys t e m s .
A p p lie d le ve l.
P o p u la t io n g e n o m ic s e xa m p le p r o b le m will b e c o n s id e r e d in t h is t a s k. In s h o r t , t h e m a t h e -
m a t ic a l c o n t e n t is t h e fo llo win g . L e t a s e t o f in t e r va ls in n -d im e n s io n a l u n it c u b e is g ive n .
It is n e c e s s a r y t o c o n s t r u c t a s e t o f ve r t ic e s s o t h a t in e a c h in t e r va l t h e r e e xis t a t le a s t
o n e p a ir o f c o m p le m e n t a r y ( a ve r t e x t o g e t h e r wit h it s n e g a t io n in s id e t h e in t e r va l) ve r t ic e s
a m o n g t h e s e le c t e d o n e s , a n d t h e s e le c t io n s iz e is t o b e m in im a l. Th is fo r m u la t io n is ve r y
c lo s e t o t h e p r u n in g p r o b le m , wh ic h is kn o wn a s N P -h a r d . D u e t o h u g e s iz e s o f g e n o m ic
in fo r m a t io n it is n e c e s s a r y t o ¯ n d a p p r o xim a t e a lg o r it h m ic c o n s t r u c t io n s . Th e t e c h n iqu e
t o b e u s e d in c lu d e s c h a in s p lit , B o o le a n m in im is a t io n , a n d r e d u c t io n t o IP in s t a n c e s . Th is
t a s k c o n s id e r s a p a r t ic u la r o p t im is a t io n p r o b le m in a p p r o xim a t io n , c o n s id e r s r e d u c t io n s t o
¯ n d o u t m o r e a p p r o xim a t e s o lu t io n s , a n d ¯ n d s t h e s a m e lo c a l c o n c e p t s t h a t m a y r e p la c e
t h e c o n c e p t o f a g lo b a l o p t im u m . Te s t in g a n d va lid a t io n o f t h e a lg o r it h m a n d s o ft wa r e
will b e p e r fo r m e d u s in g p u b lic it y a va ila b le d a t a fr o m Ge n e E xp r e s s io n Om n ib u s r e p o s it o r y
( h t t p :/ / www.n c b i.n lm .n ih .g o v/ g e o / ) .

Futur e wor k
Ou r g o a l wa s t o a d va n c e in t h e r e s e a r c h fo r n e w o p t im a lit y p a r a d ig m s , g e t t in g in s ig h t fr o m
t h e c o m p le x s ys t e m s s c ie n c e s a n d ( t o s o m e e xt e n d ) fr o m s o c io e c o n o m ic s c ie n c e s : e c o n o m ic s ,
b io lo g y o f p o p u la t io n s , c o n t r o l t h e o r y a n d o t h e r s . W e s t r o n g ly b e lie ve t h a t in t h e n e a r fu -
t u r e , t h e s e t h e m a t ic will b e r e s h a p in g t h e r e s e a r c h la n d s c a p e in c o m b in a t o r ia l o p t im iz a t io n .
Th e y a r e e qu a lly e xp e c t e d t o in ° u e n c e a ll t h e a c t ive r e s e a r c h fo r n e w c o m p u t in g m a c h in e
p a r a d ig m s b a s e d u p o n p r o p e r t ie s o f n a t u r a l s ys t e m s t h a t a r e n o t e xp lo it e d b y c o n ve n t io n a l
c o m p u t e r s . W e c a n , t h u s , b e s e e n a s a n in it ia t ive t o d r a s t ic a lly r e n o va t e t h e r e s e a r c h a g e n d a



L. Aslanyan 4 1

in c o m b in a t o r ia l o p t im iz a t io n , b y a d d r e s s in g o p e n a n d n o ve l p r o b le m s a r is in g fr o m c o m p le x
s ys t e m s . In p a r t ic u la r , o u r fu r t h e r r e s e a r c h will e n r ic h t h e t r a c t a b ilit y a n d a p p r o xim a t io n
a r e a s o f c o m b in a t o r ia l o p t im iz a t io n b y t h e b a s ic s e t o f p a r a d ig m a t ic p r o b le m s S A T, IP , TS P ,
3 D M, e t c . Th e c o n c e p t o f o p t im iz a t io n fo r c o m p le x s ys t e m s will b e m o d e le d in t e r m s o f
lo c a l c r it e r ia s t a b ilit y a n d e qu ilib r ia . Th e s e t o f p r a c t ic a l c o m p le x s ys t e m s will b e d e s ig n e d
a n d s o lve d a lg o r it h m ic a lly.

R eferences

1 . Ga r e y, M. R . a n d Jo h n s o n , D . S . ( 1 9 7 9 ) . Co m p u t e r s a n d In t r a c t ib ilit y: A Gu id e t o t h e
Th e o r y o f N P -Co m p le t e n e s s . W . H . Fr e e m a n a n d Co m p a n y, N e w Y o r k.
2 . Cr e s c e n z i P ., K a n n V ., A p p r o xim a t io n o n t h e we b : A c o m p e n d iu m o f N P o p t im iz a -
t io n p r o b le m s , R a n d o m iz a t io n a n d A p p r o xim a t io n Te c h n iqu e s in Co m p u t e r S c ie n c e , L e c t u r e
N o t e s in Co m p u t e r S c ie n c e , 1 9 9 7 , V o lu m e 1 2 6 9 / 1 9 9 7 , 1 1 1 -1 1 8 .
3 . P a p a d im it r io u C.H ., S t e ig lit z K ., Co m b in a t o r ia l o p t im is a t io n : a lg o r it h m s a n d c o m p le x-
it y, D o ve r P u b lic a t io n s In c ., 1 9 9 8 . N e w Y o r k, 4 9 8 p .
4 . K o r t e B ., Je n s V ., Co m b in a t o r ia l o p t im iz a t io n : Th e o r y a n d a lg o r it h m s ( 2 1 A lg o r it h m s
a n d Co m b in a t o r ic s ) , 4 t h E d ., S p r in g e r , 2 0 0 8 , 6 2 7 p .
5 . Tr e vis a n L ., S o r kin G.B ., S u d a n M. a n d W illia m s o n D .P ., Ga d g e t s , A p p r o xim a t io n , a n d
L in e a r P r o g r a m m in g , S IA M Jo u r n a l o n Co m p u t in g , V o lu m e 2 9 , Is s u e 6 , 2 0 7 4 -2 0 9 7 ( 2 0 0 0 ) .
6 . Zh u r a vle v Y u ., E le c t e d R e s e a r c h W o r ks , Ma g is t e r , Mo s c o w, 1 9 9 8 , 4 2 0 p .
7 . Gr e e n b e r g H ., H a r t W .E ., L a n c ia G., Op p o r t u n it ie s fo r c o m b in a t o r ia l o p t im iz a t io n in
c o m p u t a t io n a l b io lo g y, IN FOR MS Jo u r n a l o n Co m p u t in g 1 6 , 2 2 1 -2 3 1 ( 2 0 0 4 ) .
8 . A r a ke lya n A ., B o ya jia n A ., A s la n ya n L ., S a h a kya n H ., Iva n o va K ., Mit o v I., Gr o w-
in g s u p p o r t s e t s ys t e m s in a n a lys is o f h ig h -t h r o u g h p u t g e n e e xp r e s s io n d a t a , Cla s s ī c a t io n ,
fo r e c a s t in g , D a t a Min in g c o n fe r e n c e , V a r n a , 2 2 -2 4 Ju n e , 2 0 1 0 .