First Melbourne Maths and Science Meetup

This Tuesday (21st of August) – Tomorrow – I will be holding the first Melbourne Maths and Science Meetup. It will be held at RMIT, in the Physics Building (information about the location is below).

The idea of the group is to gather together scientists and mathematicians of all types, and have them present a technical topic in their field. There will be around 3 presentations each night, with time for small little questions to be posed to the group as a whole. After each meeting we will head to a local pub for drinks, which Biarri will sponsor!

I invite anyone in Melbourne who is interested in Maths and any type of Science to come down and furthermore, to present on any topic that you may find interesting!

Please do sign up to the Meetup group, and I look forward to seeing you there on Tuesday!

Location details

The RMIT expression for the particular room is “14.6.13”, which, perhaps unsurprisingly, means “Building 14, Level 6, Room 13”. To be more helpful, it means you should enter at the front of RMIT, from Swanston St, head generally left, past the cafeteria, go to the lifts, go to level 6, and then continue heading left until you meet a glass door. Then, you should call me, as the door will likely be locked. My phone number can be found on the Meetup group website.

Optimisation: Striking the Right Balance

One of the guiding principles we use in commercial mathematics is to “Model Conservatively, but Optimise Aggressively”. This means that the problem domain should be modeled with sufficient “fat” in the data to ensure that the results are both legal and robust; but given this, we should then seek to apply the best (fastest and highest quality) solution approach that we can get our hands on.

Optimising aggressively can sometimes have it’s downfalls, though, if taken too literally. I’ve been doing a few experiments with numerical weightings of the objective function in a Vehicle Routing problem, where this issue is readily apparent. (Actually it is a Vehicle Routing problem with time windows, heterogeneous fleet, travel times with peak hours, both volume and weight capacities, and various other side constraints).

Our Vehicle Routing uses travel times (based on shortest paths through the street network) that are characterised by distance and duration. Durations can vary due to different road speeds on different types of streets (highways vs suburban roads for example). This leads to the question of how (on what basis) to optimise the vehicle routes – given that the optimisation has already to some extent minimised the number of vehicles and created well-clustered routes – what is the most desirable outcome for KPIs in terms of duration and distance?

In one experiment I’ve tried three different weightings for the duration (cost per hour) while keeping the cost per distance constant. I’ve run three values for this cost per hour – low, medium, and high weightings – on real-life delivery problems across two different Australian metropolitan regions.

Region 1
Total Duration Driving Duration Distance
Cost/hour
Low 74:47 24:38 708
Medium 72:45 23:55 712
High 72:58 23:42 768
Region 2
Total Duration Driving Duration Distance
Cost/hour
Low 113:54 46:44 1465
Medium 107:51 41:36 1479
High 108:51 43:49 1518

From these results, there is a (more-or-less) general correspondence between distance and the driver cost per hour as you would expect. However, if you push one weighting too far (ie. optimise too aggressively or naively), it will sometimes be to the detriment of all the KPIs as the optimisation will be pushing too strongly in one direction (perhaps it is outside the parameter space for which it was originally tuned, or perhaps it pushes the metaheuristic into search-space regions which are more difficult to escape from). This is most acutely seen in Region 2 when using the high cost per hour value. Conversely if you drop the cost per hour to a low value, the (very modest) reduction you get in distance is very badly paid for in terms of much longer durations. What is most likely happening in this case is that the routes are including much more waiting time (waiting at delivery points for the time windows to “open”), in order to avoid even a short trip (incurring distance) to a nearby delivery point that could be done instead of waiting.

The problem of striking the right balance is most acute with metaheuristics which can only really be tuned and investigated by being run many times across multiple data sets, in order to get a feel for how the solution “cost curve” looks in response to different input weightings. In our example, an in-between value for cost per hour seems to strike the best balance to produce the overall most desirable KPI outcome.

Custom Excel Charts: Scatter Plots

 

I am often required to create some very specific charts for clients that are far outside of the capability of regular Excel charting functionality. I use VBA to create these custom charts in a dynamic way to visualise outputs of mathematical modelling. These outputs are important to clients as they allow them to view the complex outputs in simple, familiar ways.

I have in the past created L-Shaped Graphs for clients that helped optimise the use of space for a dynamic Excel Dashboard that needed to be constrained to an A4 print out.

More recently, I have been required to create a custom ‘March Chart’ that plots the movements of different work crews over space and time. I received a print out of an old ‘March Chart’ that had been manually created by the client, and was asked to replicate it exactly in Excel so that it could be viewed as an output of a mathematical model.

 

THE POWER OF SCATTER PLOTS

When creating a custom chart in Excel, you must use one of the existing charts as a template. This template can then be twisted and abused into doing what you need through tricks and manipulation within VBA.

For the March Chart project, I discovered just how very useful a scatter plot can be as the template for an advanced Excel chart. The scatter plot can be thought of as a blank canvas on to which x,y data points can be plotted. Each data point can then be joined by a line to another data point, creating a straight line. A series of sequential data points with straight lines joining them called a ‘data series’ can be used to create paths and even ‘curves’. With this functionality in mind, you essentially now have a blank canvas that you can draw anything on in Excel with VBA!

This all seems far too good, so Excel had to put some barriers in our way to make it a little trickier.

  • For starters, there is the ever present issue of backward compatibility to Excel 2003. The object model used to create charts was changed from Excel 2003 to Excel 2007, so it is very important to be aware of this, and find out early if your client is using Excel 2003. Fortunately for myself, the client for the ‘March Chart’ had upgraded to at least Excel 2007 so this was not an issue for me.
  • More specific to the advanced use of scatter plots, Excel limits you to 255 data series on a chart. Each sequence of coordinates that join together to make a continuous line are defined as a data series. This means that you can only have 255 distinct continuous lines on your chart.
  • Each of these data series, can only consist of 255 data points. Unless your chart is extremely big and going to be shown on a very large screen, this is pretty easy to manage. There are two options:

o Split the data series into multiple data series. If you make the two data series the same colour, and begin the second data series at the last point of the first data series then they will appear to be a continuous line. This is a good option if you are not close to the limit of data series, however can create more issues to overcome as an additional legend entry will be created.

o For any data series that has more than 255 potential data points, skip over every second, third, etc. depending on the actual number so that the number of data points implemented to the actual plotted data series remains under 255. This is my preferred method as no additional work is required in fixing the legend and is in my opinion neater.

The following is an example output of the March Chart showing different colours for different work crew types. You can track the geographic location over time of each work crew very simply with this visualisation.

 

The ‘L’ Shaped Excel Graph

 

I recently had to develop a graphical report in Excel that was required to fit perfectly on a single A4 page for printing purposes. A lot of information was supposed to fit on this page, so using the space well was very important. After the initial formatting was reviewed it was decided that one graph in particular needed to be bigger and clearer. With a bit of reshuffling the final space available for this graph was a big ‘L’ shape at the bottom of the page.

A perfect amount of space but unfortunately part of the ‘L’ would have to go to waste – unless some sort of ‘L’ shaped graph could be created…

The ‘L’ Shaped Graph:

 

The ‘L’ shaped graph utilises the extra space by moving the title and legend away from the actual data. This results in the data having space to expand and become more readable (very important with this detailed ‘Clustered-Stacked Column Graph’). It is important to note that once created, it is very difficult to edit this graph and it should most likely be treated as read only.

How it is done:

  • Finalise the data for your chart. (The legend will no longer update to reflect changes in the data once we are done)
  • Create a copy of the chart
  • Delete all axis labels and gridlines on the copy.

Now comes the trick – removing the data without affecting the legend:

  • To do this, select each data point on the copy (not data series) and right-click: Format data point. When you first click a data point it most likely selects the entire series, so click again to target just the data point. If you were to do this for the series then the legend would update to reflect the change, which we don’t want.
  • Select No-fill in the Fill tab. This will white out that data point. Do this for all the data points until just the legend and title remain on the copy.

Now to fix up the original chart:

  • Select the legend and title of the original chart and delete
  • Resize to utilise the space

The rest is just simple formatting to customise the graph to your needs. Here are some of the things I did:

  • Select the legend of the copy and right-click: Format legend
  • In Legend Options: Legend Position select ‘Top’.
  • Now resize the legend of the copied chart to whatever you like. You may notice that the chart area, although blank, is still selectable and may be an annoyance while resizing other aspects of the copy. This can not be deleted however you can resize it to be very tiny in one of the corners of that graph.
  • Remove the borders of both the original graph and the copy. Right-click: Format Chart area: Border Colour: No line.
  • Now create borders to surround the ‘L’ shaped chart on the spreadsheet itself to make it appear like the original and the copy are joined.

 

The process of whiting out each data point can be very tedious. In practice I created this graph with VBA to automate the process. There are some more tricks required if using VBA for the whole graph however I won’t go into them here. Like all VBA, heavy use of the macro recorder, trial and error, a little blind luck and a lot of patience go a long way.

The Trajectory of a Vehicle Routing

I recently wanted to view an animation of a vehicle routing optimisation algorithm I have been working on.

The algorithm uses a two phase optimisation approach. The first phase is a construction heuristic. The second phase is guided local search meta heuristic. The algorithms primary focus is to produce a visually attractive solution. Visually attractive solutions are usually synonymous with compact, non-overlapping routes with little or no intra-route cross over.

A colleague suggested I have a look at pygame. I hunted around to try and find an existing script that did something similar to what I wanted and found the fracture simulator. It is always easier to modify something than to start from scratch!

I was pleasantly surprised at how easy it turned out to be. I am very much a python novice, and had never heard of pygame before, but have been programming for a number of years. I was able to get the basics of my animation up and running in one evening! This far exceeded my expectations!

The python script can be viewed here

The input file used to create the uploaded animation can be viewed here

Drawing figures for scientific publications

I recently had to modify a picture (figure) as part of a resubmission to an academic journal.

The picture was created using XFig some time ago. XFig is one of the most widely used applications for creating figures for academic publications, and easily the best application I have used for this purpose. Its ability to incorporate Latex scientific formulas (use “xfig -specialtext -latexfonts -startlatexFont default” when launching XFig) and fonts, means that figures can be easily and beautifully integrated into Latex documents.

As I now have a windows machine, and am definitely no expert on linux (I am slowly trying to remedy this) I was dreading having to jump through the hoops to get XFig working on my new windows box (See http://www.cs.usask.ca/~wew036/latex/xfig.html). Part of the process involves installing Cygwin (a Linux-like environment for Windows). Not being familiar with linux this process seems quite convoluted (and I have been down this path before).

Googling XFig also brings up WinFig. Which is supposed to be very similar to XFig but runs on MS Windows. After downloading WinFig I quickly found out that you can only save figures with 15 or less objects in them without paying for the full version (making the free version not very useful). Something that the homepage neglects to mention.

I soon realised that because I had already installed virtual box and installed ubuntu (the process was very pain free) I should definitely try to use XFig within Ubuntu. Installing XFig within Ubuntu is what one my colleagues would call automagical – with a terminal inside Ubuntu type “sudo apt-get install xfig”, then as mentioned before type “xfig -specialtext -latexfonts -startlatexFont default” and I was cooking straight away.

In order to open my file in XFig in Ubuntu I was hoping to be able to share some folders with MSWindows, and then mount them inside Ubuntu. Alas, despite all my efforts I have still not been able to get this to work. Email to the rescue, emailed them to myself, opened my gmail in ubuntu, saved the file and the problem was solved.

The moral of the story (well this blog) is that if you are trying to get XFig working on windows, – don’t. Use the power that virtual box gives you and run XFig in Ubuntu within virtual box on your Windows machine! Now to move back to the Latex editing applications in linux and away from those I have been using with MS Windows!