how to linearize the full model for TSP quadratic formulation?

Question

I tried to solve this problem but I failed, please how to linearized full model.

Answer 1

You can linearize a product of binary variables by introducing a new nonnegative variable and linear constraints, as shown here. In the present case, you can exploit the fact that the product appears only in the objective with a nonnegative objective coefficient. So only one additional linear constraint (instead of three) is needed per product: $$z_{k,i,j} \ge y_{k,i} + y_{k+1,j} - 1$$ The linearized objective function is then $$\sum_{i,j} d_{i,j} \sum_k z_{k,i,j}.$$

Because of the original equality constraints, you can reduce the linearized problem size by using a single additional variable per edge: $$z_{i,j} \ge y_{k,i} + y_{k+1,j} - 1$$ with linearized objective function $$\sum_{i,j} d_{i,j} z_{i,j}.$$