home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / numanal / 2545 < prev    next >
Encoding:
Text File  |  1992-08-25  |  1.5 KB  |  60 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!munnari.oz.au!uniwa!bilby.cs.uwa.oz.au!mardo!gordon
  3. From: gordon@cs.uwa.oz.au (Gordon Royle)
  4. Subject: Linear Programming problem - NAG routine E04MBF
  5. Message-ID: <gordon.714813945@mardo>
  6. Sender: usenet@bilby.cs.uwa.edu.au
  7. Nntp-Posting-Host: mardo
  8. Organization: Dept. Computer Science, University of Western Australia.
  9. Date: Wed, 26 Aug 1992 07:25:45 GMT
  10. Lines: 48
  11.  
  12.  
  13. I have a linear programming problem (in fact an integer programming
  14. problem, but I thought I would experiment with the relaxation first to
  15. get some feel for these things).
  16.  
  17. It is very simple:
  18.  
  19.     Minimize    Sum x_i
  20.  
  21.     subject to    0 <= x_i <= 1
  22.             Ax > j
  23.  
  24.  
  25.     where A is a symmetric matrix with all row and column sums
  26.     equal, and j is the all-ones vector.
  27.  
  28.  
  29. Thing is, the solution of this is obvious - the best thing is to put
  30.  
  31.         x_i = 1/r        where r is the row sum of A
  32.  
  33.  
  34. So, I took a 243 x 243 example of this problem and gave it to 
  35. NAG routine E04MBF.
  36.  
  37. Funny thing was though - instead of quickly giving me the obvious
  38. solution, it gave a far-from-optimal INTEGRAL feasible point and then
  39. stopped, saying that it had made too many iterations without changing
  40. the trial solution.
  41.  
  42.  
  43. Three questions:
  44.  
  45.     1. Why does it behave like this?
  46.  
  47.     2. What do I do to make it give the right answer
  48.  
  49.     and thirdly...
  50.  
  51.     3. when I get down to actually trying to solve the 
  52.     integer linear program, is there any theory around
  53.     that says that symmetric As etc are particularly hard
  54.     (or better still, particularly easy)
  55.  
  56.  
  57.     Cheers
  58.  
  59.     Gordon
  60.