Where “make me very tired” can be understood as a euphemism for: “Drive me to a sketchily-explained mysterious ‘club meeting’ at an undisclosed bunker supposedly located along the disused country road connecting Despair and Rue, playing a really annoying Classic Hits of the 70s cassette over and over so loud that I am forced to fling myself from the moving car before we get much farther than the edge of Despair—but look! they drove off with my license in the frickin’ car, so I am forced to walk all the god. damned. rest. of. the. way. to. Rue.”

Roughly. That’s been my graduate school newcomer’s experience of Operations Research to date. Your mileage may vary.

Like many crackpots, I write stuff on 3×5 cards. Here are four cards I found while going through my notes for this other paper I’m supposed to write, and all four of them bear simple statements of nice little research projects, any one of which would be suitable for somebody’s thesis work. Not mine. Because I’m just a first-year student. A badly-trained one, being a half-assed biologist raised by wolves.

Me, I’m in this Advanced Class where we’re learning that Mathematical Programming is not the be-all end-all problem solver it’s cracked up to be. Hunh. Go fig. Been learning that all semester. Lucky thing too, because what with my complete and utter lack of meeting anybody in more than 15 years (until this last year or so) who thought it was worth considering for a minute, I might’ve slipped and fallen into the kind of unquestioning reliance of Mighty Oracular CPLEX that my peers in this new discipline are prone to exhibit. I picked that up, back in Despair.

Anyway, I need to write a paper on “How Mathematical Programming Is Sometimes Hard, and This May Excuse the Occasional Lapse into Heuristics. Briefly.” And I need to do it without seeming for a moment to be… well, uppity. That’s a word. I will use “Made tired”, and “uppity”, and leave it at that.

Raised by wolves. Biologist. Ignorance out the wazoo. ‘Nuff said.

So I will not be writing about:

• What is the VC dimension of a search algorithm? Think of it as a classifier that finds the examples in a set of test problems either easy or hard. Consider how this classifier shatters the set of possible problems of that type. Pick your favorite search algorithm and class of problems: consider using Traveling Salesman Problems (everybody else does), and maybe simulated annealing? Your call. Heck, try Linear Programming with simplex moves, and arbitrary diet problems.
• What formal representation of the set of all search and optimization problems would be useful in building a classifier that let you automatically recognize the canonical types: knapsack, assignment, traveling salesman, bin-packing, stock-cutting, knee-biting? If you could create an automated classifier, what would it mean if it told you that a problem was “93% knapsack”?
• Surely—surely—there is a No Free Lunch Theorem for branch-and-bound strategies. I mean, otherwise when you pick a variable (or some combination of variables) to branch on, you’re just guessing, and that’s so… dumb… well, I don’t even want to think it of you. So tell me you know there is an NFL Theorem there.
• Discuss a standard optimization problem, with your choice of objective function. Now restate it to find the second-best answer. Is that harder? Why? Sure seems harder than finding the worst. What do you have to do to the representation to make it easy again?

You, who are not in my discipline, who are not a first-year graduate student with a Very Poor Understanding of the finer details of Linear Programming and the Appalling Fractionality of Linear Relaxations…. you go have fun. Send me a cite, if you get something done. I can’t stand the thought of doing them, except that they sound quite interesting.

But I would have to explain them to my colleagues. That would be hard. I can tell already. If you need to get in touch about them, just drop me a line.

I’ll be somewhere between here and Rue.