Combinatorial Optimization Overview

Combinatorial optimization is an approach to finding the best solution out of a very large set of possible solutions. When the set is so large that it's impractical to search through all of them, various techniques can be used to narrow down the set or speed up the search.

Google's OR-Tools software suite makes it easy to solve many types of combinatorial optimization problems. It includes solvers for:

Constraint Programming
A set of techniques for finding feasible solutions to a problem expressed as constraints (e.g., a room can't be used for two events simultaneously, or the distance to the crops must be less than the length of the hose, or no more than five TV shows can be recorded at once).
Linear Programming
The Glop linear optimizer finds the optimal value of a linear objective function, given a set of linear inequalities as constraints (e.g., assigning people to jobs, or finding the best allocation of a set of resources while minimizing cost). Glop and the mixed-integer programming software SCIP are also available via both Google Sheets and Google Apps Script.
Vehicle Routing
A specialized library for identifying best paths given constraints (e.g., "this truck can't hold more than 20,000 pounds" or "all deliveries must be made within a two-hour window").
Graph Algorithms
Code for finding shortest paths, min-cost flows, max flows, and linear sum assignments.

Send feedback about...