linear_solver.h File Reference

Detailed Description

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

maximize: 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 optimal.

See also

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

../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.

Definition in file linear_solver.h.

Go to the source code of this file.

Classes
class	MPSolver
	This mathematical programming (MP) solver class is the main class though which users build and solve problems. More...
class	MPObjective
	A class to express a linear objective. More...
class	MPVariable
	The class for variables of a Mathematical Programming (MP) model. More...
class	MPConstraint
	The class for constraints of a Mathematical Programming (MP) model. More...
class	MPSolverParameters
	This class stores parameter settings for LP and MIP solvers. More...
class	MPSolverInterface

Namespaces
	operations_research

Functions
bool	SolverTypeIsMip (MPModelRequest::SolverType solver_type)
bool	SolverTypeIsMip (MPSolver::OptimizationProblemType solver_type)
const absl::string_view	ToString (MPSolver::OptimizationProblemType optimization_problem_type)
std::ostream &	operator<< (std::ostream &os, MPSolver::OptimizationProblemType optimization_problem_type)
std::ostream &	operator<< (std::ostream &os, MPSolver::ResultStatus status)
bool	AbslParseFlag (absl::string_view text, MPSolver::OptimizationProblemType *solver_type, std::string *error)
std::string	AbslUnparseFlag (MPSolver::OptimizationProblemType solver_type)
bool	MPSolverResponseStatusIsRpcError (MPSolverResponseStatus status)

Variables
constexpr double	kDefaultPrimalTolerance = 1e-07