MARC

 008260126s2025        us                              c    eng  d
■001000017360470
■00520260202105532
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798263341862
■035    ▼a(MiAaPQ)AAI32309861
■035    ▼a(MiAaPQ)GeorgiaTech77883
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a006
■1001  ▼aShah,  Prachi.
■24510▼aClosing  the  Gap:  A  Theoretical  and  Practical  Exploration  of  Branch-and-Bound  Procedure  for  Mixed-Integer  Programs
■260    ▼a[Sl]▼bGeorgia  Institute  of  Technology▼c2025
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2025
■300    ▼a131  p
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  87-06,  Section:  B.
■500    ▼aAdvisor:  Dey,  Santanu.
■5021  ▼aThesis  (Ph.D.)--Georgia  Institute  of  Technology,  2025.
■520    ▼aThe  branch-and-bound  scheme,  invented  by  Land  and  Doig,  is  the  method  of  choice  for  solving  mixed  integer  linear  programs  (MILP)  by  all  modern  state-of-the-art  MILP  solvers.  While  the  branch-and-bound  algorithm  has  been  studied  for  a  long  time,  atheoretical  understanding  of  its  performance  guarantees  is  lacking.  Furthermore,  in  practice,  its  efficiency  relies  on  the  performance  of  several  heuristics  whose  interactions  are  not  well  understood.  This  thesis  is  motivated  by  the  goal  to  improve  both  theoretical  as  well  as  practical  understanding  of  branch-and-bound  for  MILPs.  Given  that  node  selection  rules  are  well-understood,  this  thesis  focuses  primarily  on  branching  rules.Branch-and-bound  shares  similarity  with  dynamic  programming  in  the  sense  that  both  employ  recursions  to  solve  the  problem.  This  raises  the  question  of  whether  there  is  a  correspondence  between  the  two  algorithms.  Previous  works  in  literature  have  proved  branching-and-bound  with  general  disjunctions  to  be  exponentially  more  efficient  than  dynamic  programming  on  some  classes  of  problems.  However,  it  was  unclear  if  general  branch-and-bound  is  always  superior  to  dynamic  programming.  In  Chapter  2,  we  show  that  to  be  untrue.  We  consider  the  lot-sizing  problem  for  which  there  exists  a  polynomial  time  dynamic  programming  algorithm  and  prove  an  (worst  case)  exponential  lower  bound  on  the  size  of  branch-and-bound  trees  even  when  branching  is  considered  on  general  disjunctions.State-of-the-art  mixed  integer  programming  (MIP)  solvers  are  based  on  the  branch  and-cut  framework  where  cutting  planes  are  added  to  strengthen  the  linear  relaxation  before  branching  is  initiated.  This  is  done  with  the  hope  that  improved  bounds  may  lead  to  more  efficient  pruning  and  therefore  a  smaller  branch-and-bound  tree.  However,  in  practice  branching  rules  typically  use  local  node  LP  information  to  decide  on  which  variable  to  branch.  Therefore,  the  addition  of  cuts  may  also  potentially  change  the  branching  decisions  whose  impact  on  tree  size  is  difficult  to  model.  In  Chapter  3,  we  consider  the  question  of  whether  adding  cuts  will  always  lead  to  smaller  trees  for  a  given  fixed  branching  rule.  We  formally  call  such  a  property  of  a  branching  rule  monotonicity.  We  prove  that  most  of  the  standard  branching  rules  used  in  practice  are  non-monotonic.  We  also  empirically  attempt  to  estimate  the  prevalence  of  non-monotonicity  in  practice  while  using  full  strong  branching  and  discover  that  non-monotonicity  is  surprisingly  prevalent.Full  strong-branching  (henceforth  referred  to  as  strong-branching)  is  experimentally  known  to  produce  significantly  smaller  branch-and-bound  trees  in  comparison  to  all  other  known  variable  selection  rules  and  is  often  used  as  a  benchmark  to  compare  other  rules.  However,  there  is  no  objective  metric  to  evaluate  the  performance  of  strong-branching  itself.  In  Chapter  4,  we  introduce  the  notion  of  an  "optimal  branch-and-bound  tree",  that  is,  the  smallest  branch-and-bound  tree  that  solves  a  given  instance.  We  present  a  dynamic  programming  algorithm  for  generating  the  optimal  trees  and  use  it  to  evaluate  the  efficiency  of  strong-branching  on  (small)  instances  from  a  range  of  classical  problems.With  the  goal  of  bridging  the  gap  between  the  strong-branching  trees  and  optimal  trees,  we  seek  to  better  understand  the  properties  and  limitations  of  FSB  in  Chapter  5.  Strong  branching  guides  branching  decisions  based  exclusively  on  the  information  regarding  local  gains  in  the  linear  programming  (LP)  bounds,  but  we  identify  two  additional  factors  that  significantly  impact  its  tree  sizes.  We  incorporate  these  into  the  strong-branching  score  to  design  new  rules  that  demonstrate  remarkable  performance  benefits  on  benchmark  instances.
■590    ▼aSchool  code:  0078.
■650  4▼aFeature  selection
■650  4▼aInteger  programming
■650  4▼aLinear  programming
■650  4▼aDynamic  programming
■650  4▼aKnapsack  problem
■650  4▼aBranch  &  bound  algorithms
■650  4▼aIndustrial  engineering
■650  4▼aSystems  science
■653    ▼aMixed  integer  linear  programs
■653    ▼aFeature  selection
■653    ▼aInteger  programming
■690    ▼a0790
■690    ▼a0546
■71020▼aGeorgia  Institute  of  Technology.
■7730  ▼tDissertations  Abstracts  International▼g87-06B.
■790    ▼a0078
■791    ▼aPh.D.
■792    ▼a2025
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17360470▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.

Preview

Export

ChatGPT Discussion

AI Recommended Related Books