Stopping a long-running asynchronous computation
Task-based Asynchronous Pattern (MSDN)

public async Task&lt;IProblemSolution&gt; Search(CancellationTokenSource cts)


As I explain in this answer, one would rightfully expect the signature of that method to read like this:
public async Task&lt;IProblemSolution&gt; SearchAsync(CancellationTokenSource cts)

The pattern for async methods is quite simple: use the async keyword, return Task or Task&lt;T&gt;, and put an &quot;Async&quot; suffix to the method's name.

I haven't written much async code (read: never wrote a line of C# that leverages features of .net 4.5), but from previous reviews of such code I think this:
    Task&lt;IProblemSolution&gt; t = Engine.Search(CancelTokenSrc);
    await t;

    ResultLabel.Content = t.Result.ObjectiveValue().ToString();

Could be written like this:
    var searchResult =  await Engine.SearchAsync(CancelTokenSrc);
    ResultLabel.Content = searchResult.ObjectiveValue().ToString();
    //...

My understanding is that await somehow deals with Task.Result and so the type of searchResult would be IProblemSolution - I might be wrong here though.
Other than that, I find you could give var some lovin', and change this:
IProblemSolution s = Problem.RandomSolution();

To this:
var s = Problem.RandomSolution();

Lastly, I might be biased because I use ReSharper and with that tool IntelliSense/auto-complete is much &quot;smarter&quot;, but I don't like names like cts - I'd rather call it cancelTokenSource and then I can type ctsTab and poof I'm referring to a readable identifier with a pronounceable name.