Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(14)
Burden of Proof
Combinatorial Problems
Computational Techniques
Distance Matrix
Indexation
Integer Program
Mathematical Model
Model Verification
Objective Function
Optimal Solution
Satisfiability
Traveling Salesman Problem
Travelling Salesman Problem
Linear Program
Related Publications
(3)
Nonlinear and Dynamic Programming
Improvements and...
Solution of a LargeScale TravelingSalesman Problem
Subscribe
Academic
Publications
Integer Programming Formulation of Traveling Salesman Problems
Integer Programming Formulation of Traveling Salesman Problems,10.1145/321043.321046,Journal of The ACM,C. E. Miller,A. W. Tucker,R. A. Zemlin
Edit
Integer Programming Formulation of Traveling Salesman Problems
(
Citations: 130
)
BibTex

RIS

RefWorks
Download
C. E. Miller
,
A. W. Tucker
,
R. A. Zemlin
It has been observed by many people that a striking number of quite diverse mathematical problems can be formulated as problems in integer programming, that is, linear programming problems in which some or all of the variables are required to assume integral values. This fact is rendered quite interesting by recent research on such problems, notably by R. E. Gomory [2, 3], which gives promise of yielding efficient
computational techniques
for their solution. The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the wellknown “Travelling Salesman Problem” in integer programming terms. The authors have developed several such models, of which the one presented here is the most efficient in terms of generality, number of variables, and number of constraints. This model is due to the second author [4] and was presented briefly at the Symposium on
Combinatorial Problems
held at Princeton University, April 1960, sponsored by SIAM and IBM. The problem treated is: (1) A salesman is required to visit each of n cities, indexed by 1, ··· , n. He leaves from a “base city” indexed by 0, visits each of the n other cities exactly once, and returns to city 0. During his travels he must return to 0 exactly t times, including his final return (here t may be allowed to vary), and he must visit no more than p cities in one tour. (By a tour we mean a succession of visits to cities without stopping at city 0.) It is required to find such an itinerary which minimizes the total distance traveled by the salesman. Note that if t is fixed, then for the problem to have a solution we must have tp ≧ n. For t = 1, p ≧ n, we have the standard
traveling salesman
problem.Let dij (i ≠ j = 0, 1, ··· , n) be the distance covered in traveling from city i to city j. The following integer programming problem will be shown to be equivalent to (1): (2) Minimize the linear form ∑0≦i≠j≦n∑ dijxij over the set determined by the relations ∑ni=0i≠j xij = 1 (j = 1, ··· , n) ∑nj=0j≠i xij = 1 (i = 1, ··· , n) ui  uj + pxij ≦ p  1 (1 ≦ i ≠ j ≦ n) where the xij are nonnegative integers and the ui (i = 1, …, n) are arbitrary real numbers. (We shall see that it is permissible to restrict the ui to be nonnegative integers as well.) If t is fixed it is necessary to add the additional relation: ∑nu=1 xi0 = t Note that the constraints require that xij = 0 or 1, so that a natural correspondence between these two problems exists if the xij are interpreted as follows: The salesman proceeds from city i to city j if and only if xij = 1. Under this correspondence the form to be minimized in (2) is the total distance to be traveled by the salesman in (1), so the
burden of proof
is to show that the two feasible sets correspond; i.e., a feasible solution to (2) has xij which do define a legitimate itinerary in (1), and, conversely a legitimate itinerary in (1) defines xij, which, together with appropriate ui, satisfy the constraints of (2).Consider a feasible solution to (2). The number of returns to city 0 is given by ∑ni=1 xi0. The constraints of the form ∑ xij = 1, all xij nonnegative integers, represent the conditions that each city (other than zero) is visited exactly once. The ui play a role similar to node potentials in a network and the inequalities involving them serve to eliminate tours that do not begin and end at city 0 and tours that visit more than p cities. Consider any xr0r1 = 1 (r1 ≠ 0). There exists a unique r2 such that xr1r2 = 1. Unless r2 = 0, there is a unique r3 with xr2r3 = 1. We proceed in this fashion until some rj = 0. This must happen since the alternative is that at some point we reach an rk = rj, j + 1 k. Since none of the r's are zero we have uri  uri + 1 + pxriri + 1 ≦ p  1 or uri  uri + 1 ≦  1. Summing from i = j to k  1, we have urj  urk = 0 ≦ j + 1  k, which is a contradiction. Thus all tours include city 0. It remains to observe that no tours is of length greater than p. Suppose such a tour exists, x0r1 , xr1r2 , ···· , xrprp+1 = 1 with all ri ≠ 0. Then, as before, ur1  urp+1 ≦  p or urp+1  ur1 ≧ p. But we have urp+1  ur1 + pxrp+1r1 ≦ p  1 or urp+1  ur1 ≦ p (1  xrp+1r1)  1 ≦ p  1, which is a contradiction.Conversely, if the xij correspond to a legitimate itinerary, it is clear that the ui can be adjusted so that ui = j if city i is the jth city visited in the tour which includes city i, for we then have ui  uj =  1 if xij = 1, and always ui  uj ≦ p  1. The above
integer program
involves n2 + n constraints (if t is not fixed) in n2 + 2n variables. Since the inequality form of constraint is fundamental for integer programming calculations, one may eliminate 2n variables, say the xi0 and x0j, by means of the equation constraints and produce an equivalent problem with n2 + n inequalities and n2 variables.The currently known integer programming procedures are sufficiently regular in their behavior to cast doubt on the heuristic value of machine experiments with our model. However, it seems appropriate to report the results of the five machine experiments we have conducted so far. The solution procedure used was the allinteger algorithm of R. E. Gomory [3] without the ranking procedure he describes.The first three experiments were simple
model verification
tests on a fourcity standard
traveling salesman problem
with
distance matrix
[ 20 23 4 30 7 27 25 5 25 3 21 26 ]The first experiment was with a model, now obsolete, using roughly twice as many constraints and variables as the current model (for this problem, 28 constraints in 21 variables). The machine was halted after 4000 pivot steps had failed to produce a solution. The second experiment used the earlier model with the xi0 and x0j eliminated, resulting in a 28constraint, 15variable problem. Here the machine produced the
optimal solution
in 41 pivot steps.The third experiment used the current formulation with the xi0 and x0j eliminated, yielding 13 constraints and 9 variables. The
optimal solution
was reached in 7 pivot steps.The fourth and fifth experiments were used on a standard tencity problem, due to Barachet, solved by Dantzig, Johnson and Fulkerson [1]. The current formulation was used, yielding 91 constraints in 81 variables. The fifth problem differed from the fourth only in that the ordering of the rows was altered to attempt to introduce more favorable pivot choices. In each case the machine was stopped after over 250 pivot steps had failed to produce the solution. In each case the last 100 pivot steps had failed to change the value of the objective function.It seems hopeful that more efficient integer programming procedures now under development will yield a satisfactory algorithmic solution to the
traveling salesman
problem, when applied to this model. In any case, the model serves to illustrate how problems of this sort may be succinctly formulated in integer programming terms.
Journal:
Journal of The ACM  JACM
, vol. 7, no. 4, pp. 326329, 1960
DOI:
10.1145/321043.321046
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.informatik.unitrier.de
)
(
portal.acm.org
)
(
portal.acm.org
)
(
doi.acm.org
)
More »
Citation Context
(46)
...In particular, the sequential formulation, also known as
MillerTuckerZemlin (MTZ) formulation
17
, introduces
n
−1 new continuous variables, and it reduces the number of subtour elimination constraints to
n
^{2}
−2
n
−1...
Iacopo Gentilini
,
et al.
The travelling salesman problem with neighbourhoods: MINLP solution
...Subcycle elimination constraints: Following the modelling of [
18
], next constraints allow eliminating subcycles controlling the reaching times to nodes, which will be useful when dealing with criteria related to time...
Begoña Vitoriano
,
et al.
A multicriteria optimization model for humanitarian aid distribution
...The constraints (
2
) and (3) are associated with the conditions aiming so that the request for each type of product is satisfied...
Imen Abbes
,
et al.
Vehicle routing problem in real case application
...[
2
]). This mathematical formulation of the TSPTW differs only in constraints (5) from the formulation of the TSP...
Michael Bogl
,
et al.
Computational study of neighborhood operator performance on the Travel...
...
1960
)...
Bahram Alidaee
,
et al.
On the integer programming formulation of production scheduling optimi...
References
(1)
Outline of an algorithm for integer solutions to linear programs
(
Citations: 216
)
Ralph E. Gomory
Journal:
Bulletin of The American Mathematical Society  BULL AMER MATH SOC
, vol. 64, no. 1958, pp. 275278, 1958
Sort by:
Citations
(130)
The travelling salesman problem with neighbourhoods: MINLP solution
Iacopo Gentilini
,
François Margot
,
Kenji Shimada
Journal:
Optimization Methods & Software  OPTIM METHOD SOFTW
, vol. aheadofp, no. aheadofp, pp. 115, 2012
A multicriteria optimization model for humanitarian aid distribution
(
Citations: 3
)
Begoña Vitoriano
,
M. Teresa Ortuño
,
Gregorio Tirado
,
Javier Montero
Journal:
Journal of Global Optimization
, pp. 120, 2011
TSP in spreadsheets—A fast and flexible tool
(
Citations: 1
)
Rasmus Rasmussen
Journal:
Omegainternational Journal of Management Science  OMEGAINT J MANAGE SCI
, vol. 39, no. 1, pp. 5163, 2011
A lexicographical goal programming based decision support system for logistics of Humanitarian Aid
(
Citations: 1
)
M. T. Ortuño
,
G. Tirado
,
B. Vitoriano
Journal:
Top
, vol. 18, no. 1, pp. 116, 2011
MIP models for connected facility location: A theoretical and computational study
(
Citations: 2
)
Stefan Gollowitzer
,
Ivana Ljubic
Journal:
Computers & Operations Research  CoR
, vol. 38, no. 2, pp. 435449, 2011