30
7 Concluding remarks
Some preliminary numerical results indicate that the algorithm works remarkably
well. A large number of large-scale instances ( more than 100,000 variables ) has
also been carried out. The instances can be easily created according to the standard
form. We shall report numerical results and the complexity analysis of the algorithm
in a next paper.
Here we do not discuss any index theory. In fact there can be built up an index
theory for the algorithm. The interested reader is referred to van der Laan [4] and
Scarf [11] for insightful discussions. Finally we conjecture that the number two both
in Theorem 2.4 and in Theorem 5.2 can be replaced by the number n ⅛ 1.
Acknowledgement
I am extremely grateful to Gerard van der Laan and particularly Dolf Talman
whose insightful comments, suggestions and discussions significantly improved the
paper. I would also like to thank Curtis Eaves with whom I have had very interesting
conversations on the general topic of this paper when I was visiting him. I am,
however, solely responsible for any remaining errors. This research is part of the
VF-program ’’Competition and Cooperation”.
References
[1] C. Dang and H. van Maaren, ”A simplicial approach to integer programming”,
Report 93-06, Department of Mathematics, Delft University of Technology,
Delft, 1993, submitted to Mathematics of Operations Research.
[2] B.C. Eaves, ’’Homotopies for computation of Exed points”, Mathematical Pro-
gramming 3 (1972) 1-22.