The US Supreme Court has long held that the border mitigates "reasonable" in the 4th amendment such that warrantless searches at the border are constitutionally sound. [0]
That said, this isn't a search. It is the presumption of guilt if a search is refused. I agree with you that it's bad policy, but it's not unconstitutional.