Wednesday, November 24, 2010

Conference (snore) Presentations

The annual meeting of the Decision Sciences Institute just wrapped up in normally warm-and-sunny San Diego (which was neither this week). I achieved the dubious first of having to attend three committee meetings in two consecutive time slots (which means I "session-hopped" committee meetings).  Let's see ... I left Lansing MI for cool, rainy weather and committee meetings ... remind me again why.  Two conferences in three weeks is a bit draining, and knowing I'm going home to grading doesn't improve my disposition.

So I'm in the proper frame of mind to make the following observations about conference presentations and sessions, in no particular order:
  • Assume that your audience is reasonably smart.  Don't explain the obvious.  If you're presenting a scheduling model for buses, don't spend time explaining to the audience what a bus is.  (That's not exactly what one presenter did, but it's very close.)  If your audience is really that clueless, they won't understand your presentation anyway (and quite likely they're in the wrong room).
  • Session chairs should enforce time limits ruthlessly.  If people want to discuss the paper with the author and the author has exhausted his/her time allocation, they can do so after the session.  Besides facilitating session hopping (the least important reason for this, in my opinion), it provides an incentive for authors to shorten their presentations.  Also (and this is frequently overlooked), it's harder for the next presenter to gauge how much time they have left when they start at an off-cycle time in a session that's already behind schedule.
  • The DSI meeting was plagued by no-show presenters (including one session where I went only to hear one paper -- the one that ended up not being presented).  Occasionally a presenter is missing due to illness or death in the family (the latter happened to me once at a conference).  Sometimes their funding falls through at the last minute.  More often they just wanted to get in the proceedings, or they saw they were scheduled for the rump session and decided not to bother. I'm generally inclined to believe that a no-show presenter actually did the audience a favor: if they weren't committed to showing up, how committed were they to doing a good job preparing the presentation?
  • As a presenter, less is more.  (And I confess to screwing this one up myself at the Austin INFORMS meeting.)  Leave time for feedback.  Other than the minor value of another line on your vita and the major value of qualifying you for travel funds, the main virtue of presenting a paper is to get feedback from the audience.  Dazzling them with your brilliance is beside the point, since the (presumed) future publication in a (presumed) top-tier journal will accomplish that.
  • Graphs are good; tables of numbers are not.  Tables of numbers in 4 point font (because that's what it took to fit all the numbers on one slide) are even less useful (other than to audience members who have not been sleeping well at their hotels).
  • If your slides include any complete paragraphs (other than memorable quotations), say goodbye to your audience.  They'll be off catching up on e-mails.  If you are reading those complete paragraphs to your audience, they'll be busy e-mailing they sympathies to your students (who presumably suffer the same fate, but more regularly).
'Tis the day before Thanksgiving here, and if my (delayed) flight actually manages to make up the lost time and not blow my connection in Atlanta, I will truly be thankful.  To those of you celebrating the holiday, have a good one!

Wednesday, November 17, 2010

Obscure Engineering Conversion Factors

The following came around in this morning's e-mail, and I think it's amusing enough to be worth archiving. I've enlisted the aid of the Wikipedia to explain some of the jokes that rely on immersion in American culture.

  1. Ratio of an igloo's circumference to its diameter = Eskimo Pi
  2. 2000 pounds of Chinese Soup = Won ton
  3. 1 millionth of a mouthwash = 1 microscope
  4. Time between slipping on a peel and smacking the pavement = 1bananosecond
  5. Weight an evangelist carries with God = 1 billigram
  6. Time it takes to sail 220 yards at 1 nautical mile per hour = Knotfurlong
  7. 365.25 days of drinking low calorie beer = 1 Lite year
  8. 16.5 feet in the Twilight Zone = 1 Rod Serling
  9. Half a large intestine = 1 semicolon
  10. 1,000,000 aches = 1 megahurtz
  11. Basic unit of laryngitis = 1 hoarsepower
  12. Shortest distance between two jokes = a straight line
  13. 453.6 graham crackers = 1 pound cake
  14. 1 million microphones = 1 megaphone
  15. 1 million bicycles = 1 megacycle
  16. 365 bicycles = 1 unicycle
  17. 2000 mockingbirds = two kilomockingbirds
  18. 10 cards = 1 decacard
  19. 52 cards = 1 deckacard
  20. 1 kilogram of falling figs = 1 Fig Newton
  21. 1000 ccs of wet socks = 1 literhosen
  22. 1 millionth of a fish = 1 microfiche
  23. 1 trillion pins = 1 terrapin
  24. 10 rations = 1 decaration
  25. 100 rations = 1 C-Ration
  26. 2 monograms = 1 diagram
  27. 8 nickels = 2 paradigms
  28. 5 statute miles of intravenous surgical tubing at Yale University Hospital = 1 I.V. League

Hidden Assumptions, Unintended Consequences

The New York Times has an amusing "Budget Puzzle" that allows you to select various options for budget cuts and tax increases at the federal level, in an attempt to close the anticipated US federal deficits for 2015 and 2030. The visible math is basic addition and subtraction, but hidden below the projected results of each option are various unstated assumptions. Many of these assumptions will be economic in nature, and economists have been known to make some entertaining assumptions.  (Do you remember that bit in Econ 101 about the ideal production level for a firm being the quantity where marginal cost equals marginal revenue? Do you recall any mention of a capacity limit?)

Also missing from the NYT puzzle are projections of indirect costs for any of the options.  If we reduce our military presence in Afghanistan drastically, will we subsequently need to make an expensive redeployment there?  If we increase taxes on employer-paid health care policies, will employers reduce the availability of those policies and, if so, will that indirectly impose greater health care costs on the federal government?

It's obvious why the Times puzzle does not go into those considerations -- they're involve considerable uncertainty, and they would probably make the puzzle too complicated to be entertaining. As OR people, we're used to making assumptions (frequently designed to simplify a real-world mess into a tractable problem); but we should also be acutely aware that the puzzle contains many unstated assumptions, and not attach too much credibility to the results.

Incidentally, I balanced the budget with 34% spending cuts and 66% tax increases, and I consider myself to be a fiscal conservative (but a realist, at least in the relative topology of mathematicians).

Sunday, November 14, 2010

INFORMS Debrief

The national INFORMS meeting in Austin is in the rear-view mirror now (and I'm staring at the DSI meeting in San Diego next week -- no rest for the wicked!), so like most of the other bloggers there I feel obligated to make some (in my case random) observations about it.  In no specific order ...
  • The session chaired by Laura McLay on social networking was pretty interesting, particularly as we got an extra guest panelist (Mike Trick joined Anna Nagurney, Aurelie Thiele and Wayne Winston, along with Laura) at no extra charge. Arguably the most interesting thing from my perspective was the unstated assumption that those of us with blogs would actually have something insightful to say. I generally don't, which is one reason I hesitated for a long time about starting a blog. 
  • On the subject of blogs, shout-out to Bjarni Kristjansson of Maximal Software, who more or less badgered me into writing one at last year's meeting. Bjarni, be careful what you wish for! :-)  It took me some digging to find Bjarni's blog (or at least one of them). Now if only I could read Icelandic ...
  • I got to meet a few familiar names (Tallys Yunes, Samik Raychaudhuri ) from OR-Exchange and the blogosphere.
  • Thanks to those (including some above) who've added my blog to their blogrolls.  The number of OR-related blogs is growing pretty quickly, but with growth come scaling issues. In particular, I wonder if we should be looking for a way to provide guidance to potential readers who might be overwhelmed with the number of blogs to consider. I randomly sample some as I come across them, but if I don't see anything that piques my interest in a couple or so posts I'm liable to forget them and move on, and perhaps I'm missing something valuable. This blog, for instance, is mostly quantitative (math programming) stuff, but with an occasional rant or fluff piece (such as this entry).  I wonder if we could somehow publish a master blog roll with an associated tag cloud for each blog, to help clarify which blogs contain which sorts of content.
Getting off the social network tram for a bit ...
  • A consistent bug up my butt about INFORMS meetings is their use of time. Specifically, the A sessions run 0800 to 0930, followed by coffee from 0930 to 1000. There is then an hour that seems to be underutilized (although I think some plenaries and other special sessions occur then -- I'm not sure, as I'm not big on attending plenary talks). The B sessions run 1100 to 1230 and the C sessions run 1330 to 1500. So we have an hour of what my OM colleagues call "inserted slack" after the first coffee break, but only one hour to get out of the convention center, find some lunch and get back. It would be nice if the inserted slack and the B session could be flipped, allowing more time for lunch. My guess is that the current schedule exists either to funnel people into plenaries (who might otherwise opt for an extended lunch break) or to funnel them into the exhibits (or both).
  • We're a large meeting, so we usually need to be in a conference center (the D.C. meeting being an exception). That means we're usually in a business district, where restaurants that rely on office workers for patronage often close on Sundays (D.C. and San Diego again being exceptions). Those restaurants that are open on Sunday seem to be caught by surprise when thousands of starving geeks descend en masse, pretty much all with a 1230 - 1330 lunch hour. For a society that embraces predictive analytics, we're not doing a very good job of communicating those predictions to the local restaurants. (Could INFORMS maybe hire a wiener wagon for Sundays?)
  • The layout of the Austin convention center struck me as a bit screwy even without the construction. For non-attendees, to get from the third floor to the fourth floor you had to take an escalator to the first floor (sidebar: the escalator did not stop at the second floor), walk most of the length of the facility, go outside and walk the rest of the length, go back inside and take an escalator to the fourth floor (sidebar: this escalator did not stop at either of the two intervening floors). Someone missed an opportunity to apply the Floyd-Warshall algorithm and embed shortest routes between all nodes in the map we got.
  • The sessions I attended ranged from fairly interesting to very interesting, so I have absolutely no complaints about that. I also had good luck networking with people I wanted to see while I was there. Since sessions and networking are my two main reasons for attending a conference (my own presentation ranks a distant third), it was well worth the trip.
The conference, like all its predecessors, allowed me to collect some new observations that add to the empirical evidence supporting my theories of Geek Physics (which depart from classical Newtonian physics in a few regards). In particular:
  • A geek in motion will come to rest at the location that maximizes interdiction of other traffic (particularly purposeful traffic).
  • A geek at rest will remain at rest until someone bearing a cup of coffee enters their detection range, at which point they will sharply accelerate on an optimized collision course.
  • A geek entering or exiting a session in progress will allow the door to slam shut behind them with probability approaching 1.0. (Since I have no empirical evidence that geeks are hard of hearing, I attribute this to a very shallow learning curve for things outside the geek's immediate discipline, but I'm having trouble collecting sufficiently specific data to test that hypothesis.)
If anyone has observed other laws of Geek Physics that I'm missing, I'd be interested in hearing them.

Enough about the conference, at least for now. It was interesting, I enjoyed interacting with some people I otherwise only see online, and I brought home a bunch of notes I'll need to sort through. I'm looking forward to next year's meeting.

Thursday, November 11, 2010

Metcalfe's and Clancy's Laws

I don't have a Twitter account (years of dealing with administrators have left me averse to anything with "twit" in it), so I'll blog this instead. (In any case, I couldn't do this in 140 characters.  As a professor, I can't do anything in 140 words, let alone 140 characters.) Yesterday Laura McLay blogged about OR and the intelligence community, and mentioned in particular J. M. Steele's paper in Management Science titled “Models for Managing Secrets”.  Steele apparently presents an argument supporting the "Tom Clancy Theorem, which states that the time to detect a secret is inversely proportional to the square of the people that know it (stated without proof in the Hunt for Red October)" (quoting Laura).

The people who know the secret form, at least loosely, a social network. That brings me to Metcalfe's Law, which originally stated that the value of a communications network is proportional to the square of the number of connected devices, but which has since been generalized (bastardized?) to refer to humans as well as, or rather than, devices and to cover social networks as well as communications networks. I imagine Robert Metcalfe intended value to mean value to the aggregate set of owners of the attached devices (which in his mind might well have been one organization, since he's a pioneer in local area networks), but in a social networking context we can think of value as either or both of value to the members of the network (e.g., you and your Facebook friends) or value to the owners of the underlying support structure (e.g., the owners of Facebook.com).

So, letting $T$ be the time to detect a secret, $N$ the number of people who know the secret and $V$ the value of the social network to its members (which presumably includes the originator of the secret), we have $$T=\frac{k_1}{N^2}$$ and $$V=k_2\times N^2,$$ from which we infer $$T=\frac{k_1\times k_2}{V}.$$ Since the value of the social network to the "enemy" is inversely proportional to the time required to reveal the secret, we have direct proportionality between the value of the social network to the entity trying to conceal the secret and the value of that same network to the enemies of that entity.

So now I'm off to cancel my Facebook and LinkedIn accounts.  :-)

Wednesday, November 10, 2010

Continuous Knapsack with Count Constraint


A question recently posted to sci.op-research offered me a welcome respite from some tedious work that I’d rather not think about and you’d rather not hear about. We know that the greedy heuristic solves the continuous knapsack problem to optimality. (The proof, using duality theory, is quite easy.) Suppose that we add what I’ll call a count constraint, yielding where . Can it be solved by something other than the simplex method, such as a variant of the greedy heuristic?

The answer is yes, although I’m not at all sure that what I came up with is any easier to program or more efficient than the simplex method. Personally, I would link to a library with a linear programming solver and use simplex, but it was amusing to find an alternative even if the alternative may not be an improvement over simplex.

The method I’ll present relies on duality, specifically a well known result that if a feasible solution to a linear program and a feasible solution to its dual satisfy the complementary slackness condition, then both are optimal in their respective problems. I will denote the dual variables for the knapsack and count constraints and respectively. Note that but is unrestricted in sign. Essentially the same method stated below would work with an inequality count constraint ( ), and would in fact be slightly easier, since we would know a priori the sign of (nonnegative). The poster of the original question specified an equality count constraint, so that’s what I’ll use. There are also dual variables ( ) for the upper bounds. The dual problem is

This being a blog post and not a dissertation, I’ll assume that (2) is feasible, that all parameters are strictly positive, and that the optimal solution is unique and not degenerate. Uniqueness and degeneracy will not cause invalidate the algorithm, but they would complicate the presentation. In an optimal basic feasible solution to (2), there will be either one or two basic variables — one if the knapsack constraint is nonbinding, two if it is binding — with every other variable nonbasic at either its lower or upper bound. Suppose that is an optimal solution to the dual of (2). The reduced cost of any variable is . If the knapsack constraint is nonbinding, then and the optimal solution is If the knapsack constraint is binding, there will be two items ( , ) whose variables are basic, with . (By assuming away degeneracy, I’ve assumed away the possibility of the slack variable in the knapsack constraint being basic with value 0). Set and let and . The two basic variables are given by

The algorithm will proceed in two stages, first looking for a solution with the knapsack nonbinding (one basic variable) and then looking for a solution with the knapsack binding (two basic variables). Note that the first time we find feasible primal and dual solutions obeying complementary slackness, both must be optimal, so we are done. Also note that, given any and any , we can complete it to obtain a feasible solution to (3) by setting . So we will always be dealing with a feasible dual solution, and the algorithm will construct primal solutions that satisfy complementary slackness. The stopping criterion therefore reduces to the constructed primal solution being feasible.

For the first phase, we sort the variables so that . Since and there is a single basic variable ( ), whose reduced cost must be zero, obviously . That means the reduced cost of is nonnegative for and nonpositive for . If the solution given by (3) is feasible — that is, if and — we are done. Moreover, if the right side of either constraint is exceeded, we need to reduce the collection of variables at their upper bound, so we need only consider cases of for ; if, on the other hand, we fall short of units, we need only consider cases of for . Thus we can use a bisection search to complete this phase. If we assume a large value of , the initial sort can be done in O( ) time and the remainder of the phase requires iterations, each of which uses time.

Unfortunately, I don’t see a way to apply the bisection search to the second phase, in which we look for solutions where the knapsack constraint is binding and . We will again search on the value of , but this time monotonically. First apply the greedy heuristic to problem (1), retaining the knapsack constraint but ignoring the count constraint. If the solutions happens by chance to satisfy the count constraint, we are done. In most cases, though, the count constraint will be violated. If the count exceeds , then we can deduce that the optimal value of in (4) is positive; if the count falls short of , the optimal value of is negative. We start the second phase with and move in the direction of the optimal value.

Since the greedy heuristic sorts items so that , and since we are starting with , our current sort order has . We will preserve that ordering (resorting as needed) as we search for the optimal value of . To avoid confusion (I hope), let me assume that the optimal value of is positive, so that we will be increasing as we go. We are looking for values of where two of the variables are basic, which means two have reduced cost 0. Suppose that occurs for and ; then It is easy to show (left to the reader as an exercise) that if for the current value of , then the next higher (lower) value of which creates a tie in (7) must involve consecutive a consecutive pair of items ( ). Moreover, again waving off degeneracy (in this case meaning more than two items with reduced cost 0), if we nudge slightly beyond the value at which items and have reduced cost 0, the only change to the sort order is that items and swap places. No further movement in that direction will cause and to tie again, but of course either of them may end up tied with their new neighbor down the road.

The second phase, starting from , proceeds as follows. For each pair compute the value of at which ; replace that value with if it is less than the current value of (indicating the tie occurs in the wrong direction). Update to , compute from (7), and compute from (5) and (6). If is primal feasible (which reduces to and ), stop: is optimal. Otherwise swap and in the sort order, set (the reindexed items and will not tie again) and recompute and (no other are affected by the swap).

If the first phase did not find an optimum (and if the greedy heuristic at the start of the second phase did not get lucky), the second phase must terminate with an optimum before it runs out of values of to check (all ). Degeneracy can be handled either with a little extra effort in coding (for instance, checking multiple combinations of and in the second phase when three-way or higher ties occur) or by making small perturbations to break the degeneracy.