Sebastian Pokutta's Blog

Mathematics and related topics

Archive for February 2010

CPLEX free for academic use

with 6 comments

Probably I am not the first one to report this but CPLEX is now available for free for academics as part of IBM’s academic initiative (see here):

Full-version CPLEX now available free-of-charge to academics

Posted: Feb 18, 2010 08:30:03 PM

Effective February 15, 2010, IBM is offering no-charge full-version ILOG Optimization products via IBM’s Academic Initiative program (http://www.ibm.com/academicinitiative). This move builds on the availability of limited Teaching Editions available since August 2009, and now provides registered members with renewable one-year access to IBM ILOG OPL-CPLEX, CPLEX, CP Optimizer and CP for both teaching and research use. Registered members can access ILOG Optimization software at: https://www.ibm.com/developerworks/university/software/get_software.html, where they can search for ILOG Optimization or individual solvers by name. Depending on the search criteria, electronic assemblies will be retrieved for IBM ILOG OPL Development Studio, CPLEX, CP Optimizer or CP on all commercially available platforms. To run the software, members will also need to download a key from: https://www.ibm.com/developerworks/university/support/ilog.html, but are no longer required to install ILM. Note that as part of Academic Initiative, IBM also makes its professionally-developed training materials available for use in classrooms and labs at: https://www14.software.ibm.com/webapp/devtool/scholar/web/coursewarePickPage.do?source=ai-course-websphere.

The application is pretty forward and the verification of eligibility is supposed to take “3-5 business days”. But it seems that the accounts are approved much faster (at least in my case).

Written by Sebastian

February 22, 2010 at 2:21 pm

Sikuli – a scripting language based on screenshots

leave a comment »

There is a pretty cool, new scripting language, Sikuli which is a “research project developed by User Interface Design GroupMIT Computer Science and Artificial Intelligence Laboratory (CSAIL)“. The cool thing is that you can automate GUI interactions by using screenshots of buttons, sliders, input boxes, etc. But rather before I start to explain how it works, just check out the video.

The language itself is based on Jython and thus you can use Jython to do almost everything you like and it is fairly simple to use:


Example: Sikuli Code

So now you finally can automate your optimal FarmVille production schedule by having Sikuli interact with the applet ;-). Just put your production schedule into Sikuli and let it do the rest. Here is a GMPL model (based on the AMPL model from O.R. by the Beach – I just changed “;” and removed the “option” lines) for determining the optimal production schedule that maximizes cash. Can be solved to optimality with GLPK in 0.1 secs – the Sikuli code is left as an exercise 😉


param T;
set Horizon := 0..T;
set Crops;

param TotalArea;
param InitialArea;
param InitialMoney;
param PlowCost;
param Growth{Crops};
param Cost{Crops};
param Revenue{Crops};

var Plant{Crops,Horizon} integer >= 0;
var Area{Horizon} >= 0, <= TotalArea;
var Money{Horizon} >= 0;

maximize z: Money[T] + 4*PlowCost;

subject to

area0: Area[0] = InitialArea + sum {i in Crops} Plant[i,0];

area{t in 1..T}:  Area[t] = Area[t-1]
      + sum {i in Crops} Plant[i,t]
      - sum {i in Crops : t >= Growth[i]} Plant[i,t-Growth[i]];

money0: Money[0] = InitialMoney - sum {i in Crops} (PlowCost + Cost[i])*Plant[i,0];

money{t in 1..T}: Money[t] = Money[t-1]
      - sum {i in Crops} (PlowCost + Cost[i])*Plant[i,t]
      + sum {i in Crops : t >= Growth[i]} Revenue[i]*Plant[i,t-Growth[i]];

solve;

display z;
display {i in Crops, t in Horizon : Plant[i,t] > 0} Plant[i,t];
display Area,Money;

data;

param T := 36;
set Crops := SB EP WH SY;
param TotalArea := 144;
param InitialArea := 0;
param InitialMoney := 323;
param PlowCost := 15;

param:

Growth   Cost   Revenue :=
SB      1      10       35
EP     12      25       88
WH     18      35      115
SY      6      15       63;

end;

Written by Sebastian

February 7, 2010 at 8:33 pm

Microbes outsmarting engineers/mathematicians (reloaded)

with one comment

A paper on solving combinatorial optimization problems with biological organisms made it into Science. The paper “Rules for Biologically Inspired Adaptive Network Design” by Atsushi Tero, Seiji Takagi, Tetsu Saigusa, Kentaro Ito, Dan P. Bebber, Mark D. Fricker, Kenji Yumiki, Ryo Kobayashi, and Toshiyuki Nakagaki explains that under certain circumstances, a certain microbe can reconstruct a version of the Tokyo rail system. From the abstract:

Transport networks are ubiquitous in both social and biological systems. Robust network performance involves a complex trade-off involving cost, transport efficiency, and fault tolerance. Biological networks have been honed by many cycles of evolutionary selectionpressure and are likely to yield reasonable solutions to such combinatorial optimization problems. Furthermore, they develop without centralized control and may represent a readily scalable solution for growing networks in general. We show that the slime mold Physarum polycephalum forms networks with comparable efficiency, fault tolerance, and cost to those of real-world infrastructure networks—in this case, the Tokyo rail system. The core mechanisms needed for adaptive network formation can be captured in a biologically inspired mathematical model that may be useful to guide network construction in other domains.

Whereas the authors do not claim any real (i.e., mathematical) optimality etc. and probably the solution quality is similar to solutions that one would obtain with simulated annealing or ant colony optimization, i.e., sub-optimal solutions in many cases, a well-read website, Spiegel Online belonging to the Spiegel magazine run a story about the article a couple of days ago giving the whole thing a slightly different touch – this reminded me very much of a blog post of Mike. The article starts with (in German – I will provide a hopefully faithful translation afterwards):

Was Ingenieure mit großem Aufwand versuchen, scheint für den Schleimpilz Physarum polycephalum eine Kleinigkeit: Verkehrswege möglichst effizient zu bauen.
Translation: What Engineers try to achieve with a lot of effort, is a trivial task for the slime mold Physarum polycephalum: The construction of efficient (traffic-) networks.

Here, the witty author already gives a first indication and an executive-style summary of his opinion. And just in case you haven’t got the point that engineers and in particular discrete optimization people are superfluous, money-eating artifacts of times where excess capital had to be burnt in order to keep inflation low, the author stresses his point even further by making clear that the microbe is really dumb.

Er gehört zu den ältesten Lebensformen – und Intelligenz würde man dem schleimigen Winzling wohl kaum zusprechen.
Translation: It (the microbe) belongs to one of the oldest life forms on earth and this little slimy thing is far from being intelligent.

If one takes a closer look at the article and especially the graph of the underlying network that the magic microbes reconstructed, the graph is almost trivial (from Fresh Photos):

If you checkout the spiegel online article which also provides pictures (I didn’t want to include those for obvious reasons), the time scale shows that obtaining the final solution took the magic microbe 26 hours. Needless to say that probably trivial branch-and-bound would do the job in less than 10 secs.

In times where it is chic to suck at mathematics, a stupid microbe outperforming a whole branch of engineering and mathematics provides perfect justification for dismissing mathematics as the most decadent form of barrenness. And what is really questionable, is that in times where mathematical illiteracy is responsible to a large extent (together with greed and dismissal of the principle of universality) for the latest financial meltdown there are still authors that somewhat give the impression that the underlying mathematical problems are trivial and provide a jaded view.

We need a wikipedia page for that, distinguishing folklore optimization (yeah, every pseudo-consulting outlet does optimization) and mathematical optimization. Something that really distilles the point. Unfortunately, this page here is not really informative for the non-expert!!