A fundamental problem in linear inequalities with applications to the travelling salesman problem
Murty, Katta G.
1972-02
Citation
Murty, Katta G.; (1972). "A fundamental problem in linear inequalities with applications to the travelling salesman problem." Mathematical Programming 2(1): 296-308. <http://hdl.handle.net/2027.42/47908>
Abstract
We consider a system of m linearly independent equality constraints in n nonnegative variables: Ax = b, x ≧ 0. The fundamental problem that we discuss is the following: suppose we are given a set of r linearly independent column vectors of A , known as the special column vectors. The problem is to develop an efficient algorithm to determine whether there exists a feasible basis which contains all the special column vectors as basic column vectors and to find such a basis if one exists. Such an algorithm has several applications in the area of mathematical programming. As an illustration, we show that the famous travelling salesman problem can be solved efficiently using this algorithm. Recent published work indicates that this algorithm has applications in integer linear programming. An algorithm for this problem using a set covering approach is described.Publisher
Springer-Verlag; The Mathematical Programming Society
ISSN
0025-5610 1436-4646
Other DOIs
Types
Article
Metadata
Show full item recordAccessibility: If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.