Gmail problems

I use gmail almost exclusively and I am very happy with how it works. Recently there surfaced an interesting bug. Attachments can be downloaded individually or combined as a single zip file. It turns out gmail adds a few bytes to the zipped files. After unzipping I see:

C:\Users\erwin\Downloads>dir "AM RFP IFPRI.docx"/s Volume in drive C is HP Volume Serial Number is 8AA3-C6D2 Directory of C:\Users\erwin\Downloads 12/22/2010  01:03 PM           194,667 AM RFP IFPRI.docx                1 File(s)        194,667 bytes Directory of C:\Users\erwin\Downloads\rfpburundi 12/24/2010  12:06 PM           195,072 AM RFP IFPRI.docx                1 File(s)        195,072 bytes      Total Files Listed:                2 File(s)        389,739 bytes                0 Dir(s)  315,865,411,584 bytes free C:\Users\erwin\Downloads>

First one downloaded as single file, second one unzipped from zip. After a few nasty warning messages about corrupted files Word is actually able to open and view the second file also.

See also: http://www.google.com/support/forum/p/gmail/thread?tid=7d4f236a3538ebbc&hl=en

A scheduling problem

For a scheduling that I could not solve in one swoop I tried to develop a small algorithm. Basically: schedule the m<n jobs that come first, then fix the m jobs and schedule the next m jobs. This seems to work with Cplex. The algorithm looks like:

loop(k,    j(j0) = kj(k,j0);    solve sched minimizing makespan using mip;    report(k,'obj') = sched.objval;    report(k,'modelstat') = sched.modelstat;    report(k,'solvestat') = sched.solvestat;    xstart.fx(j,t) = xstart.l(j,t); );

This algorithm will perform the following:

1-10	11-20	21-30	31-40	41-50
solved
fixed	solved
fixed	fixed	solved
fixed	fixed	fixed	solved
fixed	fixed	fixed	fixed	solved

For Cplex we get:

----    180 PARAMETER report             obj   modelstat   solvestat k1    1480.000       1.000       1.000 k2    2940.000       1.000       1.000 k3    4400.000       1.000       1.000 k4    5860.000       1.000       1.000 k5    7320.000       1.000       1.000

However for Gurobi we get:

----    180 PARAMETER report             obj   modelstat   solvestat k1    1480.000       1.000       1.000 k2    2940.000       1.000       1.000 k3    4400.000       1.000       1.000 k4                  19.000       1.000 k5                  19.000       1.000

It turns out that the fixing of a solution causes the next iteration to be infeasible. We can actually isolate step k3 and do:

solve m minimizing makespan using mip;    xstart.fx(j,t) = xstart.l(j,t);    solve m minimizing makespan using mip;

This will make the second model infeasible: i.e. Gurobi does not like its own solution! In this case it is a tolerance question: the final solution is slightly infeasible. We can fix this by:

loop(k,    j(j0) = kj(k,j0);    solve m minimizing makespan using mip;    report(k,'obj') = m.objval;    report(k,'modelstat') = m.modelstat;    report(k,'solvestat') = m.solvestat;    xstart.fx(j,t) = round(xstart.l(j,t)); );

because we know all job step times are in whole seconds. Now both Cplex and Gurobi can solve the problem just fine.

A reasonable good solution looks like:

By accident our algorithmic batch size is the same as the batch size for a good solution (this is not required for the algorithm to work).

The solution is somewhat sensitive where we put the breaks when decomposing the model. This may indicate a rolling horizon algorithm may work better (see http://yetanothermathprogrammingconsultant.blogspot.com/2008/06/rolling-horizon-implementation-in-gams.html).

FTP client

Not many people seem to know this: the Windows file explorer can be used as a simple FTP client by entering a URL of the following format in the  text box where normally the directory is shown:

ftp://login:password@ftp.xxxx.com

Just drag files and whole directories to here and they will be transferred.

Note: when clicking on a URL like that the Internet explorer will start, allowing a “read-only” view of an FTP site.

SQL Injection

From http://www.fsf.org/blogs/sysadmin/savannah-and-www.gnu.org-downtime:

Wed Nov 24 12:59 UTC -- On the evening before Thanksgiving, an IP located in Tbilisi, Georgia started an attack targeting the savannah.nongnu.org website. The perpetrators used SQL injection attacks to download the entire database of usernames and hashed passwords, and we should assume anything else in the Savannah MySQL database.

One way to prevent this is to solely use prepared SQL statements when accessing the DB. This is the strategy I have used in http://yetanothermathprogrammingconsultant.blogspot.com/2010/10/running-large-models-using-web.html. (Other approaches often mentioned are using an appropriate quoting mechanism, e.g. through mysql_real_escape_string and/or disabling multi statements) I browsed through a few recent books on PHP for this project, and I was amazed how much text is devoted to security; it looked like a third of the material seems to be about security. It truly sends shivers down your spine. Programming web applications becomes more and more a question of being paranoid all the time; this is not really a good development as it takes the fun out of things and also reduces productivity (extra work for code that does not implement any new and possibly exciting features for regular, non-hostile users). From a different perspective one could also say that the development tools are still too primitive such that developers are not isolated from these security issues and can concentrate on the real task at hand.

Collaboration tools

For different projects I have been using some of the following document sharing tools:

• DropBox. This allows you to have a directory that is shared between different users. Advantage: on Windows this just looks like a network drive and you can easily copy files from and to the drop box directory. Disadvantages: just files. Also it looks for windows as a local disk so by default dragging means “move” instead of “copy”. Site: http://www.dropbox.com/.
• Wiki-type environments. I have experience with PmWiki (http://www.pmwiki.org) and MediaWiki (http://www.mediawiki.org). Advantage: good support for HTML presentation of rich text. Disadvantage: somewhat complicated to setup and to secure; file upload facilities may be limited depending on the hosting environment.
• Live.com. Microsofts sharing environment. Nice online editing facilities of Word documents.
• My current favorite: sites.google.com. Clean and well-thought through. Has most of the facilities I need. Easily shared with just the people you want to share it with. Limits: 20 GB files, and 100 GB per site; I had to park some of the larger data files somewhere else.

Reorganizing a large parameter in GAMS

To export some fairly substantial data in a certain format I wanted to form:

DownLoadData(downloadfiles,SP_Varname,SP_SubVarName,SP_SubSubVarName,SP_Indicator,                                 SP_Description,SP_Source,SP_Unit,cty,Fwdy) =       sum((mapdownloadfiles(downloadfiles,SP_control),SP_Map,SP_Graph,SP_Options,SP_Type,mapy(FwdY,SP_year)),           cube(SP_Control,                SP_VarName,                SP_SubVarName,                SP_SubSubVarName,                SP_Year,                SP_Indicator,                SP_Source,                SP_Description,                SP_Unit,                SP_Map,                SP_Graph,                SP_Options,                SP_Type,                cty                ) );

The original Cube parameter has 326,755 elements, and this operation basically reshuffles things into a lower-dimensional parameter with some mappings applied. Upon completion the new parameter Download_Data has the same number of elements: 326,755. Unfortunately this operation was very expensive, so much so that I never saw it finish.

The following code does exactly the same in just 0.5 seconds:

loop((mapdownloadfiles(downloadfiles,SP_control),mapy(Download_Year,SP_year)),    Download_Data(downloadfiles,SP_Varname,SP_SubVarName,SP_SubSubVarName,cty,SP_Indicator,                              SP_Description,SP_Source,SP_Unit,Download_Year) =         sum((SP_Map,SP_Graph,SP_Options,SP_Type),           cube(SP_Control,                SP_VarName,                SP_SubVarName,                SP_SubSubVarName,                SP_Year,                SP_Indicator,                SP_Source,                SP_Description,                SP_Unit,                SP_Map,                SP_Graph,                SP_Options,                SP_Type,                cty                ) ); );

GAMS has some built-in facilities to automatically rearrange assignments like these to achieve better performance, but in this case it was not very effective. So human intervention was needed to optimize this assignment.

Amazon not just selling books

Dear Amazon EC2 Customer, We are excited to announce the immediate availability of Cluster GPU Instances for Amazon EC2, a new instance type designed to deliver the power of GPU processing in the cloud. GPUs are increasingly being used to accelerate the performance of many general purpose computing problems. However, for many organizations, GPU processing has been out of reach due to the unique infrastructural challenges and high cost of the technology. Amazon Cluster GPU Instances remove this barrier by providing developers and businesses immediate access to the highly tuned compute performance of GPUs with no upfront investment or long-term commitment. Amazon Cluster GPU Instances provide 22 GB of memory, 33.5 EC2 Compute Units, and utilize the Amazon EC2 Cluster network, which provides high throughput and low latency for High Performance Computing (HPC) and data intensive applications. Each GPU instance features two NVIDIA Tesla® M2050 GPUs, delivering peak performance of more than one trillion double-precision FLOPS. Many workloads can be greatly accelerated by taking advantage of the parallel processing power of hundreds of cores in the new GPU instances. Many industries including oil and gas exploration, graphics rendering and engineering design are using GPU processors to improve the performance of their critical applications. Amazon Cluster GPU Instances extend the options for running HPC workloads in the AWS cloud. Cluster Compute Instances, launched earlier this year, provide the ability to create clusters of instances connected by a low latency, high throughput network. Cluster GPU Instances give customers with HPC workloads an additional option to further customize their high performance clusters in the cloud. For those customers who have applications that can benefit from the parallel computing power of GPUs, Amazon Cluster GPU Instances can often lead to even further efficiency gains over what can be achieved with traditional processors. By leveraging both instance types, HPC customers can tailor their compute cluster to best meet the performance needs of their workloads. For more information on HPC capabilities provided by Amazon EC2, visit aws.amazon.com/ec2/hpc-applications. Learn more about the new Cluster GPU instances for Amazon EC2 and their use in running HPC applications. Sincerely, The Amazon EC2 Team

Unfortunately I don’t have any direct use for this (it would be fun to try this out on some problems). It is interesting that Amazon is so active in the HPC arena.

U shaped penalties

For a large LP model a customer of mine wanted to have instead of a V shaped penalty around a goal, something that approximates a U shaped penalty. With standard slacks:

 

we essentially have a V shaped penalty:

We can approximate a more U shaped form by introducing extra slacks with a smaller penalty:

with unit penalty q smaller than p, e.q. q=0.1*p. This will give:

The idea is that the algorithm will select the cheap slacks t first, before spending on the expensive slacks s. This will keep the LP linear and we don’t need extra binary variables. For q=0 we essentially allow small deviations for free, but start paying when we go beyond the threshold T.

This approach can easily be extended to more piecewise linear segments (as long as we keep things convex). Also the range T for the slacks t may be generalized to:

StatPlanet

When demoing http://www.sacmeq.org/statplanet/StatPlanet.html (for which I developed a GAMS link), I reminded to Hans Rosling. Check here for some fantastic presentations: http://www.gapminder.org/videos/. The software has been acquired by Google. Here is an example:

Amazon ec2

Amazon “Elastic Compute Cloud” has some big-ass machines available: http://aws.amazon.com/ec2/#instance. See also the rates on that page.