Fischetti on Benders Decomposition

I just came across slides for a presentation that Matteo Fischetti (University of Padova) gave at the Lunteren Conference on the Mathematics of Operations Research a few days ago. Matteo is both expert at and dare I say an advocate of Benders decomposition. I use Benders decomposition (or variants of it) rather extensively in my research, so it ends up being a frequent theme in my posts. Those posts tend to generate more comments than posts on other topics. Apparently Matteo and I are not the only BD users out there.

I don't know that I would recommend Matteo's presentation as the starting point for someone who has heard of BD but never used it, but I certainly recommend having a look at the slides for anyone who has any familiarity with BD. Matteo provides several interesting perspectives as well as a tip or two for potentially improving performance. I learned a few new things.

In a sad coincidence, Professor Jacques Benders, the originator of Benders decomposition, passed away at age 92 just eight days before Matteo's presentation.

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.

More Presentation Software

I previously wrote about the tools I use to create presentations. Lately, I've been looking for tools that allow an instructor to:

• annotate files being projected (from a PC or laptop, through a digital projector);
• turn the display into a whiteboard and draw on it;
• share the screen between slides and a whiteboard (some of my colleagues like to work homework problems by hand while simultaneously displaying either the problem statement or the relevant formulas); and
• save some of the better doodling as an image (to be uploaded to our course management system).

The motivation for this is largely that we grown our classroom technology incrementally, adding features on top of features in rooms that were not designed for them. A particular recurring theme is rooms with wall-mounted whiteboards that are largely obscured by screens for the digital projectors (leaving a small margin on either side accessible to the instructor).

I've come across several useful programs that I thought I'd list here.  (I'm still working on the other piece of the puzzle, which is finding appropriate and reliable input methods.  My attempts to write with a mouse cause MDs to giggle uncontrollably.)  I should mention that I'm looking for tools for multiple platforms:  our classroom PCs are predominantly Windows-based, and most of my colleagues run Windows on their laptops, but I run Linux on mine and there are at least a few Mac users to be considered.  Also, I'm looking exclusively at free (preferably but not necessarily open source) software, and I'm not looking at "smart board" technology (we may get into that, but most classrooms will continue to have stupid boards, if I may be un-PC). What I've found so far:

• ZoomIt (Windows only, any version): This is a very lightweight program (267KB download; no installation, no writing to the registry) that does what it does very well.  It requires keyboard use to control but handles pen input for the actual writing.  You freeze whatever is currently on the screen (optionally zooming in on it), then draw in one of six colors (red, blue, orange, green, yellow, pink -- no black).  The width of the pen stroke can be varied.  You can draw rectangles, ellipses and straight lines by holding a key down as you go.  There's blanket erase (with one keystroke) and  incremental undo, but no redo.  With one keystroke, you can turn the entire display into a whiteboard or blackboard.  You can copy the screen (to be pasted into an appropriate program) or save it to disk (as an image).  Three caveats: if you switch among screen annotation, whiteboard and blackboard you lose your annotations; there is no way to return to presentation mode, then come back and retain your annotations; and the image capture is always the full screen (so you may need to crop in another program before uploading it to its final home).  Image manipulations can be done in a variety of programs (I recommend IrfanView).
• Ardesia (Linux, Windows Vista/7): Ordinarily I find it easier to find free/open-source applications for Linux than for Windows, but it took me a couple of hours of searching to find a screen annotation program I liked. Gromit works pretty well, but it has limited flexibility and requires you to tweak a configuration file to change pen color, etc. Ardesia seems to do almost everything I'd want.  Documentation is a bit lacking, so you need to read the tool tips and do some experimenting, but it works very well.  You can draw in any color, using one of three or four stroke widths, in one of three modes (totally freehand, or with automatic conversion of some strokes to either lines or splines).  You can also type text. If you draw an enclosed region, you can fill it (something I'm not sure I'd use much).  You can add arrow heads, erase portions of the screen (or the whole screen with one click), undo and redo, and save your screen (PDF or PNG).  There's even a recording feature (which I've not figured out yet).  Once it's running, everything is controlled from a toolbar docked on the perimeter of the screen, which is helpful when you're using a convertible laptop and the screen/tablet is covering the keyboard.  There are a few "eye-candy" options I have not mentioned (and have not installed ... yet). Ardesia is available as a .deb package for Ubuntu, and allegedly compiles on other Linux/BSD systems.  It requires a composite manager.  I have not tested the Win 7 version (yet), but it might end up replacing ZoomIt for me.  The only real drawback (other than documentation) from my perspective is that there are no ellipse and rectangle tools.  (Hypothetically I can draw polygons and ellipses in the straight line or spline mode, but so far that has proved to be purely hypothetical.)
• Whyteboard (Windows, Linux, Mac): If you want to turn your display into a whiteboard (either full screen or windowed), rather than writing on top of some other image, I doubt you'll do better than this. You get a tabbed interface (so that you can have multiple screens of writing, and switch among them at will) with a full palette of drawing tools (text, arrows, lines, basic shapes), with multiple colors and an eraser.  You can save and reopen tabs, and you can attach notes to them. Unlike the screen drawing programs, you can grab any shape and move or resize it, and change its color.  A history of your drawings is kept and can be replayed.  Audio and video players can be dropped onto the whiteboard. If ImageMagick is installed, you can suck in a PDF and draw over it.  Windows 7 (or XP tablet version) users can do some of this in Windows Journal, but having tried both I'm going with Whyteboard (plus it's cross-platform, which is useful to me). The biggest drawback I've found so far is that, while you can save your drawings in a program-specific format, there does not seem to be an image export feature.  [Editor's note:  Author is apparently blind.  Program does export images.  See comment below.] You can, however, select a portion of a tab and copy it to the clipboard, so you can paste it into a program (such as IrfanView, which incidentally runs fine on Linux under Wine) and then crop, rotate, fiddle and export.

Now if I could just like that illegible screen writing problem ...

Using Impressive on Mint/Ubuntu

I've earlier mentioned Impressive, a very handy program for presenting slide shows done as PDF files (e.g., using the LaTeX beamer class).  Today I finally managed to get a couple of features working on my laptop (Linux Mint "Helena") that had eluded me until recently.

• The tab key toggles an overview mode where you can see (and jump to) any slide in the show. Beamer's method of displaying bullets etc. incrementally on a slide is to create a new PDF page for each "overlay"; so a slide ("frame") with five bullet items would occupy five pages in the PDF file. That's fine until you use the tab key in impressive and see a few bazillion "slides" listed. The answer is to run impressive with the option -O first in the command line. Well and good, except who wants to open a shell in order to run impressive. So the answer was to right-click a PDF file, select Open With > Other Application > Use a custom command and set the command to /usr/bin/impressive -O first.  Simple enough.

• Theoretically, with the right helper software installed (pdftk), you can click on a hyperlink in a PDF file while displaying it with Impressive, and Impressive will jump to the designated page (if within the document) or open the target in a browser (if the URL points outside the document). Small problem: it has never worked for me. A web search revealed that the version of pdftk (1.41+dfsg-1) included in recent Ubuntu repositories (and thus also available in Mint's package manager) is the culprit. Downgrading to 1.41-3ubuntu1 solves the problem. This requires three steps: uninstall 1.41+dfsg-1; download and install 1.41-3ubuntu1; and, in the Synaptic package manager, mark pdftk as not to be updated (otherwise Synaptic will try to upgrade it back to 1.41+dfsg-1 every time it finds updates, and it would be easy to forget to uncheck it in some mass update).

Presentation Software

I do all my writing in LyX, a very user-friendly authoring program that employs LaTeX as its publishing engine. It makes for nice-looking output, and composing math (which I do a fair bit) is very easy once you get the hang of it. LaTeX contains numerous user-contributed packages, and I find Till Tantau's Beamer package excellent for doing presentations. The presentations are generated as PDF files (with options for handouts and notes).

Business students are a bit disconcerted by the use of PDF (as opposed to PowerPoint), but there are advantages. Not least of those advantages is a comparative freedom from Adventures in Fonts. At a conference, presenters often share a single laptop brought by one of them. A couple of years ago, I attended a conference where the presenters were split roughly equally between Beamer users (mainly I think from Europe, some from the U.S.) and PowerPoint users (mainly from the U.S.). Both groups of users tended to have equations in their presentations. This was no problem for the Beamer users (with perhaps one exception), because the necessary math fonts were embedded in the PDF files. The PowerPoint users, however, relied on the laptop having the requisite fonts installed, and approximately half the PowerPoint presentations ended up with equations that were either missing (the space was there but appeared blank) or garbled.

PowerPoint does have advantages in terms of eye-candy, though. That advantage is somewhat negated by Martin Fiedler's Impressive program. Impressive allows me to present PDF files with transitions. I use the default, which is a random mix, but the transitions can be customized. More useful features, from my perspective, are the ability to highlight parts of a slide, put a "spotlight" on a portion of a slide, zoom in and out, and use the tab key to bring up thumbnails of all the slides and then jump to the one I want. Impressive is written in Python and runs on Linux, Mac OS and Windows. Very handy!