operations_research::MPSolver Class Reference

This mathematical programming (MP) solver class is the main class though which users build and solve problems. More...

#include <linear_solver.h>

List of all members.

Public Types

enum OptimizationProblemType

The type of problems (LP or MIP) that will be solved and the underlying solver (GLPK, CLP, CBC or SCIP) that will solve them. More...

enum ResultStatus {
  OPTIMAL, FEASIBLE, INFEASIBLE, UNBOUNDED,
  ABNORMAL, NOT_SOLVED
}

Solve. More...

enum LoadStatus { NO_ERROR = 0, DUPLICATE_VARIABLE_ID = 2, UNKNOWN_VARIABLE_ID = 3 }

Methods using protocol buffers. More...

enum BasisStatus {
  FREE = 0, AT_LOWER_BOUND, AT_UPPER_BOUND, FIXED_VALUE,
  BASIC
}

Misc. More...

Public Member Functions

MPSolver (const string &name, OptimizationProblemType problem_type)

namespace

virtual ~MPSolver ()

string Name () const

void Clear ()

Clears the objective (including the optimization direction), all variables and constraints.

int NumVariables () const

Variables Returns the number of variables.

MPVariable * LookupVariableOrNull (const string &var_name) const

Look up a variable by name, and return NULL if it does not exist.

MPVariable * MakeVar (double lb, double ub, bool integer, const string &name)

Creates a variable with the given bounds, integrality requirement and name.

MPVariable * MakeNumVar (double lb, double ub, const string &name)

Creates a continuous variable.

MPVariable * MakeIntVar (double lb, double ub, const string &name)

Creates an integer variable.

MPVariable * MakeBoolVar (const string &name)

Creates a boolean variable.

void MakeVarArray (int nb, double lb, double ub, bool integer, const string &name_prefix, std::vector< MPVariable * > *vars)

Creates an array of variables.

void MakeNumVarArray (int nb, double lb, double ub, const string &name, std::vector< MPVariable * > *vars)

Creates an array of continuous variables.

void MakeIntVarArray (int nb, double lb, double ub, const string &name, std::vector< MPVariable * > *vars)

Creates an array of integer variables.

void MakeBoolVarArray (int nb, const string &name, std::vector< MPVariable * > *vars)

Creates an array of boolean variables.

int NumConstraints () const

Constraints Returns the number of constraints.

MPConstraint * LookupConstraintOrNull (const string &constraint_name) const

Look up a constraint by name, and return NULL if it does not exist.

MPConstraint * MakeRowConstraint (double lb, double ub)

Creates a linear constraint with given bounds.

MPConstraint * MakeRowConstraint ()

Creates a constraint with -infinity and +infinity bounds.

MPConstraint * MakeRowConstraint (double lb, double ub, const string &name)

Creates a named constraint with given bounds.

MPConstraint * MakeRowConstraint (const string &name)

Creates a named constraint with -infinity and +infinity bounds.

const MPObjective & Objective () const

Objective Note that the objective is owned by the solver, and is initialized to its default value (see the MPObjective class below) at construction.

MPObjective * MutableObjective ()

ResultStatus Solve ()

Solves the problem using default parameter values.

ResultStatus Solve (const MPSolverParameters &param)

Solves the problem using the specified parameter values.

void Reset ()

Advanced usage: resets extracted model to solve from scratch.

LoadStatus LoadModel (const MPModelProto &input_model)

Loads model from protocol buffer.

void ExportModel (MPModelProto *output_model) const

Exports model to protocol buffer.

void FillSolutionResponse (MPSolutionResponse *response) const

Encodes the current solution in a solution response protocol buffer.

void SuppressOutput ()

Suppresses all output from the underlying solver.

void EnableOutput ()

Enables a reasonably verbose output from the underlying solver.

void set_write_model_filename (const string &filename)

string write_model_filename () const

void set_time_limit (int64 time_limit)

int64 time_limit () const

int64 wall_time () const

Returns wall_time() in milliseconds since the creation of the solver.

int64 iterations () const

Returns the number of simplex iterations.

int64 nodes () const

Returns the number of branch-and-bound nodes.

bool CheckNameValidity (const string &name)

Checks the validity of a variable or constraint name.

bool CheckAllNamesValidity ()

Checks the validity of all variables and constraints names.

string SolverVersion () const

Returns a string describing the underlying solver and its version.

void * underlying_solver ()

Advanced usage: returns the underlying solver so that the user can use solver-specific features or features that are not exposed in the simple API of MPSolver.

double ComputeExactConditionNumber () const

Advanced usage: computes the exact condition number of the current scaled basis: L1norm(B) * L1norm(inverse(B)), where B is the scaled basis.

double objective_value () const

DEPRECATED Setters and getters for the objective.

double best_objective_bound () const

void ClearObjective ()

void SetObjectiveCoefficient (const MPVariable *const var, double coeff)

void SetObjectiveOffset (double value)

void AddObjectiveOffset (double value)

void SetOptimizationDirection (bool maximize)

void SetMinimization ()

void SetMaximization ()

bool Maximization () const

bool Minimization () const

Static Public Member Functions

static void SolveWithProtocolBuffers (const MPModelRequest &model_request, MPSolutionResponse *response)

Solves the model encoded by a MPModelRequest protocol buffer and fills the solution encoded as a MPSolutionResponse.

static double infinity ()

Infinity. You can use -MPSolverinfinity() for negative infinity.

Friends

class GLPKInterface

class CLPInterface

class CBCInterface

class SCIPInterface

class MPSolverInterface

Detailed Description

This mathematical programming (MP) solver class is the main class though which users build and solve problems.

Definition at line 164 of file linear_solver.h.

Member Enumeration Documentation

enum operations_research::MPSolver::OptimizationProblemType

The type of problems (LP or MIP) that will be solved and the underlying solver (GLPK, CLP, CBC or SCIP) that will solve them.

Definition at line 168 of file linear_solver.h.

enum operations_research::MPSolver::ResultStatus

Solve.

The status of solving the problem.

Todo:: TODO(user): Figure out once and for all what the status of underlying solvers exactly mean, especially for feasible and infeasible.

Enumerator:

OPTIMAL	optimal.
FEASIBLE	feasible, or stopped by limit.
INFEASIBLE	proven infeasible.
UNBOUNDED	proven unbounded.
ABNORMAL	abnormal, i.e., error of some kind.
NOT_SOLVED	not been solved yet.

Definition at line 272 of file linear_solver.h.

enum operations_research::MPSolver::LoadStatus

Methods using protocol buffers.

The status of loading the problem from a protocol buffer.

Enumerator:

NO_ERROR	no error has been encountered.
DUPLICATE_VARIABLE_ID	Skip value '1' to stay consistent with the .proto. error: two variables have the same id.
UNKNOWN_VARIABLE_ID	error: a variable has an unknown id.

Definition at line 292 of file linear_solver.h.

enum operations_research::MPSolver::BasisStatus

Misc.

Advanced usage: possible basis status values for a variable and the slack variable of a linear constraint.

Enumerator:

FREE
AT_LOWER_BOUND
AT_UPPER_BOUND
FIXED_VALUE
BASIC

Definition at line 323 of file linear_solver.h.

Constructor & Destructor Documentation

operations_research::MPSolver::MPSolver	(	const string &	name,
		OptimizationProblemType	problem_type
	)

namespace

Definition at line 322 of file linear_solver.cc.

operations_research::MPSolver::~MPSolver ( ) [virtual]

Definition at line 331 of file linear_solver.cc.

Member Function Documentation

string operations_research::MPSolver::Name ( ) const [inline]

Definition at line 187 of file linear_solver.h.

void operations_research::MPSolver::Clear ( )

Clears the objective (including the optimization direction), all variables and constraints.

All the other properties of the MPSolver (like the time limit) are kept untouched.

Definition at line 604 of file linear_solver.cc.

int operations_research::MPSolver::NumVariables ( ) const [inline]

Variables Returns the number of variables.

Definition at line 198 of file linear_solver.h.

MPVariable * operations_research::MPSolver::LookupVariableOrNull ( const string & var_name ) const

Look up a variable by name, and return NULL if it does not exist.

Definition at line 335 of file linear_solver.cc.

MPVariable * operations_research::MPSolver::MakeVar	(	double	lb,
		double	ub,
		bool	integer,
		const string &	name
	)

Creates a variable with the given bounds, integrality requirement and name.

Bounds can be finite or +/- MPSolver::infinity(). The MPSolver owns the variable (i.e. the returned pointer is borrowed). Variable names must be unique (it may crash otherwise). Empty variable names are allowed, an automated variable name will then be assigned.

Definition at line 627 of file linear_solver.cc.

MPVariable * operations_research::MPSolver::MakeNumVar	(	double	lb,
		double	ub,
		const string &	name
	)

Creates a continuous variable.

Definition at line 640 of file linear_solver.cc.

MPVariable * operations_research::MPSolver::MakeIntVar	(	double	lb,
		double	ub,
		const string &	name
	)

Creates an integer variable.

Definition at line 645 of file linear_solver.cc.

MPVariable * operations_research::MPSolver::MakeBoolVar ( const string & name )

Creates a boolean variable.

Definition at line 650 of file linear_solver.cc.

void operations_research::MPSolver::MakeVarArray	(	int	nb,
		double	lb,
		double	ub,
		bool	integer,
		const string &	name_prefix,
		std::vector< MPVariable * > *	vars
	)

Creates an array of variables.

All variables created have the same bounds and integrality requirement.

Parameters:

name

the prefix of the variable names. Variables are named name0, name1, ...

Definition at line 654 of file linear_solver.cc.

void operations_research::MPSolver::MakeNumVarArray	(	int	nb,
		double	lb,
		double	ub,
		const string &	name,
		std::vector< MPVariable * > *	vars
	)

Creates an array of continuous variables.

Definition at line 677 of file linear_solver.cc.

void operations_research::MPSolver::MakeIntVarArray	(	int	nb,
		double	lb,
		double	ub,
		const string &	name,
		std::vector< MPVariable * > *	vars
	)

Creates an array of integer variables.

Definition at line 685 of file linear_solver.cc.

void operations_research::MPSolver::MakeBoolVarArray	(	int	nb,
		const string &	name,
		std::vector< MPVariable * > *	vars
	)

Creates an array of boolean variables.

Definition at line 693 of file linear_solver.cc.

int operations_research::MPSolver::NumConstraints ( ) const [inline]

Constraints Returns the number of constraints.

Definition at line 244 of file linear_solver.h.

MPConstraint * operations_research::MPSolver::LookupConstraintOrNull ( const string & constraint_name ) const

Look up a constraint by name, and return NULL if it does not exist.

Definition at line 342 of file linear_solver.cc.

MPConstraint * operations_research::MPSolver::MakeRowConstraint	(	double	lb,
		double	ub
	)

Creates a linear constraint with given bounds.

Bounds can be finite or +/- MPSolver::infinity(). The MPSolver class assumes ownership of the constraint.

Returns:: a pointer to the newly created constraint.

Definition at line 699 of file linear_solver.cc.

MPConstraint * operations_research::MPSolver::MakeRowConstraint ( )

Creates a constraint with -infinity and +infinity bounds.

Definition at line 703 of file linear_solver.cc.

MPConstraint * operations_research::MPSolver::MakeRowConstraint	(	double	lb,
		double	ub,
		const string &	name
	)

Creates a named constraint with given bounds.

Definition at line 707 of file linear_solver.cc.

MPConstraint * operations_research::MPSolver::MakeRowConstraint ( const string & name )

Creates a named constraint with -infinity and +infinity bounds.

Definition at line 721 of file linear_solver.cc.

const MPObjective& operations_research::MPSolver::Objective ( ) const [inline]

Objective Note that the objective is owned by the solver, and is initialized to its default value (see the MPObjective class below) at construction.

Definition at line 263 of file linear_solver.h.

MPObjective* operations_research::MPSolver::MutableObjective ( ) [inline]

Definition at line 264 of file linear_solver.h.

MPSolver::ResultStatus operations_research::MPSolver::Solve ( )

Solves the problem using default parameter values.

Definition at line 753 of file linear_solver.cc.

MPSolver::ResultStatus operations_research::MPSolver::Solve ( const MPSolverParameters & param )

Solves the problem using the specified parameter values.

Definition at line 758 of file linear_solver.cc.

void operations_research::MPSolver::Reset ( )

Advanced usage: resets extracted model to solve from scratch.

Definition at line 615 of file linear_solver.cc.

MPSolver::LoadStatus operations_research::MPSolver::LoadModel ( const MPModelProto & input_model )

Loads model from protocol buffer.

Methods using protocol buffers.

Definition at line 397 of file linear_solver.cc.

void operations_research::MPSolver::ExportModel ( MPModelProto * output_model ) const

Exports model to protocol buffer.

Definition at line 461 of file linear_solver.cc.

void operations_research::MPSolver::FillSolutionResponse ( MPSolutionResponse * response ) const

Encodes the current solution in a solution response protocol buffer.

Only nonzero variable values are stored in order to reduce the size of the MPSolutionResponse protocol buffer.

Definition at line 524 of file linear_solver.cc.

void operations_research::MPSolver::SolveWithProtocolBuffers	(	const MPModelRequest &	model_request,
		MPSolutionResponse *	response
	)			`[static]`

Solves the model encoded by a MPModelRequest protocol buffer and fills the solution encoded as a MPSolutionResponse.

static

Note(user): This creates a temporary MPSolver and destroys it at the end. If you want to keep the MPSolver alive (for debugging, or for incremental solving), you should write another version of this function that creates the MPSolver object on the heap and returns it.

Definition at line 583 of file linear_solver.cc.

static double operations_research::MPSolver::infinity ( ) [inline, static]

Infinity. You can use -MPSolverinfinity() for negative infinity.

Definition at line 332 of file linear_solver.h.

void operations_research::MPSolver::SuppressOutput ( )

Suppresses all output from the underlying solver.

Definition at line 623 of file linear_solver.cc.

void operations_research::MPSolver::EnableOutput ( )

Enables a reasonably verbose output from the underlying solver.

The level of verbosity and the location of this output depends on the underlying solver. In most cases, it is sent to stdout.

Definition at line 619 of file linear_solver.cc.

void operations_research::MPSolver::set_write_model_filename ( const string & filename ) [inline]

Definition at line 345 of file linear_solver.h.

string operations_research::MPSolver::write_model_filename ( ) const [inline]

Definition at line 349 of file linear_solver.h.

void operations_research::MPSolver::set_time_limit ( int64 time_limit ) [inline]

Definition at line 353 of file linear_solver.h.

int64 operations_research::MPSolver::time_limit ( ) const [inline]

Definition at line 358 of file linear_solver.h.

int64 operations_research::MPSolver::wall_time ( ) const [inline]

Returns wall_time() in milliseconds since the creation of the solver.

Definition at line 363 of file linear_solver.h.

int64 operations_research::MPSolver::iterations ( ) const

Returns the number of simplex iterations.

Definition at line 769 of file linear_solver.cc.

int64 operations_research::MPSolver::nodes ( ) const

Returns the number of branch-and-bound nodes.

Only available for discrete problems.

Definition at line 773 of file linear_solver.cc.

bool operations_research::MPSolver::CheckNameValidity ( const string & name )

Checks the validity of a variable or constraint name.

Names management.

Definition at line 352 of file linear_solver.cc.

bool operations_research::MPSolver::CheckAllNamesValidity ( )

Checks the validity of all variables and constraints names.

Definition at line 381 of file linear_solver.cc.

string operations_research::MPSolver::SolverVersion ( ) const

Returns a string describing the underlying solver and its version.

Version.

Definition at line 268 of file linear_solver.cc.

void * operations_research::MPSolver::underlying_solver ( )

Advanced usage: returns the underlying solver so that the user can use solver-specific features or features that are not exposed in the simple API of MPSolver.

Underlying solver.

This method is for advanced users, use at your own risk! In particular, if you modify the model or the solution by accessing the underlying solver directly, then the underlying solver will be out of sync with the information kept in the wrapper (MPSolver, MPVariable, MPConstraint, MPObjective). You need to cast the void* returned back to its original type that depends on the interface (CBC: OsiClpSolverInterface*, CLP: ClpSimplex*, GLPK: glp_prob*, SCIP: SCIP*).

Definition at line 274 of file linear_solver.cc.

double operations_research::MPSolver::ComputeExactConditionNumber ( ) const

Advanced usage: computes the exact condition number of the current scaled basis: L1norm(B) * L1norm(inverse(B)), where B is the scaled basis.

This method requires that a basis exists: it should be called after Solve. It is only available for continuous problems. It is implemented for GLPK but not CLP because CLP does not provide the API for doing it. The condition number measures how well the constraint matrix is conditioned and can be used to predict whether numerical issues will arise during the solve: the model is declared infeasible whereas it is feasible (or vice-versa), the solution obtained is not optimal or violates some constraints, the resolution is slow because of repeated singularities. The rule of thumb to interpret the condition number kappa is: o kappa <= 1e7: virtually no chance of numerical issues o 1e7 < kappa <= 1e10: small chance of numerical issues o 1e10 < kappa <= 1e13: medium chance of numerical issues o kappa > 1e13: high chance of numerical issues The computation of the condition number depends on the quality of the LU decomposition, so it is not very accurate when the matrix is ill conditioned.

Definition at line 777 of file linear_solver.cc.

double operations_research::MPSolver::objective_value ( ) const

DEPRECATED Setters and getters for the objective.

Objective (DEPRECATED methods).

Please call Objective().Getter() and MutableObjective()->Setter() instead.

Todo:: TODO(user): remove when they are no longer used.

Definition at line 229 of file linear_solver.cc.

double operations_research::MPSolver::best_objective_bound ( ) const

Definition at line 233 of file linear_solver.cc.

void operations_research::MPSolver::ClearObjective ( )

Definition at line 237 of file linear_solver.cc.

void operations_research::MPSolver::SetObjectiveCoefficient	(	const MPVariable *const	var,
		double	coeff
	)

Definition at line 241 of file linear_solver.cc.

void operations_research::MPSolver::SetObjectiveOffset ( double value )

Definition at line 246 of file linear_solver.cc.

void operations_research::MPSolver::AddObjectiveOffset ( double value )

Definition at line 250 of file linear_solver.cc.

void operations_research::MPSolver::SetOptimizationDirection ( bool maximize )

Definition at line 254 of file linear_solver.cc.

void operations_research::MPSolver::SetMinimization ( ) [inline]

Definition at line 435 of file linear_solver.h.

void operations_research::MPSolver::SetMaximization ( ) [inline]

Definition at line 436 of file linear_solver.h.

bool operations_research::MPSolver::Maximization ( ) const

Definition at line 258 of file linear_solver.cc.

bool operations_research::MPSolver::Minimization ( ) const

Definition at line 262 of file linear_solver.cc.

Friends And Related Function Documentation

friend class GLPKInterface [friend]

Definition at line 418 of file linear_solver.h.

friend class CLPInterface [friend]

Definition at line 419 of file linear_solver.h.

friend class CBCInterface [friend]

Definition at line 420 of file linear_solver.h.

friend class SCIPInterface [friend]

Definition at line 421 of file linear_solver.h.

friend class MPSolverInterface [friend]

Definition at line 422 of file linear_solver.h.

The documentation for this class was generated from the following files:

or-tools/src/linear_solver/linear_solver.h
or-tools/src/linear_solver/linear_solver.cc


Public Types
enum	OptimizationProblemType
	The type of problems (LP or MIP) that will be solved and the underlying solver (GLPK, CLP, CBC or SCIP) that will solve them. More...
enum	ResultStatus { OPTIMAL, FEASIBLE, INFEASIBLE, UNBOUNDED, ABNORMAL, NOT_SOLVED }
	Solve. More...
enum	LoadStatus { NO_ERROR = 0, DUPLICATE_VARIABLE_ID = 2, UNKNOWN_VARIABLE_ID = 3 }
	Methods using protocol buffers. More...
enum	BasisStatus { FREE = 0, AT_LOWER_BOUND, AT_UPPER_BOUND, FIXED_VALUE, BASIC }
	Misc. More...
Public Member Functions
	MPSolver (const string &name, OptimizationProblemType problem_type)
	namespace
virtual	~MPSolver ()
string	Name () const
void	Clear ()
	Clears the objective (including the optimization direction), all variables and constraints.
int	NumVariables () const
	Variables Returns the number of variables.
MPVariable *	LookupVariableOrNull (const string &var_name) const
	Look up a variable by name, and return NULL if it does not exist.
MPVariable *	MakeVar (double lb, double ub, bool integer, const string &name)
	Creates a variable with the given bounds, integrality requirement and name.
MPVariable *	MakeNumVar (double lb, double ub, const string &name)
	Creates a continuous variable.
MPVariable *	MakeIntVar (double lb, double ub, const string &name)
	Creates an integer variable.
MPVariable *	MakeBoolVar (const string &name)
	Creates a boolean variable.
void	MakeVarArray (int nb, double lb, double ub, bool integer, const string &name_prefix, std::vector< MPVariable * > *vars)
	Creates an array of variables.
void	MakeNumVarArray (int nb, double lb, double ub, const string &name, std::vector< MPVariable * > *vars)
	Creates an array of continuous variables.
void	MakeIntVarArray (int nb, double lb, double ub, const string &name, std::vector< MPVariable * > *vars)
	Creates an array of integer variables.
void	MakeBoolVarArray (int nb, const string &name, std::vector< MPVariable * > *vars)
	Creates an array of boolean variables.
int	NumConstraints () const
	Constraints Returns the number of constraints.
MPConstraint *	LookupConstraintOrNull (const string &constraint_name) const
	Look up a constraint by name, and return NULL if it does not exist.
MPConstraint *	MakeRowConstraint (double lb, double ub)
	Creates a linear constraint with given bounds.
MPConstraint *	MakeRowConstraint ()
	Creates a constraint with -infinity and +infinity bounds.
MPConstraint *	MakeRowConstraint (double lb, double ub, const string &name)
	Creates a named constraint with given bounds.
MPConstraint *	MakeRowConstraint (const string &name)
	Creates a named constraint with -infinity and +infinity bounds.
const MPObjective &	Objective () const
	Objective Note that the objective is owned by the solver, and is initialized to its default value (see the MPObjective class below) at construction.
MPObjective *	MutableObjective ()
ResultStatus	Solve ()
	Solves the problem using default parameter values.
ResultStatus	Solve (const MPSolverParameters &param)
	Solves the problem using the specified parameter values.
void	Reset ()
	Advanced usage: resets extracted model to solve from scratch.
LoadStatus	LoadModel (const MPModelProto &input_model)
	Loads model from protocol buffer.
void	ExportModel (MPModelProto *output_model) const
	Exports model to protocol buffer.
void	FillSolutionResponse (MPSolutionResponse *response) const
	Encodes the current solution in a solution response protocol buffer.
void	SuppressOutput ()
	Suppresses all output from the underlying solver.
void	EnableOutput ()
	Enables a reasonably verbose output from the underlying solver.
void	set_write_model_filename (const string &filename)
string	write_model_filename () const
void	set_time_limit (int64 time_limit)
int64	time_limit () const
int64	wall_time () const
	Returns wall_time() in milliseconds since the creation of the solver.
int64	iterations () const
	Returns the number of simplex iterations.
int64	nodes () const
	Returns the number of branch-and-bound nodes.
bool	CheckNameValidity (const string &name)
	Checks the validity of a variable or constraint name.
bool	CheckAllNamesValidity ()
	Checks the validity of all variables and constraints names.
string	SolverVersion () const
	Returns a string describing the underlying solver and its version.
void *	underlying_solver ()
	Advanced usage: returns the underlying solver so that the user can use solver-specific features or features that are not exposed in the simple API of MPSolver.
double	ComputeExactConditionNumber () const
	Advanced usage: computes the exact condition number of the current scaled basis: L1norm(B) * L1norm(inverse(B)), where B is the scaled basis.
double	objective_value () const
	DEPRECATED Setters and getters for the objective.
double	best_objective_bound () const
void	ClearObjective ()
void	SetObjectiveCoefficient (const MPVariable *const var, double coeff)
void	SetObjectiveOffset (double value)
void	AddObjectiveOffset (double value)
void	SetOptimizationDirection (bool maximize)
void	SetMinimization ()
void	SetMaximization ()
bool	Maximization () const
bool	Minimization () const
Static Public Member Functions
static void	SolveWithProtocolBuffers (const MPModelRequest &model_request, MPSolutionResponse *response)
	Solves the model encoded by a MPModelRequest protocol buffer and fills the solution encoded as a MPSolutionResponse.
static double	infinity ()
	Infinity. You can use -MPSolverinfinity() for negative infinity.
Friends
class	GLPKInterface
class	CLPInterface
class	CBCInterface
class	SCIPInterface
class	MPSolverInterface