Linear-Cutting: Linear-Cutting

As if right on cue, our esteemed Royal Mathematician writes in regarding Dr. J.'s post yesterday:

A most happy New Year to all Gormogons whose calendar-origin-of-choice has recently passed, and general seasonally-appropriate greetings to the others: 

A quick word about the cutting-plane method of solving the TSP, since it really is a very clever trick and, believe it or not, a good general problem-solving strategy (though your short-form description was just fine). 

[Of course it was, I'm a Gormogon after all, ed.] 

The idea is this: if we could describe the set of all tours (let's call it T) by a set of linear equations, then we could easily solve the TSP using linear programming (LP) techniques. We can't do that, but we can easily describe a bigger set (let's call it S1) by linear equations, and then find the best (suitably defined) thing in S1. If this best thing turns out to be a tour, then we're done. Otherwise, we can find another linear equation that cuts this current best thing off from all the tours. This gives us another (smaller) set that still contains all the tours (let's call this one S2). Now, we use LP find the best thing in S2, and lather, rinse and repeat. Eventually this process will give us an answer that's a tour and we're done. The tricky bit, of course, is to do the cutting effectively (hopefully we cut off a big chunk that gets us closer to the tours, rather than a teensy chunk that just barely cuts off the previous best thing – surgeons have this problem as well). 

This is a good general problem-solving strategy - if you can't solve the problem you have, find a vaguely related problem that you can solve, and see where it gets you. Then, refine the problem to remove the spurious solution you just obtained, and get closer to the original problem that you want to solve. 

Say, for example, you want to find a good, electable Presidential candidate. We seem not to know how to solve that at the moment, so let’s first find the best candidate among a certain group. If that one turns out not to be electable, we cut down our feasibility set, and try again. Alternatively, we could search for the most electable candidate among a certain group, and if that one turns out not to be good, we cut down our feasibility set and try again. One hopes, of course, that we don’t get down to an empty feasibility set prior to November… 

Now, back to waiting for the impending birth of my first grandson. 

--Dr. (KN)J, Royal Mathematician to the Gormogons.

Dear Dr. (KN)J,

Thank you for writing in. I think your description of the methodology is quite good. Even better how you apply it to how the Republican faithful are winnowing the Republican field and picking a candidate is equally apt.

Good luck with the new grandson. Mama J. informs Dr. J. that being a grandparent is very enjoyable (albeit potentially expensive), probably because the lil resident and lil medstudent are far better company then Dr. J. was at their age...