C++ Reference: linear_solver

This documentation is automatically generated.

A C++ wrapper that provides a simple and unified interface to several linear programming and mixed integer programming solvers: GLOP, GLPK, CLP, CBC, and SCIP. The wrapper can also be used in Java, C#, and Python via SWIG.

What is Linear Programming?

In mathematics, linear programming (LP) is a technique for optimization of a linear objective function, subject to linear equality and linear inequality constraints. Informally, linear programming determines the way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model and given some list of requirements represented as linear equations.

The most widely used technique for solving a linear program is the Simplex algorithm, devised by George Dantzig in 1947. It performs very well on most instances, for which its running time is polynomial. A lot of effort has been put into improving the algorithm and its implementation. As a byproduct, it has however been shown that one can always construct problems that take exponential time for the Simplex algorithm to solve. Research has thus focused on trying to find a polynomial algorithm for linear programming, or to prove that linear programming is indeed polynomial.

Leonid Khachiyan first exhibited in 1979 a weakly polynomial algorithm for linear programming. "Weakly polynomial" means that the running time of the algorithm is in O(P(n) * 2^p) where P(n) is a polynomial of the size of the problem, and p is the precision of computations expressed in number of bits. With a fixed-precision, floating-point-based implementation, a weakly polynomial algorithm will thus run in polynomial time. No implementation of Khachiyan's algorithm has proved efficient, but a larger breakthrough in the field came in 1984 when Narendra Karmarkar introduced a new interior point method for solving linear programming problems. Interior point algorithms have proved efficient on very large linear programs.

Check Wikipedia for more detail: http://en.wikipedia.org/wiki/Linear_programming


Example of a Linear Program
     3x + y
   subject to:
     1.5 x + 2 y <= 12
     0 <= x <= 3
     0 <= y <= 5
A linear program has: 1) a linear objective function 2) linear constraints that can be equalities or inequalities 3) bounds on variables that can be positive, negative, finite or infinite.


What is Mixed Integer Programming?

Here, the constraints and the objective are still linear but there are additional integrality requirements for variables. If all variables are required to take integer values, then the problem is called an integer program (IP). In most cases, only some variables are required to be integer and the rest of the variables are continuous: this is called a mixed integer program (MIP). IPs and MIPs are generally NP-hard.

Integer variables can be used to model discrete decisions (build a datacenter in city A or city B), logical relationships (only place machines in datacenter A if we have decided to build datacenter A) and approximate non-linear functions with piecewise linear functions (for example, the cost of machines as a function of how many machines are bought, or the latency of a server as a function of its load).


How to use the wrapper

The user builds the model and solves it through the MPSolver class, then queries the solution through the MPSolver, MPVariable and MPConstraint classes. To be able to query a solution, you need the following:
   - A solution exists: MPSolver::Solve has been called and a solution
   has been found.
   - The model has not been modified since the last time
   MPSolver::Solve was called. Otherwise, the solution obtained
   before the model modification may not longer be feasible or

@see ../examples/linear_programming.cc for a simple LP example.

@see ../examples/integer_programming.cc for a simple MIP example.

All methods cannot be called successfully in all cases. For example: you cannot query a solution when no solution exists, you cannot query a reduced cost value (which makes sense only on continuous problems) on a discrete problem. When a method is called in an unsuitable context, it aborts with a LOG(FATAL). TODO(user): handle failures gracefully.


For developers: How the wrapper works

MPSolver stores a representation of the model (variables, constraints and objective) in its own data structures and a pointer to a MPSolverInterface that wraps the underlying solver (GLOP, CBC, CLP, GLPK, or SCIP) that does the actual work. The underlying solver also keeps a representation of the model in its own data structures. The model representations in MPSolver and in the underlying solver are kept in sync by the 'extraction' mechanism: synchronously for some changes and asynchronously (when MPSolver::Solve is called) for others. Synchronicity depends on the modification applied and on the underlying solver.