In this technical note, an algorithm for binary quadratic programs defined by matrices with band structure is proposed. It was shown in the article by T. Alamo, D. M. de la Pena, D. Limon, and E. F. Camacho, "Constrained min-max predictive control: Modifications of the objective function leading to polynomial complexity," IEEE Iran. Autom. Control, vol. 511, pp. 710-714, May 2005, that this class of problems arise in robust model predictive control when min-max techniques are applied. Although binary quadratic problems belongs to a class of NP-complete problems, the computational burden of the proposed maximization algorithm tits band matrices is polynomial with the dimension of the optimization variable and exponential with the band size. Computational results and comparisons on several hundred test problems demonstrate the efficiency of the algorithm.