Vladimir Deineko Warwick Specially structured matrices in combinatorial optimisation Identifying polynomially solvable cases of NP-hard optimisation problems is one of the well known branches in combinatorial optimisation. We consider two classical problems such as the travelling salesman problem and the quadratic assignment problem. It is known that if the underlying distance matrices have special structures then the optimal solutions to these problems can be found in polynomial time. We give a short survey of known solvable cases as well as present some new relaxations on the known structures in matrices which still keep these notoriously difficult problems manageable.