There are a few more questions I’d like to ask to get a better understanding of what’s happening. Is VS2015 the only version of Visual Studio on the machine currently? If so, does the problem occur after installing VS2013? Are Visual Studio and Unreal Engine on the same drive on the computer? What is the path for VS and UE? If there are any special characters in the path you may need to rename the path folders or move the programs to a different location. It may also help to check that the path variables are set appropriately. Here are a couple of other posts with the same issue (couldn’t find valid VS install) along with how they were able to solve the issue by editing the path variables:
Let me know if either of these helps