Optimization

Optimization can be applied to many common problems such as scheduling, routing, planning, and resource allocation, to find solutions that create real value in several ways:

Soundience typically uses optimization in combination with data mining or other modelling approaches.

Approach and Algorithms

Our approach is to look first at the objective of solving each problem, i.e., is the challenge to reduce cost, decrease time, increase value, etc. Whe then identify the relevant constraints (e.g., maximum marketing budget for a mail campaign, capacity for transport problems), and the sensitivities around these constraints.

We then formulate the optimization problem, often with a web-based front end that allows you to explore different inputs and view outputs in an actionable way, and solve it using the appropriate algorithms.

Soundience builds prototypes of optimization solutions using a variety of open-source algorithms, which perform well enough. For further development and for deployment, we have a partnership with Satalia, a start-up out of University College London, which gives us access to the best among hundreds of diverse optimization algorithms, specific for each problem, and are accessed over the cloud.

In addition to developing fully-fledged optimization models, we are very interested in using optimization models to identify the theoretical optimum for a problem, and then developing much faster heuristics that nearly reach the optimium, but at a much lower computation cost (see Credit Card Offers example, below).

Case Example: Boris Bikes (prototype)

We used optimization in a pilot example for a client that was bidding on the operation of the public bicycle rental scheme in London, to identify the likely optimal configuration of shuttles to move bicycles around between different parking stations.

The optimization model looked at a wide variety of demand scenarios, and demonstrated a significant increase in value, both by reducing unmet demand (i.e., bicycles in the wrong place at any time), and by reducing the number of shuttles required.

In the screenshot at the right, circles represent the bicycle parking stations (size of circle proportional to the capacity at that station), red lines represent common routes (shown as straight lines for simplicity), and the graphs show cumulative inflow and outflow of bicycles over a day in green and red, respectively. Unmet demand (for a non-optimized case) is shown in red. The timeline along the top shows the progress of an animated simulation over a 24-hour period.

Please get in touch if you'd like to see a demo, or discuss relevance to your application.

Case Example: Marketing Offer Optimization (prototype)

In another project, we developed a proof of concept for a credit card company, in which we demonstrated how optimization could be used to target a limited number of special offers to a heterogeneous customer base. The optimization showed a significant increase in value over alternative allocation approaches, for customers, merchants, and for the credit card company itself.

We used this theoretical maximum to calibrate a number of heuristic approaches, which came within 90% of the theoretical optimum, but with a computation speed hundreds of times faster than the full optimization, allowing the heuristics to be used in real-time (e.g., for generating offers on till receipts).

In the screenshot at the left, the area at the left shows customers as circles (size of circle roughly proportional to customer value), and the tiny dots are offers (red offers are higher value, blue dots lower value). The area to the right above the graph shows offers that have not been allocated (at the beginning of each simulation, all offers start off in this area). The bar graph at the bottom shows the value of random allocation in grey, the optimal value in blue, and various heuristic-based allocations in-between in other colours. Notice that the blue optimization is significantly higher than the random allocation, but the yellow heuristic-based allocation comes close. For other combinations of offers and customers the spread can be more or less pronounced (the demo allows you to vary this).

Again, please get in touch if you'd like to get together to see a live demo or discuss how this might apply to your requirements.