Problem 
ILP model 
(#variables, #constraints) 
The associated LP relaxation is 

UFLP 




Set Covering 

(n ; m) 
strong" 

Set Partitioning 

(n ; m) 
strong" 

Set Packing 

(n ; m) 
intermediate" if all constraints are associated with maximal cliques of G(A) (see Stable Set) 

CFLP 

(n + mn ; m + mn + n) 
generally \strong",even if tends tobecome \weak" if facilities are equal (see BinPacking) 

Bin Packing 




Fixed Charge 

(2n ; n) plus Ax > b 
weak" depending on M values 

Stable Set 




Vertex Coloring 




ATSP 

(n(n  1); 2n + O(2^{n})) 
strong" 

TSP 

(n(n  1)=2; n + O(2^{n})) 
strong" 