Monday, April 25, 2016

Matching Ordering Is Not Always Easy

In some circumstances, you might want to build an optimization model containing two sets of variables, say $x_1,\dots,x_N$ and $y_1,\dots,y_N$, and constrain them so that the sort order of each matches. That condition is easily expressed in logical terms: $x_i \ge x_j$ if and only if $y_i \ge y_j$ for all pairs $i,j \in \{1,\dots,N\}$ with $i\neq j$. Translating that into a mathematical programming model that is easy to solve may be tricky, though.

I'm thinking specifically of situations where you want your model to be a linear program or, at worst, an integer linear program. It is well known that linear programs have convex feasible regions, and that is the basis for most algorithms. For integer or mixed integer problems, solvers again rely on convexity, in two respects: the continuous relaxation of the model (relaxing integrality constraints) should have a convex feasible region; and the restricted problem obtained by fixing values for the integer variables should have a convex feasible region.

What makes the order matching constraint tricky can be seen in Figure 1 below. Let's assume for simplicity that $N=2$. Figure 1 shows a two dimensional space spanned by $x_1 - x_2$ and $y_1 - y_2$, with the set of points satisfying the ordering constraint (the first and third quadrants) shaded green. If we relax any integrality restrictions in the original model and project its feasible region (linearly) onto this plane, the "shadow" of the feasible region must lie within the green area.

Figure 1: first and third quadrants shaded with line segment showing the union is not convex
Figure 1

Assuming the original feasible region (again, with any integrality restrictions relaxed) is convex, the way we want (need?) it to be, its projection will also be convex. The green area, though is not convex. The blue dotted line segment connects two feasible points but obviously leaves the green region. When we "cut away" the portion of the original feasible region that projects onto the white areas, we gain enforcement of the ordering constraint but may lose convexity of the feasible region.

So, are we screwed (to use a technical term)? Not necessarily. The projection of the original feasible region is unlikely to fill the green quadrants, and other constraints may cooperate to force the projection to remain convex. Figure 2 shows a somewhat trivial case, in which the original model also contains the constraint $x_1 - x_2 = y_1 - y_2$. That constraint by itself will cause the ordering restriction to be satisfied. The projection of the feasible region is the red line in Figure 2, which is clearly convex.

first and third quadrants shaded with a diagonal line through the origin
Figure 2

The takeaway from Figure 1, at least for me, is that getting the ordering constraint in while preserving convexity will be tricky in general (unless you get "lucky" courtesy of other constraints). Since the green area is the union of two convex sets (cones, to be specific), a standard way to finesse the convexity issue is to add a binary variable indicating which cone you are in. (See, for instance, Partitioning with Binary Variables.) Once the value of the binary variable is fixed, the feasible region is restricted to a particular quadrant (cone), and you can stop worrying about loss of convexity. You need a binary variable for each pair of subscripts, though, so in the general case this introduces $O(N^2)$ binary variables, which might get a bit annoying.

If all the variables are bounded and either $x$ or $y$ is integer valued, there might be a less cumbersome way to handle the ordering constraint, but that's a topic for another day (or never, whichever comes second).

Saturday, April 9, 2016

SOLVED: Problem with Impressive

I've written before (here and here) about using the open-source Impressive program to display PDF presentations. It's been quite a while since I used it, or any other presentation software for that matter -- retired geezers don't do a lot of presenting -- but I'll be helping the INFORMS Student Chapter at the University of Louisville catch up on their sleep this coming week, so I thought it was time to install something on my laptop. A quick Google search revealed that not much has come down the pike in recent years to rival it, so I installed Impressive. The version in the Canonical repositories is a bit dated, so I got the current version from Liviu Andronic's PPA. (Thanks, Liviu, for maintaining this!)

Impressive (and various dependencies) installed just fine, but when I tried to open one of my slide shows, I got the following error:
Warning: The input file `<path to my file>' could not be analyzed.
The presentation doesn't have any pages, quitting.
So I tried opening a random PDF I had lying around my laptop's desktop screen, and lo and behold it opened! After banging on Google and finding mostly rather antiquated posts, the most plausible explanation I could find was something about graphics being produced in a "recent" (several years ago) version of PDF and the current (back then) version of the PDFtk toolkit (pdftk) having a bug, with the suggested fix being to revert to an older version of pdftk. I looked in the Synaptic package manager to see what version I had, and it turned out the answer was none!

I installed pdftk (and necessary dependencies) from the Canonical repositories, and that fixed the problem. Impressive now worked just fine with my presentation. This leaves me with a few observations:
  • Neither pdftk nor any of the dependencies that installed with it must be absolute dependencies of Impressive, since Impressive was able to display the second file I tried without having pdftk etc. installed.
  • The pdftk bug mentioned in the old posts has, I'm pretty sure, long since been fixed ... and, in any case, that wasn't the problem, since I did not have any version of pdftk, buggy or not, installed.
  • Either pdftk or one of its dependencies, while not strictly required to run Impressive, must be required to correctly parse something (all graphics? some graphics? something to do with the use of overlays?) in my presentation.
Bottom line: I don't fully understand what happened, but at least it works now.

Sunday, April 3, 2016

Tale of the Loose Cable

Friday I used my laptop (Acer Aspire V5-131, Linux Mint 17.3) at a coffee shop with no problems. Saturday it wouldn't boot. The specific error message was:
Broadcom UNDI PXE2.1 v15.0.1
<blah blah blah>
PXE-E61: Media test failure, check cable
PXE-M0F: Exiting Broadcom PXE ROM
No bootable device -- insert boot disk and press any key
The message suggests that either the hard drive was down, the data cable to the hard drive was loose (or broken), or the hard drive was somehow no longer bootable. Searching online essentially confirmed that.

I opened up the laptop and confirmed that the ribbon cable seemed to be connected at both ends. That was a bit worrisome. Could the disk be dead? Then came one of those good news/bad news situations. I booted the laptop from a live Mint USB drive. Once I was at the desktop, I was able to mount the hard disk and read it just fine. So the disk was not dead, which was the good news. The bad news was that this sent me off on a wild goose chase.

If I could read the hard drive when I booted from a USB, but I couldn't boot from it, logic said that the boot partition must either be corrupted or no longer marked as the boot partition. Right? A few episodes of cycling the power off and on confirmed that it consistently could read the hard disk when started from the USB stick and consistently could not boot from the hard disk. Only problem: running off the USB stick, I could read the boot partition just fine, and gparted confirmed that it was marked as the boot partition.

Unwilling to abandon my chase of the wild goose, I did the only thing I could think of: I reinstalled Mint (forcing me to update or reinstall tons of software -- still not done with that). After the reinstallation, the laptop booted from the hard disk just fine. I took it to the coffee shop and slugged down coffee while some of the software updates ran. Things were back on track ... until I got home and discovered it once again would not boot from the hard drive (same message as above). Grrrr.

Turns out a loose cable was at fault. It just didn't look (or feel) loose. In hindsight, the Broadcom ROM media test may just be more accurate (or more finicky) than whatever Mint does when deciding whether to mount a disk. For the benefit of anyone else staring at PXE-E61, here's a quick synopsis of what to check.

The first step is to remove the cover from the base of the laptop (Figure 1). (This might be a good time to apologize for the fuzzy images.)

laptop base
Figure 1: Laptop base

Remove one small (and easily lost!) Phillips-head screw from the base (highlighted in the photo), then slide the case in the direction indicated by the arrow and remove it, exposing the innards (Figure 2).

laptop interior
Figure 2: Laptop interior
The blue padding covers the hard disk; the arrow points to the ribbon cable connecting the hard disk to the (largely obscured) circuit board.

I'm used to cables that snap into place, but while this one connects solidly at the hard disk, the connection to the circuit board is secured largely by inertia. Figure 3 shows that end of the ribbon cable exposed. Note the metal "teeth"  (fingers? tentacles?). Also note the black line running across the width of the ribbon.

exposed cable end
Figure 3: Exposed cable end
Finally, Figure 4 shows the cable pushed all the way in at the circuit board end.

cable plugged in
Figure 4: Cable plugged in

You can see a light colored plastic tab covering the teeth of the cable, with a dark colored (and, it turns out, removable) plastic widget underneath the cable (visible on either side of the cable). Getting the cable to slide in between them is a bit of a pain in the ass. I don't know whether the dark plastic piece is a guide that was originally glued to the cable or not. In any case, the key is that the black line running across the width of the cable is close to the plastic stuff and, importantly, none of the metal teeth (fingers? tentacles?) are showing. If you see any portion of the teeth (connectors), the cable may be making intermittent content.