RESEARCHERS APPROACH NEW SPEED LIMIT FOR SEMINAL PROBLEM

Summary from the TLDR newsletter

The traveling salesperson problem asks for the ideal route through a list of locations, minimizing mileage. It is notoriously difficult, but a mathematical model called linear programming is able to approximate the problem as a set of equations and find the best solution. Integer linear programming (ILP) is a variant of linear programming that optimizes for problems solving whole-number amounts. A researcher from the University of Washington has combined geometric tools to create a new, faster algorithm for solving ILP in almost the same time as a trivial binary case. It is the first major improvement to ILP solvers in nearly 40 years.