Well, you've got a bit of a problem there. The battery does not have enough current capacity to trigger than relay. Lemme guess, this is a 9V battery? That can put out something like 300ma, 500ma or so.
Best thing is to use a logic level n-channel MOSFET to trigger the solenoid. Why? Well, this figures into the plan...
The reg generally won't drain power off the 5V rail if the source voltage falls. So if we can put a decent amount of capacitance on the 5V side and keep the power usage to a minimum, the 5v rail can survive a momentary power loss. An npn transistor driving 7 amps requires hundreds of times more base current than the entire system would require with a MOSFET. So if you watch power consumption from sensors, etc and keep the PIC's freq as the minimum needed to do the job, you can keep the 5V rail away from brownout for several moments.
You must- MUST- have a flyback diode the relay's coil.
It's still a huge problem that there's just not enough power on the battery, it's just not cricket to load a battery so high. At best, you could use a huge capacitance. We're talking huge, if you want to have a cap that supplies 7 amps for 1/10th sec with only a 2v drop this would need to be 350,000uf. Now there are "supercapacitors" which can do this, they can be in the range of 100,000uF to 1F. But they're usually only made as 5.5V ratings at most. You could potentially put 2 in series (the total capacitance is halved), but some protective measures must be taken to assure the center terminal does not float away from 9v/2 or it will blow one of the caps.
There is also the issue of the internal resistance of the cap. Most are not made for charge/discharges in the range of amps, their terminal voltage will drop a lot and it can damage the cap.