AbstractRecent research has led to several surrogate multiplier search procedures for use in a primal branch‐and‐bound procedure. As single constrained integer programming problems, the surrogate subproblems are also solved via branch‐and‐bound. This paper develops the inner play between the surrogate subproblem and the primal branch‐and‐bound trees which can be exploited to produce a number of computational efficiencies. Most important is a restarting procedure which precludes the need to solve numerous surrogate subproblems at each node of a primal branch‐and‐bound tree. Empirical evidence suggests that this procedure greatly reduces total computation time.