I have a UMax Hosting VPS which is very cheap but also very flakey.

This script (python / selenium) will log in and reboot your VPS – you could tie it to a Icinga Event Command for example.