-2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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}.$$

$\endgroup$
1
  • $\begingroup$ Thanks a lot, I appreciate your time. $\endgroup$ – Ali Jan 23 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.