Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | Namespaces | Functions | Variables
linear_solver.h File Reference
#include <atomic>
#include <cstdint>
#include <functional>
#include <limits>
#include <map>
#include <memory>
#include <optional>
#include <ostream>
#include <string>
#include <utility>
#include <vector>
#include "absl/base/attributes.h"
#include "absl/base/port.h"
#include "absl/base/thread_annotations.h"
#include "absl/container/flat_hash_map.h"
#include "absl/flags/declare.h"
#include "absl/log/check.h"
#include "absl/status/status.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/time/clock.h"
#include "absl/time/time.h"
#include "absl/types/optional.h"
#include "ortools/base/logging.h"
#include "ortools/linear_solver/linear_expr.h"
#include "ortools/linear_solver/linear_solver.pb.h"
#include "ortools/linear_solver/linear_solver_callback.h"
#include "ortools/port/proto_utils.h"
#include "ortools/util/lazy_mutable_copy.h"

Go to the source code of this file.

Classes

class  operations_research::MPSolver
 
class  operations_research::MPObjective
 A class to express a linear objective. More...
 
class  operations_research::MPVariable
 The class for variables of a Mathematical Programming (MP) model. More...
 
class  operations_research::MPConstraint
 
class  operations_research::MPSolverParameters
 
class  operations_research::MPSolverInterface
 

Namespaces

namespace  operations_research
 In SWIG mode, we don't want anything besides these top-level includes.
 

Functions

 ABSL_DECLARE_FLAG (bool, linear_solver_enable_verbose_output)
 
 ABSL_DECLARE_FLAG (bool, log_verification_errors)
 
 ABSL_DECLARE_FLAG (bool, verify_solution)
 
bool operations_research::SolverTypeIsMip (MPModelRequest::SolverType solver_type)
 There is a homonymous version taking a MPSolver::OptimizationProblemType.
 
bool operations_research::SolverTypeIsMip (MPSolver::OptimizationProblemType solver_type)
 
absl::string_view operations_research::ToString (MPSolver::OptimizationProblemType optimization_problem_type)
 
std::ostream & operations_research::operator<< (std::ostream &os, MPSolver::OptimizationProblemType optimization_problem_type)
 
std::ostream & operations_research::operator<< (std::ostream &os, MPSolver::ResultStatus status)
 
bool operations_research::AbslParseFlag (const absl::string_view text, MPSolver::OptimizationProblemType *solver_type, std::string *error)
 
std::string operations_research::AbslUnparseFlag (MPSolver::OptimizationProblemType solver_type)
 
bool operations_research::MPSolverResponseStatusIsRpcError (MPSolverResponseStatus status)
 

Variables

constexpr double operations_research::kDefaultPrimalTolerance = 1e-07
 

Detailed Description

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

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.

Function Documentation

◆ ABSL_DECLARE_FLAG() [1/3]

ABSL_DECLARE_FLAG ( bool ,
linear_solver_enable_verbose_output  )

◆ ABSL_DECLARE_FLAG() [2/3]

ABSL_DECLARE_FLAG ( bool ,
log_verification_errors  )

◆ ABSL_DECLARE_FLAG() [3/3]

ABSL_DECLARE_FLAG ( bool ,
verify_solution  )