It has recently been important to obtain optimal solutions to multidimensional nonlinear integer programming problems with multiple constraints. The surrogate constraint method is very effective in obtaining high-quality solutions of the original multidimensional problems. The surrogate constraint method translates a multidimensional problem into a one-dimensional problem by using a surrogate multiplier. But when there exists a surrogate duality gap between the translated one-dimensional problem and the original multidimensional problem, the optimal solution to the surrogate problem is not optimal with respect to the original problem. Nakagawa has recently proposed an improved surrogate constraint (ISC) method that can reduce the surrogate duality gap and provide an exact solution to the original problem. By using this method, we can obtain exact solutions to separable nonlinear integer programming problems with 1000 variables and 5 or 6 constraints. The ISC method requires an optimal surrogate multiplier. However, there are problems of calculation time and memory requirements in the algorithm for obtaining the optimal surrogate multiplier when the number of constraints is large. In this paper, the Dyer algorithm and Nakagawa's Cutting-Off Polyhedron (COP) algorithm for an algorithm that obtains the optimal surrogate multiplier in the ISC method are compared in computational experiments, and the advantages and disadvantages of these algorithms are investigated. In addition, an improved Dyer algorithm is proposed and computational experiments show that the improved algorithm is more effective than the original algorithm. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(8): 38–48, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20114