Archive for February 2009
Two articles on Risk Management worthwhile reading:
- “Recipe for Disaster: The Formula That Killed Wall Street” on Wired
- “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.
A series of three tutorials on using the GNU Linear Programming Kit (glpk) is available on the IBM website
- The GNU Linear Programming Kit, Part 1: Introduction to linear optimization
- The GNU Linear Programming Kit, Part 2: Intermediate problems in linear programming
- 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.
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:
- 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.
- 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.
- 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.
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
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.
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”.
The recent discussions about the new Gurobi solver and its performance as compared to CPLEX (, ) as well as the discussion about using open source solvers () 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.
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.
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
glp_maxflow_ffalg find maximal flow with Ford-Fulkerson
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
–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