From:	Chris Beck [jcb@mie.utoronto.ca]
Sent:	08 October 2010 15:21
To:	Patrick Prosser
Subject:	LP thoughts

  Hi Patrick,

I had a closer look at all the 100 node and the 90 instances with 20-nodes 
that I've run. In every case (1140 instances), the value of the LP relaxation 
at the root node is equal to the eventual optimal solution. (Well, in some 
cases it is fractionally higher, but since the objective must be integer with 
truncation they are equal).

This makes me think that there might be something provable about the LP 
relaxation.

I've been hearing people talk about fixed-parameter tractability recently. If 
we know we are looking for independent sets of size k does the problem become 
easy? I guess not or else SMTI would be polynomial?

Chris

-- 
J. Christopher Beck				
Toronto Intelligent Decision Engineering Lab	
Mechanical&  Industrial Engineering		
University of Toronto				
5 King's College Rd
Toronto, ON CANADA M5S 3G8
ph:  (416) 946-8854
fax: (416) 978-7753