I presume you mean "solution" in the sense of finding a way to overcome a problem. In that case, "solution" is the noun form of "solve". There's no need to take a noun derived from a verb and then derive yet another verb from that noun. You say "We are working on solving the problem", NOT "We are working on solutioning the problem."
If by "solution" you mean a solid mixed into a liquid, then the verb is "dissolve". Again, no need to invent a new word.
If there's some reason why you need to distinguish some method or process of finding solutions, or some specific approach to finding solutions, from simply solving problems, I suppose it's plausible to invent a new word.
But please please please don't tell me that you want to say "we solutioned the problem" rather than "we solved the problem" because it "sounds more professional" or something like that. I hate it when people utilize paradigms inculcating contra-diminutive words for the ostensible objective of maximizing pretentiousness.