آرامش برنامه نویسی نیمه کامل برای سفارش خطی و مشکل فروشندگان مسافرتی

In this paper we strengthen the relaxation proposed by Newman (2004) [43] and conduct a polyhedral study of the corresponding polytope. Furthermore we relate the relaxation to other linear and semidefinite relaxations for the (LOP) and for the Traveling Salesman Problem and elaborate on its connection to the Max Cut problem.