Two articles on Risk Management

Two articles on Risk Management worthwhile reading:

1. “Recipe for Disaster: The Formula That Killed Wall Street” on Wired
2. “Six Ways to Mismanage Risk” on the Harvard Business Review (exec summary freely available) – A brief summary can be also found on Aurelie Thiele’s Blog.

Tutorials for glpk

A series of three tutorials on using the GNU Linear Programming Kit (glpk) is available on the IBM website

1. The GNU Linear Programming Kit, Part 1: Introduction to linear optimization
2. The GNU Linear Programming Kit, Part 2: Intermediate problems in linear programming
3. The GNU Linear Programming Kit, Part 3: Advanced problems and elegant solutions

These tutorials deal in particular with using glpsol, the standalone mip solver and the modeling language GNU MathProg which is very similar to AMPL (actually GNU MathProg is a subset of AMPL). Several examples and well-known optimization problems are discussed, modeled, and solved using glpk.

So if you are interested in linear / integer programming with glpk and you are looking for a good introduction, you should definitely check out these tutorials. Also, glpk comes with a lot of examples that give a pretty good overview on how to formulate optimization problems in GNU MathProg. In case you are using windows you also might want to try the GUSEK IDE which wraps glpk in a nice user interface.

Also, if you have the feeling at some point that GNU MathProg is a cool modeling language (afterall it is almost AMPL but free) but you need to use a different solver like CPLEX or CBC you can still continue using your old models written in GNU MathProg or even write new ones as you can use the modeling language and the solver separately: Using glpsol (the standalone solver contained in glpk) with the appropriate parameter set, you can write CPLEX LP or MPS files for example that you can use as input for e.g., CPLEX.

UPDATE 24.01.2010: An updated version with much more information about GLPK, interfaces to other software, tutorials, etc. can be found here.

The integrity of user reviews

I was unpleasantly surprised when I had to learn from The Daily Background that companies (in this case Belkin) use services like Amazon’s Mechanical Turk to improve their online reviews by actually paying people to write positive reviews and rate bad reviews as “not helpful”. For the sake of fairness, the statement of Belkin’s president concerning this incident is available here.

Amazon’s Mechanical Turk (from their website)

is a marketplace for work that requires human intelligence. [...] Mechanical Turk aims to make accessing human intelligence simple, scalable, and cost-effective. Businesses or developers needing tasks done (called Human Intelligence Tasks or “HITs”) can use the robust Mechanical Turk APIs to access thousands of high quality, low cost, global, on-demand workers [...]

Whatever one might think about the Belkin case, it highlights three things:

1. As we might have already suspected, user reviews might be indeed bought. In this particular case it was really obvious but I would not be too surprised if there are agencies specialized in writing reviews as part of their marketing services.
2. It is not clear how one should evaluate the credibility of user reviews. Given that these reviews were actually written by different people it is rather unlikely to find a pattern – except maybe for the requested downgrading of bad reviews in this particular case.
3. How would one actually establish that the request for user reviews was indeed posted by Belkin (or one of its employees). This poses a problem of a completely different dimension: Somebody might stage such a request to deliberately damage the reputation of a company (as discussed here).

If somebody is willing to pay for such a service, there will be somebody doing the job. Actually the construct reminds me of how spam networks work: trojans or viruses take control of an infected computer and report to some kind of a central instance (in many cases IRC channels). Then when spam emails have to be sent out the master forwards the spam email to the (so called) zombies that in turn  forward it to millions of people. The catch is that it appears that the emails came from the infected computers making it especially hard to track down the spammers. Similarly in the Belkin case, expect for the fact that the human intelligence task (HIT) was discovered before it was completed (and hence automatically removed from the list of available HIT jobs). Otherwise it would have been equally hard to establish that the reviews were indeed fabricated.

One possibility (at least for Amazon) would be to allow only ratings from people that actually bought the product (which of course might pose some other problems). Alternatively, with user consent, Amazon might indicate when the user bought the product on Amazon. I guess it would cost significantly more than $0.65 (this is what the Belkin rep was willing to pay) to have somebody write a positive review for a product one wishes to not have bought in first place.

In any case, it becomes more and more apparent that we might need strong mechanism to ensure or verify identities. First, to track down questionable behavior and second to protect other entities from false accusations or other forms of misconduct. I am well aware that this discussion also has a lot of privacy related aspects that I didn’t address here…

But honestly, what is a review system good for when it lacks credibility? Just imagine the consequences in the case of scientific publications…

Also check out The Noisy Channel to learn how to trade 10 facebook friends for a whopper.

Updated version of normaliz available

Normaliz is an excellent tool to compute Hilbert bases or e.g., integral closures of rational cones. It can also be used to calculate the integral closure of solutions to a system of (in-)equalities.

From the announcement:

We have now uploaded  version 2.1 of Normaliz. See

http://www.math.uos.de/normaliz
The main changes relative to version 2.0 are:

– a Macaulay2 package written by Gesa Kämpf

– addition of (a variant of) Pottier’s algorithm for solving systems of equations and inequalities

– improvements in the user interface

See http://www.math.uos.de/normaliz/Normaliz2.1Documentation.pdf for more information.

The Cult of Genius

I just came across an interesting article on the Cosmic Variance Blog with the title The Cult of Genius. Ok the article is a bit older, i.e., from February 2007 but still worth reading.  I guess the title is self-explaining Although it, in particular, deals with physicists I suppose the message applies to other fields as well.

From the article:

While some physicists are known for their hearty support of atheism, even they can have some personal dieties. High in the physicist’s pantheon sits Richard Feynman, due not only to his obvious smarts and good work, but also to an outsized personality chonicled in a wealth of popular writings (and even a movie!). I’ve always had mixed feelings about Feynman as a cult figurehead, however. It’s nothing personal against Feynman in particular, but about the hero worship he represents. During high school or college, many aspiring physicists latch onto Feynman or Einstein or Hawking as representing all they hope to become. The problem is, the vast majority of us are just not that smart. Oh sure, we’re plenty clever, and are whizzes at figuring out the tip when the check comes due, but we’re not Feynman-Einstein-Hawking smart. We go through a phase where we hope that we are, and then reality sets in, and we either (1) deal, (2) spend the rest of our career trying to hide the fact that we’re not, or (3) drop out. It’s always bugged the crap out of me that physicists’ worship of genius conveys the simultaneous message that if you’re not F-E-H smart, then what good are you? In physics recommendation land, there is no more damning praise than saying someone is a “hard worker”.

Read more…

Poll: Which MIP solver do you use?

The recent discussions about the new Gurobi solver and its performance as compared to CPLEX  ([1], [2]) as well as the discussion about using open source solvers ([3]) made me wonder about the proportion of  people using a particular solver.  So I decided to set up a poll and find out who is using what.  There are many solvers out there… So drop me a line if you feel that another solver should be included.

MOPTA 2009 Modeling Competition

If you are interested in modeling optimization problems (and you are a grad student) you might want to consider participating in the MOPTA 2009 modeling competition. Using AIMMS and CPLEX a truck maintenance scheduling problem has to be solved:

The trucks of the transportation company “Move Efficiently” have to undergo periodic maintenance of different types ranging from changing the oil to a complete engine overhaul. The time intervals between consecutive maintenance checks of each type are pre-described based on experience and information from the truck manufacturer. The trucks become unusable if they are behind on the required maintenance. However, maintenance is expensive and trucks should not be over-maintained. The problem, therefore, is to schedule maintenance so that it minimizes costs while making sure that trucks can be used. The problem needs to be solved over a 2-year time-horizon on a weekly basis, From July 1, 2009 till June 30, 2011. There are constraints on the number of trucks that are required to be active, and capacity constraints at the single maintenance location.

After registration a copy of AIMMS and CPLEX (I suppose either a time limited or a student version) is provided. For more details see the MOPTA 2009 competition homepage.

GLPK 4.36 released / Updated GUSEK version

A new version of the GNU linear programming kit (GLPK) (one of my favorite solvers) has been released today. While not being CPLEX it is probably one of the best freely available solvers out there and it comes with its own modeling language GMPL which is very similar to AMPL. GLPK comes with an interesting feature: It has an exact simplex algorithm. The new version includes new API functions for networks and flows and can read flow data in DIMACS format:

In this release:

The following new API routines were added to the package:

glp_mincost_okalg     find minimum-cost flow with out-of-kilter
algorithm

glp_maxflow_ffalg     find maximal flow with Ford-Fulkerson
algorithm

For detailed description of these new routines and related data
structures see chapter “Graph and Network API Routines” in the
reference manual included in the distribution.

The following new command-line options were added to the solver
glpsol:

–mincost             read min-cost flow data in DIMACS format
–maxflow             read maximum flow data in DIMACS format

Also GUSEK, a freely available GLPK IDE for Windows has been updated as well to include the new GLPK 4.36 version. GUSEK is pretty decent and if you are using Windows and you want to use GLPK you should definitely give it a closer look. Unfortunately, it is available for Windows only – maybe there will be a version for Macs or Linux soon? As GUSEK is based on open source it might be rather easy to do I suppose? There is also an IEOR Tools interview available with Luiz Bettoni, the developer of GUSEK.

UPDATE (17.02.2009): Great tutorials on how to use GLPK are available as well!

GLPK benchmarks for NETGEN instances:

Below here are benchmarks for 50 original NETGEN instances of min-cost
flow problem obtained with the glpk primal simplex.

Solver:   GLPSOL 4.36 (options used: --mincost --nopresol)
Computer: Intel Pentium 4, 3.0 GHz
Platform: Cygwin/Windows XP
Compiler: GCC 3.4.4 (options used: -O3)
Test set: 50 original NETGEN instances of min-cost flow problem
         (generated by glpk/examples/netgen.c)

Problem    Nodes   Arcs       Optimum        Iters  Time,s
--------  ------  ------  ----------------  ------  ------
netgn101    5000   25336  +6.191726000e+06   17222      41
netgn102    5000   25387  +7.233714400e+07   28528      71
netgn103    5000   25355  +2.189475530e+08   35530      91
netgn104    5000   25344  -1.910037100e+07   16962      41
netgn105    5000   25332  +3.119257800e+07   17112      42
netgn106    5000   12870  +4.314276000e+06   11813      17
netgn107    5000   37832  +7.393769000e+06   20941      69
netgn108    5000   50309  +8.405738000e+06   24587     104
netgn109    5000   75299  +9.190300000e+06   30547     188
netgn110    5000   12825  +8.975048000e+06   12012      18
netgn111    5000   37828  +4.747532000e+06   19920      65
netgn112    5000   50325  +4.012671000e+06   22034      92
netgn113    5000   75318  +2.979725000e+06   24210     147
netgn114    5000   26514  +5.821181000e+06   13548      27
netgn115    5000   25962  +6.353310000e+06   15917      35
netgn116    5000   25304  +5.915426000e+06   13874      34
netgn117    5000   12816  +4.420560000e+06    9225      14
netgn118    5000   37797  +7.045842000e+06   16456      55
netgn119    5000   50301  +7.724179000e+06   18006      77
netgn120    5000   75330  +8.455200000e+06   20607     127
netgn121    5000   25000  +6.636636000e+07   25563      56
netgn122    5000   25000  +3.099752900e+07   23774      52
netgn123    5000   25000  +2.338877700e+07   24382      56
netgn124    5000   25000  +1.780344300e+07   24357      60
netgn125    5000   25000  +1.411962200e+07   24245      62
netgn126    5000   12500  +1.880221800e+07   13808      21
netgn127    5000   37500  +2.767464700e+07   32483     103
netgn128    5000   50000  +3.090619400e+07   40121     164
netgn129    5000   75000  +4.090520900e+07   51742     322
netgn130    5000   12500  +3.893960800e+07   15259      23
netgn131    5000   37500  +1.675297800e+07   28777      86
netgn132    5000   50000  +1.330295100e+07   31967     117
netgn133    5000   75000  +9.830268000e+06   35709     178
netgn134    1000   25000  +3.804874000e+06    7426      12
netgn135    2500   25000  +1.172961600e+07   15506      29
netgn136    7500   25000  +3.331810100e+07   29578      82
netgn137   10000   25000  +4.642603000e+07   31433     104
netgn138    5000   25000  +6.071087900e+07   46106     134
netgn139    5000   25000  +3.272968200e+07   34657      93
netgn140    5000   25000  +2.718383100e+07   28635      71
netgn141    5000   25000  +1.996328600e+07   20610      43
netgn142    5000   25000  +2.024345700e+07   17830      36
netgn143    5000   25000  +1.858677700e+07   13875      25
netgn144    5000   25000  +2.504591000e+06   24581      56
netgn145    5000   25000  +2.159561380e+08   24018      55
netgn146    5000   25000  +2.253113811e+09   24680      57
netgn147    5000   25000  -4.279083730e+08   47990     144
netgn148    5000   25000  -9.296531800e+07   37528     105
netgn149    5000   25000  +8.605122400e+07   24057      54
netgn150    5000   25000  +6.193149190e+08   23429      52