Sunday, August 21, 2011

Piecewise-linear Functions Redux

A recent question on OR-Exchange about step functions in mathematical programs made me decide to update an earlier post about piecewise-linear functions.

In the prior post I dealt with continuous piecewise-linear functions (of a single variable) in mathematical programs. As a quick recap, if the function represents a diseconomy of scale (convex in the objective of a minimization problem or concave in the objective of a maximization problem), as in the first plot below, it can be modeled strictly with linear inequality constraints (no binary variables needed). Note that convexity implies continuity everywhere except possibly the endpoints (where you can have a jump discontinuity and still be convex or concave). The method I previously described requires continuity at the endpoints as well.

If the function is continuous but lacks the appropriate convexity/concavity, as in the next plot (which is neither convex nor concave), the all-inequality trick fails. It may also fail for convex or concave functions that appear in constraints, either because the convexity of the function does not match the direction of the inequality (you have $f(x)\ge b$ where $f()$ is convex or $f(x)\le b$ where $f()$ is concave), or because $f()$ is tied to other variables in the constraints in such a way that there is a diseconomy of scale to the direct contribution of $f()$ to the objective value but an economy of scale overall (overestimating the value of convex $f()$ or underestimating the value of concave $f()$ allows the other variables to take values that should be infeasible given the value of $x$). If $f()$ appears in any constraints and you are not absolutely certain that it matches the directions of the constraints in which it appears and represents an overall diseconomy of scale, treat it as an arbitrary continuous piecewise-linear function, as discussed next.
Again recapping the previous post, for an arbitrary continuous piecewise linear function $f(x)$ with break points $a_{1}\lt a_{2}\lt\cdots\lt a_{n+1}$ and values $f_{i}=f(a_{i})$ at the break points, we introduce continuous variables $\lambda_{1},\dots,\lambda_{n+1}$, add the constraint $\lambda_{1}+\cdots+\lambda_{n+1}=1$, and tell the solver that the $\lambda$ variables form an SOS2 set. We then add the constraint $x=a_{1}\lambda_{1}+\cdots+a_{n+1}\lambda_{n+1}$ and replace $y=f(x)$ with $y=f_{1}\lambda_{1}+\cdots+f_{n+1}\lambda_{n+1}$. If the solver does not understand SOS2 sets, it is necessary to introduce binary variables (as described in the previous post).

Step functions, such as the one plotted below, are not continuous, so nothing from the earlier post applies to them. Suppose we have break points $a_{i}$ as above, with $f(x)=f_{i}$ when $a_{i}\le x\lt a_{i+1}$. The first problem we confront is that mathematical programs abhor strict inequalities. To a mathematical programming solver, there is no difference between $x\lt a_{i+1}$ and $x\le a_{i+1}$ unless $x$ is a discrete variable (i.e., there is a largest possible value for $x$ strictly less than $a_{i+1}$. That will not be the case here, so we will simply have to deal with the fact that if the solver decides it wants $x=a_{i+1}$, it will set $f(x)$ arbitrarily to whichever of $f_{i}$ and $f_{i+1}$ makes for the better objective result.

To model a step function, we use an SOS1 rather than SOS2 set. Add binary variables $u_{1},\dots,u_{n}$ constrained by $u_{1}+\cdots+u_{n}=1$, declare them to be an SOS1 set, and include the constraints \begin{eqnarray*} \sum_{i=1}^{n}a_{i}u_{i} &\le & x &\le &\sum_{i=1}^{n}a_{i+1}u_{i}\\ y & &= && \sum_{i=1}^{n}f_{i}u_{i}. \end{eqnarray*} (Explicit declaration of the SOS1 set may not be necessary; some solvers recognize SOS1 sets automatically, and some may not exploit the useful properties of an SOS1 set even if the set is identified for them by the modeler.)

One last point: both the SOS1 and SOS2 methods require that $x$ have a finite upper bound ($a_{n+1}$). That upper bound will show up as a coefficient in the constraint matrix. The larger it is, the more likely the model is to be numerically unstable. So avoid the temptation to set $a_{n+1}$ equal to the largest floating point value your compiler can handle. Infinity is not your friend here.

Hmm. This is all a bit dry.  Maybe a soundtrack would help? 


Saturday, August 20, 2011

The Heisenberg Budget Principle

Watching Congress turn sirloin into (bad) hamburger during the recent borrowing limit debate/debacle, I realized that the Heisenberg Uncertainty Principle translates somewhat cleanly from particle physics to political economics:
The difference of two numbers can simultaneously have both positive and negative sign, depending on the position of the viewer (left or right side of the aisle).
I don't think this actually works in the real universe, but in the bubble universe of Washington D.C. it appears to hold.

Edit: I confess that I suck at physics. This probably is a manifestation of Einstein's special relativity rather than Heisenberg's uncertainty principle. First, it's not the act of observing the difference from a particular vantage point that makes it positive or negative; it's the location of the observer (and/or the observer's velocity toward the extreme of his/her party's ideology). Second, there is no uncertainty involved: one party is absolute, irrefutably certain the difference is positive; and the other party is equally certain the difference is negative. To admit a grain of doubt is to cause your party's bubble universe to collapse noisily and, worse still, to concede the possibility the other guys are right (this once).

Tuesday, August 16, 2011

Spontaneous Reboots

Mint Katya (a derivative of Ubuntu Natty Narwhal) on my AMD-64 system has suddenly developed a penchant for spontaneously rebooting.  So far, it has only happened while I'm typing. I think it has happened twice when I was typing messages in Thunderbird and once or perhaps twice when I was typing in the Yoono plug-in for Firefox. I don't recall any recent updates to T-bird, Firefox or Yoono, nor have I changed my keyboard (in case this is related to n-key rollover -- my fingers sometimes get ahead of my brain when I'm typing). The mosquitoes have gotten quite aggressive (and numerous) around my house; maybe they drove some gremlins indoors?

Update #1: I was sloppy above. It's not Mint that is rebooting; it's the X server. This is apparently a common problem,although the variety of symptoms posted there suggest that this is in fact multiple distinct bugs with a common end result (X crashing). Things I have discovered:
  • Unlike several of those reports, I have not experienced any crashes as a result of clicking. Only typing triggers a crash.
  • Unlike the reports from laptop users, power management is not the culprit (the machine that crashes for me is a desktop).
  • Someone pointed the finger at running the AMD-64 version of Natty on an Intel CPU. My copy of Mint is in fact based on the AMD-64 Natty, but my box has an AMD-64 CPU.
  • Turning the proprietary nVidia driver off and then on did not help. (I have a GPU from nVidia.)
  • Installing xserver-xorg-video-nv did not help.
Update #2: I used the wizardous sgfxi script to update my nVidia drivers a few days ago. Since then I have had no spontaneous X crashes. I hesitated to claim victory lest it be premature, but today I wrote a moderately lengthy blog post (touch-typing at my usual subsonic speed) with nary a glitch. So hopefully the driver reload cured this problem. Thanks to Harald Hope for a handy script!

Update #3: See this post for earlier problems and this post for a later round of nVidia issues (and how I resolved them).

Friday, August 12, 2011

Q&A Sites for Engineers

One of the authors at Online Engineering Degree asked me to mention an article there: 25 Q&A Sites for Engineers.  It's a compendium of links to exactly what the title describes.  I'm not sure anyone reading this blog will be interested (industrial engineering does not seem to get much play among the sites listed), but I'm happy to pass the link along.

Saturday, August 6, 2011

Tab Completion Bug in Mint 11

This is really a tab completion bug in Ubuntu 11.04 - and may actually be a pair of bugs (I'm not sure), one not the fault of Ubuntu.  Details can be found in this bug report. The short form is that command line tab completion (where you start typing a path and hit TAB to complete it) started breaking down on one of my Mint machines. Hitting TAB would add an unwanted space at the end of the path (forcing me to backspace if I were not yet done) and also failed to escape spaces.  In fact, if I typed the portion of the path containing the space and escaped it, then hit TAB, the escape character (backslash) would be removed.

The bug report contains two possible fixes. As it happens, I had started out with Acrobat Reader 9 installed from the repository on this machine, then replaced it with the version downloaded from Adobe's web site.  This is my 64 bit box, and there's an issue with Acrobat Reader looking for 32 bit versions of libraries (which I have installed), finding the 64 bit versions instead, and tripping over them.  I thought maybe using the Adobe version would fix the problem.  (It did not.)

At any rate, I tried one of the two suggestions in the bug report: deleting /etc/bash_
completion.d/acroread.sh (which is a symlink to a script that comes with the Adobe version of Reader). That seems to have fixed the tab completion bug (knock on virtual wood). It does not seem to have done any harm to Reader, either.

Thursday, August 4, 2011

A GNOME Panel Hack

Linux Mint 11 (Katya), built on Ubuntu 11.04 (Natty Narwhal), continues to act goofy at times, notably with intermittent boot failures on both my home PC (AMD 64 bit quad-core) and my laptop (Intel 32 bit dual-core).  On the desktop, when a boot fails I get a set of messages that stop abruptly; the failure point is a bit random (sometimes it stops after the battery check, sometimes it goes deeper).  On the laptop, the screen stays blank; two of the LED indicators (either numeric lock and caps lock or caps lock and scroll lock; I forget which pair) blink in unison.  On both machines, rebooting eventually succeeds.

Another intermittent problem has to do with the GNOME panel. Again on both machines, I sometimes get a message that one of the panel components failed to load (sometimes the indicator applet, sometimes the clock applet, this morning the Mint Menu button).  I'm asked if I want to delete it, to which I always reply in the negative.

Killing the GNOME panel will cause it to spontaneously regenerate, and usually it regenerates correctly.  (Occasionally it needs to be killed a second, or even third, time.)  So I cobbled together a menu entry to do this.  I put a file named Fix\ Panel.desktop into ~/.local/share/applications.  The contents of the file are listed below.  Now all I have to do is click the Menu button, find "Fix Panel" and click it to (hopefully) repair the panel.

#!/usr/bin/env xdg-open

[Desktop Entry]
Version=1.0
Type=Application
Terminal=false
Icon[en_US]=gnome-panel-launcher
Name[en_US]=Fix Panel
Exec=killall gnome-panel
Comment[en_US]=Restarts GNOME panel if it's glitched
Name=Fix Panel
Comment=Restarts GNOME panel if it's glitched
Icon=gnome-panel-launcher