MARC

 008240220s2023        ulk                      00        kor
■001000016934953
■00520240214101835
■006m          o    d                
■007cr#unu||||||||
■020    ▼a9798380142410
■035    ▼a(MiAaPQ)AAI30637183
■040    ▼aMiAaPQ▼cMiAaPQ
■0820  ▼a510
■1001  ▼aSoni,  Akhilesh.
■24510▼aDiscrete  Optimization  Methods  for  Scheduling  and  Matrix  Completion▼h[electronic  resource]
■260    ▼a[S.l.]▼bThe  University  of  Wisconsin  -  Madison.  ▼c2023
■260  1▼aAnn  Arbor▼bProQuest  Dissertations  &  Theses▼c2023
■300    ▼a1  online  resource(172  p.)
■500    ▼aSource:  Dissertations  Abstracts  International,  Volume:  85-02,  Section:  B.
■500    ▼aAdvisor:  Linderoth,  Jeffrey;Luedtke,  James.
■5021  ▼aThesis  (Ph.D.)--The  University  of  Wisconsin  -  Madison,  2023.
■506    ▼aThis  item  must  not  be  sold  to  any  third  party  vendors.
■520    ▼aThe  thesis  consists  of  research  in  mixed  integer  linear  programming  with  applications  to  scheduling  and  matrix  completion.  We  first  study  the  problem  of  scheduling  drilling  and  fracturing  of  pads  in  the  development  of  an  unconventional  oil  field.  We  propose  a  novel  MILP  formulation  for  solving  this  scheduling  problem  which  considers  capacity,  operational,  precedence,  and  interference  constraints.  We  also  propose  a  formulation  that  uses  more  decision  variables,  but  which  provides  a  stronger  linear  programming  relaxation.  Due  to  the  large  problem  size,  solving  the  full  MILP  model  for  instances  with  many  pads  and  a  large  number  of  time  periods  is  intractable.  Thus,  we  also  derive  a  MILP-based  rolling  horizon  framework  that  solves  a  sequence  of  limited  horizon,  coarser-scale  MILP  instances  in  a  rolling  forward  fashion  to  obtain  a  solution  to  the  full  horizon  problem  on  the  daily  time  scale.  We  benchmark  this  approach  against  a  baseline  scheduling  algorithm  that  approximates  current  practice  of  scheduling  pads  in  the  order  of  discounted  production  profit  with  limited  lookahead.  Our  results  show  that  our  proposed  MILP-based  rolling  horizon  approach  can  improve  the  net  present  value  of  a  field  by  4-6%.Next,  we  present  new  integer  programming  approaches  to  matrix  completion  problems,  both  in  the  real  field  and  in  the  finite  field  GF(2).  First,  we  study  an  integer  programming  approach  for  subspace  clustering  with  missing  data  problem  in  real  field  with  an  assumption  that  underlying  data  comes  from  a  union  of  subspaces.  Subspace  clustering  with  missing  data  is  the  task  of  identifying  clusters  of  vectors  belonging  to  the  same  subspace  in  a  partially  observed  data  matrix  whose  columns  are  assumed  to  lie  in  a  union  of  K  subspaces.  We  propose  a  novel  mixed-integer  linear  programming  solution  framework  (MISS-DSG)  for  this  problem  that  is  based  on  dynamically  determining  a  set  of  candidate  subspaces  and  optimally  assigning  data  points  to  the  closest  selected  subspace.  MISS-DSG  handles  a  large  number  of  candidate  subspaces  through  its  use  of  Benders  decomposition  and  dynamically  generates  new  candidate  subspaces  through  its  use  of  column  generation.  We  cast  the  subspace  generation  problem  as  a  nonlinear,  nonconvex  optimization  problem  and  propose  a  gradient-based  approximate  solution  approach.  The  model  has  the  advantage  of  integrating  the  subspace  generation  and  clustering  in  a  single,  unified  optimization  framework  without  requiring  any  hyperparameter  tuning  when  number  of  subspaces  and  subspaces  dimensions  are  known.  Our  computational  results  reveal  that  the  proposed  method  can  achieve  higher  clustering  accuracy  than  state-of-the-art  methods  when  data  is  of  high-rank,  the  percentage  of  missing  data  is  high,  or  subspaces  are  close  to  each  other.We  next  discuss  binary  matrix  completion  methods  in  GF(2)  where  the  arithmetic  is  done  with  respect  to  modulo-2  operations.  We  give  integer  linear  programming  formulations  for  matrix  factorization  and  completion  in  GF(2).  We  first  derive  formulations  making  use  of  McCormick  envelopes  for  the  product  of  two  binary  variables:  a  base  formulation  using  a  general  integer  variable  and  an  extended  formulation  using  ideas  from  disjunctive  programming  and  parity  polytopes.  The  latter  formulation  characterizes  the  convex  hull  of  the  dot  product  of  two  vectors  in  an  extended  space.  We  then  derive  a  novel  formulation  based  on  a  new  class  of  valid  inequalities  that  also  characterizes  the  convex  hull  of  the  dot  product  in  the  original  space  of  variables.  Our  computational  results  reveal  that  the  proposed  formulation  results  in  smaller  branch-and-bound  trees.  Furthermore,  we  also  derive  additional  classes  of  valid  inequalities  linking  dot  products  between  two  matrix  elements.
■590    ▼aSchool  code:  0262.
■650  4▼aMathematics.
■650  4▼aComputer  science.
■653    ▼aBenders  decomposition
■653    ▼aColumn  generation
■653    ▼aInteger  programming
■653    ▼aMatrix  completion
■653    ▼aScheduling
■653    ▼aValid  inequalities
■690    ▼a0796
■690    ▼a0984
■690    ▼a0405
■71020▼aThe  University  of  Wisconsin  -  Madison▼bIndustrial  Engineering.
■7730  ▼tDissertations  Abstracts  International▼g85-02B.
■773    ▼tDissertation  Abstract  International
■790    ▼a0262
■791    ▼aPh.D.
■792    ▼a2023
■793    ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16934953▼nKERIS▼z이  자료의  원문은  한국교육학술정보원에서  제공합니다.
■980    ▼a202402▼f2024

미리보기

내보내기

chatGPT토론

Ai 추천 관련 도서