#include <linear_solver.h>

Public Types
enum	OptimizationProblemType { CLP_LINEAR_PROGRAMMING = 0 , GLPK_LINEAR_PROGRAMMING = 1 , GLOP_LINEAR_PROGRAMMING = 2 , PDLP_LINEAR_PROGRAMMING = 8 , HIGHS_LINEAR_PROGRAMMING = 15 , SCIP_MIXED_INTEGER_PROGRAMMING = 3 , GLPK_MIXED_INTEGER_PROGRAMMING = 4 , CBC_MIXED_INTEGER_PROGRAMMING = 5 , HIGHS_MIXED_INTEGER_PROGRAMMING = 16 , BOP_INTEGER_PROGRAMMING = 12 , SAT_INTEGER_PROGRAMMING = 14 , KNAPSACK_MIXED_INTEGER_PROGRAMMING = 13 , GUROBI_LINEAR_PROGRAMMING = 6 , GUROBI_MIXED_INTEGER_PROGRAMMING = 7 , CPLEX_LINEAR_PROGRAMMING = 10 , CPLEX_MIXED_INTEGER_PROGRAMMING = 11 , XPRESS_LINEAR_PROGRAMMING = 101 , XPRESS_MIXED_INTEGER_PROGRAMMING = 102 , COPT_LINEAR_PROGRAMMING = 103 , COPT_MIXED_INTEGER_PROGRAMMING = 104 }

enum	ResultStatus { OPTIMAL , FEASIBLE , INFEASIBLE , UNBOUNDED , ABNORMAL , MODEL_INVALID , NOT_SOLVED = 6 }

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

Public Member Functions
	MPSolver (const std::string &name, OptimizationProblemType problem_type)
	Create a solver with the given name and underlying solver backend.

	MPSolver (const MPSolver &)=delete
	This type is neither copyable nor movable.

MPSolver &	operator= (const MPSolver &)=delete

virtual	~MPSolver ()

bool	IsMIP () const
	--— Interface shortcuts --—

const std::string &	Name () const
	Returns the name of the model set at construction.

virtual OptimizationProblemType	ProblemType () const
	Returns the optimization problem type set at construction.

void	Clear ()

int	NumVariables () const
	Returns the number of variables.

const std::vector< MPVariable * > &	variables () const

MPVariable *	variable (int index) const

MPVariable *	LookupVariableOrNull (const std::string &var_name) const

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

MPVariable *	MakeNumVar (double lb, double ub, const std::string &name)
	Creates a continuous variable.

MPVariable *	MakeIntVar (double lb, double ub, const std::string &name)
	Creates an integer variable.

MPVariable *	MakeBoolVar (const std::string &name)
	Creates a boolean variable.

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

void	MakeNumVarArray (int nb, double lb, double ub, const std::string &name, std::vector< MPVariable * > *vars)
	Creates an array of continuous variables.

void	MakeIntVarArray (int nb, double lb, double ub, const std::string &name, std::vector< MPVariable * > *vars)
	Creates an array of integer variables.

void	MakeBoolVarArray (int nb, const std::string &name, std::vector< MPVariable * > *vars)
	Creates an array of boolean variables.

int	NumConstraints () const
	Returns the number of constraints.

const std::vector< MPConstraint * > &	constraints () const

MPConstraint *	constraint (int index) const

MPConstraint *	LookupConstraintOrNull (const std::string &constraint_name) const

MPConstraint *	MakeRowConstraint (double lb, double ub)

MPConstraint *	MakeRowConstraint ()
	Creates a constraint with -infinity and +infinity bounds.

MPConstraint *	MakeRowConstraint (double lb, double ub, const std::string &name)
	Creates a named constraint with given bounds.

MPConstraint *	MakeRowConstraint (const std::string &name)
	Creates a named constraint with -infinity and +infinity bounds.

MPConstraint *	MakeRowConstraint (const LinearRange &range)

MPConstraint *	MakeRowConstraint (const LinearRange &range, const std::string &name)
	As above, but also names the constraint.

const MPObjective &	Objective () const

MPObjective *	MutableObjective ()
	Returns the mutable objective object.

ResultStatus	Solve ()
	Solves the problem using the default parameter values.

ResultStatus	Solve (const MPSolverParameters &param)
	Solves the problem using the specified parameter values.

void	Write (const std::string &file_name)

std::vector< double >	ComputeConstraintActivities () const

bool	VerifySolution (double tolerance, bool log_errors) const

void	Reset ()

bool	InterruptSolve ()

MPSolverResponseStatus	LoadModelFromProto (const MPModelProto &input_model, std::string *error_message, bool clear_names=true)
	--— Methods using protocol buffers --—

MPSolverResponseStatus	LoadModelFromProtoWithUniqueNamesOrDie (const MPModelProto &input_model, std::string *error_message)

void	FillSolutionResponseProto (MPSolutionResponse *response) const
	Encodes the current solution in a solution response protocol buffer.

	ABSL_DEPRECATED ("Prefer SolverTypeSupportsInterruption() from solve_mp_model.h.") static bool SolverTypeSupportsInterruption(const MPModelRequest

void	ExportModelToProto (MPModelProto *output_model) const
	Exports model to protocol buffer.

absl::Status	LoadSolutionFromProto (const MPSolutionResponse &response, double tolerance=std::numeric_limits< double >::infinity())

absl::Status	ClampSolutionWithinBounds ()

bool	ExportModelAsLpFormat (bool obfuscate, std::string *model_str) const

bool	ExportModelAsMpsFormat (bool fixed_format, bool obfuscate, std::string *model_str) const

absl::Status	SetNumThreads (int num_threads)
	-— Solver-specific parameters -—

int	GetNumThreads () const
	Returns the number of threads to be used during solve.

bool	SetSolverSpecificParametersAsString (const std::string &parameters)

std::string	GetSolverSpecificParametersAsString () const

void	SetHint (std::vector< std::pair< const MPVariable *, double > > hint)

void	SetStartingLpBasis (const std::vector< MPSolver::BasisStatus > &variable_statuses, const std::vector< MPSolver::BasisStatus > &constraint_statuses)

double	solver_infinity ()

bool	OutputIsEnabled () const

void	EnableOutput ()
	Enables solver logging.

void	SuppressOutput ()
	Suppresses solver logging.

absl::Duration	TimeLimit () const

void	SetTimeLimit (absl::Duration time_limit)

absl::Duration	DurationSinceConstruction () const

int64_t	iterations () const
	Returns the number of simplex iterations.

int64_t	nodes () const

std::string	SolverVersion () const
	Returns a string describing the underlying solver and its version.

void *	underlying_solver ()

double	ComputeExactConditionNumber () const

ABSL_MUST_USE_RESULT bool	NextSolution ()

void	SetCallback (MPCallback *mp_callback)

bool	SupportsCallbacks () const

int64_t	time_limit () const

void	set_time_limit (int64_t time_limit_milliseconds)

double	time_limit_in_secs () const

int64_t	wall_time () const

bool	OwnsVariable (const MPVariable *var) const
	Debugging: verify that the given MPVariable* belongs to this solver.

Static Public Member Functions
static MPSolver *	CreateSolver (const std::string &solver_id)

static bool	SupportsProblemType (OptimizationProblemType problem_type)
	static

static bool	ParseSolverType (absl::string_view solver_id, OptimizationProblemType *type)
	static

static OptimizationProblemType	ParseSolverTypeOrDie (const std::string &solver_id)

static void	SolveWithProto (const MPModelRequest &model_request, MPSolutionResponse response, std::atomic< bool > interrupt=nullptr)
	static

static void	SolveLazyMutableRequest (LazyMutableCopy< MPModelRequest > request, MPSolutionResponse response, std::atomic< bool > interrupt=nullptr)
	static

static std::string	GetMPModelRequestLoggingInfo (const MPModelRequest &request)
	static

static double	infinity ()

static int64_t	global_num_variables ()
	static

static int64_t	global_num_constraints ()
	static

Friends
class	GLPKInterface

class	CLPInterface

class	CBCInterface

class	SCIPInterface

class	GurobiInterface

class	CplexInterface

class	XpressInterface

class	SLMInterface

class	MPSolverInterface

class	GLOPInterface

class	BopInterface

class	SatInterface

class	PdlpInterface

class	HighsInterface

class	KnapsackInterface

Detailed Description

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

Definition at line 189 of file linear_solver.h.

Member Enumeration Documentation

◆ BasisStatus

enum operations_research::MPSolver::BasisStatus

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 728 of file linear_solver.h.

◆ OptimizationProblemType

enum operations_research::MPSolver::OptimizationProblemType

The type of problems (LP or MIP) that will be solved and the underlying solver (GLOP, GLPK, CLP, CBC or SCIP) that will solve them. This must remain consistent with MPModelRequest::OptimizationProblemType (take particular care of the open-source version).

Enumerator
CLP_LINEAR_PROGRAMMING	Linear programming problems.
GLPK_LINEAR_PROGRAMMING
GLOP_LINEAR_PROGRAMMING
PDLP_LINEAR_PROGRAMMING	In-house linear programming solver based on the primal-dual hybrid gradient method. Sometimes faster than Glop for medium-size problems and scales to much larger problems than Glop.
HIGHS_LINEAR_PROGRAMMING
SCIP_MIXED_INTEGER_PROGRAMMING	Recommended default value for MIP problems. Integer programming problems.
GLPK_MIXED_INTEGER_PROGRAMMING
CBC_MIXED_INTEGER_PROGRAMMING
HIGHS_MIXED_INTEGER_PROGRAMMING
BOP_INTEGER_PROGRAMMING	Boolean optimization problem (requires only integer variables and works best with only Boolean variables).
SAT_INTEGER_PROGRAMMING	SAT based solver (requires only integer and Boolean variables). If you pass it mixed integer problems, it will scale coefficients to integer values, and solver continuous variables as integral variables. Recommended default value for pure integral problems problems.
KNAPSACK_MIXED_INTEGER_PROGRAMMING	Dedicated knapsack solvers.
GUROBI_LINEAR_PROGRAMMING	Commercial software (need license).
GUROBI_MIXED_INTEGER_PROGRAMMING
CPLEX_LINEAR_PROGRAMMING
CPLEX_MIXED_INTEGER_PROGRAMMING
XPRESS_LINEAR_PROGRAMMING
XPRESS_MIXED_INTEGER_PROGRAMMING
COPT_LINEAR_PROGRAMMING
COPT_MIXED_INTEGER_PROGRAMMING

Definition at line 197 of file linear_solver.h.

◆ ResultStatus

enum operations_research::MPSolver::ResultStatus

The status of solving the problem. The straightforward translation to homonymous enum values of MPSolverResponseStatus (see ./linear_solver.proto) is guaranteed by ./enum_consistency_test.cc, you may rely on it.

Enumerator
OPTIMAL	optimal.
FEASIBLE	feasible, or stopped by limit.
INFEASIBLE	proven infeasible.
UNBOUNDED	proven unbounded.
ABNORMAL	abnormal, i.e., error of some kind.
MODEL_INVALID	the model is trivially invalid (NaN coefficients, etc).
NOT_SOLVED	not been solved yet.

Definition at line 465 of file linear_solver.h.

Constructor & Destructor Documentation

◆ MPSolver() [1/2]

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

Create a solver with the given name and underlying solver backend.

Definition at line 486 of file linear_solver.cc.

◆ MPSolver() [2/2]

operations_research::MPSolver::MPSolver ( const MPSolver & )

delete

This type is neither copyable nor movable.

◆ ~MPSolver()

operations_research::MPSolver::~MPSolver ( )

virtual

Definition at line 498 of file linear_solver.cc.

Member Function Documentation

◆ ABSL_DEPRECATED()

operations_research::MPSolver::ABSL_DEPRECATED ( "Prefer SolverTypeSupportsInterruption() from solve_mp_model.h." ) const

inline

Interruption requires that MPSolver::InterruptSolve is supported for the underlying solver. Interrupting requests using SCIP is also not supported as of 2021/08/23, since InterruptSolve is not thread safe for SCIP.

Definition at line 605 of file linear_solver.h.

◆ ClampSolutionWithinBounds()

absl::Status operations_research::MPSolver::ClampSolutionWithinBounds ( )

Resets values of out of bound variables to the corresponding bound and returns an error if any of the variables have NaN value.

Definition at line 1646 of file linear_solver.cc.

◆ Clear()

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 1377 of file linear_solver.cc.

◆ ComputeConstraintActivities()

std::vector< double > operations_research::MPSolver::ComputeConstraintActivities ( ) const

Advanced usage: compute the "activities" of all constraints, which are the sums of their linear terms. The activities are returned in the same order as constraints(), which is the order in which constraints were added; but you can also use MPConstraint::index() to get a constraint's index.

Todo: (user): test this failure case.

Definition at line 1664 of file linear_solver.cc.

◆ ComputeExactConditionNumber()

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 1834 of file linear_solver.cc.

◆ constraint()

MPConstraint * operations_research::MPSolver::constraint ( int index ) const

inline

Returns the constraint at the given index.

Definition at line 406 of file linear_solver.h.

◆ constraints()

const std::vector< MPConstraint * > & operations_research::MPSolver::constraints ( ) const

inline

Returns the array of constraints handled by the MPSolver.

They are listed in the order in which they were created.

Definition at line 403 of file linear_solver.h.

◆ CreateSolver()

MPSolver * operations_research::MPSolver::CreateSolver ( const std::string & solver_id )

static

Recommended factory method to create a MPSolver instance, especially in non C++ languages.

It returns a newly created solver instance if successful, or a nullptr otherwise. This can occur if the relevant interface is not linked in, or if a needed license is not accessible for commercial solvers.

Ownership of the solver is passed on to the caller of this method. It will accept both string names of the OptimizationProblemType enum, as well as a short version (i.e. "SCIP_MIXED_INTEGER_PROGRAMMING" or "SCIP").

solver_id is case insensitive, and the following names are supported:

CLP_LINEAR_PROGRAMMING or CLP
CBC_MIXED_INTEGER_PROGRAMMING or CBC
GLOP_LINEAR_PROGRAMMING or GLOP
BOP_INTEGER_PROGRAMMING or BOP
SAT_INTEGER_PROGRAMMING or SAT or CP_SAT
SCIP_MIXED_INTEGER_PROGRAMMING or SCIP
GUROBI_LINEAR_PROGRAMMING or GUROBI_LP
GUROBI_MIXED_INTEGER_PROGRAMMING or GUROBI or GUROBI_MIP
CPLEX_LINEAR_PROGRAMMING or CPLEX_LP
CPLEX_MIXED_INTEGER_PROGRAMMING or CPLEX or CPLEX_MIP
XPRESS_LINEAR_PROGRAMMING or XPRESS_LP
XPRESS_MIXED_INTEGER_PROGRAMMING or XPRESS or XPRESS_MIP
GLPK_LINEAR_PROGRAMMING or GLPK_LP
GLPK_MIXED_INTEGER_PROGRAMMING or GLPK or GLPK_MIP

Definition at line 660 of file linear_solver.cc.

◆ DurationSinceConstruction()

absl::Duration operations_research::MPSolver::DurationSinceConstruction ( ) const

inline

Definition at line 781 of file linear_solver.h.

◆ EnableOutput()

void operations_research::MPSolver::EnableOutput ( )

Enables solver logging.

Definition at line 1826 of file linear_solver.cc.

◆ ExportModelAsLpFormat()

bool operations_research::MPSolver::ExportModelAsLpFormat	(	bool	obfuscate,
		std::string *	model_str ) const

Shortcuts to the homonymous MPModelProtoExporter methods, via exporting to a MPModelProto with ExportModelToProto() (see above).

Produces empty std::string on portable platforms (e.g. android, ios).

Definition at line 1847 of file linear_solver.cc.

◆ ExportModelAsMpsFormat()

bool operations_research::MPSolver::ExportModelAsMpsFormat	(	bool	fixed_format,
		bool	obfuscate,
		std::string *	model_str ) const

Definition at line 1859 of file linear_solver.cc.

◆ ExportModelToProto()

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

Exports model to protocol buffer.

Name

Variables

Todo: (user): Add option to avoid filling the var name to avoid overly large protocol buffers.

Map the variables to their indices. This is needed to output the variables in the order they were created, which in turn is needed to have repeatable results with ExportModelAsLpFormat and ExportModelAsMpsFormat. This step is needed as long as the variable indices are given by the underlying solver at the time of model extraction.

Todo: (user): remove this step.

Constraints

Vector linear_term will contain pairs (variable index, coeff), that will be sorted by variable index.

The cost of sort is expected to be low as constraints usually have very few terms.

Now use linear term.

Definition at line 1199 of file linear_solver.cc.

◆ FillSolutionResponseProto()

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

Encodes the current solution in a solution response protocol buffer.

Dual values have no meaning in MIP.

Reduced cost have no meaning in MIP.

Definition at line 969 of file linear_solver.cc.

◆ GetMPModelRequestLoggingInfo()

std::string operations_research::MPSolver::GetMPModelRequestLoggingInfo ( const MPModelRequest & request )

static

Gives some brief (a few lines, at most) human-readable information about the given request, suitable for debug logging.

Definition at line 2325 of file linear_solver.cc.

◆ GetNumThreads()

int operations_research::MPSolver::GetNumThreads ( ) const

inline

Returns the number of threads to be used during solve.

Definition at line 688 of file linear_solver.h.

◆ GetSolverSpecificParametersAsString()

std::string operations_research::MPSolver::GetSolverSpecificParametersAsString ( ) const

inline

Definition at line 697 of file linear_solver.h.

◆ global_num_constraints()

int64_t operations_research::MPSolver::global_num_constraints ( )

static

Definition at line 1917 of file linear_solver.cc.

◆ global_num_variables()

int64_t operations_research::MPSolver::global_num_variables ( )

static

Global counters of variables and constraints ever created across all MPSolver instances. Those are only updated after the destruction (or Clear()) of each MPSolver instance.

Definition at line 1911 of file linear_solver.cc.

◆ infinity()

static double operations_research::MPSolver::infinity ( )

inlinestatic

Infinity.

You can use -MPSolver::infinity() for negative infinity.

Definition at line 756 of file linear_solver.h.

◆ InterruptSolve()

bool operations_research::MPSolver::InterruptSolve ( )

Interrupts the Solve() execution to terminate processing if possible.

If the underlying interface supports interruption; it does that and returns true regardless of whether there's an ongoing Solve() or not. The Solve() call may still linger for a while depending on the conditions. If interruption is not supported; returns false and does nothing. MPSolver::SolverTypeSupportsInterruption can be used to check if interruption is supported for a given solver type.

Definition at line 1400 of file linear_solver.cc.

◆ IsMIP()

bool operations_research::MPSolver::IsMIP ( ) const

--— Interface shortcuts --—

Definition at line 348 of file linear_solver.cc.

◆ iterations()

int64_t operations_research::MPSolver::iterations ( ) const

Returns the number of simplex iterations.

Definition at line 1830 of file linear_solver.cc.

◆ LoadModelFromProto()

MPSolverResponseStatus operations_research::MPSolver::LoadModelFromProto	(	const MPModelProto &	input_model,
		std::string *	error_message,
		bool	clear_names = true )

--— Methods using protocol buffers --—

Loads model from protocol buffer.

Returns MPSOLVER_MODEL_IS_VALID if the model is valid, and another status otherwise (currently only MPSOLVER_MODEL_INVALID and MPSOLVER_INFEASIBLE). If the model isn't valid, populates "error_message". If clear_names is true (the default), clears all names, otherwise returns MPSOLVER_MODEL_INVALID if there are duplicates (non-empty) names.

The variable and constraint names are dropped, because we allow duplicate names in the proto (they're not considered as 'ids'), unlike the MPSolver C++ API which crashes if there are duplicate names. Clearing the names makes the MPSolver generate unique names.

Definition at line 695 of file linear_solver.cc.

◆ LoadModelFromProtoWithUniqueNamesOrDie()

MPSolverResponseStatus operations_research::MPSolver::LoadModelFromProtoWithUniqueNamesOrDie	(	const MPModelProto &	input_model,
		std::string *	error_message )

Loads model from protocol buffer.

The same as above, except that the loading keeps original variable and constraint names. Caller should make sure that all variable names and constraint names are unique, respectively.

Force variable and constraint name indexing (which CHECKs name uniqueness).

Definition at line 712 of file linear_solver.cc.

◆ LoadSolutionFromProto()

absl::Status operations_research::MPSolver::LoadSolutionFromProto	(	const MPSolutionResponse &	response,
		double	tolerance = std::numeric_limits<double>::infinity() )

Load a solution encoded in a protocol buffer onto this solver for easy access via the MPSolver interface.

IMPORTANT: This may only be used in conjunction with ExportModel(), following this example:

MPSolver my_solver;
... add variables and constraints ...
MPModelProto model_proto;
my_solver.ExportModelToProto(&model_proto);
MPSolutionResponse solver_response;
MPSolver::SolveWithProto(model_proto, &solver_response);
if (solver_response.result_status() == MPSolutionResponse::OPTIMAL) {
  CHECK_OK(my_solver.LoadSolutionFromProto(solver_response));
  ... inspect the solution using the usual API: solution_value(), etc...
}

The response must be in OPTIMAL or FEASIBLE status.

Returns a non-OK status if a problem arised (typically, if it wasn't used like it should be):

loading a solution whose variables don't correspond to the solver's current variables
loading a dual solution whose constraints don't correspond to the solver's current constraints
loading a solution with a status other than OPTIMAL / FEASIBLE.

Note: the objective value isn't checked. You can use VerifySolution() for that.

Before touching the variables, verify that the solution looks legit: each variable of the MPSolver must have its value listed exactly once, and each listed solution should correspond to a known variable.

Look further: verify that the variable values are within the bounds.

Todo: (user): Use parameter when they become available in this class.

Set the objective value, if is known. NOTE(user): We do not verify the objective, even though we could!

Mark the status as SOLUTION_SYNCHRONIZED, so that users may inspect the solution normally.

Definition at line 1286 of file linear_solver.cc.

◆ LookupConstraintOrNull()

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

Looks up a constraint by name, and returns nullptr if it does not exist.

The first call has a O(n) complexity, as the constraint name index is lazily created upon first use. Will crash if constraint names are not unique.

Definition at line 684 of file linear_solver.cc.

◆ LookupVariableOrNull()

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

Looks up a variable by name, and returns nullptr if it does not exist. The first call has a O(n) complexity, as the variable name index is lazily created upon first use. Will crash if variable names are not unique.

Definition at line 675 of file linear_solver.cc.

◆ MakeBoolVar()

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

Creates a boolean variable.

Definition at line 1434 of file linear_solver.cc.

◆ MakeBoolVarArray()

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

Creates an array of boolean variables.

Definition at line 1467 of file linear_solver.cc.

◆ MakeIntVar()

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

Creates an integer variable.

Definition at line 1429 of file linear_solver.cc.

◆ MakeIntVarArray()

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

Creates an array of integer variables.

Definition at line 1461 of file linear_solver.cc.

◆ MakeNumVar()

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

Creates a continuous variable.

Definition at line 1424 of file linear_solver.cc.

◆ MakeNumVarArray()

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

Creates an array of continuous variables.

Definition at line 1455 of file linear_solver.cc.

◆ MakeRowConstraint() [1/6]

MPConstraint * operations_research::MPSolver::MakeRowConstraint ( )

Creates a constraint with -infinity and +infinity bounds.

Definition at line 1476 of file linear_solver.cc.

◆ MakeRowConstraint() [2/6]

MPConstraint * operations_research::MPSolver::MakeRowConstraint ( const LinearRange & range )

Creates a constraint owned by MPSolver enforcing: range.lower_bound() <= range.linear_expr() <= range.upper_bound()

Definition at line 1499 of file linear_solver.cc.

◆ MakeRowConstraint() [3/6]

MPConstraint * operations_research::MPSolver::MakeRowConstraint	(	const LinearRange &	range,
		const std::string &	name )

As above, but also names the constraint.

Definition at line 1503 of file linear_solver.cc.

◆ MakeRowConstraint() [4/6]

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

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

Definition at line 1495 of file linear_solver.cc.

◆ MakeRowConstraint() [5/6]

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 1472 of file linear_solver.cc.

◆ MakeRowConstraint() [6/6]

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

Creates a named constraint with given bounds.

Definition at line 1480 of file linear_solver.cc.

◆ MakeVar()

MPVariable * operations_research::MPSolver::MakeVar	(	double	lb,
		double	ub,
		bool	integer,
		const std::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 are optional. If you give an empty name, name() will auto-generate one for you upon request.

Definition at line 1410 of file linear_solver.cc.

◆ MakeVarArray()

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

Creates an array of variables. All variables created have the same bounds and integrality requirement. If nb <= 0, no variables are created, the function crashes in non-opt mode.

Parameters

	nb	the number of variables to create.
	lb	the lower bound of created variables
	ub	the upper bound of created variables
	integer	controls whether the created variables are continuous or integral.
	name_prefix	the prefix of the variable names. Variables are named name_prefix0, name_prefix1, ...
[out]	vars	the vector of variables to fill with variables.

Definition at line 1438 of file linear_solver.cc.

◆ MutableObjective()

MPObjective * operations_research::MPSolver::MutableObjective ( )

inline

Returns the mutable objective object.

Definition at line 457 of file linear_solver.h.

◆ Name()

const std::string & operations_research::MPSolver::Name ( ) const

inline

Returns the name of the model set at construction.

Definition at line 309 of file linear_solver.h.

◆ NextSolution()

bool operations_research::MPSolver::NextSolution ( )

Some solvers (MIP only, not LP) can produce multiple solutions to the problem. Returns true when another solution is available, and updates the MPVariable* objects to make the new solution queryable. Call only after calling solve.

The optimality properties of the additional solutions found, and whether or not the solver computes them ahead of time or when NextSolution() is called is solver specific.

As of 2020-02-10, only Gurobi and SCIP support NextSolution(), see linear_solver_interfaces_test for an example of how to configure these solvers for multiple solutions. Other solvers return false unconditionally.

Definition at line 1895 of file linear_solver.cc.

◆ nodes()

int64_t operations_research::MPSolver::nodes ( ) const

Returns the number of branch-and-bound nodes evaluated during the solve.

Only available for discrete problems.

Definition at line 1832 of file linear_solver.cc.

◆ NumConstraints()

int operations_research::MPSolver::NumConstraints ( ) const

inline

Returns the number of constraints.

Definition at line 396 of file linear_solver.h.

◆ NumVariables()

int operations_research::MPSolver::NumVariables ( ) const

inline

Returns the number of variables.

Definition at line 326 of file linear_solver.h.

◆ Objective()

const MPObjective & operations_research::MPSolver::Objective ( ) const

inline

Returns the objective object.

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 454 of file linear_solver.h.

◆ operator=()

MPSolver & operations_research::MPSolver::operator= ( const MPSolver & )

delete

◆ OutputIsEnabled()

bool operations_research::MPSolver::OutputIsEnabled ( ) const

Controls (or queries) the amount of output produced by the underlying solver. The output can surface to LOGs, or to stdout or stderr, depending on the implementation. The amount of output will greatly vary with each implementation and each problem.

Output is suppressed by default.

Definition at line 1824 of file linear_solver.cc.

◆ OwnsVariable()

bool operations_research::MPSolver::OwnsVariable ( const MPVariable * var ) const

Debugging: verify that the given MPVariable* belongs to this solver.

Then, verify that the variable with this index has the same address.

Definition at line 1838 of file linear_solver.cc.

◆ ParseSolverType()

bool operations_research::MPSolver::ParseSolverType	(	absl::string_view	solver_id,
		MPSolver::OptimizationProblemType *	type )

static

Parses the name of the solver. Returns true if the solver type is successfully parsed as one of the OptimizationProblemType. See the documentation of CreateSolver() for the list of supported names.

Normalize the solver id.

Support the full enum name

Names are stored in lower case.

Remove any "_mip" suffix, since they are optional.

Rewrite CP-SAT into SAT.

Reverse lookup in the kOptimizationProblemTypeNames[] array.

Definition at line 590 of file linear_solver.cc.

◆ ParseSolverTypeOrDie()

MPSolver::OptimizationProblemType operations_research::MPSolver::ParseSolverTypeOrDie ( const std::string & solver_id )

static

Parses the name of the solver and returns the correct optimization type or dies. Invariant: ParseSolverTypeOrDie(ToString(type)) = type.

Definition at line 652 of file linear_solver.cc.

◆ ProblemType()

virtual OptimizationProblemType operations_research::MPSolver::ProblemType ( ) const

inlinevirtual

Returns the optimization problem type set at construction.

Definition at line 314 of file linear_solver.h.

◆ Reset()

void operations_research::MPSolver::Reset ( )

Advanced usage: resets extracted model to solve from scratch.

This won't reset the parameters that were set with SetSolverSpecificParametersAsString() or set_time_limit() or even clear the linear program. It will just make sure that next Solve() will be as if everything was reconstructed from scratch.

Definition at line 1398 of file linear_solver.cc.

◆ set_time_limit()

void operations_research::MPSolver::set_time_limit ( int64_t time_limit_milliseconds )

inline

Definition at line 875 of file linear_solver.h.

◆ SetCallback()

void operations_research::MPSolver::SetCallback ( MPCallback * mp_callback )

Does not take ownership of "mp_callback".

As of 2019-10-22, only SCIP and Gurobi support Callbacks. SCIP does not support suggesting a heuristic solution in the callback.

Definition at line 1897 of file linear_solver.cc.

◆ SetHint()

void operations_research::MPSolver::SetHint ( std::vector< std::pair< const MPVariable *, double > > hint )

Sets a hint for solution.

If a feasible or almost-feasible solution to the problem is already known, it may be helpful to pass it to the solver so that it can be used. A solver that supports this feature will try to use this information to create its initial feasible solution.

Note: It may not always be faster to give a hint like this to the solver. There is also no guarantee that the solver will use this hint or try to return a solution "close" to this assignment in case of multiple optimal solutions.

Calling SetHint clears all previous hints.

Definition at line 1871 of file linear_solver.cc.

◆ SetNumThreads()

absl::Status operations_research::MPSolver::SetNumThreads ( int num_threads )

-— Solver-specific parameters -—

Sets the number of threads to use by the underlying solver.

Returns OkStatus if the operation was successful. num_threads must be equal to or greater than 1. Note that the behaviour of this call depends on the underlying solver. E.g., it may set the exact number of threads or the max number of threads (check the solver's interface implementation for details). Also, some solvers may not (yet) support this function, but still enable multi-threading via SetSolverSpecificParametersAsString().

Definition at line 358 of file linear_solver.cc.

◆ SetSolverSpecificParametersAsString()

bool operations_research::MPSolver::SetSolverSpecificParametersAsString ( const std::string & parameters )

Advanced usage: pass solver specific parameters in text format.

The format is solver-specific and is the same as the corresponding solver configuration file format. Returns true if the operation was successful.

Definition at line 369 of file linear_solver.cc.

◆ SetStartingLpBasis()

void operations_research::MPSolver::SetStartingLpBasis	(	const std::vector< MPSolver::BasisStatus > &	variable_statuses,
		const std::vector< MPSolver::BasisStatus > &	constraint_statuses )

Advanced usage: Incrementality.

This function takes a starting basis to be used in the next LP Solve() call. The statuses of a current solution can be retrieved via the basis_status() function of a MPVariable or a MPConstraint.

WARNING: With Glop, you should disable presolve when using this because this information will not be modified in sync with the presolve and will likely not mean much on the presolved problem.

Definition at line 1402 of file linear_solver.cc.

◆ SetTimeLimit()

void operations_research::MPSolver::SetTimeLimit ( absl::Duration time_limit )

inline

Definition at line 776 of file linear_solver.h.

◆ Solve() [1/2]

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

Solves the problem using the default parameter values.

Definition at line 1549 of file linear_solver.cc.

◆ Solve() [2/2]

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

Solves the problem using the specified parameter values.

Special case for infeasible constraints so that all solvers have the same behavior.

Todo: (user): replace this by model extraction to proto + proto validation (the proto has very low overhead compared to the wrapper, both in performance and memory, so it's ok).

Definition at line 1554 of file linear_solver.cc.

◆ SolveLazyMutableRequest()

void operations_research::MPSolver::SolveLazyMutableRequest	(	LazyMutableCopy< MPModelRequest >	request,
		MPSolutionResponse *	response,
		std::atomic< bool > *	interrupt = nullptr )

static

This version support both const MPModelRequest& and MPModelRequest&& for the request. When using the second form, it will try to delete the request as soon as it is translated to the solver internal representation. This saves peak memory usage.

Note that we need a different name and can't just accept MPModelRequest&& otherwise we have swig issues.

If the solver supports it, we can std::move() the request since we will return right after this in all cases.

Validate and extract model delta. Also deal with trivial problems.

Even though we don't re-check model validity here, there can be some problems found by LoadModelFromProto, eg. unsupported features.

We'll add a warning message in status_str after the solve.

If we don't need interruption support, we can save some overhead by running the solve in the current thread.

If we get here, we received an interruption notification before the solve finished "naturally".

SUBTLE: our call to InterruptSolve() can be ignored by the underlying solver for several reasons: 1) The solver thread doesn't poll its 'interrupted' bit often enough and takes too long to realize that it should return, or its mere return + FillSolutionResponse() takes too long. 2) The user interrupted the solve so early that Solve() hadn't really started yet when we called InterruptSolve(). In case 1), we should just wait a little longer. In case 2), we should call InterruptSolve() again, maybe several times. To both accommodate cases where the solver takes really a long time to react to the interruption, while returning as quickly as possible, we poll the solve_finished notification with increasing durations and call InterruptSolve again, each time.

Note: in opt builds, the polling thread terminates here with an error message, but we let Solve() finish, ignoring the user interruption request.

The choice to do polling rather than solving in the second thread is not arbitrary, as we want to maintain any custom thread options set by the user. They shouldn't matter for polling, but for solving we might e.g. use a larger stack.

Make sure the interruption notification didn't arrive while waiting to be scheduled.

We block until the thread finishes when thread_pool goes out of scope.

Despite the interruption, the solver might still have found a useful result. If so, don't overwrite the status.

Definition at line 1021 of file linear_solver.cc.

◆ solver_infinity()

double operations_research::MPSolver::solver_infinity ( )

Definition at line 1408 of file linear_solver.cc.

◆ SolverVersion()

std::string operations_research::MPSolver::SolverVersion ( ) const

Returns a string describing the underlying solver and its version.

Definition at line 350 of file linear_solver.cc.

◆ SolveWithProto()

void operations_research::MPSolver::SolveWithProto	(	const MPModelRequest &	model_request,
		MPSolutionResponse *	response,
		std::atomic< bool > *	interrupt = nullptr )

static

Solves the model encoded by a MPModelRequest protocol buffer and fills the solution encoded as a MPSolutionResponse. The solve is stopped prematurely if interrupt is non-null at set to true during (or before) solving. Interruption is only supported if SolverTypeSupportsInterruption() returns true for the requested solver. Passing a non-null interruption with any other solver type immediately returns an MPSOLVER_INCOMPATIBLE_OPTIONS error.

interrupt is non-const because the internal solver may set it to true itself, in some cases.

Note(user): This attempts to first use DirectlySolveProto() (if implemented). Consequently, this most likely does not override any of the default parameters of the underlying solver. This behavior differs from MPSolver::Solve() which by default sets the feasibility tolerance and the gap limit (as of 2020/02/11, to 1e-7 and 0.0001, respectively).

Definition at line 1014 of file linear_solver.cc.

◆ SupportsCallbacks()

bool operations_research::MPSolver::SupportsCallbacks ( ) const

Definition at line 1901 of file linear_solver.cc.

◆ SupportsProblemType()

bool operations_research::MPSolver::SupportsProblemType ( OptimizationProblemType problem_type )

static

Whether the given problem type is supported (this will depend on the targets that you linked).

Definition at line 504 of file linear_solver.cc.

◆ SuppressOutput()

void operations_research::MPSolver::SuppressOutput ( )

Suppresses solver logging.

Definition at line 1828 of file linear_solver.cc.

◆ time_limit()

int64_t operations_research::MPSolver::time_limit ( ) const

inline

Deprecated: Use TimeLimit() and SetTimeLimit(absl::Duration) instead.

Note: These deprecated functions used the convention time_limit = 0 to mean "no limit", which now corresponds to time_limit_ = InfiniteDuration().

Definition at line 870 of file linear_solver.h.

◆ time_limit_in_secs()

double operations_research::MPSolver::time_limit_in_secs ( ) const

inline

Definition at line 880 of file linear_solver.h.

◆ TimeLimit()

absl::Duration operations_research::MPSolver::TimeLimit ( ) const

inline

Definition at line 775 of file linear_solver.h.

◆ underlying_solver()

void * operations_research::MPSolver::underlying_solver ( )

Advanced usage: returns the underlying solver.

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. 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 354 of file linear_solver.cc.

◆ variable()

MPVariable * operations_research::MPSolver::variable ( int index ) const

inline

Returns the variable at position index.

Definition at line 337 of file linear_solver.h.

◆ variables()

const std::vector< MPVariable * > & operations_research::MPSolver::variables ( ) const

inline

Returns the array of variables handled by the MPSolver. (They are listed in the order in which they were created.)

Definition at line 332 of file linear_solver.h.

◆ VerifySolution()

bool operations_research::MPSolver::VerifySolution	(	double	tolerance,
		bool	log_errors ) const

Advanced usage: Verifies the correctness of the solution.

It verifies that all variables must be within their domains, all constraints must be satisfied, and the reported objective value must be accurate.

Usage:

This can only be called after Solve() was called.
"tolerance" is interpreted as an absolute error threshold.
For the objective value only, if the absolute error is too large, the tolerance is interpreted as a relative error threshold instead.
If "log_errors" is true, every single violation will be logged.
If "tolerance" is negative, it will be set to infinity().

Most users should just set the –verify_solution flag and not bother using this method directly.

Todo: (user): split.

Verify variables.

Check for NaN.

Check lower bound.

Check upper bound.

Check integrality.

Verify constraints.

Re-compute the activity with a inaccurate summing algorithm.

Catch NaNs.

Check bounds.

Verify that the objective value wasn't reported incorrectly.

Definition at line 1680 of file linear_solver.cc.

◆ wall_time()

int64_t operations_research::MPSolver::wall_time ( ) const

inline

Deprecated: Use DurationSinceConstruction() instead.

Definition at line 885 of file linear_solver.h.

◆ Write()

void operations_research::MPSolver::Write ( const std::string & file_name )

Writes the model using the solver internal write function. Currently only available for Gurobi.

Definition at line 1581 of file linear_solver.cc.

Friends And Related Symbol Documentation

◆ BopInterface

friend class BopInterface

friend

Definition at line 899 of file linear_solver.h.

◆ CBCInterface

friend class CBCInterface

friend

Definition at line 891 of file linear_solver.h.

◆ CLPInterface

friend class CLPInterface

friend

Definition at line 890 of file linear_solver.h.

◆ CplexInterface

friend class CplexInterface

friend

Definition at line 894 of file linear_solver.h.

◆ GLOPInterface

friend class GLOPInterface

friend

Definition at line 898 of file linear_solver.h.

◆ GLPKInterface

friend class GLPKInterface

friend

Definition at line 889 of file linear_solver.h.

◆ GurobiInterface

friend class GurobiInterface

friend

Definition at line 893 of file linear_solver.h.

◆ HighsInterface

friend class HighsInterface

friend

Definition at line 902 of file linear_solver.h.

◆ KnapsackInterface

friend class KnapsackInterface

friend

Definition at line 903 of file linear_solver.h.

◆ MPSolverInterface

friend class MPSolverInterface

friend

Definition at line 897 of file linear_solver.h.

◆ PdlpInterface

friend class PdlpInterface

friend

Definition at line 901 of file linear_solver.h.

◆ SatInterface

friend class SatInterface

friend

Definition at line 900 of file linear_solver.h.

◆ SCIPInterface

friend class SCIPInterface

friend

Definition at line 892 of file linear_solver.h.

◆ SLMInterface

friend class SLMInterface

friend

Definition at line 896 of file linear_solver.h.

◆ XpressInterface

friend class XpressInterface

friend

Definition at line 895 of file linear_solver.h.

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

ortools/linear_solver/linear_solver.h
ortools/linear_solver/linear_solver.cc

Public Types

Public Member Functions

Static Public Member Functions

Friends

Detailed Description

Member Enumeration Documentation

◆ BasisStatus

◆ OptimizationProblemType

◆ ResultStatus

Constructor & Destructor Documentation

◆ MPSolver() [1/2]

◆ MPSolver() [2/2]

◆ ~MPSolver()

Member Function Documentation

◆ ABSL_DEPRECATED()

◆ ClampSolutionWithinBounds()

◆ Clear()

◆ ComputeConstraintActivities()

◆ ComputeExactConditionNumber()

◆ constraint()

◆ constraints()

◆ CreateSolver()

◆ DurationSinceConstruction()

◆ EnableOutput()

◆ ExportModelAsLpFormat()

◆ ExportModelAsMpsFormat()

◆ ExportModelToProto()

◆ FillSolutionResponseProto()

◆ GetMPModelRequestLoggingInfo()

◆ GetNumThreads()

◆ GetSolverSpecificParametersAsString()

◆ global_num_constraints()

◆ global_num_variables()

◆ infinity()

◆ InterruptSolve()

◆ IsMIP()

◆ iterations()

◆ LoadModelFromProto()

◆ LoadModelFromProtoWithUniqueNamesOrDie()

◆ LoadSolutionFromProto()

◆ LookupConstraintOrNull()

◆ LookupVariableOrNull()

◆ MakeBoolVar()

◆ MakeBoolVarArray()

◆ MakeIntVar()

◆ MakeIntVarArray()

◆ MakeNumVar()

◆ MakeNumVarArray()

◆ MakeRowConstraint() [1/6]

◆ MakeRowConstraint() [2/6]

◆ MakeRowConstraint() [3/6]

◆ MakeRowConstraint() [4/6]

◆ MakeRowConstraint() [5/6]

◆ MakeRowConstraint() [6/6]

◆ MakeVar()

◆ MakeVarArray()

◆ MutableObjective()

◆ Name()

◆ NextSolution()

◆ nodes()

◆ NumConstraints()

◆ NumVariables()

◆ Objective()

◆ operator=()

◆ OutputIsEnabled()

◆ OwnsVariable()

◆ ParseSolverType()

◆ ParseSolverTypeOrDie()

◆ ProblemType()

◆ Reset()

◆ set_time_limit()

◆ SetCallback()

◆ SetHint()

◆ SetNumThreads()

◆ SetSolverSpecificParametersAsString()

◆ SetStartingLpBasis()

◆ SetTimeLimit()

◆ Solve() [1/2]

◆ Solve() [2/2]

◆ SolveLazyMutableRequest()