1
$\begingroup$

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

I saw this Gurobi post that uses Integer Linear Programming to solve the traveling salesman problem.

I compared its runtime with a Backtracking algorithm written in python, and the Integer Linear Program seems to be faster?

Is the Integer Linear Program faster because Gurobi is implemented in C++ or is it faster because it uses heuristics, pruning and other optimizations to improve its runtime?

$\endgroup$
2
$\begingroup$

Integer linear programming can potentially be more efficient. ILP solvers normally combine backtracking with many other methods, so for many problems ILP might be faster than backtracking alone. There are no hard-and-fast rules about which will do better on every problem, though. It's not just implementation in C++.

$\endgroup$

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.