Monday, October 22, 2012

Thanks a Bunch, Twitter!

At the INFORMS 2012 panel session on social media, I suggested that people interested in dipping a toe into the waters use Google Reader to watch RSS feeds of various things, including Twitter timelines. Ironically, a few days before the session (October 11 by my estimation), Twitter made API changes that broke existing RSS feeds. The feeds I was watching in Google Reader all stopped updating at the same time (last visible entries dated October 10).

Twitter unveiled their new API in September and, among other things, dropped support for RSS. RSS feeds are still available on an interim basis, but apparently they'll be gone for good as of March 5, 2013. Hopefully Google will come up with a workaround for Google Reader by then.

In the meantime, if you want to read tweets in Google Reader, you need to reload your Twitter RSS feeds. After a lengthy web search, I found a tip on this thread that, combined with something I picked up on another site (which one I no longer remember), seems to work.

I'm assuming you already have a Google account and use Google Reader. Open a new browser tab and paste the following verbatim in the URL bar:

http://www.google.com/reader/view/feed/http://api.twitter.com/1/statuses/user_timeline.rss%3Fscreen_name%3D

Don't hit Enter yet; we're not quite done. Append the screen name of the Twitter account you want to follow in Reader. For instance, to follow me (and, trust me, I do not recommend this), add parubin after %3D. Now hit Enter. If you're lucky, you'll be told that you Reader found the feed and be given an opportunity to subscribe to it.

Here's where it gets tricky. The screen name is case-sensitive; but sometimes the correct case does not work, and you have to experiment with intentional errors. (No, I'm not making that up.) I just tried to subscribe to my own feed (against my own advice above) using

http://www.google.com/reader/view/feed/http://api.twitter.com/1/statuses/user_timeline.rss%3Fscreen_name%3Dparubin

and was told my feed does not exist (news to me!). So I repeated it with

http://www.google.com/reader/view/feed/http://api.twitter.com/1/statuses/user_timeline.rss%3Fscreen_name%3DParubin

(note the incorrect capitalization of the "P") and was rewarded with the option to subscribe. In another case, I tried to repair my subscription to the feed for @ThisIsTrue. Note the camel case. Appending ThisIsTrue after %3D failed, but appending ThisisTrue (incorrect lower case on the second "i") succeeded. I'm skipping over a few unsuccessful attempts. Finding the correct single letter to muff is a trial-and-error process, happily not needed in all cases, sadly needed occasionally.


Tuesday, October 9, 2012

Detecting Multiple Optima in an LP

This is a frequently asked question: given an optimal solution to a linear program, how can you tell if there are other optimal solutions? Theory tells us that if there are two optima, there are an infinite number (any convex combination of optima is optimal). What in the output tips us off this is going on? The answer is sensitivity analysis. Any LP software worth its price will provide sensitivity output in some form. I'll illustrate using CPLEX, but what I'll say should apply, with a little translation, to any other solver.

An Example


Let's consider a simple LP with multiple optimal solutions:\begin{eqnarray*}\textrm{maximize } x\\ x & \le & 1\\ x + y & \le  & 3 \\ x, y & \ge & 0.\end{eqnarray*} The feasible region and two optima (blue dots) are depicted in the following graph:

The optima occur at $(1,2)$ and $(1,0)$.

Ordinarily, the hyperplane (isoquant) corresponding to the objective function at its optimal value (the set of all points where the optimal objective value is reached)  is tangent to the feasible region of an LP at a single point. Tilt it a little and it is still tangent at the same point. When multiple optima occur, the isoquant is tangent along a face of dimension greater than zero, as in this picture (where it is tangent along the vertical segment between the blue dots). Now think about what would happen in the illustration if we perturbed the slope of the objective function slightly. If we tilted it at all upward (say, maximize $x + \epsilon y$ for small positive $\epsilon$), $(1,2)$ would be the unique winner ($1 + 2\epsilon \gt 1$).

If we tilted it at all downward (say, maximize $x - \epsilon y$), $(1,0)$ would be the unique winner ($1 \gt 1-2\epsilon$).

So the tipoff that you may have multiple optima is that there is some objective coefficient which, if perturbed at all in the wrong direction, causes the current optimal solution to cease to be optimal.

Sensitivity Output for the Objective Function


I coded this model in CPLEX, entering the constraint $x\le 1$ as an upper bound on $x$ rather than as a functional constraint (but the end result would be the same either way). The Java API for CPLEX contains a method, IloCplex.getObjSA(), that takes as arguments two double precision vectors and a vector of variables, and returns the lower and upper limits for the constraint coefficients in the first and second vectors respectively. As long as any one objective coefficient changes but stays between its upper and lower limits, and the others stay constant, the current optimal solution is known to remain optimal. Here's the results of a call to getObjSA (along with the current objective coefficients):

Objective Coefficient
VariableLowCurrentHigh
$x$01$+\infty$
$y$$-\infty$00

CPLEX does not literally return values of $\pm \infty$; I'm interpreting anything with magnitude $10^{20}$ or larger as $\infty$. Note that the upper limit of the objective coefficient for $y$ matches its current value ($0$). Any increase in that coefficient, however small, jumps to a new solution. That is the signal of a possible alternate optimum.

"Possible" Alternate Optimum?


There's one small catch with this. Having an objective coefficient at its upper or lower limit is a necessary condition for an alternate optimum to exist, but not quite a sufficient one. Suppose we change our objective to maximizing $x+2y$ and add one more constraint to our example: $x+2y \le 0$. The feasible region collapses down to just the origin (which must therefore be the optimal solution), and the origin is a degenerate corner (more than the requisite number of constraints, two in this case since we are operating in $\mathbb{R}^2$, are binding).
Here is the objective sensitivity table:

Objective Coefficient
VariableLowCurrentHigh
$x$11$+\infty$
$y$$-\infty$22

This time we have two signals of a possible alternate optimum: the objective coefficient of $x$ is at its lower limit, and the objective coefficient of $y$ is at its upper limit. From the graph, though, it is clear that no other optimum can exist (since no other feasible point exists).

As with the objective function, we can get sensitivity information for the right-hand sides of constraints (IloCplex.getRHSSA()) and variable bounds (IloCplex.getBoundSA()). If any one right-hand side or bound changes but stays within the indicated range, with all other right-hand sides/bounds remaining constant, the current basis remains a valid basis (although the values of the variables will change). Violate a range and the basis may change. Degeneracy is signaled by a right-hand side or bound that has no room to move in one particular direction.

For our modified example, the sensitivity tables are as follows:

Lower BoundUpper Bound
VariableLowCurrentHighLowCurrentHigh
$x$$-\infty$0001$+\infty$
$y$-0.5000$+\infty$$+\infty$

ConstraintLowCurrentHigh
$x+y\le 3$03$+\infty$
$x+2y\le 0$001

We have three signals of degeneracy.

The Bottom Line


The first thing to look at, when trying to detect alternate optima, is the objective ranging table. A coefficient at one of its limits is a necessary condition. The next step is a bit less obvious. You can check bound and constraint sensitivity. If there are no signals of degeneracy, the necessary condition becomes sufficient: you have other optima. If degeneracy is present, however, that does not rule out alternate optima; it just means the objective ranging condition is not sufficient to be sure.

One way to resolve the uncertainty (and also find another optimum, if one exists) is to select one of the objective coefficients which is at a limit, and nudge it just a little past that limit. Then solve the modified LP, verify that the new solution is not the old solution (i.e., that you nudged the coefficient enough to jump to a new vertex of the feasible region). Finally, evaluate the new solution using the original coefficient and verify that the objective value matches the original optimal value (i.e., that you did not nudge the objective coefficient too far).

Friday, October 5, 2012

Updated Java Command Line Utility

A couple of years ago, I posted source code for a (massively over-engineered?) Java utility I wrote to parse command line arguments. Recently, I added a new capability. The utility will let you specify options using "key value" or "key=value", where keys can be case-sensitive or case-insensitive at your discretion, and the "=" separator can be changed to any character. (The utility also understands toggles and positional arguments, and can cope with excess arguments on the command line.) The new capability allows you to use the same key more than once (if you declare it to be reusable), with the values found returned in a list.

If you're wondering why I would want that feature, the specific motivation was to let me put multiple CPLEX parameters on the command line without having to declare a zillion keys. (If you don't know what CPLEX is, don't worry about it.) So a command line in one of my programs might look like

... -p TiLim=30 -p PreInd=false -p MIPEmphasis=3 ...

with "-p" translated as "here comes another bleeping parameter to set".

The updated utility (including a test program to demonstrate its capabilities) is now posted here. As before, I'm releasing it under the Apache 2.0 license.

Update: The utility, which also includes methods to parse file specifications with wildcards and find matching files, is now available from Sourceforge under the name JCLILIB, still under the Apache 2.0 license.

Tuesday, October 2, 2012

Setting CPLEX Parameters

UPDATE: I have new versions of the code, and a new post (superseding this one) documenting how to get and use the code.

When I write Java programs that link to CPLEX (typically for research purposes), I often want to specify some CPLEX parameters, such as time limit for runs, on the command line. Unfortunately, CPLEX has about as many parameters as the US tax code has loopholes. When I know I'll only be tweaking a few parameters, I write code the looks specifically for those parameters, which is mildly tedious. For a current project, though, I want to open a wider range of parameters to experimentation, and writing code to check for each one in the command line would be brutal.

So I wrote a Java class that lets the user set any CPLEX parameter by specifying the parameter name (case-sensitive) and value in strings, the way they would come from the command line. Suppose, for example, that I have a Java program in a JAR file named myprog.jar, and I want to set a time limit of 37.5 seconds and turn off the presolver. My command line would look like

java -Djava.library.path=<path to CPLEX> -jar myprog.jar TiLim 37.5 PreInd false

The code would look like the following:

try {
  IloCplex cplex = new IloCplex();  // create a CPLEX critter
  // assume the command line stuff is in String args[]
  CplexParamSetter.set(cplex, args[0], args[1]); // set TiLim
  CplexParamSetter.set(cplex, args[2], args[3]); // set PreInd
  // do stuff ...
} catch (...) {
  // panic and run for the hills
}

with class CplexParamSetter properly imported and with a whole slew of exceptions it might throw correctly caught and dealt with. (The exceptions are documented via Javadoc in the code.)

I've run a few unit tests on the code, and it seems to work properly, but I make no guarantees. Feel free to download the source code for CplexParamSetter and use it under the Eclipse Public License.

Update: I just modified the code to work with CPLEX 12.5.1 (which made some changes to the Java API that affected parameter recognition). Hopefully it is backward compatible, but I've only tested against 12.5.1. Also, I moved the code from Google Drive to Bitbucket (and updated the link above).

Update: It's no longer on Bitbucket. Please use the link at the top of the post (in the red box).