We present new valid inequalities that work in similar ways to well known cover inequalities.The differences exist in three aspects. First difference is in the generation of the inequalities. The method used in generation of the new cuts is more practical in contrast to classical cover inequalities. Second difference is the more general applicability, i.e., being useful for problems like TSP. The third aspect is superior efficiency as indicated by our preliminary experiments.
Dept. of Industrial Engineering, Bilkent University, Ankara, Turkey.(November 2006)