I nd o ne s ia n J o urna l o f   E lect rica E ng ineering   a nd   Co m p u t er   Science   Vo l.   10 ,   No .   3 J un e   201 8 ,   p p .   1319 ~ 1 3 3 0   I SS N:  2 5 0 2 - 4752 ,   DOI 1 0 . 1 1 5 9 1 /i j ee cs.v 1 0 . i3 . p p 1 3 1 9 - 1 3 3 0          1319       J o ur na l ho m ep a g e h ttp : //ia e s co r e. co m/jo u r n a ls /in d ex . p h p / ijeec s   Neur a l Ne tw o rk   A nd Lo ca S ea rch   T S o lv e Bina ry  CSP       Adil B o uh o uch * 1 ,   H a m i d B ennis 2 ,   C ha k ir  L o q m a n 3 ,   Abd er ra h i m   E Q a di 4   1 ,2 T e a m   T IM ,   Hig h   S c h o o o f   T e c h n o lo g y   -   M o u lay   Is m a il   Un iv e rs it y ,   M e k n e s,  M o ro c c o   3 d e p a rtm e n o f   in f o r m a ti c s,  S c ien c e s F a c u lt y ,   Dh a M e h ra z ,   S i d M o h a m m e d   Be n   A b d e ll a h   Un iv e rsity ,   F e z ,   M o ro c c o   4 LA S T IM I,   Hig h   S c h o o o f   T e c h n o l o g y   -   M o h a m m e d   V   Un iv e rsity   o f   Ra b a M o ro c c o   * Co rre sp o n d in g   a u t h o r ,   e - m a il b o u h o u c h . a d il @g m a il . c o m         Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   J an   15 ,   2 0 1 8   R ev i s ed   Mar   1 2 ,   2 0 1 8   A cc ep ted   Mar   2 8 ,   2 0 1 8     Co n ti n u o u Ho p f ield   n e u ra N e tw o rk   (CH N)  is  o n e   o f   th e   e ffe c ti v e   a p p ro a c h e to   s o lv e   Co n stra in   S a ti sf a c ti o n   P ro b lem (CS P s).  Ho w e v e r,   th e   m a in   p ro b lem   w it h   CHN   is  th a t   i c a n   re a c h   sta b il isa ti o n   w it h   o u t p u ts  i n   re a v a lu e s,  w h ich   m e a n a n   in c o n sist e n so lu ti o n   o a n   in c o m p lete   a ss i g n m e n o CS P   v a riab les .   In   th is  p a p e r,   w e   p ro p o se   a   n e h y b rid   a p p r o a c h   c o m b in in g   CHN   a n d   m in - c o n f li c h e u risti c   to   m it ig a te  th e se   p ro b lem s.  T h e   o b tain e d   re su lt   sh o w     a n     im p ro v e m e n   in     term   o f     so lu ti o n     q u a li ty ,     e it h e   o u r   a p p ro a c h   a c h iev e f e a sib le  so lu io n   w it h   a   h ig h   ra t e   o f   c o n v e rg e n c e ,   f u rth e rm o re ,   th is  a p p ro a c h   c a n   a lso   e n h a n c e   th e p e rf o r m a n c e   m o re   th a n   c o n v e n ti o n a CHN   in   so m e   c a s e s,  p a rti c u larly ,   w h e n   th e   n e tw o rk   c ra sh es .     K ey w o r d s :   C o n s tr ai n t   S a ti sf a c ti o n   P r o b l e m   C o n t i n u o u s   H opf ield   N e u r al   Ne t w o r k   M e eti n g   S ch e du l in g   Qu ad r atic  P r o b lem   Co p y rig h ©   2 0 1 8   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   B o u h o u c h   Ad i l ,   T e a m   T I M ,   Hi g h   S c h o o l   o f   T e ch n o l og y ,     M ou l a y   I s m ail   U n i v e rs i ty , M e k n e s ,   M o r o c co .   E m ail: b o u h o u c h . ad il@ g m ail. co m       1.   I NT RO D UCT I O N   I n   g en er al,   C o n s tr ain Satis f ac tio n   P r o b lem   ( C SP )   co n s is t s   o f   f in ite  s et  o f   v ar iab les;   ea c h   o n h as   f i n ite  d o m ai n   o f   v a lu e s   an d   s et  o f   co n s tr ai n ts   w h ich   i m p o s es a   v ar iab le  d o m a in   r es tr ict io n .   A n d   t h g o al  is   f i n d in g   co m p lete  as s i g n m e n o f   v ar iab les  w h ich   s ati s f ie s   all  co n s tr ai n t s .   Ma n y   p r o b le m s   f r o m   t h r ea l   w o r ld   ca n   b r ef o r m u lated   as  C SP .   Fo r   ex am p le,   q u ali tativ e   an d   s y m b o lic  r ea s o n i n g ,   d iag n o s is ,   s c h ed u li n g ,   s p atial  an d   te m p o r al  p lan n i n g ,   h ar d w ar d esi g n   a n d   v er i f icat io n ,   r ea l - ti m s y s te m s   an d   r o b o p lan n i n g ,   etc.   I t   is   k n o w n   t h at   s o l v in g   a   C SP   w it h   f i n ite  d o m a in   is   an   NP - co m p lete   p r o b lem ,   w h ich   r eq u ir es  a   co m b i n atio n   o f   h e u r is t ics  [ 1 ]   an d   co m b in a to r y   s ea r ch   m et h o d s ,   i n   o r d er   to   b s o lv ed   i n   r ea s o n ab le   ti m e   [ 2 ] .   Ma in l y ,   ap p r o ac h es  to   s o lv C SP s   ca n   b class i f ied   i n to   t w o   ca te g o r ies:   ex ac ap p r o ac h es  an d   h e u r is tic   o n es.  As  f o r   ex ac ap p r o ac h es,  m o s t   o f   t h e m   h a v t h b ac k tr ac k i n g   al g o r ith m   ( B T )   as  m ai n   al g o r ith m   f o r   s o lv i n g   co n s tr ain s a tis f ac tio n   p r o b lem s .   T h B T   ap p lies   Dep t h - First  s ea r ch   in   o r d er   to   in s ta n tiate  v ar iab le s   a n d   a   b ac k tr ac k   m ec h a n is m   w h en   d ea d - en d s   ap p ea r .   Ma n y   w o r k s   h av b ee n   d ev o ted   to   i m p r o v its   f o r w ar d   an d   b ac k w ar d   p h a s es  b y   i n tr o d u cin g   lo o k - ah ea d   a n d   lo o k - b a ck   s c h e m es.  So m o t h er   s ea r ch   alg o r it h m s   f o r   class ical   C SP s   li k Fo r w ar d   C h ec k i n g ,   P ar tial  L o o k - a h ea d ,   Fu ll   L o o k - a h ea d ,   an d   R ea ll y   Fu ll   L o o k - a h ea d   ar e   in tr o d u ce d   an d   th e ir   p er f o r m an ce s   ar s t u d ied   w id el y   i n   th liter at u r [ 3 6 ] .   Fo r   s m a ll  p r o b lem s   e x ac m et h o d   ar b etter   b u f o r   b ig   i n s ta n ce s   o f   NP - Har d   p r o b lem   lik C SP   n ee d   h i g h   ti m co s t,  d u to   all  m et h o d s   h av at  last   e x p er ien tial  co m p lex i t y .   I n   t h is   ca s e   n o n   ex ac ap p r o ac h es  g iv an   ac c ep tab le  s o lu tio n   in   r ea s o n ab le  ti m es.  A s   f ar   as  h eu r is tic  ap p r o ac h es  ar co n ce r n ed ,   w f i n d   th at,   v er y   d if f er en ap p r o ac h   h as  in v e s ti g ated   d is cr ete  Ho p f ield   Neu r al  Net w o r k   ( HNN)   to   s o lv C SP   [ 7 ] .   I n   th is   n e u r al  n et w o r k   ap p r o ac h ,   th e   C SP   co n s tr ain ts   ar ass o ciate d   w it h   th n et w o r k   to p o lo g y ,   b iases ,   an d   co n n ec tio n   s tr en g t h s .   R ec e n tl y ,   m a n y   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,  Vo l.  1 0 ,   No .   3 ,   J u n 2 0 1 8   : 1 3 1 9     1 3 3 0   1320   ap p r o ac h es  in tr o d u ce d   C o n ti n u o u s   Ho p f ield   n et w o r k   to   s o lv C SP s   [ 8 1 0 ]   o r   p r o b l e m s   w h ic h   ca n   b e   f o r m u lated   as  C SP   [ 1 1 ] .   A s   we  ca n   s ee   in   [ 1 0 ] ,   th au t h o r s   p r o p o s m ap p in g   C SP   to   q u ad r atic  p r o b lem   an d   elab o r ate  an   ap p r o p r iate  p a r a m eter s   s etti n g   o f   n et w o r k   en er g y ,   t h e n   t h e y   s o lv it  b y   f i n d in g   t h n et w o r k   eq u ilib r iu m   p o in [ 8 ] .   B ased   o n   th s a m co n v er g en ce   p r o ce d u r e,   C alab u ig   [ 1 2 ]   ad d s   d y n a m icall y   li n ea r   co n s tr ain ts   to   co n f i n t h n et w o r k   to   th f ea s ib le  s u b s p ac o f   s o l u tio n s t h is   i m p r o v e m e n e n s u r es  t h f i n al   s o lu tio n   v alid it y .   P r ac ticall y ,   t h er ar t w o   i m p o r tan t   p r o b lem s   w it h   ap p r o ac h es   b ased   o n   co n v e n tio n al   n eu r al   n et w o r k   ar c h itect u r es .   T h f ir s p r o b le m   i s   t h at  H NN  p ar tia ll y   m it ig ate s   t h p r o b le m   o f   g ettin g   s tu c k   in   lo ca o p tim u m .   T h s ec o n d   o n i s   d u to   Ho p f ield   n e t w o r k   d y n a m ic  w h ic h   co n ti n u o u s l y   e x p lo r es  th s ea r c h   s p ac e   an d   w i ll  n o al w a y s   s tab ilize  at  b o r d e r   0   o r   1 .   I f   th s a m ca s ap p ea r s ,   w g et  lo w   s o l u tio n   q u a lit y   o r   an   in co m p lete  as s i g n m e n o f   v ar iab les  p r o b lem .   I n   o r d er   to   ta ck le  th e s p r o b lem s ,   w p r o p o s to   im p r o v t h e   C HN  s o lu tio n   b y   th e   Mi n - C o n f lict  h eu r i s tic( MN C )   [ 1 3 ] .   T h MN C   w o r k s   as   f o llo w s it   s elec ts   th e   v a lu e   f r o m   ea ch   v ar iab le  d o m a in   f o r   w h ic h   th to tal  er r o r   in   th n ex co n f i g u r atio n   w ill  b m i n i m al.   P r ec is el y ,   MN C   is   r ep air - b ased   s to ch asti ap p r o ac h ,   w h ic h   s tar ts   w it h   co m p lete  b u in co n s i s t en ass i g n m en a n d   th en   r ep air s   v ar iab les  i m p li ca ted   in   co n s tr ain v i o latio n s   r ep etitiv el y   u n til  co n s i s ten ass ig n m en is   ac h iev ed ,   t h is   ap p r o ac h   ca n   s o lv lar g e - s ca le  p r o b lem s   in   p r ac tical  ti m e.     T h is   p ap er   is   o r g an ized   as  f o ll o w s I n   s ec tio n   1 ,   w p r esen m o d eliza tio n   o f   t h b in ar y   C SP   as  0 - q u ad r atic  p r o g r a m ,   a n d   g e n er alize s   e n er g y   f u n c tio n   a s s o cia ted   w ith   t h C SP s .   Sec tio n   2   i s   d ev o ted   to   g i v i n g   i m p le m en ta tio n   d etails o f   th p r o p o s ed   ap p r o ac h .   I n   th last   s ec tio n ,   w s h o w   th co m p lex it y   a n al y s is   a n d   th e   r esu lt s   o f   t h n u m er ica l e x p er i m en ts   a g ain s t o th er   ap p r o ac h es   lik t h Ge n etic  A l g o r ith m   [ 1 4 1 6 ] .         2.   B I NARY   CSPS  SO L V E B CH N   2 . 1 .   Q ua dra t ic  m o del o f   Co ns t ra int  s a t is f a ct io n pro ble m   A   lar g n u m b er   o f   r ea p r o b le m s   s u c h   as  ar ti f ic ial  in telli g en ce ,   s ch ed u l in g ,   as s ig n m e n p r o b lem   ca n   b f o r m u lated   as  C o n s tr ain t   Sati s f ac tio n   P r o b lem .   So lv in g   C SP   r eq u ir es  to   f in d in g   a n   ass i g n m e n o f   all   v ar iab les p r o b lem   u n d er   co n s t r ain ts   r estrict io n .   T h C SP   ca n   b f o r m u lated   as t h r ee   s ets :   1)   Set o f   v ar iab les X= { X i   ; 1     i ≤     }.   2)   Set  o f   N   v ar iab les   d o m ai n s D     ={     D i   1        d i   w h er ea ch   Di  co n tai n s   s et  o f   d i   r an g e   v alu e s   f o r   X i .   3)   Set o f   co n s tr ai n t s : C   ={     C i   ; 1        M}.   E ac h   co n s tr ain C i   as s o ciate s   a n   o r d er ed   v ar iab les s u b s e w h i ch   is   ca lled   th s co p o f   C i .   T h ar it y   o f   co n s tr ain is   t h n u m b er   o f   in v o l v ed   v ar iab les.  W ca n   ea s il y   r ef o r m u late  C SP   as  Qu ad r atic  P r o b lem   ( QP ) ,   b y   in tr o d u cin g   b in ar y   v ar iab le  x ik   f o r   ea ch   C SP   v ar iab le  x i ,   w h er k   v ar ies  o v er   t h r an g o f   x i ,   g iv e n   as f o llo w s :     o t h e r w i s e k v a l u e t a k e s i v a r i a b l e if x ik 0, 1, =             ( 1 )   Fo r   ea ch   b in ar y   co n s tr ai n C ij   ,   b etw ee n   t h v ar iab le s   y i   an d   y j   ,   w a s s o ciate   s tat f u n ctio n   d ef in ed   as:   i r j s js ir j d s i d r ij Q x x x S 1 = 1 = = ) (                   ( 2 )     W h er } ], [ 1 . . , { = i ik d k N i x x   v ec to r   o f   QP   s o lu tio n   an d   th q u ad r atic  ter m s   i r j s Q   d ef i n ed   as:     o t h e r w is e C s r if Q ij i r j s 0 ) , ( 1 =                 ( 3 )     Fro m   all   t h eq u a tio n s   d ef in ed   in   ( 2 ) ,   w h ic h   co r r esp o n d   to   p r o b lem   co n s tr ai n t s ,   w e   d ed u ce   t h e   o b j ec tiv f u n c tio n   o f   it s   eq u i v alen t Q P     i r j s js ir j d s N j i d r N i Q x x x f 1 = 1 = 1 = 1 = = ) (                 ( 4 )   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       N eu r a l Net w o r a n d   Lo ca S e a r ch   to   S o lve  B in a r C S P   ( A d i   B o u h o u ch )   1321   Fu r t h er m o r e,   s o m s tr ict  li n ea r   co n s tr ain t s   eq u at io n s   m u s t b s atis f ied   b y   t h s o l u tio n 1 = =1 ir i d r x   f o r   N i 1 . . =   w h ic h   ca n   b w r itte n   als o   as  b Ax =   ( A   is   M N   m atr i x   an d   b   is   M   d i m en s io n   v ec t o r   f u ll y   i n it ialized   to   1 ) .   So ,   th m o d el  is   g iv e n   as  f o llo w s     n T x b Ax w i t h Qx x x f M i n QP { 0 , 1} = = ) ( ) (               ( 5 )     S y s te m a ticall y ,   to   s o l v t h la s Q u ad r atic  Op ti m izatio n   P r o b le m   w it h   Ho p f ield   m o d el,   we  n ee d   to   b u ild   an   e n er g y   f u n ctio n   s u ch   as  th f ea s ib le  s o lu t io n s   o f   t h p r o b lem   co r r esp o n d in g   to   th m i n i m al  o f   C HN   en er g y   f u n ctio n .       2 . 2 .   H o pfie ld neura l net w o r k   Ho p f ield   n e u r al  n et w o r k   w as  in tr o d u ce d   b y   Ho p f ield   an d   T an k   [ 1 7 ]   [ 1 8 ]   [ 1 9 ] .   A t h b e g in n i n g ,   i t   w a s   d ev elo p ed   to   s o l v co m b i n ato r ial  o p ti m izatio n   p r o b lem s .   T h en   i w a s   e x ten d ed   e x te n s iv el y   to   o t h er   ar ea s   o f   ap p licatio n ,   s u c h   as  r ec o g n itio n   an d   o p ti m izatio n .   Ho p f ield   n eu r al  n et w o r k   is   cla s s i f ied   as  a n   e f f icien t   lo ca s ea r ch ,   w h ic h   g i v es   a n   ac ce p tab le  s o l u tio n   to   h ar d   o p ti m izatio n   p r o b lem s   at   r ea s o n ab le  ti m e.   B asicall y ,   t h i s   n eu r al   n e t w o r k   m o d el  i s   f u ll y   co n n ec ted   n eu r al  n et w o r k   a n d   it s   d y n a m i s tat s   ar g o v er n ed   b y   t h f o llo w in g   d if f er en tial e q u atio n :       b i x T x dt dy =                 ( 6 )     W h er e:     x   : v e cto r   o f   n e u r o n s   in p u     y   : v ec to r   o f   o u tp u     T     : m atr ix   o f   w e ig h t b et w ee n   ea ch   n e u r o n es p air s         i b   : T h b iases   w h ich   d escr ib e   th n e u r o n s   s el f - i n ter n al  n o i s es.     Ho p f ield   p r o v ed   th at  if   T   is   s y m m etr ic  th e n   t h n et w o r k   en er g ies i s   L y ap u n o v   f u n ctio n :               ( 7 )     Fo r   ea ch   n eu r o n s ,   t h in p u is   g o v er n ed   b y   a n   ac ti v atio n   f u n ctio n   x   g ( y )   w h ic h   v ar ies  b et w ee n   0   an d   1 .   T h is   f u n ctio n   i s   g i v e n   b y :         )) ( t a n h (1 2 1 = ) ( 0 u y y g                 ( 8 )     W d ef in t h en er g y   f u n ct i o n   o f   C H as  to   b ass o cia te  w i th   t h co s o f   th p r o b le m   to   b m i n i m ized ; th i s   is   d o w n   b y   ta k en       to o   lar g e:     x i x T x x E t b t ) ( = ) (                 ( 9 )     I n   t h is   p ap er ,   w u s e   th e   ab ili t y   o f   C HN  to   r eso l v Q u ad r at ic  m o d el  o p ti m izatio n .   So   w e   ch o o s a   C HN  en er g y   f u n c tio n   s i m ilar   to   [ 1 0 ] ,   w h ic h   is   ad ap ted   to   s o lv e   th q u ad r atic  f o r m u latio n   o f   th b i n ar y   C SP s       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,  Vo l.  1 0 ,   No .   3 ,   J u n 2 0 1 8   : 1 3 1 9     1 3 3 0   1322   i j r s js j d s i d r N j N i Q x i r x x E 1 = 1 = 1 = 1 = 2 = ) ( ) (1 1 = 1 = 1 = 1 = ir ir i d r N i ir i d r N i x x x       ( 1 0 )     T h f ir s ter m   p en alize s   t w o   v alu es  ta k en   b y   t w o   lin k ed   v ar iab les  w h ic h   ca u s ed   v io latio n ,   th e   s ec o n d   ter m   r e s tr icts   ea c h   v ar i ab le  to   tak o n v al u e,   t h t h ir d   ter m   ag g r eg a tes  all   li n ea r   co n s tr ai n ts   ( Ax   b ) ,   an d   th last   ter m   s a tis f ies  t h e   p r o p r iety   o f   in teg r it y   w h ich   en s u r es  n e u r o n s   to   s tab ilize  a 0   o r   1   s tate.   B y   co r r esp o n d in g   ( 9 )   an d   ( 1 0 ) ,   w d ed u ce   th lin k   w ei g h t a n d   b iases   o f   t h n e t w o r k .     = 2 ) (1 = b ir rs ij ij i r j s ij i r j s i q T             ( 1 1 )     w it h   j i if j i if ij 0 = 1 =    is   th Kr o n ec k er   d elta.     T o   o b tain   an   eq u ilib r iu m   p o in o f   th C HN,   th p ar a m eter s   s etti n g   p r o ce d u r is   u s ed   [ 1 0 ]   [ 8 ] .   T h P r in cip o f   t h is   p r o ce d u r is   t o   m o v th e   n et w o r k   i n   t h d i r ec tio n   o f          .   T h is   p r o ce s s   s p ee d s   u p   t h n e u r al   n et w o r k   co n v er g e n ce   s ig n i f i ca n tl y .   Fu r t h er m o r e,   to   as s u r th s tab ili t y ,   w u s th h y p er p la n an al y s is   m et h o d   w h ich   ca lc u lates  t h en er g ie  f u n ctio n   ev o lu tio n .   L e t                             ,   th f o llo w in g   co n d itio n s   m u s b e   i m p o s ed   to   en s u r th co n v er g en ce .       >   0   to   h av m i n i m izatio n   p r o b lem       T h f ir s o n co n ce r n s   av o id i n g   t h ca s w h e n   t w o   v al u es  ar ass ig n ed   to   th s a m v ar i ab le,                          w it h           an d   th eir   co r r esp o n d in g   n eu r o n s     x ki =x k j =1 ,   s o   E ( x )   m u s v er if y :     E ir ( x ) 2 +                    ( 1 2 )       T h s ec o n d   en s u r es   t h at  all  v ar iab le  m u s b a s s i g n ed   an d   escap th ca s w h er x ir =0                         s o   E ( x )   m u s t v er i f y   also     E ir ( x )    d + +                  ( 1 3 )     W ith :         E m p ir icall y ,   t h b est v a lu o f       is   1 0 - 5   p ar am eter   s ett in g   b y   s o lv in g   [ 1 0 ]     = = 2 0 2 0 > 0, d               ( 1 4 )     T h C HN  p ar a m eter s   s et tin g   an d   t h s tar ti n g   p o in u s ed   in   th i s   p ap er   ar s i m ila r   to   [ 1 0 ] .   Fu r t h er m o r e,   p r o ce d u r w h i ch   allo w s   ea ch   n e u r o n   o f   th s a m v ar iab le  to   tak 0 ,   if   o n co n v er g es  to   th e   b o ar d e r   1 ,   is   ad d ed .   T h is   p r o c ed u r is   ca lled   Mo d er ato r   ( Fig u r 1 ) .       Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       N eu r a l Net w o r a n d   Lo ca S e a r ch   to   S o lve  B in a r C S P   ( A d i   B o u h o u ch )   1323       Fig u r 1 .   Mo d er ato r       T h is   ap p r o ac h ,   w h ic h   o n l y   u s e s   C o n ti n u o u s   Ho p f ield   n eu r al  Net w o r k   ( C H N) ,   w as  ex ten s i v el y   s tu d ied   o v er   d i f f er e n i n s ta n ce s   o f   C o n s tr ain t s   s at is f ac tio n   p r o b lem   [ 8 ] ,   b u s i m u latio n   p r o v ed   th at  t h i s   ap p r o ac h   h as  m an y   d i s ad v a n tag es.  Fo r   ex a m p le,   s o m eti m es  th e   n et w o r k   i n   co n tin u o u s   d y n a m ic  d o es  n o g iv e s   v alid   s o lu tio n ,   an d   it  is   attr ac ted   b y   t h n ea r est  lo c al  m in i m a to   th s tar tin g   p o in t.  T h is   attr ac tin g   ef f ec r e m ai n s   r es u lt  o f   its   d eter m i n is tic   in p u t - o u tp u i n ter ac tio n   o f   t h u n its   in   t h n et wo r k .   C o n s eq u en tl y ,   th n et w o r k   is   n o ab le  to   escap f r o m   lo ca s o lu tio n   clo s ed   to   th s tar tin g   p o in t.  A ls o ,   f o r   Ho p f ield   n eu r al  n et w o r k   w it h   co n ti n u o u s   d y n a m ic s   ca s e,   ea ch   u n it  o u tp u ca n   ta k an y   v alu b et w ee n   0   an d   1 .   So ,   th n et w o r k   ca n   b s tr a n d ed   at  a   l o ca m i n i m u m   w h ic h   co n tain s   s o m e   u n i ts   th at   s t ill  tak e   r ea v alu e s .   I n   t h i s   ca s e,   w o b tai n   an   in v alid   s o l u tio n   f o r   C SP .   T o   o v er co m t h i s   n e u r al  n et w o r k   w ea k n es s ,   th m ai n   id ea   o f   t h i s   w o r k   is   to   r ep air   th s o lu tio n   g i v en   b y   t h C HN  an d   i m p r o v it b y   k n o w n   M in - co n f lic t a lg o r it h m .       3.   CH AND  M I CO NF L I C T   H E UR I S T I T O   SO L V E   C SPS   T h er ar m a n y   m e th o d s   wh ich   co m b i n t w o   o r   m o r n o   ex ac t s   ap p r o ac h es  to   s o l v g iv e n   o p tim izatio n   p r o b le m   [ 1 1 ,   2 0 2 3 ] .   I n   th s a m d ir ec tio n   w i n tr o d u ce   h y b r id   ap p r o ac h   b ased   C HN  a n d   MN C .   T h MN C   al g o r ith m   [ 1 3 ]   is   v er y   s i m p le  a n d   f ast   lo ca l r ep air in g   m e th o d   to   r eso l v C SP s ,   w h ic h   ai m s   at  ass i g n i n g   all  th v ar iab les  r an d o m l y .   Ne x t,  it  iter ati v el y   s elec ts   o n v ar iab le  f r o m   th s et  o f   th v ar iab le s   w it h   co n f lict s   w h ic h   v io lates   o n o r   m o r co n s tr ain t s   o f   t h C SP .   T h en ,   it  ass ig n s   v alu to   th s elec ted   v ar iab le,   s o   th at  it  ca n   m in i m ize  th n u m b er   o f   co n f lict s .   MN C   h as  d e m o n s tr ated   to   b ab le  to   s o lv th q u ee n s   p r o b le m   i n   m i n u tes   [ 2 4 ] .   MN C   i s   w id el y   u s ed   to   co n s tr u ct  h y b r id   al g o r it h m s   w i th   o th er   o p ti m izatio n s   [ 2 5 2 8 ] .   I n   th is   w a y ,   t h b asic   id ea   o f   o u r   p r o p o s ed   ap p r o ac h   is   to   u s MN C   to   i m p r o v t h s o lu t io n   r ea ch ed   b y   C HN.   T h is   w i ll b d o n in   t w   o   s tep s   ( s ee   Fi g u r 2 ) .   First,  MN C   v i s it s   all  as s ig n ed   v ar i ab les;   f o r   ea ch   o n e ,   w ap p l y   Min - C o n f lict  d ir ec t l y   to   th n eu r al  n et w o r k   s tr u c tu r e,   th en ,   it  r etu r n s   th b est  ass i g n m e n f o r   th cu r r en v ar iab le  ( s ee   Fi g u r 3 ) ,   th d ec is io n   w ill  b tak e n   b y   th s u m   o f   al ac tiv ated   n eu r o n s   w ei g h t.  Seco n d ,   w p r o p ag ate  th i s   ass i g n m en to   o th er   s et  v ar iab les  n o y et  ass ig n ed   iter ativ e l y   b y   a p p ly i n g   th MN C   h eu r i s tic  to   g u ar a n tee  as   m u c h   co n s is te n c y   as  p o s s i b le.   T h d iag r a m   o f   o u r   p r o p o s ed   alg o r ith m   i s   d escr ib ed   b y   ( Fi g u r 4 ) .           Fig u r 2 .   Ma in   f u n ctio n   w h ic h   i m p r o v s o lu t io n   b y   Mi n - co n f lict a l g o r ith m     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,  Vo l.  1 0 ,   No .   3 ,   J u n 2 0 1 8   : 1 3 1 9     1 3 3 0   1324         Fig u r 3 .   Selecte d   th m o s t c o h er en n eu r o n   o f   cu r r en t c lu s te r   w it h   o th er   v ar iab les cl u s ter s   alr ea d y   a f f ec ted           Fig u r 4 .   Diag r a m   o f   th p r o p o s ed   alg o r ith m             Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       N eu r a l Net w o r a n d   Lo ca S e a r ch   to   S o lve  B in a r C S P   ( A d i   B o u h o u ch )   1325   E x a m p le  1 :   Meetin g   S ch ed u lin g   P r o b lem    T h Me etin g   Sc h ed u lin g   p r o b le m   ( MSP )   is   d ec is io n - m ak in g   p r o ce s s   a f f ec ti n g   s ev er al  p eo p le,   in   w h ic h   it  is   n ec es s ar y   to   d ec id w h e n   a n d   w h er s e v er al  m ee ti n g s   co u ld   b s ch ed u led .   T o   s h o w   h o w   th i s   alg o r ith m   w o r k s ,   w co n s id er   th f o llo w i n g   MSP   ex a m p le:      P ers o n s ={0 , 1 , 2 , 3     Meetin g s :       m 1   a tten d   p ers o n   g r o u p :   {0 , 1     m 2   a tten d   p ers o n   g r o u p : {1 , 2     m 3   a tten d   p ers o n   g r o u p : {0 , 1 , 2     m 4   a tten d   p ers o n   g r o u p : {2 , 3     Lo ca tio n   L={   p l 1 ,   p l 2 ,   p l 3 ,   p l 4 }     Dis ta n ce s   :               Time  S lo t={   t 1 , t 2 , t 3 , t 4 , t 5     Du r a tio n   o f e a c h   mee tin g   1   ti me   s lo     T his   p r o b lem   ca b r ef o r m ula ted   a s   the f o llo w ing   C SP:       V a r i a b les:  V ={ m 1 , m 2 , m 3 , m 4 }   lis t o f m ee tin g       Do ma in s   D=={ t 1 , t 2 , t 3 , t 4 , t 5   w h ere      t 1 =t 4 ={0 , 1 , 2 , 3 , 4 } a n d   t 2 =t 3 ={0 , 4 }     C o n s tr a in ts   C = {C i ,   1     i ≤     4   }     W s u p p o s ed   th a t   C HN   a fter   r u n n in g   g ives  a n   in co mp lete  s o lu tio n   S =V a ={{ m 1 =1 } , {m 2 =4 } , {m 3 =0 }}   F ir s t p a s s   :   F o r   ea ch   va r ia b le  in   V a       m 1       w ( 0 ) = w ( 1 ) = w ( 3 ) = w ( 4 ) = - α      w ( 2 ) =0   s o   Min - C o n f( m 1 ,V a )   r etu r n   2       m 2       w ( 0 ) - α     w ( 4 ) =0     S o   Min - C o n f( m 2 ,V a )     r etu r n   4       m 3       w ( 0 ) =0       w ( 4 ) = -   α   s o   Min - C o n f( m 3 ,V a )   r etu r n   0     Th s ec o n d   p h a s w ill ta ke   m 4   w h ich   is   n o t y et  a s s ig n ed   :     m 4       w ( 0 ) = w ( 1 ) = w ( 3 ) = w ( 4 ) - α      w ( 2 ) =0     s o   Min - C o n f( m 4 ,V a )   r etu r n   2       Th fin a l so lu tio n   is   S ={{ m 1 =2 },{m 2 =4 },{m 3 =0 },{ m 4 =2 },}.   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,  Vo l.  1 0 ,   No .   3 ,   J u n 2 0 1 8   : 1 3 1 9     1 3 3 0   1326   4.   NUM E RICAL   R E SU L T S   4 . 1 .     G ener a t ed  ra nd o m ly   in s t a nces   T o   ev alu ate  t h p er f o r m an ce   o f   p r o p o s ed   r eso lv in g   m et h o d s ,   w r u n   s o m p r eli m in ar y   e x p er i m e n t s   o n   th e   r an d o m l y   g e n er ated   p r o b lem s   an d   w e   co m p ar t h s o lu tio n   q u a lit y   b y   t h n u m b er   o f   v io latio n s .   Si m u latio n   h a s   b ee n   d o n w i t h   th f o llo w in g   m ac h i n ch ar ac ter is tics I 5   co r e( T M)   2 , 3 5 GHz   p r o ce s s o r   an d   li m ita tio n   o f   m e m o r y   to   2 GO.   Fo r   C HN  p ar a m eter s ,   th b es t v alu e s   w er f o u n d ed   e m p ir ica ll y     T o   g en er ate  r an d o m   p r o b lem s ,   w u s r an d o m   g en er ato r   b ased   ex ten d ed   m o d el  B   as  it  is   d escr ib ed   in   [ 2 9 - 3 1] .   T h is   ex te n d ed   m o d el  w h ich   is   ca lled   Mo d el  R B   is   ab le  to   g en er ate  h ar d   s ati s f iab le  i n s tan ce .   T o   s u m m ar ize  th i s   g e n er atio n   m e th o d ,   r an d o m   C SP   is   d ef i n ed   b y   t h f o llo w i n g   f i v i n p u t p a r a m eter s :         k : d en o tes th ar it y   o f   ea ch   co n s tr ai n t,  f ix ed   at  k =2 ,   s o   all  co n s tr ai n ts   ar b in ar y       n   : d en o tes th n u m b er   o f   v ar i ab les,      α : d eter m i n es t h d o m ai n   s ize  d =n α   o f   ea ch   v ar iab le,       r >0 : d eter m in e s   th n u m b er   m = r   n   l n ( n )   o f   co n s tr ai n ts ,       1> p >0 : d eter m in e s   th n u m b e r   t = p   d k   o f   d is allo w ed   tu p le s   o f   ea ch   r elatio n .       I n   th f o llo w i n g ,   class   o f   C S P s   w ill  b d en o ted   b y   tu p le  o f   th f o r m   < n , d , m , k , p >.   Fo r   s i m u latio n ,   w g e n er ate  5 0   in s ta n ce s   f o r   ea ch   p   v alu f o r   k =2 ,   α   =0 . 8 ,   r =3   an d   n   in   {2 0 ,   3 0 ,   4 0 },   a n d   w ca lcu late  th e   av er ag o f   v io lated   co n s tr ai n t s   o f   ea ch   i n s ta n ce   in   t h s a m e   class   o f   p   v al u e.   Fo r   th m o d el  p ar am eter   u s ed ,   w g et  <2 0 , 1 1 , 1 8 0 , p >,   <3 0 , 1 5 , 3 0 6 , p an d   <4 0 , 1 9 , 4 4 3 , p >.   T h co r r esp o n d in g   lo ad   cu r v i s   g i v e n   i n   F ig u r es   5 ,   6   an d   7   r esp ec tiv el y .   C o m p ar is o n   is   m ad b et w ee n   th s o lu tio n   o b tai n ed   b y   th p r o p o s ed   alg o r ith m   an d   t h e   s o lu tio n   g iv e n   b y   t h o r i g i n al  ap p r o ac h   [ 1 0 ] .   As  w ca n   s ee   Min - C o n f lict i m p r o v es   t h q u alit y   o f   th e   s o lu tio n   co n s id er ab l y   ar o u n d   m ea n   5 0 %,  an d   th s u cc e s s   o f   n et w o r k   is   u p   to   1 0 0 %,  b u f o r   C HN  ap p r o ac h ,   w f i n d   th e m p ir icall y   m ea n   v al u 7 2 % o v er   all  r u n s .                          Fig u r 5 .   nu m b er   o f   v io latio n   o v er   class N= 2 0       Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       N eu r a l Net w o r a n d   Lo ca S e a r ch   to   S o lve  B in a r C S P   ( A d i   B o u h o u ch )   1327     Fig u r 6 .   n u m b er   o f   v io latio n   o v er   class N= 3 0           Fig u r 7 .   n u m b er   o f   v io latio n   o v er   class N= 4 0         4 . 2     T y pica l ins t a nces   Fo r   s h o w in g   t h p r ac tical  in te r est  o f   o u r   ap p r o ac h ,   w also   s tu d y   its   p er f o r m a n ce   o v er   p r o b lem s   o f   d if f er e n n at u r es  ( r an d o m ,   ac a d em ic  an d   r ea l - w o r ld   p r o b lem s )   [ 3 2 ] .   T h g o al  is   to   e v al u ate  its   p er f o r m an ce   w it h   o t h er   ev o lu tio n ar y   a lg o r ith m s   [ 3 3 ,   3 4 ] .   T h u s ,   w co m p ar it s   e f f icien c y   w it h   t h e   Gen e tic  A l g o r ith m   ( GA )   [ 3 5 ]   an d   th P ar ticu lar   Sw ar m   Op ti m izatio n   ( P SO)   [ 3 6 ,   3 7 ] .   I n   p r ac tice,   r ath er   th an   a u th o r s   s etti n g s   w e   h av e m p ir icall y   s ea r ch in g   t h Gen etic  A l g o r ith m   a n d   P SO  g o o d s   o n es,  ad o p ted   to   C SP   p r o b lem .   So ,   f o r   G th p o p u latio n   w as   2 0 0   in d iv i d u als,  m u tatio n   r ate   eq u al s   to   5 an d   cr o s s i n g   r ate  eq u al s   t o   7 2 %,  as  f o r   P SO   [ 3 6 ,   3 7 ]   w ch o s                 an d   p o p u latio n   s ize  f ix ed   at  1 0 0 .   W also   r u n   ea ch   o n 2 0 0   tim e s .     T h C HN  p ar a m eter s   s etti n g   an d   th s tar ti n g   p o i n u s ed   in   th is   p ap er   ar s i m ilar   to   [ 1 0 ] ,   w h a v e   u s ed   th Var iab le  Up d atin g   S t ep   ( VUS)   tech n iq u p r o p o s ed   b y   T alav án   an d   Yáñ e i n   [ 8 ] .   T ab le  1   s h o w s   th e   co m p ar is o n   b et w ee n   o u r   ap p r o ac h   C H N - M NC   a n d   o r ig i n a C HN.   T h d escr ip tio n   o f   ta b le  co lu m n s   is   th e   f o llo w in g     V:  th n u m b er   o f   v ar iab les.      C : th n u m b er   o f   co n s tr ain ts .       R atio   m ea n : t h av er a g o f   th e   o p tim al  v al u in   2 0 0   r u n .       T im e:  t h av er a g o f   th t i m o f   all  r u n s .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,  Vo l.  1 0 ,   No .   3 ,   J u n 2 0 1 8   : 1 3 1 9     1 3 3 0   1328       T ab le  1 .   P e r f o r m a n ce   o f   o u r   p r o p o s ed   m eth o d s   C HN - MN C   an d   C HN  o v er   t y p ical  in s ta n c es p r o b lem s       N a me   o f   V   C   C H N - M N C     GA     PSO     I n st a n c e       M e a n   C P U ( s)     M e a n   C P U ( s)     M e a n   C P U ( s)   q u e e n s - 10   1 0 , 0 0   4 5 , 0 0   1 , 0 0   0 , 0 1     2 , 0 0   0 , 0 2     1 3 , 0 0   0 , 0 4   q u e e n s - 20   2 0 , 0 0   1 9 0 , 0 0   2 , 0 0   0 , 0 3     4 , 0 0   0 , 0 6     3 9 , 0 0   0 , 1 1   q u e e n s - 5 - 5 - 5   2 5 , 0 0   1 6 0 , 0 0   0 , 0 0   0 , 0 3     0 , 0 0   0 , 0 6     1 9 , 0 0   0 , 1 0   f r b 3 0 - 15 - 5 - mg d   3 0 , 0 0   2 1 0 , 0 0   1 0 , 0 0   1 , 0 7     1 4 , 0 0   2 , 4 6     4 0 , 0 0   4 , 0 8   g e o m - 30a - 5   3 0 , 0 0   8 1 , 0 0   1 , 0 0   0 , 0 6     2 , 0 0   0 , 1 3     7 , 0 0   0 , 2 1   g e o m - 30a - 6   3 0 , 0 0   8 1 , 0 0   0 , 0 0   0 , 0 5     0 , 0 0   0 , 1 2     4 , 0 0   0 , 2 0   q u e e n s - 30   3 0 , 0 0   4 3 5 , 0 0   4 , 0 0   1 , 9 4     6 , 0 0   4 , 4 5     8 3 , 0 0   7 , 3 9   frb 40 - 19 - 3 - mg d   4 0 , 0 0   3 0 8 , 0 0   1 4 , 0 0   0 , 9 3     2 1 , 0 0   2 , 1 4     5 3 , 0 0   3 , 5 6   g e o m - 40 - 2   4 0 , 0 0   7 8 , 0 0   2 3 , 0 0   0 , 0 1     2 4 , 0 0   0 , 0 3     2 8 , 0 0   0 , 0 4   g e o m - 40 - 6   4 0 , 0 0   7 8 , 0 0   0 , 0 0   0 , 0 9     0 , 0 0   0 , 2 1     4 , 0 0   0 , 3 6   my c i e l - 5g - 3   4 7 , 0 0   2 3 6 , 0 0   1 0 , 0 0   0 , 2 2     1 2 , 0 0   0 , 5 0     4 7 , 0 0   0 , 8 3   my c i e l - 5g - 4   4 7 , 0 0   2 3 6 , 0 0   5 , 0 0   0 , 4 1     8 , 0 0   0 , 9 5     2 9 , 0 0   1 , 5 8   my c i e l - 5g - 5   4 7 , 0 0   2 3 6 , 0 0   1 , 0 0   0 , 4 7     3 , 0 0   1 , 0 9     1 2 , 0 0   1 , 8 1   my c i e l - 5g - 6   4 7 , 0 0   2 3 6 , 0 0   0 , 0 0   0 , 1 3     1 , 0 0   0 , 3 1     1 2 , 0 0   0 , 5 1   d r i v e r l o g w - 01c   7 1 , 0 0   2 1 7 , 0 0   0 , 0 0   0 , 0 8     0 , 0 0   0 , 1 7     3 , 0 0   0 , 2 9   c o mp o se d *   1 0 5 , 0 0   6 2 0 , 0 0   1 3 , 0 0   2 , 9 3     1 4 , 00   6 , 7 5     5 6 , 0 0   1 1 , 2 0   d sj c - 1 2 5 - 1 - 4   1 2 5 , 0 0   7 3 6 , 0 0   5 0 , 0 0   0 , 3 0     6 4 , 0 0   0 , 6 9     1 0 2 , 0 0   1 , 1 5   d sj c - 1 2 5 - 1 - 5   1 2 5 , 0 0   7 3 6 , 0 0   1 9 , 0 0   0 , 8 0     2 9 , 0 0   1 , 8 3     8 5 , 0 0   3 , 0 4   Q w   h - 15 - 106 - 1   2 2 5 , 0 0   2 3 2 4 , 0 0   2 0 , 0 0   1 , 6 0     2 3 , 0 0   3 , 6 8     6 6 , 0 0   6 , 1 1   q w h - 15 - 1 0 6 - 4   2 2 5 , 0 0   2 3 2 4 , 0 0   1 8 , 0 0   4 , 0 6     22 , 0 0   9 , 3 5     5 9 , 0 0   1 5 , 5 2   q w h - 15 - 1 0 6 - 6   2 2 5 , 0 0   2 3 2 4 , 0 0   2 2 , 0 0   2 , 3 1     2 3 , 0 0   5 , 3 1     6 8 , 0 0   8 , 8 2   d r i v e r l o g w - 04c   2 7 2 , 0 0   3 8 7 6 , 0 0   3 , 0 0   8 , 3 2     5 , 0 0   1 9 , 1 3     1 1 , 0 0   3 1 , 7 5   d r i v e r l o g w - 02c   3 0 1 , 0 0   4 0 5 5 , 0 0   3 , 0 0   9 , 1 7     5 , 0 0   2 1 , 0 9     9 , 0 0   3 5 , 0 1   q w h - 20 - 1 6 6 - 0   4 0 0 , 0 0   5 0 9 2 , 0 0   3 0 , 0 0   1 6 , 7 9     3 2 , 0 0   3 8 , 6 3     9 3 , 0 0   6 4 , 1 2   q w h - 20 - 1 6 6 - 3   4 0 0 , 0 0   5 0 9 2 , 0 0   2 9 , 0 0   2 , 8 8     3 1 , 0 0   6 , 6 3     8 9 , 0 0   1 1 , 0 0   q w h - 20 - 1 6 6 - 6   4 0 0 , 0 0   5 0 9 2 , 0 0   2 5 , 0 0   8 , 1 9     2 9 , 0 0   1 8 , 8 4     8 6 , 0 0   3 1 , 2 7   le - 450 - 5a - 3   4 5 0 , 0 0   5 7 1 4 , 0 0   1 1 7 3 , 0 0   3 3 3 , 6 9     1 2 6 1 , 0 0   7 6 7 , 4 9     1 5 6 6 , 0 0   1 2 7 4 , 0 3   le - 450 - 5a - 4   4 5 0 , 0 0   5 7 1 4 , 0 0   7 1 2 , 0 0   3 , 8 9     7 4 5 , 0 0   8 , 9 5     1 0 6 6 , 0 0   1 4 , 8 6   le - 450 - 5a - 5t   4 5 0 , 0 0   5 7 1 4 , 0 0   4 4 1 , 0 0   2 , 2 9     4 7 0 , 0 0   5 , 2 6     8 7 4 , 0 0   8 , 7 2   NB : c o m pos e d *   i s   th e   in s ta n c e   c o m pos e d - 25 - 10 - 20 -           T ab le   1   w lear n   th at  G A   an d   C HN - MN C   ar clo s an d   b o th   b etter   th an   P SO,  b u r e g ar d in g   th e   m ea n   t i m ta k e n   b y   all  co m p ar ed   alg o r ith m s   C H N - M NC   i s   th s h o r o n e.   G A   [ 3 5 ]   h av e   th s a m p r in cip le   w it h   o u r   ap p r o ac h   w h ile  th e y   u s G A   a n d   Mi n i m izatio n   o f   co n f lict s ,   b u t h e y   i m p r o v t h b est  i n d iv id u al.   I t’ s   n o s u r t h at  i m p r o v in g   b est  s o lu tio n   w ill  g iv t h e   g o o d   o n e,   it  ca n   b n ea r   th w o r s o n i n   t h p o p u latio n .   Fo r   th i s   r ea s o n ,   t h m ea n s   v alu e   o f   t h m u lti p le  r u n s   o f   o u r   ap p r o ac h   w as  th b est  b ec a u s i i m p r o v es e ac h   f o u n d ed   s o lu t i o n .         5.   CO NCLU SI O N   I n   th i s   p ap er ,   w h a v p r o p o s ed   n e w   ap p r o ac h   f o r   s o l v in g   b in ar y   co n s tr ain t   s atis f ac tio n   p r o b lem s .   Ou r   h y b r id   alg o r it h m   g i v es  g o o d   s o lu tio n   q u alit y   r ath er   t h an   u s in g   C HN  alo n e,   th i s   i m p r o v e m en is   d o n e   b y   ad d in g   n o   i m p o r tu n ed   ti m co m p u ta tio n .   Fu r t h er m o r th r ate   o f   n et w o r k   s u cc e s s   to   g i v a   v al id   s o lu tio n   is   u p   to   1 0 0 b y   r ep air in g .   A ls o ,   th r es u lts   o f   t h n u m er ical  e x a m p le  s h o w   t h at  o u r   ap p r o ac h   is   co m p eti tiv w i th   G A   a n d   P SO.  T h b asic  Ho p f ield   n eu r al   n et w o r k   ar ch itect u r d escr ib ed   ab o v in clu d es   o n l y   b i n ar y   co n s tr ai n ts ,   b u s o m e   clas s es  o f   p r o b lem s   ar n ati v el y   n - ar y .   T h e x ten s io n   o f   th is   ap p r o ac h   to   s o lv th e s p r o b lem s   is   p o s s i b le  if   w ca n   tr an s la te  an y   n - ar y   p r o b le m   to   an   eq u iv a len t   b in ar y   o n e.   Oth er   s tu d ie s   ar in   p r o g r es s   to   ap p ly   t h i s   ap p r o ac h   to   m an y   r ea l - w o r ld   p r o b lem s   s u c h   a s   air cr af co n f lic t,   ti m etab li n g   an d   Me eti n g   s ch e d u lin g .       RE F E R E NC E S     [1 ]     K.  L e n in ,   B.   R.   Re d d y ,   a n d   M .   S .   Ka lav a th i,   W o l f   se a rc h   a lg o rit h m   f o so lv in g   o p ti m a re a c ti v e   (IJEEI ),   v o l.   3 ,   n o .   1 ,   p p .   7 1 5 ,   2 0 1 5 .   [2 ]     A .   C a rv a lh o   a n d   C.   S a n to s,  A   g e n e ra to o h e a v y - tailed   se a rc h   tree s,”   in   Re c e n D e v e l o p m e n ts  in   d e li n g   a n d   A p p li c a ti o n s i n   S tatisti c s.  S p ri n g e r,   2 0 1 3 ,   p p .   1 0 7 1 1 3 .   [3 ]     B.   A .   N a d e l,   T r e e   s e a rc h   a n d   a rc   c o n siste n c y   in   c o n stra in sa ti sf a c ti o n   a lg o rit h m s,”  in   S e a rc h   in   A rti f icia l   In telli g e n c e .   S p ri n g e r,   1 9 8 8 ,   p p .   2 8 7 3 4 2 .   [4 ]     C.   Be s siè re ,   P .   M e se g u e r ,   E.   C.   F re u d e r,   a n d   J.  L a rro sa ,   On   f o rwa rd   c h e c k in g   f o n o n b in a ry   c o n stra in t   sa ti sfa c ti o n ,   in   P rin c i p les   a n d   P r a c ti c e   o f   Co n stra in P r o g ra m m in g C P 9 9 .   S p ri n g e r,   1 9 9 9 ,   p p .   8 8 1 0 2 .     Evaluation Warning : The document was created with Spire.PDF for Python.