The relocation costs would be considered in the analysis of the bids. In fact, in this case, as you mentioned, where the department or the agency was located was classified fourth on the list. The winning bidder was notified, and then there was a request to remain where they were, so government ended up having to pay two rental spaces. At the end of the day you have to ask, if there really was the significant need to stay where they were, why did they go out for a bid? If you're going out for a bid process, then you should respect that process.
On June 1st, 2006. See this statement in context.