# Biarri is selected as one of the world’s best analytics teams

Biarri and NBN Co have been selected as one of six global finalists for the prestigious Franz Edelman Award. The Prize is the world’s most prestigious recognition for excellence in applying advanced analytics to benefit business and humanitarian outcomes. Biarri and NBN Co have been selected for developing a unique mathematical approach for designing broadband networks. Now in its 43rd year, the INFORMS Franz Edelman Prize competition recognises outstanding examples of analytics and operations research projects that transform companies, entire industries and people’s lives. Using innovative advanced analytical methods, the teams were instrumental in helping their respective institutions make better decisions, providing a disciplined way by which management can improve organisational performance in a wide variety of situations and across both public and private organisations.

INFORMS Franz Edelman finalist teams have contributed over $200 billion in benefits to business and the public interest. The 2014 INFORMS Franz Edelman Prize finalists were chosen after a rigorous review by accomplished verifiers, all of whom have led successful analytics projects. The verifiers come from IBM, BNSF, Bank of America, Verizon Wireless, HP, Eastman Chemical, Columbia University, Carnegie Mellon University, University of Chicago, the University of Chile, and other noted organisations. Finalists are chosen on the merits of how analytics methodologies were applied to solve problems, reduce costs, or otherwise improve results in real-world environments. The 2014 Edelman Prize winner will be announced at the Edelman Gala on March 31 during the INFORMS Conference on Business Analytics & Operations Research in Boston. Biarri and NBN Co are only the second finalists ever from Australia, Joe Forbes, co-founder of Biarri states, “We are excited and honoured to be selected as an Edelman finalist. We are very proud of the work we are doing with NBN Co on the broadband network and the contribution we can make to such an important national infrastructure project. As an Australian technology start-up it is great to be recognised one a global stage with some of the most prominent companies and institutions in the world.” NBN Co and Biarri worked together to develop software (FOND) with an algorithmic engine that can quickly generate low cost broadband network designs. The mathematics allows NBN Co to design optimised (lowest cost) networks for any given network strategy or architecture (FFTH, FFTN, hybrid, etc). The mathematics has allowed NBN Co to reduce design effort by 80%. The technology allows NBN Co and its partners to design the optimal network for the Government’s current broadband strategy. Paul Kennedy, CEO of Biarri Networks states, “There is a real satisfaction in working with NBN Co to solve a problem that hasn’t been solved before, and delivering real benefit to this massive project”. This international recognition of NBN Co and Biarri is a testament to Australia’s leadership in Technology and Innovation. Biarri is now deploying FOND to Chorus in NZ for the design of the UFB (Ultra Fast Broadband Network) and is conducting pilot projects for broadband networks throughout North America and Asia. The winner for 2014 Edelman Award will be announced at the INFORMS Conference on Business Analytics & O.R., Boston, MA on Monday 31 March 2014. Also, each year the finalist organisations are inducted as members of the Franz Edelman Academy. Members of the Academy, inducted each year at the Edelman Gala, include the primary client organisation (NBN Co) along with the mathematical organisation (Biarri). ## 2014 Edelman Finalists 1. Twitter, with Stanford University, for “The ‘Who to Follow’ System at Twitter: Strategy, Algorithms, and Revenue Impact.” 2. The U.S. Centers for Disease Control and Prevention (CDC), with Kid Risk, Inc., for “Using Integrated Analytical Models to Support Global Health Policies to Manage Vaccine Preventable Diseases: Polio Eradication and Beyond.” 3. The Energy Authority for “Hydroelectric Generation and Water Routing Optimizer.” 4. Grady Memorial Hospital, with the Georgia Institute of Technology, for “Modeling and Optimising Emergency Department Workflow.” 5. Kidney Exchange at the Alliance for Paired Donation, with Stanford and Mitford “Kidney Exchange.” 6. NBN Company, with Biarri, for “Fibre Optic Network Optimization at NBN Co.” ## About NBN Co NBN Co is a Government Business Enterprise whose aim is to assist the Australian Government in ensuring Australians have access to the most appropriate high-speed broadband technology. Biarri (www.biarrinetworks.com and www.biarri.com) is an Australian commercial mathematics and technology business. It was founded in 2009 to provide accessible optimisation to improve business efficiency. Some of Biarri’s other customers include Schweppes, Boral, Rio Tinto, Aurizon and Chorus NZ. ## About INFORMS The Edelman Award is presented by The Institute for Operations Research and the Management Sciences (INFORMS – www.informs.org). INFORMS is the largest society in the world for professionals in the field of operations research (O.R.), management science, and analytics. ## The BAM (Biarri Applied Mathematics) 2012 The second Biarri Applied Mathematics conference, or BAM, was hosted by the University of Melbourne over two days, November 12 to 13. The conference was a big success, with around 80 people attending, including industry representatives, academics and students. All the talks (given by Operations Research practioners from both Biarri and from industry, as well as academics) were informative and interesting and generated discussion and questions. Biarri once again thanks those who attended as well as those behind the scenes who helped make the event a success. Download all presentations ## The Future of Research in Operations Research New technologies, particularly Internet-enabled technologies like cloud computing and social collaboration tools, are changing how mathematics is done. This post showcases some of these emerging trends and lays out a vision for how the research and practice of Operations Research in particular could be much more effective. Consider one of the most famous mathematical theorems of all: Fermat’s Last Theorem. This theorem can be easily stated and readily understood, but has been truly devilish to prove, so much so that it lay unsolved for 360 years. Finally in 1993 Andrew Wiles provided a 108-page proof after 7 years of effort. This is a very “traditional” way of doing mathematics (albeit, pure mathematics), where a “lone wolf” makes a large single contribution; but it also hints at the limits of what one brain can achieve. By contrast, there is an equally old conjecture, from 1611, that has also only recently been proven. This is Kepler’s Conjecture, which states that the most efficient way to stack spheres has 74.048% density. An example of this “packing” is hexagonal close packing, which is the way you typically see oranges stacked in a shop. In 1998 a proof emerged for Kepler’s Conjecture which required the solution of about 100,000 Linear Programming problems by computer. This shows the emergence of a different model for “doing maths”, that is applicable even for purposes of obtaining mathematical proofs. It is no surprise that computers have become indispensable for mathematics, particularly in applied mathematics in general, and in Operations Research in particular. What is more interesting is the emerging role of other new technologies on how mathematics might be done. These trends include: • More data (e.g. availability of spatial data via Google Earth; the prevalence of data mining and “big data” analytics), faster machines (the well-documented exponential growth of computing power), and more machines (we are rapidly approaching the age of ubiquitous computing). • Internet-enabled technologies such as mashups, Software as a Service, open APIs, cloud computing, web 2.0, and social network integration. Browsers are prevalent and using web and mobile apps instead of desktop apps – even for complex tasks like image editing – is now commonplace. These newer trends all lay on top of the benefits and behaviours we have already become accustomed to from the Internet, such as: increasing market efficiencies (e.g. sectors that approach perfect information, such as hotel and flight bookings, and connecting businesses more directly to customers and suppliers), the commoditising of products (e.g. the so-called “race to the bottom” for pricing), the “long tail” (disproportionately favouring small businesses through the power of search e.g. niche goods and services); hypercompetition (where it becomes more difficult to monopolise by keeping customers ignorant of alternatives); and the abolition of geography (the so-called “global village”). • Competition, crowd sourcing and collaboration – e.g. log-in style tools which let people from anywhere collaborate together; there are many examples of competitive crowd-sourcing mentioned below. • Not to mention the remarkable explosion of knowledge enabled through Wikipedia, Google, etc. There have been some astonishing examples of how these trends have been put to use, both in academic and commercial contexts: • SETI@Home – a large-scale use of distributed computing over the Internet for research purposes, analysing radio signals (using digital signal processing) to look for signs of extra-terrestrial intelligence. • The Folding@Home project – using a statistical simulation method for protein folding. This used consumer computation (such as Playstation 3 cores and GPUs) to achieve millions of CPU days in short periods of time; it was much faster than the platform powering the SETI projects, and one of the largest scale distributed computing systems ever created. In Jan 2010 it simulated protein folding in the 1.5ms range – thousands of times longer than previously achieved. • Netflix prize – a global competition for collaborative filtering of movie recommendations. The competition was started in October 2006, and by June 2007 there were 20,000 teams competing. The Netflix grand prize of$1m was eventually awarded in September 2009. The training data had 100 million ratings over 17,700 movies, and the winner had to beat Netflix’s Cinematch algorithm (RMSE .9514) by at least 10%.  Netflix’s own algorithm was beaten within 6 days of competition start.
•     Other examples of competitive or prize-driven activity: Millenium problems, 99Designs.com, Kaggle.com – like the Netflix prize, many of these would not be possible at large scale without internet enablement.
•    Human Genome Project – was a good example of exponential progress, where the pace  far outstripped predictions.
•     Citizen Science, arXiv and various open science initiatives show a trend towards more open and collaborative approaches to science.
•     Polymath project – in a 2009 post on his blog, Timothy Gowers asked “is massively collaborative mathematics possible?”. This post led to the collaborative solution of a hard combinatorics problem through blog comments, in around 7 weeks. The success of the so-called “Polymath1” problem has spawned additional Polymath collaborations.
•    In 1999, Garry Kasparov played and eventually won a game of chess against a “World Team” which decided its moves by the votes of thousands of chessplayers, including many rank amateurs.  Kasparov called this challenging game “the greatest game in the history of chess”, and co-authored a book as a result, constituting the longest analysis of a single game of chess.

These examples of massive collaboration and computation are not isolated curiosities, but the leading edge of a new approach to solving problems, that shows how knowledge and creativity can be harnessed by new technologies.  They show that there is an emerging new way of working which can be surprisingly effective.

Consider now the typical Operations Research researcher/academic (and, to a lesser extent, many OR practitioners):

•    They care about the HOW: algorithms, parameters, results
•    They want to collaborate with colleagues
•    They want to replicate and build upon the work of others
•    They’d like their contributions to be recognised – in both senses of the word: both visible, and valued.

The usual current way of working, through journal paper submissions, does not necessarily cater well for these needs.  Why not?  Consider a typical OR paper, which might contain an Abstract, a Literature Review, a Statement of a Problem, an Approach, some Results and experiments, and a Conclusion and References.  Such papers have some good properties: they are generally self-contained (you can find a lot out about the given problem once you’ve found the paper); they’re peer-reviewed, and – tellingly, perhaps – they’re easily replicated or extended by same author(s) (for their next paper!).  However, they are very often:

x    Difficult to search for and find – papers are often held behind pay-walls or restricted access (e.g. in University collections).
x    Hard to reproduce the results – in Operations Research, implementation details (parameters, source code, data sets) are important, but these aspects are typically not peer-reviewed – so how can the computations be verified, or replicated by others?  They fail Karl Popper’s basic test of falsifiability in science.  Even when source code is made available, it has likely been run in a completely different environment, making proper comparison of results or run-times difficult.
x    Long gestation times – the publication cycle from submission to publication is often extensive, and includes opaque periods when papers are reviewed.  This tends to encourage a culture of “the scoop” – a pressure to publish a new result before someone else.  Moreover, arguably the entire publication environment is self-serving and institutionally locked in (by universities and journal publishers).  Neither is it very democratic; when students and researchers leave academia and become OR practitioners, it can be difficult to keep close ties.
x      “Soft” links – the references in papers are usually simply textual, not hypertext links, even when published electronically.

The OR community prides itself on the Science of Better, of finding optimal or near-optimal ways to improve the world, but its own internal mechanism for improvement is itself inefficient (sometimes highly so).  In particular the process does not much allow for micro-contributions; the slow journal-focused approach inhibits rapid incremental development (which is somewhat ironic, considering that many papers offer slight improvements upon previously published results).  Nor does it make it easy to discover the state of the art for a particular problem – e.g. what are the best algorithms, the best test instances, and the best known results on those instances.  This must often be laboriously uncovered: even when the papers embodying the best known results are found, the associated data sets are non-standardised and often held on someone’s home page website; there is no standard code (and very often, no code at all) for reading in the data sets, and sometimes interpretation of the data is needed as documentation is lacking.  Certainly there are isolated but laudable aspirations towards “Reproducible Research” in science, but it has not been generally adopted by the OR community.

The question therefore becomes: How can we harness new technologies for Internet-based collaboration and crowd-sourcing, to do Operations Research more effectively?  What if we could complement (or even avoid!) slow journal-focused progress?  How can we improve upon silo’ed academic results and source code?

We can remove IT burdens by using the power of cloud computing – delivering powerful computational and collaborative capability through the browser, being flexible about how the underlying computational power is employed, and storing the data in the cloud.   Software as a service, or open-sourced, releases us from capital cost investment (which also allows us to switch more easily and not get too “invested” into one way of working); instead of the pursuit of mathematics research getting buried under software installation, environment issues and management (the tail wagging the dog), we can again make computation serve us.  Using servers in the cloud is usually not time-shared (as in the bad old days) – in fact computation power is generally cheap enough that we can now even be wasteful of server resources.  We can “spin up” compute instances and pay per hour if we like.  A good example is Gurobi, the leading commercial LP/MIP solver, which now offers Amazon EC2 instances prebuilt with Gurobi which can be essentially “rented” by time (in small or large amounts), so that no installation is necessary.

We can share models and data by using versioned wiki-style tools that store models and their results in the cloud.  I lay out a detailed vision for how this might work later.

We can aim to build an online, global OR community that collaborates frictionlessly, using forums and social network integration on a common platform.  Log-ins would facilitate a user and user group system; websites (such as StackOverflow and its ilk) also show that user reputations can work.  Particularly, a common platform can also build bridges between academics and practitioners.

If these aims seem ambitious, it’s worth pointing out that many of the pieces of the puzzle we need are already (conceptually at least) in place:

•    www.or-exchange.com / math.stackexchange.com
•    OR Librarywww.exampleproblems.com
•    www.wikipedia.org / www.proofwiki.org
•    Gurobi via AWS + Python
•    MathML / MathJax
•    Tons of modelling languages (Mosel, AMPL, etc)
•    Online IDEs – e.g. CodePad, Eclipse Orion, etc.
•    Collaborative referencing tools e.g. www.mendeley.com
•    Cloud storage and cloud platforms (examples are Google App Engine, Heroku, etc)

Some of these examples show skeletal websites whose communities have not really “taken off”.  Part of the reason is that they are not open enough – for example, OR Library, probably the biggest resource for OR data sets on the Internet, currently resides on someone’s home page – it is not editable (you cannot add a data set for a new problem for example), or integrated (even with basic links) to the associated results or source codes; nor does it allow for comments or discussion.  Other tools lack adoption simply for not being powerful, fully-featured or wide-ranging enough to attract a broad user base.

So we have tools which form the pieces of the puzzle, they just need to be put together well to serve a more ambitious purpose.  What is this ultimate purpose? I claim that our goal should be global crowd-sourced Operations Research in real time.

Here’s one way that it might work.  In the pictures I’ve cheekily called this rough mock up of such a platform “OR 4 ALL”.

The different types of pages are:

A Problem page describes a mathematical problem, for example, “The Capacitated Vehicle Routing Problem”.  These pages will look similar to the Wikipedia page, except that they will use a math-aware markup language to facilitate easy authorship (Wikipedia pages use images for equations, which provides a barrier to making micro-changes).  These pages will provide links to the associated data set pages, and the associated algorithm pages (see below).  These links will likely be ranked in some way (for example, the algorithm that has the most community votes might rank first, and there might also be an automatic ranking of the algorithms that have produced the best known solutions to the widest range of data sets).

Algorithm Approaches pages describe an approach to solving a problem.  Here there might be also be a discussion of the parameters and their effects, and perhaps some proofs that are specific to this algorithm.

Data Set pages list the data set instances for a given problem, and include links to associated results.

Implementation pages hold modelling language source code.  Python would probably work best for this.  The page would contain an online IDE (essentially, allowing the users to code right inside the browser).  Crucially, however, there is a Solve button, where you can apply the implementation to a data set, and the system will run it for you and compose a Results page with the solution.

Results pages, like the other pages, include history and versioned snapshots.  However, for this page it links right back to the implementation as it was run, in a timestamped fashion.  That way, if the implementation changes, the result can still be replicated.

Hence, you do not need to leave the OR4ALL web application in order to go right through from composing an algorithm, implementing it and running it, and comparing its results to the state of the art.

To various extents the different types of pages will have the following features:
•    WYSIWYG editing
•    versioning
•    API access
•    voting
•    social media integration

The arrows shown in the diagram are typically “one to many” links.  For example, there will be many algorithmic approaches to one particular problem.  Similarly, for any one problem clearly there are also many data sets.  Each data set/algorithm combination can be run many times with small parameter or implementation changes, giving many result sets.

All changes and contributions are versioned, timestamped and archived.  Contributions are attributed to the appropriate user.  The entire system is searchable, with everything linked.  It allows for rich content, e.g. videos and animations where there is a pedagogical angle, and graphs and other analytical components where there is a data visualisation need.

The data would be also able to be accessed – potentially in unforeseen ways – via open APIs.  That is, other completely separate systems would be able to repurpose the data programmatically; as an example, a completely different web application could be devoted to analysing particular test instances and their results, and it would enjoy direct (read only) access to the required data via API to the OR4ALL system.

Cloud computation is achieved via open APIs.  The algorithms are proven and reproducible for given data sets, so practitioners or others looking to build further on an approach do not have to start from scratch; similarly, practitioners have a starting point if they want to expand or implement an algorithm in their own software.  Furthermore, other, non-default computation engines can potentially be “plugged in” behind the system (perhaps specific ones aimed at particular requirements, e.g. massively parallel dynamic programming).

Clearly a platform like this would be – at a minimum – an amazing boon for students.  But all users would benefit from the open, “many eyes” style of model and implementation development – the phenomenon that “somewhere out there, someone can easily help you”.  In particular, researchers and practitioners can find areas of common interest.

The system as described can start simple but grow in sophistication.  Reputation points might be gained for best solutions, with user points gained from previous best solutions decaying away over time.  Companies can offer bounties for the best solution to their difficult data set.  There would be plenty of opportunities for 3rd parties to provide a marketplace for alternative computation or analysis plug-ins via the APIs. Or, the system could potentially be monetised via advertising – for example, commercial OR companies could proffer their own software packages and services, with these ads appearing only on pages associated with that company’s specific areas of expertise.

Examples of the everyday use of this kind of system in practice might be (from a typical user’s point of view):
•    I get a notification email one day that someone is trying a new approach to solving a problem on a data set that I recently optimised;
•    I get a small boost in reputation because users upvoted an approach I suggested to someone else’s algorithm;
•    I use a proprietary piece of software (completely outside of the OR4ALL) system to find a new, closer-to-optimal solution to a hard problem, and upload it.  It ends up in the linked Results page for that problem, with an icon marking it as “unverified” (as it was run outside the OR4ALL computation framework);
•    I upload a teaching video to an Algorithm Approach page to help the students that Iam teaching.

Clearly there are some potential challenges to be overcome: the signal to noise ratio for one (keeping unhelpful contributions from polluting or distorting progressive development).  A system like this would also likely enforce standardisation of formulations, and to a lesser extent implementations – although this arguably has more benefit than downside.  Many in academia might also find it hard to move away from “research grant and published paper”-driven development, or otherwise be uncomfortable with voting or reputation-based status systems; clearly we would need appropriate and effective metrics to measure the contributions by each user or user group.

I firmly believe that this way of working will come about no matter what; I’d be very surprised if in 10 years time this more collaborative, technology-enabled approach had not overtaken journal-based research.  So wouldn’t it be better for the OR community to be self-directed and evolve in a very aware way towards this goal?  It might not even be particularly hard to build – as we have shown, most of the pieces are already proven possible in some form or other.  The possibilities and benefits of the system I have described are exciting and endless – if there was a truly open and powerful platform for OR with good community adoption, it would attain uses and purposes which we can now barely imagine.

Reinventing Discovery – a book about internet-powered collaborative science
Wakari – a new, hosted Python data analysis environment that has some of the features described above

## Biarri Applied Mathematics conference a success!

The first Biarri Applied Mathematics conference, or BAM, was hosted by the School of Mathematics and Physics at the University of Queensland on Monday (Feb 22). The conference was a big success, with around 65 people attending, including industry representatives, academics and students.

Dr Simon Dunstall from CSIRO won the prize for the best talk of the day, however all the talks (given by Operations Research practioners from both Biarri and from industry) were informative and interesting and generated discussion and questions. In particular it seemed that Network Flow techniques were very much alive and well, as they came up in several different modelling contexts throughout the day.

Biarri once again thanks those who attended as well as those behind the scenes who helped make the event a success.

## 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.

## Successfully Implementing Commercial Mathematics

We have grown Biarri based on successfully bringing the power of mathematics to bear on business. We try hard to make operations research easier for business to digest.  Over the last few years there are a few things we have learned that are worth pointing out.

1. Target businesses that need analytical support and know they need it. Many businesses now have lots of data but that they lack the analytical ability to utilise that data. The businesses we target understand that smart decisions are based on ‘results gleaned from algorithmic insight and executed with the confidence that comes from really doing the math’. ‘Analytics’ is now part of the business improvement conversation however you need to target businesses that have complex problems that are solvable and need solving. Additionally, we have always had better success when the problem has a clear owner who will benefit directly from solving the problem.

2. Differentiate your offering. ‘Optimisation’ and now ‘Analytics’ are overused terms. As applied mathematicians we can certainly bring some real science to the table. But this is not enough. What has emerged as very important is our ability to make the mathematics digestible. We have tried hard to deliver ‘Accessible Optimisation’. We believe optimisation is only powerful if it is:

• Easy to apply to real world operations
• Easy to understand (intuitive)
• Easy to access (usable)
• Affordable with minimum capital spend
• Fast and reliable

3. Focus on implementation practicalities. You need to keep your eye on the basics of project management. Some of the key issues for us have been:

• Work hard to keep the scope tight by focusing on the 20% of features that deliver 80% of the value.
• Use simple frameworks that everyone can understand. All our custom models and tools use a simple linear workflow/logic around a smart engine.
• Stay close to your customer and practice the art of no surprises.
• Excel is useful for modelling. It is available on every desk top, flexible, familiar, easy to use and accepted by non-technical managers.
• Develop and implement prototype models quickly and have a simple way of upgrading them when needed.  For example, we always keep our prototype engines separate to the front-end so we can easily port them to different solution frameworks.

## The Launch of Biarri’s WorkBench

With the impending launch of Biarri’s workbench and our ongoing close relationship with Schweppes for the daily routing of soft drink deliveries (an application of perhaps the most well known operations research problem: the vehicle routing problem), I thought that the following excerpt from a journal article submitted to the Asia Pacific Journal of Operations Research would be a very timely blog post.

The journal article is entitled “Real-Life Vehicle Routing with Time Windows for Visual Attractiveness and Operational Robustness” and it describes the vehicle routing algorithm we have implemented for Schweppes.

The excerpt details a specific example encompassing two things we are very passionate about at Biarri. First “Commercial Mathematics” – that is making OR (well not strictly just OR) work in the real world. And second, the revolutionary capabilities that the advent of cloud computing has for the delivery of software.

“Vehicle routing problems manifest in a remarkably wide range of commercial and non-commercial enterprises. From: industrial waste collection to grocery delivery; underground mining crew replenishment to postal and courier collection and delivery; inbound manufacturing component transportation to finished car distribution; in-home primary health care delivery to pathology specimen clearances from surgeries for analysis; and from coal seam gas field equipment maintenance to beverage distribution, to name but a few.

Automated planning systems used by industry at present are predominantly client-server or desktop based applications. Such systems are often: expensive, requiring a large upfront capital investment; accompanied by a large software deployment project requiring initial and ongoing IT department cooperation; customisable to a particular organisations requirements, however commonly retain a large amount of exposed functionality due to the breadth of the existing client base; and require substantial user training as the workflow is usually not restricted in a linear fashion …. Each of these characteristics constitutes a barrier to adoption of automated planning systems, and for most small to medium enterprises these barriers prove insurmountable.

With the advent of cloud computing and software as a service (SaaS) these barriers are being removed. SaaS: embodies a different commercial model; has essentially no IT footprint; mandates (as vendors may never directly interact with potential clients) simple intuitive linear workflows; and involves almost no end user training beyond perhaps an optional demonstration video.

The emergence of this new avenue for the delivery of optimisation based planning systems heralds, a heretofore, unparalleled opportunity for operations research practitioners to engage with a wider potential consumer base than ever before. However, the nature of the delivery mechanism requires the algorithms developed: to be robust and flexible (within their domain of application they must be capable to dealing with a wide range of input data); to have very short run times (the user base is more likely to be under time pressure than ever before); to produce high quality solutions (noting the inherent trade off between run time and solution quality); to be wrapped in a simple linear workflow (meaning it is always obvious what the next step in the planning process is); but above all, be able to produce real-life, practically implementable solutions, without the need for user training and/or experience.

For pure delivery, or pure pick up vehicle routing applications, real-life, practically implementable solutions are often synonymous with geographically compact, non-overlapping routes with little or no intra-route cross over. There are numerous reasons why such solutions are preferred …. If a customer cannot be serviced at the preferred time (e.g. the vehicle cannot get access, the customer is closed, another delivery is taking place, the customer is too busy), because the route stays in the same geographical area, it is easy to return to the customer at a later time. During busy traffic periods drivers are loathe to exit and re-enter a motorway to service individual customers. Even though such customers may be enroute to the
bulk of the customers the route services, thus incurring a minimum of additional kilometres, they may nevertheless be far from the majority of the customers the route services. If there is severe traffic disruption, it is easier to use local alternate routes between customers in a route that is geographically compact to ensure that pick-ups or deliveries can still be made. Third party transport providers, which prefer routes to be as simple as possible, may exert some influence over the planning process. Finally … it is easier to maintain customer relationships by assigning drivers to routes that routinely service a similar geographical area. In summary, solutions which are more visually attractive are more robust, and thus more likely to actually deliver the full extent of the cost savings that should flow from the use of automated planning systems.

This paper describes an algorithm for the vehicle routing problem with time windows, …. The algorithm is: robust and flexible; fast; wrapped in a user interface utilising a simple linear workflow and so requires no user training or experience; and produces high quality, visually attractive and practically implementable solutions.”

## Re-solving Linear Programs with COIN-OR

I recently had to go from solving a Linear Program (LP) once only, to modifying the problem and re-solving it multiple times. I was using the excellent open source COIN-OR libraries as my interface (OSI) and solver (CLP).

I found that you will get obscure-looking crashes (though, to be sure, I am using the downloaded binaries, not building COIN from source) inside OSI/COIN if you do not keep around the matrix and vector objects that you use to build your LP. It is safe to delete these objects if you are solving the problem once only, even before you have called initialSolve(). But it is not safe if you have to re-solve the LP!

A simple generic little helper class I used for this is:

class LPObjects
{
public:
CoinPackedMatrix* m_matrix;
double* m_objective, * m_col_lb, * m_col_ub, * m_rowrhs, * m_rowsen;

LPObjects()
{
m_objective = NULL;
m_col_lb = m_col_ub = NULL;
m_rowrhs = m_rowsen = NULL;
m_matrix = NULL;
}

void Create(int n_cols, int n_rows, double dblInfinity)
{
m_objective = new double[n_cols]; //the objective coefficients
m_col_lb = new double[n_cols]; //the column lower bounds
m_col_ub = new double[n_cols]; //the column upper bounds
m_rowrhs = new double[n_rows]; //the row rhs
m_rowsen = new char[n_rows]; //the row sense

for (int i = 0; i
m_objective[i] = 0.0;
for (int i = 0; i
{
m_col_lb[i] = 0.0;
m_col_ub[i] = dblInfinity;
}
m_matrix = new CoinPackedMatrix(false, 0, 0);
m_matrix->setDimensions(0, n_cols);
}
};

If si is your OsiXxxSolverInterface object, and g_LP is a static pointer to an instance of LPObjects, then g_LP can be initialised with:

if (g_LP == NULL)
{
g_LP = new LPObjects;
g_LP->Create(n_cols, n_rows, si->getInfinity());
}

Create your problem representation by filling out rowrhs, rowsen, etc, and be sure to use CoinPackedMatrix’s appendRows to populate your matrix coefficients in bulk rather than using multiple calls to appendRow (which is much much slower for larger LPs).

si->loadProblem(*g_LP->m_matrix, g_LP->m_col_lb, g_LP->m_col_ub, g_LP->m_objective, g_LP->m_rowsen, g_LP->m_rowrhs, NULL);

and solve with si->initialSolve(). Now you change the LP using the usual methods such as si->setColUpper(), and re-solve with si->resolve(). Note your call to si->setColUpper() (or whatever) does not directly reference the matrix or vectors of g_LP, but those objects must remain in memory!

Code used with binary distribution “CoinAll-1.2.0-win32-msvc9” under Windows Vista / Visual C++ Express 2008.

## Designing Distribution Networks for Utilities

Many utilities face the problem of designing distribution networks.  These networks need to reach all (or nearly all) households to distribute (or collect) the commodity supplied by the utility.  This may be electricity, gas, water, data (cable or optical fibre) or sewerage.

Typically these distribution networks are built as a subset of some underlying network.  Most commonly this is the street network.  The reason for this is obvious – the street network connects all households and businesses – which are the final demand points of utilities.  Some networks may piggyback on existing networks.  For example an optical fibre rollout may be done using existing power poles.

From a mathematical point of view we can consider the underlying points of demand (households or small collections of households) as nodes in a graph.  The potential connections between these nodes are arcs.  We refer to this network of potential connections as the underlying network.  If the distribution network can be represented as a tree (and this is often the case) then the problem of determining the best distribution network is similar to the minimum spanning tree problem solved on the underlying network (http://en.wikipedia.org/wiki/Minimum_spanning_tree).  This problem is straightforward to solve with an algorithm that is relatively easy to understand.  The main information required is the cost of the candidate arcs.  For example, it may be relatively cheap to string new cable between existing poles (for electricity or data networks), but much more expensive to dig a trench to install cable underground in an area with no overhead poles.

The problem faced by a utility will however have many practical considerations that cannot be handled by the classical minimum spanning tree algorithm.  These will include:

• The problem is really one of building several spanning trees, each of which can handle a maximum demand.  This arises because of underlying technical restrictions such as transformer capacity; the need to have pumping stations for water, gas and sewerage; the maximum number of optical fibre connections to a hub; etc.
• The cost of arcs in the tree depends on the downstream demand.  This arises because the pipes or cables need to get bigger as the tree collects more downstream demand.
• Splitting nodes in the tree may be expensive.  This can occur because of splicing costs (in optical fibre networks) or the need to distribute pressure evenly.
• The spanning trees will themselves need to be connected back to the “mains” network.  Indeed the problem of designing the mains network may need to be considered as part of the overall problem, though typically most of the cost will be in the feeder network due to the sheer number of connections required.
• The maximum network length from the mains to a node is limited due to pressure/voltage losses.

Recently Biarri has undertaken a Proof of Concept project with a utility to look at designing a distribution network.  We have formulated and solved an optimisation based approach to give solutions guaranteed to be within a very small margin of the optimal solution.  On a sample network covering around 2000 households we were able to achieve:

• An optimal solution in two minutes on standard PC’s
• 6% reduction in equipment costs
• Huge reduction in planning effort – it took many man weeks to design the same area by hand

The speed of the solution process frees up the network designer to consider higher level issues that are not part of the optimisation model, such as the possible saving from using different technical approaches.  These choices can be modelled as a series of “What if…?” scenarios.

We plan to extend the work done so far to cover even more of the practical issues faced by utilities.  A technical paper covering the work will be prepared in 2010.

## Using Open Street Map data for Australia

I’ve been using Open Street Map (OSM) data for Australia for generating matrices of travel times and distances that are suitable for input to truck routing optimisation problems. OSM is a world-wide map data set that anyone can edit and is impressively comprehensive.

Some of the resources I’ve used are www.osmaustralia.org, which does a regular batch job to extract country by country OSM data, and http://keepright.x10hosting.com/ which keeps an up to date list of map data errors. These types of errors are important to know about when producing routable data from OSM, in particular dead end one way streets and “almost junctions”.

I’ve been using Quantum GIS (QGIS) to look at the data after converting it to MID/MIF format. I can get it to label the lines that are one way streets, but unfortunately there is no way to show the line direction in QGIS, which is a major pain. (Actually there is a way but you have to get a source code branch from their repo and build it all etc etc). [Now that I think of it, a silly cheat way to do it would also be to produce another field in the map data, say a letter which represents whether the arc is “D” for down or “L” for left etc (based on the difference in the lat/longs of the start and end nodes of each arc), and label that way.]

I also found that the performance of QGIS is quite different depending on whether the data is opened as TAB or MIDMIF format. TAB format is fairly fast (just zooming, panning etc) but MIDMIF is quite noticeably slower. You’d think it wouldn’t make a difference as it would be using the same internal data representation, but obviously not.

I’m using some extra layers to show some of the processed data (picture below). For example, I have a layer which just shows the arcs involved in restricted turns, which I can layer on top of the street network and use a thicker line style for. I also use dots in another layer which I have produced based on my “island” processing. The dots represent “orphaned” nodes which are not on the main “island” of map data (which is connected in the sense that all nodes can reach all other nodes). These orphaned nodes will be ignored by the travel time calculation. There are around 9600 of these nodes in the entire set of Australia OSM routable data I’m using (which has 620042 nodes and 1503668 arcs in total). This filtered subset of OSM data I am using includes only street segments with a “highway” tag – this will exclude cycleways, pathways, hiking trails, ferry routes, ski slopes, building outlines, administrative boundaries, waterways etc.

Some observations on the OSM data (for Australia):
• One way information seems quite complete.
• Only 12% of the streets have road speed information (“max_speed” tag). This is an issue as vehicle routing needs highways to have a faster speed otherwise they won’t be used (and there will be lots of rat-running for example). In longer routes (e.g. interstate) the travel time will also be grossly overestimated. A couple of things we could do here: search for all segments with “highway”, “motorway”, or “freeway” in their names and assume some sort of speed like 80km/h on these segments. Or, with a bit more coding effort, if there are chains of segments where one has a speed and the others with the same street name don’t, assume that speed on all of those segments.
• About 70% of the road segments have street names. Some of the unnamed segments are bits of roundabout, service roads, motorway on/off-ramps etc. But, there are also a lot of streets which are classified (by their “highway” tag) as “secondary”, “tertiary”, “unclassified” and even “residential” which are not named. This is an issue when vehicle routing needs to produce driver directions or verbose path information.
• There’s only several hundred instances of streets which have restricted manoeuvre information (banned right hand turns being the prime example). Most of these instances are in Sydney. In reality this number should be in the thousands or tens of thousands. This will likely be the biggest issue from a routing quality point of view – it will mean you can do many illegal right turns.
• I found a weird character or two at the end of the file, which causes both Python and C++ file reading functions to get confused and read blanks forever. Weird, but easily avoided.