The Travelling Salesman Problem (TSP) is the problem of finding the shortest cyclic tour between a set of cities, visiting each city exactly once. This can be formulated using mixed integer programming.
When solving mixed integer optimization problems it is important to use a strong formulation of the problem, otherwise MOSEK may spend a very long time solving the optimization problem. This is not only true for MOSEK but for the branch-and-bound based solution method too.
The approach explored in this section is an implementation of the approach discussed in the article “Teaching integer programming formulations using the Traveling Salesman Problem” by Gábor Pataki [13].
Given a set of nodes we want to find the shortest tour (a directed cycle containing all nodes) in a complete directed graph. We use the variables to indicate whether the arc (i,j) is included in the tour.
The core of the formulation is
![]() |
(13.1.1) |
These constraints are called the assignment constraints. The assignment constraints, however, do not constitute the entire formulation as groups of disjoint cycles, called subtours, as well as the complete tours are feasible.
To exclude the subtours two sets of constraints are considered.
The MTZ (Miller-Tucker-Zemlin) formulation of the TSP includes the following constraints
![]() |
(13.1.2) |
The idea of this formulation is to assign the numbers 1 through n to the nodes with the extra variables so that this numbering corresponds to the order of the nodes in the tour. It is obvious that this excludes subtours, as a subtour excluding the node 1 cannot have a feasible assignment of the corresponding
variables.
An alternative approach is simply to take any potential subtour, i.e. any true subset of nodes, and declare that it is illegal.
![]() |
(13.1.3) |
As the subtour inequality for is a linear combination of the inequality for S and the assignment constraints, it is sufficient to use the subtour inequalities with S having size n/2 at most. Note that this formulation has the disadvantage of being exponential in size.
The MTZ formulation of the TSP is a very weak formulation so we will try to strengthen it by adding some of the subtour constraints from the stronger subtour formulation and then compare the solution times. For each problem we will try to identify some of the most relevant subtour constraints by solving the relaxed IP without the MTZ constraints and then choosing some of the violated subtour inequalities, corresponding to the subtours in the solution. The complete algorithm in pseudo-code is (the complete C implementation is included below in Section 13.1.3):
for k=1 to
Each round we add 1000 constraints at most as the number of violated subtour inequalities is exponential in r.
Setting equal to 0, 1, and 2, we obtain three formulations of increasing strength which we solve in 3.
We have tested this method on six TSP instances from the TSPLIB library which can be found at
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
The time and number of B&B nodes for each of the three formulations are recorded in Table 13.1. The entry “***” means that the problem was unsolvable within a time window of 5000 seconds. The time spent solving the relaxed IPs and identifying subtour constraints was negligible.
|
Not surprisingly a stronger formulation means shorter solution time (with a few exceptions where the second round of strengthening seemingly is superfluous), but it is worth noting the magnitude of the decrease in solution time arising from stronger formulations.
Therefore, it is often worthwhile to consider whether one can strengthen a given formulation when solving a mixed integer optimization problem.
The following example is included in the distribution in the file msktsp.c.
A geometric optimization problem can be stated as follows
![]() |
(13.2.1) |
where it is assumed that
![]() |
and if , then
![]() |
Hence, A is a matrix and c is a vector of length T. Given
then
![]() |
is called a monomial . A sum of monomials i.e.
![]() |
is called a posynomial . In general, the problem (13.2.1) is very hard to solve. However, the posynomial case where it is required that
![]() |
is relatively easy. The reason is that using a simple variable transformation a convex optimization problem can be obtained. Indeed using the variable transformation
![]() |
(13.2.2) |
we obtain the problem
![]() |
(13.2.3) |
which is a convex optimization problem that can be solved using MOSEK. We will call
![]() |
a term and hence the number of terms is T.
As stated, the problem (13.2.3) is non-separable. However, using
![]() |
we obtain the separable problem
![]() |
(13.2.4) |
which is a separable convex optimization problem.
A warning about this approach is that the exponential function is only numerically well-defined for values of x in a small interval around 0 since
grows very rapidly as x becomes larger. Therefore numerical problems may arise when solving the problem on this form.
A large number of practical applications, particularly in electrical circuit design, can be cast as a geometric optimization problem. We will not review these applications here but rather refer the reader to [14] and the references therein.
A lot of tricks that can be used for modeling posynomial optimization problems are described in [14]. Therefore, in this section we cover only one important case.
In general, equalities are not allowed in (13.2.1), i.e.
![]() |
is not allowed. However, a monomial equality is not a problem. Indeed consider the example
![]() |
of a monomial equality. The equality is identical to
![]() |
which in turn is identical to the two inequalities
![]() |
Hence, it is possible to model a monomial equality using two inequalities.
Certain formulations of geometric optimization problems may cause problems for the algorithms implemented in MOSEK. Basically there are two kinds of problems that may occur:
The following problem illustrates an unattainable solution:
![]() |
Clearly, the optimal objective value is 0 but because of the constraint the x,y>0 constraint this value can never be attained: To see why this is a problem, remember that MOSEK substitutes and
and solves the problem as
![]() |
The optimal solution implies that or
, and thus it is unattainable.
Now, the issue should be clear: If a variable x appears only with nonnegative exponents, then fixing x=0 will minimize all terms in which it appears — but such a solution cannot be attained.
A similar problem will occur if a finite optimal objective value requires a variable to be infinite. This can be illustrated by the following example:
![]() |
which is a valid geometric programming problem. In this case the optimal objective is 0, but this requires x=∞, which is unattainable.
Again, this specific case will appear if a variable x appears only with negative exponents in the problem, implying that each term in which it appears can be minimized for .
Consider the example
![]() |
which is not a geometric optimization problem. However, using the obvious transformations we obtain the problem
![]() |
(13.2.5) |
which is a geometric optimization problem.
MOSEK provides the command line tool mskexpopt to solve a problem on the form (13.2.4). As demonstrated previously an optimal solution to this problem can be transformed into an optimal solution to the geometric optimization problem (13.2.1) by using the transform:
![]() |
A more detailed description of mskexpopt and the definition of the input format used is found in Section 6.2. The source code is also included in the MOSEK distribution.
The problem (13.2.5) can be written in the mskexpopt format as follows:
5 * numcon 3 * numvar 7 * numter * Coefficients of terms 1 1 3 1 1 0.1 0.333333 * Constraints each term belong to 0 1 1 2 3 4 5 * Section defining a_kj. * Format: term var coef 0 0 -1 0 1 1 1 0 2 1 1 -0.5 2 1 0.5 2 2 -1 3 0 1 3 1 -1 3 2 -2 4 0 -1 4 1 1 4 2 2 5 0 -1 6 0 1
The command line:
mskexpopt go1.eo
solves the problem and writes the solution file:
PROBLEM STATUS : PRIMAL_AND_DUAL_FEASIBLE SOLUTION STATUS : OPTIMAL OBJECTIVE : 1.001904e-03 PRIMAL VARIABLES INDEX ACTIVITY 1 -2.302585e+00 2 -9.208438e+00 3 3.452927e+00 DUAL VARIABLES INDEX ACTIVITY 1 1.000000e+00 2 2.003813e+00 3 1.906415e-03 4 5.272269e+00 5 5.273223e+00 6 3.006672e+00 7 8.758884e-12
The primal solution can be transformed into a solution to the geometric optimization problem as follows
![]() |
(13.2.6) |
![]() |
(13.2.7) |
![]() |
(13.2.8) |
More information about geometric optimization problems is located in [18, 24, 14].