Thursday, January 21, 2010

Linear Ordering Problems

Linear Ordering Problems (LOP) are encountered in a wide range of applications, such as ranking sports teams, triangulation of matrices (i.e., finding a reordering of the rows and columns that maximizes the total above or below the diagonal), or ordering lists of individual preferences. Recently I came across an interesting application for the scheduling of printing tasks. The data consisted of a array of entries $x_{ij}$  which give the time saved if task i is completed before task j.  The times savings were attributed to setup work done for the first task that would benefit subsequent tasks.  The problem was to find an ordering of tasks that maximize the overall time savings.

Like many problems in Operations Research, the LOP has a rich history of study and algorithm development.  LOP are  known to be NP hard, but state of the art algorithms provide for many practical uses. A somewhat older MILP formulation is easily implemented in GMPL/GLPK as shown in the Scheduling: Linear Ordering of Tasks example.

Wednesday, January 6, 2010

Setting up a Mac for Computational Work

It is not difficult to set up your Mac for work in the scientific/technical arena.  Here are some thoughts and advice based on my own experience.

1. Backup/Collaboration

First thing is to establish a backup/collaboration strategy. Obviously TimeMachine is the simplest alternative.  However, I've been using on-line services for this, in particular SugarSync and Dropbox.  I use SugarSync to maintain an on-line mirror of the Documents folder, and Dropbox to facilitate sharing of documents with collaborators. A nice advantage of these services is that they also provide web and mobile access to your files.

You likely maintain files on other servers. MacFusion (which requires MacFuse) allows you to access files on other servers as if they were local volumes.

2. Technical Documents

It's hard to beat Latex for the preparation of scientific and technical documents.  Moreover, mathematical software packages sometimes require the installation of latex to format output.

MacTeX is an excellent free distribution of the core tools needed to prepare a wide range of documents including papers, theses, and presentations (using Beamer).  Everything you need is available in one large download and simple installation. The tools include BibDesk for managing bibliographies, TexShop and TexWorks for editing and preparing documents, and the Excalibur spell checker.  Use the TeXLiveUtility to maintain the package.

Many scientific Mac users recommend Papers to manage bibliographies.  Having tried alternatives like Papers, I personally prefer BibDesk.  Though not quite as polished, by working directly with bibtex databases BiBDesk interfaces beautifully with LyX.

LyX is an almost WYSIWYG front end to Latex that generally masks the underlying markup language. If you want to use Latex without having to work directly with Latex commands, then LyX is for you.

The MacOS, of course, comes with an indispensable pdf and graphics previewer in Preview.  Skim is a freeware pdf viewer and notetaker that provides an additional capability to annotate pdf documents and enhanced presentation features.

3. General Software Utilities

Apple provides tools for software development in a separate package called Xcode that includes text editors, compilers, and other components. Many of the software tools you download from the internet require the tools contained in Xcode.   The most recent release of Xcode can be obtained at no cost by joining the Apple Developer's Connection.

There are many 'programmer's text editors' available for the Mac, including TextEdit that comes with MacOS.  TextMate is low-cost (with free trial) with bundles that adapt the editor for use in wide variety of applications.

MacPorts is a tool for finding and installing open-source software packages. MacPorts simplifies the installation of those packages which have been adapted to the Mac. MacPorts is a simple command line tool, Porticus provides a GUI interface to MacPorts.

Unfortunately, you'll occasionally come across software packages that simply are not available for the Mac.  One way to deal with this is to install Windows or Linux under one of the available virtual environments for the Mac such as Apple's Bootcamp, or Parallels, VMware Fusion, or VirtualBox. If you go that route you'll need to acquire and maintain a copy of a second operating system.  In many cases, however, the WINE package will provide enough support to run Windows software within the Mac environment.

4. Mathematical Software

Finally this brings us to the tools for actually doing computational science on a Mac.  Matlab and Mathematica are examples of commercial packages for doing mathematics on a Mac. There is an enormous variety of tools.

Here are some of the tools I find useful:
  • General mathematical computation
    • Matlab. Licensed for download to University affiliated students and faculty.
    • Octave.  A GPL licensed package with syntax similar to Matlab. Provided you have MacPorts installed, you can install Octave with the command line: sudo port install octave
    • Sage.  This is a big package based on Python that provides an enormous range of computational and visualization tools.
  • Statistical Computation.
    • Matlab statistics and econometrics toolboxes
    • R
    • Quantlib
  • Optimization
    • Gusek/GLPK (runs under WINE)
    • lpsolveIDE (runs under WINE)
    • Sage provides access to GLPK, the COIN-OR CBC package, and CVXOPT.
    • CVX, a Matlab class for convex optimization
    • YALMIP, a Matlab class for optimization with a variety of solvers
  • Python Development
    • Enthought Python distribution (using TextMate)
    • Sage