If you are using the relay to turn the solenoid on and off, I recommend taking the output from your PID and creating a PWM with a duty cycle equivalent to the PID result. You can then use that PWM to control the relay. For some help creating a PWM you might look at these examples:
You might however have to scale the results from the PID so that you obtain the temperature reading that you require.
Sappster
