M E M O R Y L E S S N E S S

19:43 2nd May 2012

Notes: 1

Tags: shoes shoelaces optimization tsp traveling salesman problem operations research

Optimal Shoelacing

This [lacing shoes] is of course an instance of a Traveling Salesman Problem (TSP). Each lace hole represents a city which can be visited exactly once. For example, the slack is maximized by finding the shortest tour, while the slack can be minimized by finding the longest Hamiltonian circuit. Of course, my daughter would prefer finding a good balance between these two extreme solutions, while also ensuring that tightening and loosening the laces are relatively easy to perform. The former objective can be equivalently specified in terms of minimizing deviation from a desired tour length, while the latter requirement can perhaps be approximated by eliminating unfavorable connection patterns and reducing overall friction.

This [lacing shoes] is of course an instance of a Traveling Salesman Problem (TSP). Each lace hole represents a city which can be visited exactly once. For example, the slack is maximized by finding the shortest tour, while the slack can be minimized by finding the longest Hamiltonian circuit. Of course, my daughter would prefer finding a good balance between these two extreme solutions, while also ensuring that tightening and loosening the laces are relatively easy to perform. The former objective can be equivalently specified in terms of minimizing deviation from a desired tour length, while the latter requirement can perhaps be approximated by eliminating unfavorable connection patterns and reducing overall friction.

20:48 28th Oct 2010

Notes: 1

Tags: agriculture bees crops math mathematics np-hard operations research optimization pollination traveling salesman problem tsp operations management orms

Bees Resolve a Complex Mathematical Problem Daily

Bees solve the Traveling Salesman Problem everyday.

The TSP is heavily used in theoretical compute science and in operations research, and is classified as a NP-hard problem.

In its original formulation, the solver is given a list of cities, and their pairwise distances, and is then tasked with finding the shortest possible distance that will allow them to visit each of the cities exactly once.

…

“Foraging bees solve traveling salesman problems every day. They visit flowers at multiple locations and, because bees use lots of energy to fly, they find a route which keeps flying to a minimum,” explains Dr Nigel Raine.

…

“Despite their tiny brains bees are capable of extraordinary feats of behavior. We need to understand how they can solve the Traveling Salesman Problem without a computer. What short-cuts do they use?” Raine says.

The new investigation could have significant implications for agriculture, because bee pollination patterns are critically important for next year’s crops.

(image source)

19:14 21st Aug 2010

Notes: 3

Tags: informs management science operations research optimization seat geek tickets orms

SeatGeek

Looking for upcoming sports tickets? http://seatgeek.com/ uses an algorithm to predict when to optimize your purchase.

(via INFORMS)

This is neat. O.R. for the win, quite literally in the case of sports tickets.

18:38 3rd Aug 2010

Notes: 6

Tags: call center staffing call centers contact centers demand forecasting forecasting gurvich industrial engineering informs itai gurvich journal article management science operations research optimization staffing uncertain demand orms

Staffing Call Centers with Uncertain Demand Forecasts: A Chance-Constrained Optimization Approach

Here’s an interesting paper by Gurvich et al. that’s in the current issue of Management Science.

Full paper here.

INFORMS 2005 Presentations

I had two presentations at INFORMS San Francisco 2005. Here’s the session info.

“Optimal Call Center Capacity Allocation Model,” by W. Lin, A. Dhawan, S. Myles, and S. Venkatachalam

Abstract: The presentation describes the call volume allocation process, business constraints, and areas of improvement needed. The mathematical model (Linear Programming) that was built to optimally allocated call volumes and the detailed formulation of this model will be explained. The authors will compare the performance of this optimization with the current process and quantify the monetary benefits of using this model in real operations.

“Optimization Strategies for Resolving Inventory Problems in Customer Service Repair Centers,” by S. Myles, V. Buraparate, and T. Thruston

Abstract: The authors discuss an overall process for inventory management over the entire life cycle of consumer product support. Challenges and opportunities that exist in the current process are identified. The optimization techniques that fit the situation in different phases of the product life cycle (e.g., New Product Introduction (NPI) and End-of-Life (EOL)) will be shared along with the results of their implementation.

mem·o·ry·less·ness