I have often wondered if Scrum can be characterized as a local search technique, specifically hill-climbing, and therefore can be understood from a theoretical perspective by comparison. In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Similarly, Scrum is an empirical method for creating solutions to user problems where optimal solutions are difficult or impossible and so software product solutions are created iteratively by maximizing perceived customer value. The following table compares some of the basic elements of local search and Scrum.
| Local Search[1] | Scrum |
| Local search algorithms move from solution to solution in the space of candidate solutions (the search space) by applying local changes, until a solution deemed optimal is found or a time bound is elapsed. | Starts from a current set of software functionality and adds incremental solution elements in sprints and releases. |
| A local search algorithm starts from a candidate solution and then iteratively moves to a neighbor solution. | Starts from a current set of software functionality and iteratively adds new solution elements. |
| A neighborhood being the set of all potential solutions that differ from the current solution by the minimal possible extent. | The backlog is a set of potential solution elements that can be incrementally added to the functionality. |
| Typically, every candidate solution has more than one neighbor solution; the choice of which one to select is taken using only information about the solutions in the neighborhood of the current assignment, hence the name local search. | Sprint planning from a backlog considers only incremental solutions that can be achieved from the current solution state. |
| When the choice of the neighbor solution is done by taking the one locally maximizing the criterion, i.e.: a greedy search, the metaheuristic takes the name hill climbing. | Focus on maximizing customer value in sprint planning. |
| The search can terminate after a given time bound, or when the best solution found thus far has not improved in a given number of steps. | Development can conclude with a release of the minimum viable product. |
Accepting the analogy of Scrum as a local search process allows us to identify interesting properties of Scrum development and products.
| Local Search | Scrum |
| Local search does not provide a guarantee that any given solution is optimal. Hill climbing will not necessarily find the global maximum but may instead converge on a local maximum. | Solutions built using Scrum may reach a point of being unsustainable or too expensive to continue to enhance due to technical debt or absence of architectural structure. |
| When no improving neighbors are present, local search is stuck at a locally optimal point. This local-optima problem can be cured by using restarts. | If elements of a current solution inhibit or do not support the addition of new solution elements, product elements can be refactored. |
| Restarts are included in the computation of total complexity of local search methods. | Refactoring has cost. Evaluating Scrum and other Agile methods against plan-based methods should include realistic assessment of the cost of refactoring. |
| Other local search algorithms try to overcome the problem of local maxima with methods such as stochastic hill climbing, random walks and simulated annealing. | Randomizing techniques do not seem appropriate to software product development. E.g., imagine deciding to remove a feature at random and recreate it or randomly selecting backlog items to develop. |
How can we best assess the impacts of local search maxima in Scrum development (coding dead-ends or technical debt) and the impact of refactoring? Are there other lessons learned from local search methods that provide insight into Scrum and other Agile methods?
[1] Excerpted from Wikipedia article on Local Search 9/2/2022.
