Where “make me very tired” can be under­stood as a euphemism for: “Drive me to a sketchily-​​explained mys­te­ri­ous ‘club meet­ing’ at an undis­closed bunker sup­pos­edly located along the dis­used coun­try road con­nect­ing Despair and Rue, play­ing a really annoy­ing Clas­sic Hits of the 70s cas­sette over and over so loud that I am forced to fling myself from the mov­ing car before we get much far­ther 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 grad­u­ate school newcomer’s expe­ri­ence of Oper­a­tions Research to date. Your mileage may vary.

Like many crack­pots, I write stuff on 3×5 cards. Here are four cards I found while going through my notes for this other paper I’m sup­posed to write, and all four of them bear sim­ple state­ments of nice lit­tle research projects, any one of which would be suit­able for somebody’s the­sis work. Not mine. Because I’m just a first-​​year stu­dent. A badly-​​trained one, being a half-​​assed biol­o­gist raised by wolves.

Me, I’m in this Advanced Class where we’re learn­ing that Math­e­mat­i­cal Pro­gram­ming is not the be-​​all end-​​all prob­lem solver it’s cracked up to be. Hunh. Go fig. Been learn­ing that all semes­ter. Lucky thing too, because what with my com­plete and utter lack of meet­ing any­body in more than 15 years (until this last year or so) who thought it was worth con­sid­er­ing for a minute, I might’ve slipped and fallen into the kind of unques­tion­ing reliance of Mighty Orac­u­lar CPLEX that my peers in this new dis­ci­pline are prone to exhibit. I picked that up, back in Despair.

Any­way, I need to write a paper on “How Math­e­mat­i­cal Pro­gram­ming Is Some­times Hard, and This May Excuse the Occa­sional Lapse into Heuris­tics. Briefly.” And I need to do it with­out seem­ing 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. Biol­o­gist. Igno­rance out the wazoo. ‘Nuff said.

So I will not be writ­ing about:

• What is the VC dimen­sion of a search algo­rithm? Think of it as a clas­si­fier that finds the exam­ples in a set of test prob­lems either easy or hard. Con­sider how this clas­si­fier shat­ters the set of pos­si­ble prob­lems of that type. Pick your favorite search algo­rithm and class of prob­lems: con­sider using Trav­el­ing Sales­man Prob­lems (every­body else does), and maybe sim­u­lated anneal­ing? Your call. Heck, try Lin­ear Pro­gram­ming with sim­plex moves, and arbi­trary diet problems.
• What for­mal rep­re­sen­ta­tion of the set of all search and opti­miza­tion prob­lems would be use­ful in build­ing a clas­si­fier that let you auto­mat­i­cally rec­og­nize the canon­i­cal types: knap­sack, assign­ment, trav­el­ing sales­man, bin-​​packing, stock-​​cutting, knee-​​biting? If you could cre­ate an auto­mated clas­si­fier, what would it mean if it told you that a prob­lem was “93% knapsack”?
• Surely—surely—there is a No Free Lunch The­o­rem for branch-​​and-​​bound strate­gies. I mean, oth­er­wise when you pick a vari­able (or some com­bi­na­tion of vari­ables) to branch on, you’re just guess­ing, 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 The­o­rem there.
• Dis­cuss a stan­dard opti­miza­tion prob­lem, with your choice of objec­tive func­tion. Now restate it to find the second-​​best answer. Is that harder? Why? Sure seems harder than find­ing the worst. What do you have to do to the rep­re­sen­ta­tion to make it easy again?

You, who are not in my dis­ci­pline, who are not a first-​​year grad­u­ate stu­dent with a Very Poor Under­stand­ing of the finer details of Lin­ear Pro­gram­ming and the Appalling Frac­tion­al­ity of Lin­ear Relax­ations.… you go have fun. Send me a cite, if you get some­thing 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 col­leagues. 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 some­where between here and Rue.