Traveling Salesman Problem

In the Premium Solver Platform, you can model problems that involve ordering or permutations of choices easily with an "alldifferent" constraint, which specifies that a set of variables should have integer values from 1 to N, all of them different at the solution.

pspalldiff.jpg (8852 bytes)

Add Constraint dialog
with "dif" selected to specify
an alldifferent constraint.

Problems involving ordering or permutations of choices are very difficult to model using conventional constraints, even with integer variables. An example is the famous Traveling Salesman Problem (TSP), where a salesman must choose the order of cities to visit so as to minimize travel time, and each city must be visited exactly once. In the Premium Solver Platform, you can model this kind of problem easily with an "alldifferent" constraint.  (Click on the worksheet below to see it full size.)

Traveling Salesman Problem (43683 bytes)

All Solver engines in the Premium Solver Platform supports this new type of constraint.  The Branch & Bound process used by the LP/Quadratic and GRG nonlinear Solvers is extended to handle "alldifferent" constraints as a native type, and the hybrid Evolutionary / Classical Solver implements these constraints using mutation and crossover operators for permutations. 

Field-installable Solver engines also support the "alldifferent" constraint, implementing it in different ways. This allows you to model the problem in a high-level way, and try a variety of Solver engines to see which one yields the best performance on your problem.

< Back to Premium Solver Platform Product Overview