home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15016 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.9 KB
  1. Path: sparky!uunet!ogicse!mimbres.cs.unm.edu!nmt.edu!borchers
  2. From: borchers@nmt.edu (Brian Borchers)
  3. Newsgroups: sci.math
  4. Subject: Mixed Integer Linear Programming: sample problems
  5. Message-ID: <1992Nov15.015048.1742@nmt.edu>
  6. Date: 15 Nov 92 01:50:48 GMT
  7. Article-I.D.: nmt.1992Nov15.015048.1742
  8. Sender: news@nmt.edu
  9. Organization: New Mexico Tech
  10. Lines: 29
  11. Nntp-Posting-Host: titan
  12.  
  13. It's been a couple of years since I first made this request, so I thought
  14. a repost might be helpful.  
  15.  
  16. I'm looking for large zero-one mixed integer linear programming problems.  
  17. By large, I mean that the problem should have thousands of variables
  18. and at least a few hundred constraints.  I'm interested in problems
  19. with up to about 100 integer variables.  I'm also interested in applications
  20. of these problems.  So far, the problems that I have seen are mostly 
  21. facility location/fixed charged network design problems.  
  22.  
  23. Yes, I'm familiar with the MIPLIB collection.  MIPLIB contains a number
  24. of interesting problems, including mod011, rentacar, modglob, and khb05250.
  25. Some of these problems are extremely hard to solve.  Unforutnately, most 
  26. of the rest of the problems in MIPLIB are pure zero-one problems which 
  27. aren't of much interest to me.  
  28.  
  29. Why am I looking for these problems?  I'm doing research into branch
  30. and bound algorithms that use LP relaxations to obtain bounds.  For 
  31. pure IP's, there are a number of better techniques (take a look into
  32. implicit enumeration, problem reformulation, cutting planes, and
  33. rounding heuristics.)  For large mixed problems, branch and bound
  34. with LP relaxations still seems to be the way to go.  
  35.  
  36. ---------------------------------------------------------------------------
  37. Brian Borchers                                             borchers@nmt.edu
  38. Department Of Mathematics                 New Mexico, home of the green 
  39. New Mexico Tech                           chile cheeseburger.
  40. Socorro, NM 87801
  41.  
  42.