Thread View: sci.math.num-analysis
2 messages
2 total messages
Started by Gordon Royle
Wed, 26 Aug 1992 07:25
Linear Programming problem - NAG routine E04MBF
Author: Gordon Royle
Date: Wed, 26 Aug 1992 07:25
Date: Wed, 26 Aug 1992 07:25
48 lines
1597 bytes
1597 bytes
I have a linear programming problem (in fact an integer programming
problem, but I thought I would experiment with the relaxation first to
get some feel for these things).
It is very simple:
Minimize Sum x_i
subject to 0 <= x_i <= 1
Ax > j
where A is a symmetric matrix with all row and column sums
equal, and j is the all-ones vector.
Thing is, the solution of this is obvious - the best thing is to put
x_i = 1/r where r is the row sum of A
So, I took a 243 x 243 example of this problem and gave it to
NAG routine E04MBF.
Funny thing was though - instead of quickly giving me the obvious
solution, it gave a far-from-optimal INTEGRAL feasible point and then
stopped, saying that it had made too many iterations without changing
the trial solution.
Three questions:
1. Why does it behave like this?
2. What do I do to make it give the right answer
and thirdly...
3. when I get down to actually trying to solve the
integer linear program, is there any theory around
that says that symmetric As etc are particularly hard
(or better still, particularly easy)
Cheers
Gordon
Re: Linear Programming problem - NAG routine E04MBF
Author: John Mount
Date: Wed, 26 Aug 1992 13:59
Date: Wed, 26 Aug 1992 13:59
34 lines
1546 bytes
1546 bytes
In article <gordon.714813945@mardo>, gordon@cs.uwa.oz.au (Gordon Royle) writes:
|> I have a linear programming problem (in fact an integer programming
|> problem, but I thought I would experiment with the relaxation first to
|> get some feel for these things).
|>
|> It is very simple:
|>
|> Minimize Sum x_i
|>
|> subject to 0 <= x_i <= 1
|> Ax > j
I assume you mean Ax >= j
|>
|>
|> where A is a symmetric matrix with all row and column sums
|> equal, and j is the all-ones vector.
|>
|>
|> Thing is, the solution of this is obvious - the best thing is to put
|>
|> x_i = 1/r where r is the row sum of A
I don't see where this solution is so obviously the best. For instance
what about the case where A = [ 1 -1 ] ?
[ -1 1 ]
--
--- It is kind of strange being in CS theory, given computers really do exist.
John Mount: jmount+@cs.cmu.edu (412)268-6247
School of Computer Science, Carnegie Mellon University,
5000 Forbes Ave., Pittsburgh PA 15213-3891
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads