I nte rna t io na l J o urna l o f   E lec t rica l a nd   Co m p ute E ng in ee ring   ( I J E CE )   Vo l.   9 ,   No .   4 A u g u s t   201 9 ,   p p .   2 4 8 1 ~2 4 9 0   I SS N:  2 0 8 8 - 8708 DOI : 1 0 . 1 1 5 9 1 / i j ec e . v9 i 4 . p p 2 4 8 1 - 2490          2481       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 / I JE C E   Ada pted  b ra nch - a nd - b o und  a lg o rith m   u sing  S VM     w ith  m o del   s elec ti o n       K a bb a j   M o ha m e d M us t a ph a 1 E l   A f ia   Abdella t if 2   ENS IA S ,   M o h a m e d   V   Un iv e rsit y ,   Ra b a t,   M o ro c c o       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Ma y   1 ,   2 0 1 8   R ev i s ed   J an   5 ,   2 0 1 9   A cc ep ted   Ma r   4 ,   2 0 1 9       Bra n c h - a n d - B o u n d   a lg o rit h m   is  t h e   b a sis  f o th e   m a jo rit y   o f   so lv in g   m e th o d in   m ix e d   in teg e li n e a p ro g ra m m in g .   It  h a b e e n   p ro v in g   it e ff icie n c y   in   d if fe re n f ield s.  In   f a c t,   it   c re a tes   li tt le  b y   li tt le  a   tree   o f   n o d e b y   a d o p ti n g   tw o   stra te g ies .   T h e se   stra te g ies   a re   v a riab le  se lec ti o n   stra teg y   a n d   n o d e   se lec ti o n   stra teg y .   In   o u p re v io u w o rk ,   we   e x p e rien c e d   a   m e th o d o lo g y   o lea rn in g   b ra n c h - a n d - b o u n d   stra te g ies   u sin g   re g re ss io n - b a se d   su p p o rt  v e c to m a c h in e   tw ic e .   T h a m e th o d o lo g y   a ll o w e d   f ir stl y   to   e x p lo it   in f o rm a ti o n   f ro m   p re v io u e x e c u ti o n o f   Bra n c h - a n d - Bo u n d   a lg o rit h m   o n   o th e r   in sta n c e s.  S e c o n d ly ,   it   c re a ted   in f o rm a ti o n   c h a n n e b e tw e e n   n o d e   se lec ti o n   s trate g y   a n d   v a riab le  b ra n c h in g   stra teg y .   A n d   th ir d ly ,   it   g a v e   g o o d   re su lt in   term   o ru n n in g   ti m e   c o m p a rin g   to   sta n d a rd   Bra n c h - a n d - B o u n d   a lg o rit h m .   In   th is  w o rk ,   w e   w il f o c u o n   in c re a sin g   S VM  p e rf o rm a n c e   b y   u sin g   c ro ss   v a li d a ti o n   c o u p led   w it h   m o d e se lec ti o n .   K ey w o r d s :   No d s elec tio n   s tr ate g y   Var iab le  b r an ch in g   s tr ate g y   B r an ch   an d   b o u n d     SVM    C r o s s   v a lid atio n     M o d el  s elec tio n   Co p y rig h ©   2 0 1 9   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 :   K ab b aj   Mo h a m ed   Mu s tap h a,     E NSI AS,   Un i v er s i t y   Mo h a m e d   V,   A b d ellah   R e g r ag u i Str ee t,  Ma d in at  AL   I r f an e,   R a b at,   Mo r o c co .   E m ail:  m u s tap h a. k ab b aj @ u m 5 s . n et. m a       1.   I NT RO D UCT I O N   I n   r ea lif e,   MI L P   h a s   co u n tles s   ap p licatio n s   i n   d if f er en f ield s   li k lo g is tic s ,   f in an ce   an d   tr an s p o r tatio n .   A   v er y   co m m o n   s o l u tio n   tech n iq ue   o f   MI L P   f r a m e w o r k   is   B r an ch - a n d - B o u n d .   I co n ti n u e s   to   p r o v its   r elev an ce   n o w ad a y s .   B r an ch - a n d - B o u n d   alg o r ith m   is   a n   iter ativ al g o r ith m ,   a n d   at  ea ch   iter atio n ,   w e v e n tu a ll y   g et  f ea s ib le  o r   o p tim al  s o lu tio n   o f   a n   i n iti al  p r o b lem .   C o n cr etel y ,   t h al g o r ith m   co n s tr u ct s   litt le  b y   litt le  tr ee   o f   n o d es,   w h er ea c h   n o d r ep r esen t s   m o d if ied   v er s io n   o f   t h o r i g in a p r o b le m .   T h co n s tr u ct io n   o f   c h ild   n o d es  is   co n d u cted   b y   v ar iab le  b r an ch in g   s tr ate g y .   An o t h er   f u n d a m en tal  ele m e n i n   B r an ch - a n d - B o u n d   alg o r i t h m   is   No d Selectio n   Stra te g y   th at  ai m s   to   c h o o s a m o n g   n o d es  q u eu e,   o n t h at   w il l sp ee d   u p   th s ea r c h .     R ec en t l y ,   s o m e   w o r k s   h as  b e en   tr y in g   to   id en t if y   a n   a n al y t ic  ap p r o ac h   th at   d ec id ab o u t   s tr ate g ies   d escr ib ed   ab o v e,   g iv e n   s et  o f   p r o b le m   f ea tu r e s .   Au th o r s   u s li k el y   m ac h i n lear n i n g   tec h n iq u es.  T h m ai n   r e m ar k   is   t h at  f e w   a u t h o r s   w h o   d ea w it h   n o d s elec tio n   s tr a teg y ,   a n d   if   s o ,   th e y   d id   n o u s m ac h i n lear n i n g   f r a m e w o r k .   Ou r   co n tr ib u tio n   i s   o r ien ted   to w ar d s   lear n in g   e f f icien b r an ch - a n d - b o u n d   s tr ate g ies.  T h is   i s   t h e   r esu lt  o f   co n s i s te n m et h o d o lo g y   b eg i n n in g   w it h   th co lle ctio n   o f   th d ata  s et,   an d   en d i n g   w it h   t h test   o f   th f in al  h y p o t h esi s .   Mo r ex p licitl y ,   w e:   -   Def i n f ea t u r es   -   C o llect  d ata  s et    -   P ick   th o p ti m al  lear n in g   m o d el   -   L ea r n   t h f in a h y p o t h esi s   w it h   th c h o s e n   m o d el   -   I m p le m e n t a n d   t est th f i n al  h y p o t h esi s     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 A u g u s t 2 0 1 9   :   2 4 8 1   -   2490   2482   Nex t,  w e   ad d r ess   r e s ea r ch   p ap er s   r elati v to   o u r   w o r k .   T o   d o   s o ,   w e   d iv id co n tr ib u tio n s   in   f i v e   s u b - s ec tio n s   r elati v el y   to   th s tr at eg y   a n d   to   th lear n i n g   tec h n i q u u s ed .   Firstl y ,   r elati v el y   to   v ar iab le  b r an ch in g   s tr ateg y ,   au t h o r s   in   [ 1 ] ,   lear n ed   f u n ctio n   to   b w it h   ap p r o x im a tiv e l y   t h s a m p er f o r m a n ce   as  s tr o n g   b r an ch i n g   i n   ter m   o f   p r ec is io n ,   an d   in   th s a m t i m e,   r es u lt s   in   g ai n   o f   t h p r o ce s s in g   ti m e.   I n   th i s   s a m ca teg o r y ,   w ci te   [ 2 ] ,   w h er ein   a u t h o r s   in f er   co n s i s te n d ata  f r o m   ap p l y i n g   an   alg o r ith m   f o r   d etec tin g   cla u s e s .   A   cla u s b ein g   co m b in a tio n   o f   b in ar y   v al u es   af f ec ted   to   s e o f   in d ex ed   v ar iab les,   th at  i f   it  h ap p en s ,   th w h o le   p r o b lem   w o u ld   b in f ea s ib l e.   I n   ad d itio n ,   th at  a lg o r it h m   g en er ate s   m in i m a l   clau s e s   a n d   r estar ts   w i th   ac ti v clau s e s   ( t h o s t h at  ca n   b u s ed   i n   f at h o m i n g   ch ild   n o d e s ”) .   I n   p ar allel,   t h is   in f o r m atio n   i s   u s ed   to   ch o o s b r an ch in g   v ar iab le  w it h   t h b est  ef f ec t.  Als o   [ 3 ]   an d   [ 4 ]   u s b ac k tr ac k i n g   t o   i m p r o v b r an ch i n g   d ec is io n s .   B esid es,  th er ar cla s s ic  v ar i ab le  b r an ch i n g   r u les,   li k s tr o n g   b r an c h i n g ,   p s eu d o   co s t s   b r an ch i n g ,   h y b r id   b r an c h i n g ,   r el iab le  b r an ch i n g ,   i n f er en ce - b ased   b r an c h in g   [ 5 ] .   No te  th at   r eliab ilit y   b r an ch i n g   is   k n o wn   to   b th b est  b r an ch i n g   r u le   w it h   t h r eliab ilit y   = 4      8   [ 6 ] .   Fo r   o u r   ex p er i m e n ts ,   w u s ed = 8 .   T h r eliab ilit y   p ar a m eter     is   f ix ed   to   s to p   t h ca lc u latio n   o f   p s e u d o co s v al u e s   a f ter   atta in i n g   ce r tai n   lev el  o f   t h b r an ch   a n d   b o u n d   tr ee .   T h is   is   b ec au s p s e u d o co s v alu r e m ai n   ap p r o x i m ati v el y   co n s ta n af ter   ca lcu lati n g   it se v er al  ti m es  f o r   d eter m i n ed   v ar iab le.   Seco n d l y ,   w cite   f r o m   n o d s elec tio n   s tr ateg y   li ter atu r e ,   in   ad d itio n   to   cla s s ic   n o d e   s elec tio n   s tr ateg ie s ,   s u c h   as   d ep th - f ir s t   r u le,   b r ea d th - f ir s r u le,   a n d   n o d b est - e s ti m ate   [ 5 ] ,   au t h o r s   o f   [ 1 ] ,   ex tr ac ted   in f o r m atio n   f r o m   MI L P   B en ch m ar k   lib r ar ies  b y   u s i n g   s p ec if ic  al g o r ith m   ca lled   o r ac le.   T h ir d l y ,   co n ce r n i n g   lear n in g   a lg o r it h m s ,   t h e y   ar e   u s ed   in   d if f er en e n g i n ee r i n g   f ield s .   Alg o r it h m s   p u r p o s es  ar clas s i f icatio n ,   r eg r ess io n ,   cl u s ter i n g   [ 7 ] [ 8 ] T h er ar alg o r ith m s   t h at  te n d   to   d o   w el i n   p r ac tice  m o r th a n   o t h er s   [ 9 ] [ 1 0 ] .   I n   th s a m co n te x t o f   ap p l y in g   lear n i n g   in   b r an c h   an d   b o u n d ,   th E x tr aT r ee s   is   ap p lied   in   [ 1 1 ]   Fo u r th l y ,   w h e n   lo o k i n g   a m o d el  s elec tio n   a n d   t h p er f o r m an ce   o f   al g o r it h m s ,   t h er ar tech n iq u e s   u s ed   to   tu n p ar a m eter s   s u ch   as  F u zz y   L o g ic  co n tr o ller   f o r   A n C o lo n y   S y s t e m   ( AC S)  ep s ilo n   p ar am eter   [ 1 2 ] .   A ls o ,   [ 1 3 ]   an d   [ 1 4 ]   u s ed   Hid d en   Ma r k o v   Mo d el  ( HM M)   al g o r it h m   t o   tu n t h P ar ticle   S w ar m   o p ti m izat io n   p o p u latio n   s ize  a n d   ac ce ler atio n   f ac to r s   p ar a m eter s B es id es,  a u th o r s   in   [ 1 5 ]   u s ed   HM M   to   tu n e   th in er tia  w eig h p a r a m eter   o f   t h P ar ticle  S w ar m   Op ti m izatio n   al g o r ith m .   Mo r eo v er ,   [ 1 6 ]   u s ed   Fu zz y   co n tr o ller   to   co n tr o Si m u lated   An n ea l in g   co o lin g   la w ,   [ 1 7 ]   an d   [ 1 8 ]   u s ed   HM to   tu n AC S   ev ap o r atio n   p ar a m eter   an d   lo c al  p h er o m o n d ec a y   p ar a m ete r   r esp ec tiv el y ,   [ 1 9 ]   an d   [ 2 0 ]   u s ed   HM to   ad ap th s i m u lated   an n ea li n g   co o li n g   la w .   Fu r t h er m o r e,   [ 1 4 ]   u s ed   SVM  al g o r ith m   to   p r ed ict  th p er f o r m an ce   o f   o p tim izatio n   p r o b le m s Fi n all y ,   au th o r s   i n   [ 2 0 ]   u s ed   th E x p ec tatio n - Ma x i m izatio n   alg o r ith m   to   lear n   th e   HM al g o r ith m   p ar a m eter s .   Fin all y ,   th i s   p ap er   is   t h co n ti n u i t y   o f   o u r   p r ev io u s   p ap er s   w h ic h   d ea ls   w it h   th e   lear n in g   o f   b r an c h - a n d - b o u n d   alg o r ith m   s tr ate g ies,  n a m el y   v ar iab le  b r an ch in g   s tr ate g y   an d   n o d s elec tio n   s tr ateg y   [ 2 1 ] [ 2 2 ] .   T h lear n in g   al g o r ith m   u s ed   w as S u p p o r t V ec to r   Ma ch in ( S V M ).   T h r est  o f   t h is   p ap er   is   o r g a n ized   as   f o llo w s :   Sectio n   2   r e ca lls   s o m e   b asics   o n   b r an ch - a n d - b o u n d   alg o r ith m   a n d   S VM   al g o r ith m   w i th   p ar a m eter   t u n in g .   I n   s ec tio n   3 ,   w p r ese n o u r   m eth o d o lo g y   o f   i n f er r in g   ef f icien b r an c h   a n d   b o u n d   s t r ateg ies   a n d   e x p er i m e n tatio n   co n f i g u r atio n .   Sec tio n s   4   is   d ed icate d   to   r esu lt s .   Fin all y ,   w co n cl u d an d   p r o p o s s o m f u t u r w o r k .       2.   B RANC H - AND - B O UND  AND  SVM   I n   t h is   s ec tio n ,   w ar f ir s t   g o in g   to   s ee   a n   o v er v ie w   o f   a   f o r m al  d e s cr ip tio n   o f   b r an c h - an d - b o u n d   s tr ateg ie s   an d   p r esen t h f ea t u r es  u s ed   in   th al g o r ith m .   Se co n d l y ,   w w ill  in v e s ti g ate  S VM   m o s i m p o r ta n t   ad v an ta g es  w i th   r e m a in d er   o f   lear n i n g   th eo r y .     2 . 1 .   B ra nch - a nd - bo un d a lg o rit hm   B r an ch - a n d - b o u n d   al g o r ith m   is   o u tli n ed   i n   th is   s ec tio n .   W f ir s d ef i n u s e f u n o tati o n   an d   t h en   p r o ce ed   w it h   th e x p lan a tio n   o f   th al g o r ith m   s tep s .   L et  u s   d ef in g en er al  MI L P   p r o b le m   P   as f o llo w s     = m i n   {   |  =   , 0 ,   N on - ne g ati v v ec to r   o f     d im e n s io n     co n tain i n g   at  lea s t o n i n teg er }     w h er     ,          i s     d i m en s io n   m atr i x W w ill  u s also   d ef in e :     is   r elax ed   v er s io n   of   w h ic h   is        =    {   |  =   , 0 }         is   th p r o b le m   in   t h   iter atio n   w h ich   co r r esp o n d s   to   n o d in   b r an ch - a n d - b o u n d   tr ee .   ,    i s   r elax ed   v er s io n   o f   .     is   th o b j ec tiv v al u o f     n o d e.   ( )   is   th i n c u m b e n t p o in t a t iter at io n   ,   w h ic h   m ea n s   t h v ec to r   th at  lead s   to   th b est    s o   f ar .     is   th o b j ec tiv f u n ct io n   v a lu o n   ( )   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A d a p ted   b r a n ch - a n d - b o u n d   a l g o r ith u s in g   S V M w ith   mo d e l selec tio n   ( K a b b a j Mo h a med   Mu s ta p h a )   2483   B r ief l y ,   t h B r an ch - a n d - b o u n d   alg o r ith m ,   in   th ca s o f   m i n i m iz atio n ,   i s   d escr ib ed   as   f o llo w s   a s   s h o w n   in   Alg o r it h m   1 .   I is   an   iter ati v alg o r it h m ,   a n d   in   ea ch   iter atio n   ,   w h a v at   least  th r ee   s tep s   w h ic h   ar e :   Firstl y ,   t h n o d s elec tio n   s t ep   ai m s   to   r etr iev e   n o d f r o m   n o d li s t h at   m a x i m i ze s   s o m e   cr iter io n .   T h is   latter   is   s p ec if ic  to   th n o d s elec tio n   s tr ateg y .     Seco n d l y ,   an d   o n ce   w h a v p ick ed   n o d e   w s o lv its   r ela x atio n   ,   b y   a n   al g o r ith m   f r o m   t h li n ea r   p r o g r a m m in g   f r a m e w o r k   s u c h   as  s i m p lex   o r   in ter io r   p o in ts .   Dep en d i n g   o n   th r es u lt s ,   w d i s ti n g u i s h   th r ee   ca s es.  T h f ir s t   o n is   w h e n   t h p r o b le m   ,   is   i n f ea s ib le  o r   th e   r esu lti n g   o b j ec tiv f u n ctio n     v al u is   g r e ater   th a n   .   C o n s eq u en tl y ,   t h c u r r en i ter atio n   is   ter m i n tated .   T h s ec o n d   ca s is   w h e n   th s o lu tio n   is   i n te g er   an d   < I n   th is   m o m e n t,  w u p d ate  th e   in cu m b e n t p o in a n d   its   o b j ec t iv v a lu ,   th en   w m o v to   t h n ex t i ter atio n .   I n   t h t h ir d   ca s e,   w h e n   n o n o f   th co n d if io n s   m en tio n ed   b ef o r h ap p en s ,   w p er f o r m   v ar i ab le  b r an ch in g .   I n   th i s   f i n al  s t ep ,   w m u s s elec a   v ar iab le  f r o m   s e o f   n o n - i n t eg er   v ar iab les   r e lati v el y   to   s o m d ef in ed   cr iter io n .   An d   t h i s   cr iter io n   is   d ef i n ed   b y   t h v ar iab le  b r an c h i n g   s tr at eg y .           A l g o r ith m   1 .   B r an ch - an d - b o u n d   Alg o r it h m       2 . 2 .   Su pp o rt   Vec t o M a chine   SVM  is   in   to p   ten   m ac h in le ar n in g   alg o r i th m s   [ 9 ] ,   it  is   u s ed   f o r   b o th   class if ica ti o n   an d   r eg r ess i o n .   I t a im s   to   f in d   th h y p er p l an w ith   th b est m ar g in .   T h b est  is   d em o n s tr ate d   t o   b th la r g e   o n d if f e r en t iat in g   b etw ee n   th e   h y p er p l an an d   n e ar est  d ata   p o in ts   ca l le d   s u p p o r t   v ec t o r s .       2 . 2 . 1 .   Ca s e   o f   L in ea H y po t h esis   s e t   f o r   SV M :   I n   th e   c ase   o f   r eg r ess io n ,   an d   esp ec i ally   o n e   v a r ian t   o f   SV ca l le d   - SVM,   w w ill  p r es en n ex tly ,   th c ase  o f   lin e a r   h y p o th esis   s et.   L e t’ s   h av in   h av in   th i n p u t,    tr ain in g   d at a,   n am ely   ( , ) , 0   T h e   o u t p u t   o f   th e   alg o r i th m   is   lin e ar   f u n cti o n :   ( ) = + ,   w ith     a   c o e f f icien t   v ec to r ,   x   th e   u n k n o w n   v ec t o r   an d   b   a   c o n s tan t .   T h e   d is tan c e   b etw ee n   a   h y p er p l an e   o f   e q u a ti o n   + = 0   an d   th s u p p o r t   v e ct o r s ,   is   1 | | | | C o n s eq u en tly ,   m ax i m izin g   th e   m ar g in   is   e q u iv alen t   t o   th e   n e x t o p t im izati o n   p r o b l em :     ( ) : { m in 1 2 . .     | ( + ) |   ,         W ith ,     b ein g   th er r o r   t o l er an c b etw ee n     an d   ( ) .           Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 A u g u s t 2 0 1 9   :   2 4 8 1   -   2490   2484   T h las t p r o b lem   m ig h t b in f e asib le .   A n d   t o   a d d   m o r e   ch an c to   b f ea s i b l e ,   w ad d   s l ac k   v ar i ab les   to   th e   p r o b lem ,   in   th e   f o l lo w in g   w a y :     ( ) : {         m i n ( ) = 1 2   + ( +   ) = 1 . .     ( + )   + ,   ( + )   + , n , 0 ,       w ith ,        ar e   th e   s la ck   v a r i ab les ,   an d     is   th e   c o s t   p a r am eter   u s ed   t o   p en ali ze   d at p o in ts   o u t s id e   th e   m ar g in   .   B y   u s in g   lag r ag i an   f u n ctio n ,   an d   q u a d r ati o p tim izati o n   o r   o th e r   r es o lu ti o n   m eth o d s ,   o n e   ca n   p r o v e   th at   th s o lu t io n   is   w ith   th e   f o r m   o f :     ( ) = ( ) = 1 +       w ith     0 , , 1 .     2 . 2 . 2 .   Ca s e   o f   n o lin e a h y p o t hes i s   s e t   I n   th s itu at io n ,   w h er w c an n o f in d   h y p er p l an c o n t ain in g   all  t r ain in g   in s tan c es,  o n m ig h t   tr an s f o r m   th s p a ce   o f   th e   t r a in in g   d a ta  to   an o th e r ,   in   s u ch   w a y   ca n   b e   c o m p r is e d   in   o n h y p er p l an o n   th e   n e w   s p ac e.   T o   d o   th is   tr an s f o r m ati o n ,   o n e   c an   u s e   th w ell - k n o w n   k er n el  m eth o d s .   I n   f ac t ,   th er ar in   lite r a tu r e   d if f er en k e r n els  u s ed   f o r   SV M ,   s u ch   as  R B a n d   p o ly n o m ial.   F o r   th e   r est ,   w w ill  p r es en th e   d is t an ce   c alcu l ati o n   m eth o d   f o r   th R B F   k er n el.     I n s te ad   o f   u s in g   th s t an d ar d   L 2    | | . | | ,   w u s ed   th n o r m   ass o cia te d   w ith   R B k er n el  th at  is   d es cr ib ed   as   f o ll o w s      ( , ) = e x p ( γ | | x x | | 2 )       w ith   γ ,   is   th g am m p a r am ete r .   I ts   g eo m etr ic al  in t er p r e tat io n   i s ,   w h en   th g am m p ar am ete r   h as la r g e r   v alu e s ,   th h y p er p lan ass o c iat e d   w it h   th s o lu ti o n   w ill  h av m o r in clin a ti o n s   to   c o n ta in s ,   as  f ar   as  p o s s i b l e,   all   tr a in in g   d at a.   T h e   f o r m   o f   th r esu ltin g   t ar g et  f u n ct io n ,   w ill  b as   f o ll o w s :     ( ) = ( )  ( , ) = 1 +       I n   th is   p a p e r ,   w w ill  u s e   - SVM  r eg r ess i o n   a lg o r ith m   w ith   th R B F   k e r n el   tw ice   f o r   le a r n in g   n o d e   s ele cti o n   s tr a teg y   an d   v ar ia b l b r an ch in g   s tr ateg y   r esp ec t iv ely .     2 . 3 .   L ea rning   o f   v a ria ble bra nchin g   s t ra t eg y   a nd   no de  s elec t i o n str a t eg y     C o n ce r n in g   th v a r ia b l b r a n ch in g   s tr a teg y ,   w aim   in   th is   p a p er   to   im itate  th b eh av io r   o f   th e   r el ia b il ity   b r an ch in g   r u l e.   T h i s   r u le   is   b as ed   o n   s tr o n g   b r a n ch in g ,   w h ich   is   tim c o n s u m in g .   B y   an d   l a r g e,   r el ia b il ity   b r an ch in g   u s es   an   u n r eli a b ili ty   q u ali ty   f o r   v ar i a b l p s eu d o - c o s ts   v a lu es.   Fo r   th i s   r ea s o n ,   r eli ab ilit y   d e p en d s   o n   n u m er o u s   p r o b lem   f ea tu r es .   T h ese  f ea tu r es  ar to   b class if ie d   in   n o d e - b as ed   f e atu r es  an d   v ar ia b le - b as ed   f ea tu r es.     2 . 3 . 1 .   No de - ba s ed  f ea t ures   W u s in   t h is   ca te g o r y   f ea t u r es b elo w :     -   R ed u ce d   Ob j ec tiv v al u es  g ai n :     Δ , = | 1 | | 1 |   ( No te  th at  th f ea tu r e s   s h o u ld   b in d ep en d en t o f   t h p r o b le m   s ca le)     -   Dep th   in   b r an c h   an d   b o u n d   tr ee     s tar tin g   f r o m   ze r o .   -   No d esti m ate.   -   L P   Ob j ec tiv Valu e     2 . 3 . 2 .   Va ria ble - ba s ed  f ea t ures   I n   th s a m t h i n k i n g   li n e,   w u s e:    -   P s eu d o - co s t v al u e   -   T h p o s itiv e   r ed u ce d   co s t a n d   th n e g ati v r ed u ce d   co s ts   i.e .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A d a p ted   b r a n ch - a n d - b o u n d   a l g o r ith u s in g   S V M w ith   mo d e l selec tio n   ( K a b b a j Mo h a med   Mu s ta p h a )   2485   ma x   ( | , | | , |   :     ,   0   , 0 )     an d   ma x   ( | , | | , |   :     ,   0   , 0 )       w it h   ,   i s   th   co m p o n en v alu e   o f   co s v ec to r   o f   iter atio n   .   T h ese  f ea tu r es  ai m   to   p r esen eith er   in   m i n i m izatio n   o r   m a x i m izatio n   p r o b lem s   h o w   w ap p r o ac h   t o   th o p ti m al  s o l u tio n .   T h o th er   s p ec if icit y   in   o u r   wo r k   b ey o n d   ch a n g es  in   f ea tu r e s   b ased   o n   th o s p r esen ted   in   [ 1 1 ] ,   is   w e   ad d   th v a lu e   o f   lear n ed   f u n ct io n   r ep r esen ti n g   n o d s elec tio n   i n   t h s et  o f   f ea tu r e s .   T h is   l ast  p o in t   is   j u s ti f ied   in   th f o llo w in g   s u b - s ec tio n .   F o r   lear n in g   n o d s elec tio n   s tr ateg y ,   w w ill  i m itate  n o d esti m ate  s tr ate g y .   T h is   s tr ateg y   is   t h d ef a u lt o n u s ed   in   S C I P   s o lv er .     2 . 4 .   I nte ra ct io n o f   no de  s elec t io n str a t eg y   a nd   v a ria ble selec t io n str a t eg y   I n tu itiv e ly ,   th ch o ice   o f   a   n o d e,   b y   a   n o d e   s el ec t io n   s tr a teg y ,   in f lu en ce s   th e   ch o ic th e   n ex b r an ch in g   v a r ia b l e.   Fo r   th is   r e aso n ,   w d esc r i b e   f o r m ally   th v a r ia b l b r an ch in g   s t r at eg y   f u n ctio n   VB   in   f u n ctio n   o f   co m b in at io n   o f   NS   ( N o d e   s el ec ti o n   s t r at eg y   f u n cti o n )   an d   o th e r   f ea tu r es   d esc r i b e d   b el o w :      (       ) =  (   ,            ,            ) +               w h er   an d     a r e   r ea l n u m b er s .   No t th at   w d o u b le   u s e   NS   f e atu r es  ad d   m o r e   p r e ci s i o n .     2 . 5 .   Ov er f it t ing   a nd   pa ra m et er   t un ing   I n   th i s   s u b - s ec tio n ,   w w ill   d ef in o v er f i ttin g ,   w h ic h   is   v er y   co m m o n   p r o b le m   i n   lear n i n g   tech n iq u es t h at  a f f ec ts   t h f i n a l p er f o r m a n ce .     2 . 5 . 1 .   O v er f it t ing   A   lear n i n g   m o d el  is ,   b y   d ef i n i tio n ,   co u p le  o f   a   lear n i n g   al g o r ith m   a n d   h y p o th es is   s et.   A   lear n i n g   alg o r ith m   i s   a n   iter ati v al g o r ith m   t h at  s ea r ch es   th e   b est  h y p o th esis   f it tin g   t h tr ai n i n g   d ata.   T h is   h y p o th es i s   is   in cl u d ed   in   t h h y p o th e s i s   s et  c h o s en   i n itia ll y .   A   v er y   co m m o n   p r o b le m   en co u n t er ed   in   lear n in g   i s   o v er f itti n g .   T h is   p h en o m en o n   o cc u r s   w h en   t h lear n ed   h y p o th esis   d o es  n o g e n er alize   w ell  to   all  p o s s ib le  v alu e s   b e y o n d   t h tr ain i n g   d ata.   C au s e s   ar n u m b er   o f   d ata  p o in ts ,   n o is a n d   tar g et  co m p l ex it y   [ 7 ]   T h ch o ice  o f   lear n i n g   a lg o r it h m s   co u ld   a f f ec t h n o i s b y   af f ec tin g   eit h er   b ias  o r   v ar ia n ce .   I n   t h e   ca s o f   SVM,   t h th o r o u g h   ch o ice  o f   SVM  p ar a m e ter s   is   r eq u ir ed   to   p r ev en f r o m   o v e r f itti n g .   T h R B F   Ker n el  SVR   al g o r ith m   u s ed   in   th i s   w o r k   h as  t w o   p ar am et er s ,   co s an d   g a m m a.   C o s d ef i n es  h o w   m u c h   is   p en alize d   m i s clas s i f ied   ex a m p les  an d   g a m m d e f in e s   h o w   f ar   t h i n f lu e n ce   o f   s i n g le  tr ain i n g   ex a m p le   r ea ch es.  As  k n o w n   s m al co s t   an d   lar g g a m m a,   g i v h ig h e r   b ias  an d   lo w er   v ar ia n ce .   I n   ad d itio n ,   lar g co s an d   s m all  g a m m g iv e   lo w e r   b ias  an d   lar g er   v ar ia n ce .   C o n s eq u en tl y ,   w s h o u ld   t u n co s an d   g a m m p ar am eter s   u n til  w f i n d   tr ad eo f f   v al u es  to   m i n i m ize  th g en er aliza tio n   er r o r .   On w a y   to   tu n g a m m an d   co s t p ar am eter s   is   to   u s cr o s s   v alid atio n .       2 . 5 . 2 .   Cro s s   v a lid a t io n w it m o del  s elec t io n   B ef o r d ef in i n g   cr o s s   v alid ati o n ,   let  u s   f i n d   o u w h at  is   v ali d atio n .   T o   d o   s o ,   w d ef in s o m e   u s e f u l   n o tatio n      th d ata  s et     th tr ain i n g   s et     th v alid atio n   s et    T h g o al  o f   v alid atio n   is   to   g iv an   e s ti m atio n   o f   t h g e n e r aliza tio n   er r o r .   First,  it  d iv id es    o f     d ata  p o in ts ,   to     o f   s ize    an d     o f   s ize  ,   th en   lear n s   th tar g et  f u n ctio n   b ased   o n   Fin all y ,   w ca lc u late  er r o r   o f   th tar g e f u n ctio n   i n   .   T h is   latter   er r o r   is   p r o v en   an   esti m atio n   o f   t h e   g en er aliza tio n   er r o r .   T h F ig u r r e p r esen ts   w h at  is   d escr ib ed   ab o v e .           Fi g u r 1 .   Valid atio n   m et h o d   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 A u g u s t 2 0 1 9   :   2 4 8 1   -   2490   2486   T h   er r o r   is   g o o d   esti m ate   o f   g en er aliza tio n   er r o r   b u it  is   n o to o   p r ec is e.   T o   im p r o v th e   p r ec is io n ,   o th er   tech n iq u e s   r ep o s o n   v alid atio n   li k cr o s s   v al id atio n .   W ith o u th l o s s   o f   g e n er alit y ,   w p r ese n t n e x t 1 0 - f o ld   cr o s s   v alid atio n   p r o ce s s .   L et s   p ar titi o n     to   1 ,   2   to   10 .   W u s v alid atio n   p r o ce s s   te n   ti m es  f o r   , =   w h er e   1 10    an d   , = \ .   I n   th o u tp u t,  w h a v 10   er r o r s   1   to   10 .   T h en   w ca lc u lat cr o s s   v alid atio n   er r o r   d en o ted   b y      w h ic h   i s   t h m ea n   v alid atio n   er r o r s .   T h cr o s s   v a lid atio n   er r o r   is   m o r e   p r ec is th at  v al id atio n   er r o r .   W r esu m t h is   p r o ce s s   i n   th F ig u r e   2.           Fig u r e   2 .   C r o s s   v alid atio n   f o r   s p ec if ic  lea r n in g   alg o r it h m       No w   t h at  w e   h a v p r ese n ted   cr o s s   v alid atio n ,   let  u s   lo o k   f o r w ar d   m o d el  s elec tio n ,   t h at  u s ed   i n   t h i s   p ap er   to   tu n p ar am eter s   o f   g a m m an d   co s t.  Fo r     d if f er e n co m b i n atio n s   o f   co s a n d   g a m m a,   let s   n o te  a   co u p le  ( ,  )   w ith   1   an d   1 .   A s   m e n t io n ed   in   t h F ig u r e   3 ,   cr o s s   v alid atio n   is   ex ec u ted   m u lt ip le  ti m es  w it h   d if f er en p ar a m eter   co n f ig u r atio n .   As  r esu lt,  w g et  er r o r s    1 , 1   to    , .   I n   th e n d ,   w h av t h co n f i g u r atio n   t h at  h a v t h lo w er   er r o r .           Fig u r 1 .   C r o s s   v alid atio n   f o r   m o d el  s elec tio n       3.   RE S E ARCH   M E T H O D   I n   th is   s ec t io n ,   w o u tlin t h e   m et h o d o lo g y ,   s tep   b y   s tep ,   o f   lear n i n g   t h n o d s elec tio n   s tr ateg y   NS   an d   v ar iab le  b r an ch i n g   s tr ate g y   VB  u s i n g   p ar a m ete r   tu n i n g T h en ,   w p r esen t th e x p er i m en t c o n f i g u r atio n .     3 . 1 .   Co llect ing   D a t a s et s   W u s th MI P L I B 2 0 1 0   lib r ar y   a s   i n s ta n ce s   to   w h ic h   w ap p ly   t h B r an c h - a n d - B o u n d   alg o r ith m   f ea t u r ed   b y   r eliab ilit y   b r an c h i n g   r u le  a n d   b est e s ti m ate  s elec tio n   r u le.   T h e n   w e x tr a ct  i n f o r m atio n   o f   f ea t u r es   d escr ib ed   b ef o r e.   No te  th at   th b est es ti m ate  s elec tio n   r u le   i s   t h d ef a u lt   o n e   is   v ar io u s   o p t i m izatio n   to o ls   li k e   SC I P .   Her is   th p s eu d o - co d e   o f   th d ata  co llectio n   s tep   as  s h o w n   i n   A l g o r ith m   2 .       Fo r   I   in s tan c in   M I P L I B 2 0 1 0   So lv I   b y   b r an ch - an d - b o u n d   r u le d   b y   r elia b i lity   b r an ch in g   an d   n o d est im ate  s ele cti o n   r u le  an d   co l le ct  f e atu r e   v alu es .   R etu r n   th lis t   o f   f ea tu r es   v alu es     A l g o r ith m   2 .   Data   C o llectio n   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A d a p ted   b r a n ch - a n d - b o u n d   a l g o r ith u s in g   S V M w ith   mo d e l selec tio n   ( K a b b a j Mo h a med   Mu s ta p h a )   2487   3 . 2 .   L ea rning   NS a nd   VB   First,  w d iv id co lle cted   d ata  in to   t w o   s ets,  o n u s ed   f o r   tr ain i n g   a n d   v alid atio n   an d   th o th er   f o r   test .   B y   ap p l y in g   t w ice  cr o s s   v alid atio n   b ased   m o d el   s elec tio n   d escr ip ted   ab o v e,   w f ir s tl y   lear n   t h s co r e   f u n ctio n   o f   e v er y   n o d in   t h e   n o d es  q u eu e.   So   th n o d h a v in g   t h b e s s co r  (  )   w i ll  b ch o s en   in   b r an ch - a n d - b o u n d .   Seco n d l y ,   w w i ll lea r n   t h s co r f u n ct io n   VB   o f   v ar iab le  b r an ch in g   s el ec tio n .     3 . 3 .   E x peri m e nts   I n   t h is   s u b - s ec tio n ,   w e   p r ese n t h lab - tes u s ed   to   e x p er im en o u r   m et h o d o lo g y   an d   w e   g i v t h e   p s eu d o - co d es u s ed   f o r   test s .     3 . 3 . 1 .   E x peri m e nta t io n c o nfig ura t i o n   W u s ed   SC I P   3 . 2 . 1   f o r   th r a is o n   t h at  is   t h b est  in   o p en - s o u r ce   an d   f r ee   to o ls   [ 2 3 ] .   Mo r eo v er ,   f o r   SVM  alg o r it h m   a n d   m o d el  s elec tio n ,   w u s ed   th p ac k a g e1 0 7 1   [ 2 3 ]   o f   th lan g u ag R   3 . 2 . 5   k n o w n   to   b a m o n g   th m o s t p er f o r m an t la n g u a g es i n   i m p le m e n tatio n   o f   SVM  alg o r it h m s   [ 1 3 ] .       T h co s r an g u s ed   is   { 10 4 , 10 3 , , 10 5 }   an d   t h g a m m a   r an g is   { 2 8 , 2 7 , , 2 1 } .   T h ese  r an g es  co v er   to o   s m all  a n d   to o   h ig h   v alu e s   o f   co s an d   g a m m a.   T h OS  u s ed   is   Deb ian   7   3 2   b its ,   8   Go   R A M,   I n tel  2 . 4 0   GHz   P r o ce s s o r .   W u s f o r   MI L P   i n s ta n ce s   t h b e n ch m ar k   s e t o f   MI P L I B 2 0 1 0   [ 2 8 ]   to   co llect  d ata,   v alid   it,   an d   to   tes r es u lti n g   m o d els.   F o r   tr ain in g   a n d   v a lid atio n   s et,   w e   to o k   t h e   f o ll o w i n g   i n s ta n ce s   as   s h o w n   in   F ig u r 4 .       3 0 n 2 0 b 8 . m p s       a cc - tig h t5 . mp s       a flo w 4 0 b . mp s       a ir 0 4 . mp s   a p p 1 - 2 . mp s       a s h 6 0 8 g p ia - 3 co l. mp s         b a b 5 . mp s       b ea s leyC3 . mp s       b iella 1 . mp s       b ien s t2 . mp s       b in ka r 1 0 _ 1 . mp s       b ley _ xl1 . mp s       b n a tt3 5 0 . mp s   co r e2 5 3 6 - 6 9 1 . mp s   co v 1 0 7 5 . mp s       csch ed 0 1 0 . m p s     d a n o in t.m p s       d f n - g w in - UUM. mp s       eil3 3 - 2 . m p s       eilB 1 0 1 . mp s       en lig h t1 3 . m p s       en lig h t1 4 . mp s       ex 9 . mp s       g la s s 4 . mp s       g mu - 35 - 4 0 . mp s       iis - bupa - co v. mp s       i is - p ima - co v. mp s   lectsch ed - 4 - o b j.m p s   m1 0 0 n 5 0 0 k4 r 1 . mp s       ma cro p h a g e. m p s       mcsch ed . m p s       mik - 250 - 1 - 1 0 0 - 1 . mp s min e - 166 - 5 . mp s       min e - 90 - 1 0 . mp s       n 3 d iv3 6 . mp s       n 4 - 3 . mp s       n e o s - 1 1 0 9 8 2 4 . mp s       n e o s - 1 3 3 7 3 0 7 . m p s       n eo s - 1 3 9 6 1 2 5 . mp s   n eo s 1 3 . mp s   n eo s - 1 6 0 1 9 3 6 . mp s     n eo s 1 8 . mp s       n eo s - 6 8 6 1 9 0 . m p s     n eo s - 8 4 9 7 0 2 . mp s       n eo s - 9 1 6 7 9 2 . mp s       n eo s - 9 3 4 2 7 8 . mp s       n et1 2 . m p s     Fig u r 4 .   T r ain in g   an d   v a lid ati o n   s ets          T h ese  in s tan ce s   ab o u t   ten s   o f   t h o u s an d s   o f   r o w s   a n d   co lu m n s .   T h e   to tal  d escr ip tio n   i s   av a ilab le   in   [ 28] .   C o n ce r n i n g   t h v al id atio n   s et,   i co n tai n s   ap p r o x im ati v el y   f if th   o f   n u m b er   o f   m en tio n ed   i n s ta n ce s   ab o v [ 7 ] .   Fin all y ,   th n o d li m it  is   f i x ed   to   f iv h u n d r ed   n o d es  an d   r u n n in g   ti m e   li m it  is   f i x ed   to   s ix - h u n d r ed   s ec o n d s .         3 . 3 . 2 .   P s eudo - co des   I n   t h s o lv i n g   p r o ce s s ,   th e   al g o r ith m   a s   i i s   i m p le m en ted   in   S C I P   is   e x ec u ti n g   n u m er o u s   e v e n t   co d es  r elate d   to   s o m e v en ts .   Nex t,  w w il d escr ib th ese  e v en t s ,   an d   g i v th p s e u d o - co d r elativ to   ea ch   o n e.   B esid es,  m ai n   ev e n ts   m o d if ied   ar r esp ec tiv el y :     3 . 3 . 3 .   No de  s elec t io n e v ent   T h is   ev e n o cc u r s   w h e n   t h al g o r ith m   i s   i n   t h p h ase   o f   s ele ctin g   t h n ex n o d to   s o lv e.   T h cr iter i a   o f   s elec tio n   is   d eter m i n ed   b y   th s tr ateg y   i m p le m e n ted .   No te  th at  th is   e v en co d is   also   ex ec u ted   ev e n   in   t h e   r o o n o d s elec tio n .   I n   th is   ev en t,  w i m p le m e n t h n o d s elec tio n   r u le  s co r f u n ct io n   NS   th at  is   alr ea d y   estab lis h ed .   Mo r eo v er ,   it   ca lcu lates  t h s co r f o r   ea ch   n o d e   in   th n o d lis t.  Fin all y ,   it  r etu r n s   th n o d w it h   th m a x i m u m   s co r e.   T h p s eu d o - co d is   th e   Alg o r it h m   3 .         Fo r   e ac h   le a p   n     C alcu la t NS ( n )   R etu r n   th lea p   w ith   m ax i m u m   NS ( n )     A l g o r ith m   3 .   No d s elec tio n   e v en t p s e u d o - co d e         Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 A u g u s t 2 0 1 9   :   2 4 8 1   -   2490   2488   3 . 3 . 4 .   Va ria ble bra nchin g   ev ent   T h is   ev e n o cc u r s   w h e n   t h a lg o r ith m   i s   i n   t h p h a s o f   s elec tin g   b r an c h i n g   v ar iab le   o f   n o d e   alr ea d y   s o lv ed   a n d   h ad   g a v n o n - i n te g r al  v al u e.   I n   t h is   ev en t,  w i m p le m e n th v ar i ab le  s elec tio n   r u le   s co r f u n ctio n   VB .   T h in p u o f   th i s   f u n ctio n   is   t h v a lu e s   o f   th n o d e - b ased   f ea tu r es  a n d   th v ar iab le - b ased   f ea t u r es.  T h n o d e - b ased   f ea t u r es  ar r elate d   to   f ix ed   n o d an d   th e y   ar ca lc u lated   f o r   t h cu r r en n o d as  f ir s t   s tep .   B esid es,  w e   ca lcu l ate,   th v al u o f   N S   o n   t h c u r r en n o d e.   T h en   w ca lc u la te  th v al u es   o f   th e   v ar iab le - b ased   f ea t u r es  a n d   co n s eq u e n tl y   t h v a lu o f   VB  f o r   ea ch   v ar iab le.   I n   t h o u tp u t ,   w w i ll  r et u r n   t h e   v ar iab le  w i th   t h m a x i m u m   s co r VB.  Fin all y ,   w b r an c h   o n   th s elec ted   v ar iab le  a n d   cr ea ted   t w o   r elate d   ch ild r en   n o d es.  T h p s eu d o - co d is   as  Alg o r it h m   4 .       C alcu la te   th e   v alu e   o f   th e   n o d e - b ase d   f ea tu r es         C al cu lat th v alu e   o f   NS   r el ativ e   t o   th p r es en t n o d e.         F o r   e ac h   b r an ch in g   v ar ia b le   ca n d id ate           C alcu la te   v alu es   o f   v a r ia b l e - b a s ed   f ea tu r es     C alcu la te   VB   in   t er m s   o f   ca l cu late d   f ea tu r es .         R etu r n   th e   m ax   o f   VB   an d   r e lativ e   v a r ia b le         C r ea t tw o   ch il d r en   n o d es  r e ly in g   u p o n   th e   ch o s en   v ar ia b l e       C alcu lat p o s s ib le  n o d e - b as ed   f ea tu r es  v al u es o f   t h t w o   c h ild r en     A l g o r ith m   4 .   Var iab le  b r an ch i n g   e v en t p s eu d o - co d e       3 . 3 . 5 .   No de  So lv ed  ev ent   T h is   ev e n o cc u r s   w h e n   t h a lg o r ith m   i s   t h s tate   o f   lea v i n g   t h n o d alr ea d y   s o l v ed .   W u s t h i s   ev en to   ca lc u late  th v alu e s   o f   L P   Ob j ec tiv Valu o f   th e   cu r r en n o d e,   an d   th r ed u ce d   o b j ec tiv v alu es   g ain .   T h p s eu d o - co d is   t h A l g o r ith m   5 .       Get   th e   L P O b j e ctiv e   V alu e   o f   th e   p r es en t n o d e .   C alcu la te   th e   r e d u ce d   o b ject iv v alu es g a in     A l g o r ith m   5 .   No d s o lv ed   ev e n t p s eu d o - co de         4.   RE SU L T S   W p r esen in   th is   s ec tio n ,   a   co m p ar is o n   b et w ee n   alg o r it h m s   r esu lted   f r o m   o u r   ap p r o ac h es  an d   s tan d ar d   b r an c h - a n d - b o u n d   al g o r ith m .   T h co m p ar i s o n   is   d o n i n   ter m   o f   R u n n in g   Time Du a B o u n d   an d   N u mb er  o S o lved   n o d es.  T h d u al  b o u n d   b ein g   q u an t it y   co n v er g i n g   to   t h o p ti m al  s o lu tio n   if   i ex i s ts .   T h g r ea ter   v alu o f   d u a l b o u n d   is   th b est o n e.     T o   g et  to   t h is   co m p ar is o n ,   w e   d id   th r ee   d if f er en t   s o l v i n g   co n f ig u r atio n s   o n   te s s et.   T h f i r s is   d o n e   b y   s tan d ar d   b r an ch - a n d - b o u n d   ( SB B )   alg o r ith m   r u led   b y   r eliab ilit y   p s e u d o - co s b r an c h in g   r u le  an d   b est  esti m ate  n o d s elec tio n   r u le.   T h en   f o r   th s ec o n d   an d   th ir d ,   w u s ed   o u r   alg o r ith m s   w it h   SVR   w it h o u m o d el   s elec tio n   ( A B B )   an d   w it h   m o d el  s elec tio n   ( A B B +M S).   T h e   r esu lt s   ar d etailed   in   th T ab le   1 .       T ab le  1 .   R esu lts   o f   ex p er i m e n tatio n       Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2 0 8 8 - 8708       A d a p ted   b r a n ch - a n d - b o u n d   a l g o r ith u s in g   S V M w ith   mo d e l selec tio n   ( K a b b a j Mo h a med   Mu s ta p h a )   2489   I n   t h is   test ,   w h ad   ten   i n s ta n ce s   f r o m   MI P L I B 2 0 1 0 .   T h ese  i n s ta n ce s   h a v t h r ee   d i f f er en t y p es.   T h f ir s o n is   m ix ed   in teg er   p r o g r am   ( MI P )   th at  r eg r o u p s   in teg er   an d   co n ti n u o u s   v ar ia b les.  T h e   s ec o n d   is   m i x ed   b in ar y   p r o g r a m   ( MB P ) ,   w h ich   in cl u d es  b o t h   co n ti n u o u s   an d   b i n ar y   v ar iab les.  An d   th f i n al  o n is   B in ar y   p r o g r a m   ( B P )   th at  co n tain s   e x cl u s i v el y   b i n ar y   v ar iab l es.   T h ese  r esu lt s   s h o w   u p   t h at  o u r   ap p r o ac h es  g i v eq u i v alen if   n o b etter   d u a b o u n d   co m p ar i n g   to   s tan d ar d   b r an ch - a n d - b o u n d   i n   ter m   o f   d u a b o u n d   in   8 0 o f   ca s e s   e x ce p f r o m   o p m 2 - z7 - s 2   an d   r a n 1 6 x 1 6   in s ta n ce s .   An o t h er   i m p o r tan t   r esu lt,  i s   th a o u r   last   ap p r o ac h   g i v es  eq u iv ale n o r   b etter   r u n n i n g   t i m e   co m p ar i n g   o u r   last   ap p r o ac h   in   8 0 o f   ca s es.  A l s o ,   w h e n   co m p ar i n g   it  to   t h s ta n d ar d   b r an ch   an d   b o u n d   alg o r ith m   r u led   b y   r eliab ilit y   b r an ch i n g   a n d   n o d b est  es i m ate  r u le,   o u r   ap p r o ac h   g i v es  b etter   o r   eq u iv ale n t   r esu lt i n   ab o u t h al f   o f   to tal  i n s tan ce s .     W n o ticed   th at   th er i s   a n   e m p ir ical  r elatio n   b et w ee n   th e   p er f o r m a n ce   o f   d u al   b o u n d   a n d   th n u m b er   o f   co n s tr ain ts   o f   th p r o b le m   f r o m   t h o n h an d ,   an d   r elatio n   b et w ee n   th p er f o r m a n ce   o f   r u n n i n g   ti m an d   th n u m b er   o f   v ar iab les  f r o m   t h o th er   h a n d .   T o   c o n cr etize   th ese  las t p o in ts ,   w p lo t t h e s in   Fi g u r 5 .             Fig u r 5 .   I n cr ea s o r   d ec r ea s o f   d u al  b o u n d   an d   r u n n i n g   ti m r esp ec tiv el y       T h lef t - h a n d   f i g u r s h o w s   t h at  in s ta n ce s   w it h   less   t h at  5 0 0 0   co n s tr ain ts   g av b etter   d u a b o u d   f o r   o u r   ap p r o ac h es c o m p ar in g   to   s tan d ar d   b r an ch   an d   b o u n d .   As a  m atter   o f   f ac t,  t h o p m 2 - z7 - s 2   i n s tan ce ,   w h ic h   is   r ep r esen ted   b y   t h is o lated   p o in in   th d o w n - r ig n s id h as  ap p r o x im a tiv e l y   3 1 0 0 0   v ar iab les.   C o n ce r n i n g   th r ig h t - h an d   f i g u r e,   it  s h o ws  th at  in s tan ce s   w it h   m o r th an   2 5 0 0   v ar iab les,  in cr ea s ed   th p er f o r m a n ce   o f   r u n n i n g   ti m e,   w h en   r eso l v ed   b y   o u r   ap p r o ac h es,  esp ec iall y   f o r   n s 1 2 0 8 4 0 0 ,   n s 1 6 8 8 3 4 7   an d   r ail5 0 7   in s tan ce s .       5.   C O NCLU SI O N     I n   th i s   p ap er ,   w ad d   p ar a m et er   tu n i n g   to   in f er   b etter   co n f i g u r atio n   o f   SVM.   Sa y in g   t h i s ,   w u s ed   SVM  r eg r ess io n   lear n in g   alg o r ith m   k n o w n   f o r   h is   h i g h   a cc u r ac y   to   lear n   b r an ch - a n d - b o u n d   alg o r ith m   n o d s elec tio n   a n d   v ar iab le s   b r an ch i n g   s tr ate g ies.  T h ese  c h o ices  lead   to   b etter   r esu lt s   co m p ar in g   to   r eliab ilit y   p s eu d o   co s r u le  an d   b e s es ti m ate   s elec tio n   r u le,   w h ich   ar k n o w n   t o   b f r o m   th e   b est  i n   liter at u r e.   I n   p er s p ec tiv es,  w w il w o r k   o n   eli m in a tin g   n o i s in   d ata,   co m p ar w it h   d if f er en lear n in g   alg o r ith m s   a v ailab l e   in   liter at u r e.       RE F E R E NC E S     [1 ]   He   H . e a l . ,   L e a rn in g   to   se a r c h   in   b ra n c h   a n d   b o u n d   a lg o rit h m s , ”  Ad v a n c e in   n e u ra in f o rm a ti o n   p ro c e ss in g   sy ste ms ,   p p .   3 2 9 3 - 3 3 0 1 2 0 1 4 .   [2 ]   M o ll   R . e a l . ,   L e a rn in g   in sta n c e - in d e p e n d e n v a lu e   f u n c ti o n s   to   e n h a n c e   lo c a se a rc h , ”  Ad v a n c e in   Ne u ra l   In fo rm a t io n   Pro c e ss in g   S y ste ms ,   p p .   1 0 1 7 - 1 0 2 3 1 9 9 9   [3 ]   Ka rz a n   F K . e a l . ,   In f o r m a ti o n - b a se d   b ra n c h i n g   sc h e m e s   f o b in a ry   li n e a m ix e d   in teg e p ro b lem s ,   M a th e ma ti c a l   Pro g ra mm in g   Co m p u t a ti o n ,   v o l/ issu e 1 (4 ) ,   p p .   2 4 9 - 93 2 0 0 9   [4 ]   Da v e y   B . e a l . ,   Eff icie n in telli g e n b a c k trac k in g   u sin g   li n e a p r o g ra m m in g ,   INFORM S   J o u rn a o n   C o mp u ti n g ,   vo l/ issu e 1 4 (4 ) ,   p p .   3 7 3 - 86 2 0 0 2   [5 ]   Ch e n   D S . e a l . ,   A p p li e d   i n teg e p ro g ra m m in g m o d e li n g   a n d   so lu ti o n ,   Jo h n   W il e y   &   S o n s ,   2 0 1 1 .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   4 A u g u s t 2 0 1 9   :   2 4 8 1   -   2490   2490   [6 ]   A c h terb e rg   T . e a l . ,   Bra n c h in g   ru les   re v isit e d ,   Op e ra ti o n s R e se a rc h   L e tt e rs ,   v o l/ iss u e 3 3 (1 ) ,   p p .   42 - 54 2 0 0 5 .   [7 ]   A b u - Mo sta f a   Y S . e a l . ,   L e a rn in g   f ro m   d a ta ,   Ne w   Yo rk ,   NY ,   USA ,   A M L Bo o k ,   2 0 1 2   [8 ]   C .   Ru d in ,   P re d icti o n M a c h in e   L e a rn in g   a n d   S tatisti c s ,”   2 0 1 2 .   [9 ]   X .   W u ,   e a l . ,   T o p   1 0   a lg o rit h m in   d a ta  m in in g ,”   K n o wled g e   a n d   in fo rm a t io n   sy ste ms ,   v o l / i ssu e :   14 ( 1 ),   p p .   1 - 37 2 0 0 8 .   [1 0 ]   B.   L a n tz,  M a c h in e   lea rn i n g   w it h   R ,”   P a c k P u b l ish i n g   L td ,   2 0 1 5 .   [1 1 ]   A l v a re z   A M . e a l . ,   A   m a c h in e   lea rn in g - b a se d   a p p r o x im a ti o n   o f   stro n g   b ra n c h i n g ,   INFOR M S   J o u rn a o n   Co mp u t in g ,   v o l/ issu e 2 9 (1 ) ,   p p .   185 - 95 2 0 1 7   [1 2 ]   A o u n   O . e a l . ,   In v e stig a ti o n   o f   h id d e n   m a rk o v   m o d e f o th e   tu n in g   o f   m e tah e u risti c in   a irl in e   sc h e d u li n g   p ro b lem s ,   IFA C - Pa p e rs On L in e ,   v o l/ issu e 4 9 (3 ) ,   p p .   3 4 7 - 52 2 0 1 6 .   [1 3 ]   E .   Af ia  A . e a l . ,   Hid d e n   m a r k o v   m o d e c o n tro o f   in e rti a   we ig h a d a p tati o n   f o P a rti c le  sw a r m   o p ti m iza ti o n ,   IF AC - Pa p e rs On L in e ,   v o l/ issu e 5 0 (1 ) ,   p p .   9 9 9 7 - 1 0 0 0 2 2 0 1 7 .   [1 4 ]   E .   Af ia   A .   a n d   S a rh a n M . ,   P e rf o r m a n c e   p re d ictio n   u sin g   su p p o rt  v e c to m a c h in e   f o th e   c o n f ig u ra t io n   o f   o p ti m iza ti o n   a lg o rit h m s ,   Clo u d   Co mp u t in g   T e c h n o l o g ies   a n d   A p p li c a ti o n s   ( Clo u d T e c h ) ,   2 0 1 7   3 r d   In ter n a ti o n a Co n fer e n c e ,   p p .   1 - 7 ,   2 0 1 7 .   [1 5 ]   E .   Af ia  A . e a l . ,   F u z z y   lo g ic  c o n tr o ll e f o a n   a d a p t iv e   Hu a n g   c o o li n g   o f   si m u late d   a n n e a li n g , ”  Pro c e e d in g o th e   2 n d   in ter n a ti o n a Co n fer e n c e   o n   B ig   D a ta ,   Clo u d   a n d   Ap p li c a ti o n s ,   p p .   6 4 2 0 1 7 .   [1 6 ]   Bo u z b it a   S . e a l . ,   A   n o v e b a se d   Hid d e n   M a rk o v   M o d e l   a p p r o a c h   f o c o n tro l li n g   t h e   A CS - TS P   e v a p o ra ti o n   p a ra m e ter ,   M u lt ime d ia   Co m p u ti n g   a n d   S y ste ms   ( ICM CS ),   2 0 1 6   5 t h   In ter n a ti o n a C o n fer e n c e p p .   6 3 3 - 6 3 8 ,   2 0 1 6 .   [1 7 ]   L a lao u M . e a l . ,   Hid d e n   M a r k o v   M o d e f o a   se l f - le a rn in g   o S im u late d   A n n e a li n g   c o o li n g   law ,   M u lt ime d ia   Co mp u t in g   a n d   S y ste ms   ( ICM CS ) ,   2 0 1 6   5 t h   I n ter n a t io n a l   Co n fer e n c e ,   p p .   5 5 8 - 5 6 3 ,   2 0 1 6 .   [1 8 ]   L a lao u M . e t   a l . ,   A   se lf - a d a p ti v e   v e r y   fa st  si m u late d   a n n e a li n g   b a se d   o n   Hid d e n   M a rk o v   m o d e l ,   Clo u d   Co mp u t in g   T e c h n o l o g ies   a n d   A p p li c a ti o n s ( Clo u d T e c h ),   2 0 1 7   3 rd   I n ter n a ti o n a C o n fer e n c e ,   p p .   1 - 8 ,   2 0 1 7 .   [1 9 ]   E .   Af ia  A . e a l . ,   T h e   E ff e c o f   Up d a ti n g   th e   L o c a P h e ro m o n e   o n   A CS   P e rf o rm a n c e   u sin g   F u z z y   L o g i c ,   In ter n a t io n a J o u rn a o E lec trica a n d   C o mp u ter   En g in e e rin g   ( IJ ECE ) ,   v o l/ issu e 7 (4 ) ,   p p .   2 1 6 1 - 8 2 0 1 7 .   [2 0 ]   Bo u z b it a   S . e a l . ,   Dy n a m i c   a d a p tatio n   o f   th e   A CS - T S P   lo c a p h e ro m o n e   d e c a y   p a ra m e ter  b a s e d   o n   t h e   Hid d e n   M a rk o v   M o d e l ,   Clo u d   Co m p u ti n g   T e c h n o lo g ies   a n d   A p p li c a ti o n ( Clo u d T e c h ),   2 0 1 6   2 n d   In ter n a ti o n a Co n fer e n c e ,   pp .   3 4 4 - 3 4 9 ,   2 0 1 6 .   [2 1 ]   Ka b b a M M .   a n d   E .   A f ia  A . ,   T o wa rd lea rn in g   in teg ra stra teg y   o f   b ra n c h   a n d   b o u n d , ”  M u lt im e d ia   Co m p u t in g   a n d   S y ste ms   ( ICM CS ),   2 0 1 6   5 th   I n ter n a ti o n a C o n fer e n c e ,   p p .   6 2 1 - 626 ,   2 0 1 6   [2 2 ]   E .   Af ia  A .   a n d   Ka b b a M M. ,   S u p e rv ise d   lea rn in g   in   Br a n c h - a n d - c u stra teg ies ,   Pro c e e d in g o th e   2 n d   in ter n a t io n a l   Co n fer e n c e   o n   B ig   Da ta ,   C lo u d   a n d   A p p l ica ti o n s ,   p p .   1 1 4 ,   2 0 1 7 .   [2 3 ]   h tt p : // S c ip . z ib . d e   [2 4 ]   h tt p : // M i p li b . z ib . d e   [2 5 ]   Da v id   M . ,   S u p p o rt  V e c to M a c h in e s:  T h e   In ter f a c e   to   li b sv m   in   P a c k a g e   e 1 0 7 1 ,   Da v id .   M e y e r R - Pro jec t.   o rg 2 0 1 7 .       B I O G RAP H I E S   O F   AUTH O RS       M .   K a b b a j   M o h a m e d   M u sta p h a   is   a   P HD   stu d e n in   a Na ti o n a S c h o o o f   Co m p u ter S c ien c e   a n d   S y st e m A n a l y sis  (EN S I A S ),   Ra b a t,   M o ro c c o .   He   o b tain e d   M . E n g .   in   2 0 1 3   i n   Co m p u ter  S c ien c e   f ro m   N a ti o n a S c h o o o f   Co m p u ter  S c ien c e   a n d   S y ste m A n a l y sis.  Re se a r c h   a re a o in tere st  a r e   M a c h in e   L e a rn in g ,   Co m b in a to rial   Op ti m iza ti o n ,   S t o c h a stic  P r o g ra m m in g   a n d   F e a tu re   S e lec ti o n .         Abd e ll a tif  El  Afia   is  a n   A ss o c iat e   P r o f e ss o a Na ti o n a S c h o o o f   Co m p u ter  S c ien c e   a n d   S y ste m s   A n a l y si (ENS IA S ),   Ra b a t,   M o r o c c o .   He   re c e iv e d   h is  M . S c .   d e g re e in   A p p li e d   M a th e m a ti c f ro m   Un iv e rsit y   o S h e rb ro o k .   He   o b ta in e d   h is  P h . D.  in   1 9 9 9   in   Op e ra ti o n   Re se a rc h   f ro m   Un iv e rsit y   o S h e rb r o o k ,   Ca n a d a .   Re se a rc h   a r e a o in tere st  a re   M a th e m a ti c a P r o g ra m m in g   (S to c h a stic  a n d   d e term in isti c ),   M e tah e u risti c s,  Re c o m m e n d a ti o n   S y ste m s a n d   M a c h in e   L e a rn in g .     Evaluation Warning : The document was created with Spire.PDF for Python.