Sebastian Pokutta's Blog

Mathematics and related topics

Archive for February 2009

Two articles on Risk Management

leave a comment »

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.

Written by Sebastian

February 25, 2009 at 5:10 am

Tutorials for glpk

with 3 comments

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.

Written by Sebastian

February 17, 2009 at 4:07 am

The integrity of user reviews

leave a comment »

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.

Written by Sebastian

February 17, 2009 at 2:44 am

Posted in what else is out there

Tagged with

Updated version of normaliz available

leave a comment »

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.

Written by Sebastian

February 13, 2009 at 10:45 pm

Posted in Software

The Cult of Genius

with one comment

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…

Written by Sebastian

February 13, 2009 at 10:24 pm

Poll: Which MIP solver do you use?

leave a comment »

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.

Written by Sebastian

February 9, 2009 at 3:56 pm

Posted in Polls, Software

MOPTA 2009 Modeling Competition

leave a comment »

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.

Written by Sebastian

February 6, 2009 at 11:05 pm

Follow

Get every new post delivered to your Inbox.