Society also can't really choose not to pay the cost. If they break stuff, it may have to be replaced. If they commit a crime, they have to be housed in prison (which is expensive). And if they require urgent medical attention, doctors won't refuse not to help them even if they can't recuperate the cost...
In San Francisco the situation is a bit different. Housing is more expensive, so 20K won't be enough, and homelessness in SF is a bit more of an economically issue, rather than a mainly psychological one.
And even if SF could save money, they would have a hard time creating such a program, for various political reasons. Also it would mean investing tons of money up front, without the cost reductions being easily visible afterwards.
This aspect was not mentioned in the article. Perhaps Medicine Hat is viewed as a less desirable place to live than, say, Vancouver, and therefore this hasn't been an issue. It's also possible that the Canadian legal system is more effective at preventing this kind of inter-provincial abuse.
The trick with San Francisco, if the city chose to try it, would be to find housing in commuting distance which is cheaper. Such housing wouldn't necessarily need to be in San Francisco, especially if these people don't have work or other ties there...
Which is to say that no, the homeless aren't likely to accept free housing in Walnut Creek. Not if their living patterns center on Van Ness.
The basic problem is that you're asking people who are extremely risk-averse to take what they will see as huge risks with lifestyle change.
By way of example, Las Vegas had a standing policy of "discharging" mental patients by giving them one-way bus tickets to California cities:
http://www.sacbee.com/news/investigations/nevada-patient-bus...
The problem is that the cost of housing is orthogonal to those issues. People who are in homes certainly commit crimes and go through the criminal justice system. They certainly need health care. That $100k figure may go down, perhaps even tremendously, but I suspect the real financial cost comparison isn't anywhere near so great. Otherwise, everyone would already be doing it.