A fundamental problem in linear inequalities with applications to the travelling salesman problem

We consider a system ofm linearly independent equality constraints inn nonnegative variables:Ax = b, x 0. The fundamental problem that we discuss is the following: suppose we are given a set ofr linearly independent column vectors ofA, known asthe 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.This research has been partially supported by the ISDOS research project and the National Science Foundation under Grant GK-27872 with the University of Michigan.