Saturday, June 26, 2010

When the OctoMom Solves MILPs

This has come up twice recently (that I've noticed) in forums, so it's worth writing up for future reference. In both cases the question pertained to CPLEX, but I'm pretty sure other contemporary mixed-integer linear program (MILP) solvers behave similarly. The question is: how can you create more than two child nodes from a single parent node in the search tree of a MILP?

MILP solvers typically use some version of branch-and-cut, and it's important to distinguish between their default behavior, what they'll let you do if you take control (typically through callbacks), and what is completely off the table. Although branch-and-cut lets you separate a node using any number and sort of constraints (so long as they are linear), most solvers default to an old-fashioned branch-and-bound behavior, in which a parent node is separated into two child nodes by taking one integer variable $x$ (with possibly infinite bounds $a\le x\le b$) and a current non-integer value $\hat{x}$ and rounding down in one node ($a\le x\le\left\lfloor \hat{x}\right\rfloor $) and up in the other ($\left\lceil \hat{x}\right\rceil \le x\le b$). If the solver supports callbacks, however, chances are it lets you impose your own, more general, separation of a node. CPLEX in fact does this, allowing linear inequality cuts ($h^{\prime}x\le k$ in one child, $h^{\prime}x\ge k+\Delta k$ in the other child), multiple linear cuts, and mixes of linear cuts and bounds. CPLEX does have a firm limit of at most two children per parent, however. So what if you want to split a parent node $P$ into $n>2$ children $C_{1},\ldots,C_{n}$, using sets of cuts/bounds $S_{1},\ldots,S_{n}$? (We'll charitably assume that the feasible regions for nodes $P\cup S_{1},\ldots,P\cup S_{n}$, possibly empty in some cases, are disjoint; otherwise it's not really a valid separation.)

The answer, while perhaps not elegant, is at least simple: create two children, $C_{1}$ and "not $C_{1}$" (which I'll designate somewhat more formally as $\tilde{C}_{1}$). Then separate $\tilde{C}_{1}$ into $C_{2}$ and "not $C_{2}$ either" ($\tilde{C}_{2}$), etc., ad nauseum. The nodes $C_{1},\ldots,C_{n}$ will look more like cousins than siblings -- they won't be on the same level of the search tree -- but that really has no practical effect.

Here's a picture of a simple problem in which variable $x\in\{1,\ldots,4\}$ and I'd like to create four children under the root node, one for each possible value of $x$:

It's possible that the constraints to add for one of the "tilde" children are not obvious. For instance, $\tilde{C}_{1}$ is defined by the union $S_{2}\cup\ldots\cup S_{n}$, which might not have nice compact representation. Not to worry: define $\tilde{C}_{1}$ as essentially a clone of parent node $P$ by adding some innocuous constraint (for instance, $y\ge0$, where $y$ is already defined as nonnegative) -- unless the software lets you create a clone child by adding an empty set of cuts (doubtful, but perhaps some program will allow that).

Related posts:

Friday, June 25, 2010

Expanding Recipient Lists in Thunderbird

Sometimes dealing off the bottom of the deck saves a lot of time.

I really like Thunderbird (the Mozilla mail/news/RSS program), but like any software it has its imperfections, one of which particularly bugs me. I get a lot of mail (jokes, slide shows, movies) that I want to circulate to the same list of people. That much is easy: I just created a mailing list in one of my Tbird address books, containing all the names and addresses. The problem is that the inbound message usually comes from someone on the list, and I don't want to send it back to them. So the plan is to blind carbon the list, delete the person who sent it to me, and ship it ... except that Tbird does not expand the list in the Bcc: (or To: or Cc:) field.

Searching on line, I discovered that I'm far from the only person bothered by this omission. I used to fudge it by creating a pseudo-individual (rather than a mailing list) whose e-mail "address" was actually a list of all the addresses. Tbird would duly fill in this long list in one Bcc: line, and then hitting enter or tab in that line would split it into individual lines that could be selectively edited. That stopped working reliably a version or so ago (the wages of exploiting an undocumented "feature"), so it was back to Google, where I found the answer: a nifty extension called AddExpandedList. Select the list in the contacts panel, right click it, and you have options to add the list in expanded form to any one of To:/Cc:/Bcc:.

I found it a few days ago and added it to all three of my Thunderbird 3.0 installations. So of course Mozilla came out with the upgrade to TB 3.1 today, and it blocked AddExpandedList on the grounds that it was allegedly incompatible with TB 3.1. Sigh.

That led me to start looking for information, tutorials etc. on how to write a TB extension. Skipping an hour or so of travail (out of date information, stuff that made my eyes water, ...), I found the Mozilla Add-on Builder, a wizard that asks you a few questions and then hands you the skeleton of an extension. That doesn't get you very far, since you still have to do the coding yourself. In looking at what the builder gave me, though, I noticed that the install.rdf file (which essentially tells TB what it's about to install) contains a field maxVersion that gives the highest TB version number with which the extension is compatible. (If this were a cartoon, a lightbulb would pop up over my head at this point.) So I opened the installation package for AddExpandedList in a zip utility, opened its version of install.rdf in a text editor, and sure 'nuff it had maxVersion=3.0*. I changed that to 3.1 and TB happily re-installed the extension (which works just dandy with TB 3.1). Saved me who knows how many hours of trying to learn how to write my own extension!

(Update: Not too long after I posted this, a new version of AddExpandedList came out that works with TB 3.1.)

Monday, June 14, 2010

Remote File Synchronization in Mint/Ubuntu

File sync software is one of those things where personal taste counts for a lot. On my Windows PCs the best free sync software I've found is PathSync by Cockos Inc. SynchronX, which I believe is no longer supported but can still be found on free download sites, is also very good (I used it before I found PathSync), but SynchronX had one significant weakness (which I suspect is really Microsoft's fault): every time we switch between standard and daylight savings time, all files appear to be out of sync due to an hour difference in time stamps. PathSync has an option to consider or ignore file dates (time stamps), and there's a cute "in between" option that considers the time stamps but ignores differences of exactly one or two hours to allow for daylight time nonsense.

Now, though, I work mostly in Linux (Mint/Ubuntu). I've been using PathSync (running under Wine) to sync my laptop/desktop with my USB memory stick, but today I decided to bite the bullet and try direct syncs between my laptop and desktop, using SSH. I've experimented with Conduit before but had bad luck, and it's not clear to me that Conduit would give me the file-by-file granularity of control that I want. So I installed Unison (and the GTK GUI package for it) on both machines. Unison's interface is a pain, though. You have to scroll over each individual file to see what the difference is, you apparently cannot select multiple files when you want to specify actions (at least I couldn't see how), and clicking "skip" while a file was selected didn't change the action field (which read '?'), so I wasn't sure the file would actually be skipped. Ultimately, syncing large directories would have taken too much manual effort, regardless of how quickly the actual file transfers might have gone, so I punted (and ultimately uninstalled Unison).

That brought me back to PathSync. The answer turned out to be surprisingly easy. I installed sshfs (there are very clear, easy instructions at, and permanently mounted my office PC's home directory on my laptop. Since PathSync, under Wine, can see the local file system (including /mnt), I can use it to sync any local directory with any remote directory (at least anything under my remote home, since that's what I mounted). Navigation in the file browser has a bit of latency, but file comparisons and file transfers are fairly sprightly, and I have the level of control I crave. Sweet!