🚀 go-pugleaf

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