Linear Optimization

Linear optimization (or linear programming) is the name given to computing the best solution to a problem modeled as a set of linear relationships. These problems arise in many scientific and engineering disciplines. (The word "programming" is a bit of a misnomer, similar to how "computer" once meant "a person who computes." Here, "programming" refers to the arrangement of a plan, rather than programming in a computer language.)

For a good primer on linear optimization, we recommend the Mosek modeling cookbook.

Tools

Google provides two ways to solve LP problems:

  • MPSolver: A wrapper for several third-party LP solvers, which use standard branch-and-bound techniques.
  • The Linear Optimization Service in Google Apps Script lets developers make function calls to solve linear optimization problems. It relies on Glop for pure linear optimization problems where all variables can take on real values. If any variables are constrained to be integers, the service uses SCIP, from Zuse-Institut Berlin.

Only the first option requires installing OR-Tools.