Notes on mathematical formulation and complexity considerations for blocks relocation problem

In a recent paper, caserta et al. [m. caserta, s. schwarze, and s. voβ. a mathematical formulation and complexity considerations for the blocks relocation problem, european journal of operational research, 219, pp. 96-104 (2012)] proposed two mathematical models for the blocks relocation problem. because of the complexity of their first model, called brp-i, they employed a simplifying assumption and introduced a relatively fast model, called brp-ii, to solve medium-sized instances. in this paper, it is first proven that the brp-ii model is incorrect. then, the corrected and improved formulation of brp-ii, called brp2c and brp2ci, respectively, are presented. by correcting a constraint in brp-ii, the reported optimal solution is either corrected or improved in many instances. also, it is proven that some results of brp-ii reported by caserta et al. are incorrect. incorporating some new cut constraints into brp2ci, the computational time of solving instances is decreased 25 times, on average.