A full-fledged linear programming solver. More...

#include <lp_solver.h>

Public Member Functions
	LPSolver ()

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

LPSolver &	operator= (const LPSolver &)=delete

void	SetParameters (const GlopParameters &parameters)

const GlopParameters &	GetParameters () const

GlopParameters *	GetMutableParameters ()

ABSL_MUST_USE_RESULT ProblemStatus	Solve (const LinearProgram &lp)

ABSL_MUST_USE_RESULT ProblemStatus	SolveWithTimeLimit (const LinearProgram &lp, TimeLimit *time_limit)

void	Clear ()

void	SetInitialBasis (const VariableStatusRow &variable_statuses, const ConstraintStatusColumn &constraint_statuses)

ProblemStatus	LoadAndVerifySolution (const LinearProgram &lp, const ProblemSolution &solution)

Fractional	GetObjectiveValue () const
	Returns the objective value of the solution with its offset and scaling.

const DenseRow &	variable_values () const
	Accessors to information related to variables.

const DenseRow &	reduced_costs () const

const VariableStatusRow &	variable_statuses () const

const DenseColumn &	dual_values () const

const DenseColumn &	constraint_activities () const

const ConstraintStatusColumn &	constraint_statuses () const

const DenseRow &	primal_ray () const

const DenseColumn &	constraints_dual_ray () const

const DenseRow &	variable_bounds_dual_ray () const

Fractional	GetMaximumPrimalInfeasibility () const

Fractional	GetMaximumDualInfeasibility () const

bool	MayHaveMultipleOptimalSolutions () const

int	GetNumberOfSimplexIterations () const
	Returns the number of simplex iterations used by the last Solve().

double	DeterministicTime () const

SolverLogger &	GetSolverLogger ()

Static Public Member Functions
static std::string	GlopVersion ()
	Returns a string that describes the version of the solver.

Detailed Description

A full-fledged linear programming solver.

Definition at line 31 of file lp_solver.h.

Constructor & Destructor Documentation

◆ LPSolver() [1/2]

operations_research::glop::LPSolver::LPSolver ( )

LPSolver

Definition at line 120 of file lp_solver.cc.

◆ LPSolver() [2/2]

operations_research::glop::LPSolver::LPSolver ( const LPSolver & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ Clear()

void operations_research::glop::LPSolver::Clear ( )

Puts the solver in a clean state.

Calling Solve() for the first time, or calling Clear() then Solve() on the same problem is guaranteed to be deterministic and to always give the same result, assuming that no time limit was specified.

Definition at line 275 of file lp_solver.cc.

◆ constraint_activities()

const DenseColumn & operations_research::glop::LPSolver::constraint_activities ( ) const

inline

Definition at line 122 of file lp_solver.h.

◆ constraint_statuses()

const ConstraintStatusColumn & operations_research::glop::LPSolver::constraint_statuses ( ) const

inline

Definition at line 125 of file lp_solver.h.

◆ constraints_dual_ray()

const DenseColumn & operations_research::glop::LPSolver::constraints_dual_ray ( ) const

inline

Definition at line 135 of file lp_solver.h.

◆ DeterministicTime()

double operations_research::glop::LPSolver::DeterministicTime ( ) const

Returns the "deterministic time" since the creation of the solver. Note That this time is only increased when some operations take place in this class.

Todo: (user): Currently, this is only modified when the simplex code is executed.

Todo: (user): Improve the correlation with the running time.

Definition at line 547 of file lp_solver.cc.

◆ dual_values()

const DenseColumn & operations_research::glop::LPSolver::dual_values ( ) const

inline

Accessors to information related to constraints. The activity of a constraint is the sum of its linear terms evaluated with variables taking their values at the current solution.

Note: the dual_values() do not take into account an eventual objective scaling of the solved LinearProgram.

Definition at line 121 of file lp_solver.h.

◆ GetMaximumDualInfeasibility()

Fractional operations_research::glop::LPSolver::GetMaximumDualInfeasibility ( ) const

Returns the dual maximum infeasibility of the solution. This indicates by how much the variable costs (i.e. objective) should be modified for the solution to be an exact optimal solution.

Definition at line 535 of file lp_solver.cc.

◆ GetMaximumPrimalInfeasibility()

Fractional operations_research::glop::LPSolver::GetMaximumPrimalInfeasibility ( ) const

Returns the primal maximum infeasibility of the solution. This indicates by how much the variable and constraint bounds are violated.

Definition at line 531 of file lp_solver.cc.

◆ GetMutableParameters()

GlopParameters * operations_research::glop::LPSolver::GetMutableParameters ( )

Definition at line 140 of file lp_solver.cc.

◆ GetNumberOfSimplexIterations()

int operations_research::glop::LPSolver::GetNumberOfSimplexIterations ( ) const

Returns the number of simplex iterations used by the last Solve().

Definition at line 543 of file lp_solver.cc.

◆ GetObjectiveValue()

Fractional operations_research::glop::LPSolver::GetObjectiveValue ( ) const

Returns the objective value of the solution with its offset and scaling.

Definition at line 527 of file lp_solver.cc.

◆ GetParameters()

const GlopParameters & operations_research::glop::LPSolver::GetParameters ( ) const

Definition at line 138 of file lp_solver.cc.

◆ GetSolverLogger()

SolverLogger & operations_research::glop::LPSolver::GetSolverLogger ( )

Returns the SolverLogger used during solves.

Please note that EnableLogging() and SetLogToStdOut() are reset at the beginning of each solve based on parameters so setting them will have no effect.

Definition at line 142 of file lp_solver.cc.

◆ GlopVersion()

std::string operations_research::glop::LPSolver::GlopVersion ( )

static

Returns a string that describes the version of the solver.

Definition at line 122 of file lp_solver.cc.

◆ LoadAndVerifySolution()

ProblemStatus operations_research::glop::LPSolver::LoadAndVerifySolution	(	const LinearProgram &	lp,
		const ProblemSolution &	solution )

This loads a given solution and computes related quantities so that the getters below will refer to it.

Depending on the given solution status, this also checks the solution feasibility or optimality. The exact behavior and tolerances are controlled by the solver parameters. Because of this, the returned ProblemStatus may be changed from the one passed in the ProblemSolution to ABNORMAL or IMPRECISE. Note that this is the same logic as the one used by Solve() to verify the solver solution.

Todo: (user): Try to also check the precision of an INFEASIBLE or UNBOUNDED return status.

Load the solution.

Objective before eventually moving the primal/dual values inside their bounds.

Eventually move the primal/dual values inside their bounds.

The reported objective to the user.

These will be set to true if the associated "infeasibility" is too large.

The tolerance used is the parameter solution_feasibility_tolerance. To be somewhat independent of the original problem scaling, the thresholds used depend of the quantity involved and of its coordinates:

tolerance * max(1.0, abs(cost[col])) when a reduced cost is infeasible.
tolerance * max(1.0, abs(bound)) when a bound is crossed.
tolerance for an infeasible dual value (because the limit is always 0.0).

Computes all the infeasiblities and update the Booleans above.

Todo: (user): the name is not really consistent since in practice those are the "residual" since the primal/dual infeasibility are zero when parameters_.provide_strong_optimal_guarantee() is true.

Now that all the relevant quantities are computed, we check the precision and optimality of the result. See Chvatal pp. 61-62. If any of the tests fail, we return the IMPRECISE status.

If the primal/dual values were moved to the bounds, then the primal/dual infeasibilities should be exactly zero (but not the residuals).

Note: we compare the values without offset nor scaling. We also need to compare them before we move the primal/dual values, otherwise we lose some precision since the values are modified independently of each other.

Definition at line 335 of file lp_solver.cc.

◆ MayHaveMultipleOptimalSolutions()

bool operations_research::glop::LPSolver::MayHaveMultipleOptimalSolutions ( ) const

Returns true if the solution status was OPTIMAL and it seems that there is more than one basic optimal solution. Note that this solver always returns an optimal BASIC solution and that there is only a finite number of them. Moreover, given one basic solution, since the basis is always refactorized at optimality before reporting the numerical result, then all the quantities (even the floating point ones) should be always the same.

Todo: (user): Test this behavior extensively if a client relies on it.

Definition at line 539 of file lp_solver.cc.

◆ operator=()

LPSolver & operations_research::glop::LPSolver::operator= ( const LPSolver & )

delete

◆ primal_ray()

const DenseRow & operations_research::glop::LPSolver::primal_ray ( ) const

inline

Accessors to information related to unboundedness. A primal ray is returned for primal unbounded problems and a dual ray is returned for dual unbounded problems. constraints_dual_ray corresponds to dual multiplier for constraints and variable_bounds_dual_ray corresponds to dual multipliers for variable bounds (cf. reduced_costs).

Definition at line 134 of file lp_solver.h.

◆ reduced_costs()

const DenseRow & operations_research::glop::LPSolver::reduced_costs ( ) const

inline

Definition at line 110 of file lp_solver.h.

◆ SetInitialBasis()

void operations_research::glop::LPSolver::SetInitialBasis	(	const VariableStatusRow &	variable_statuses,
		const ConstraintStatusColumn &	constraint_statuses )

Advanced usage. This should be called before calling Solve(). It will configure the solver to try to start from the given point for the next Solve() only. Note that calling Clear() will invalidate this information.

If the set of variables/constraints with a BASIC status does not form a basis a warning will be logged and the code will ignore it. Otherwise, the non-basic variables will be initialized to their given status and solving will start from there (even if the solution is not primal/dual feasible).

Important: There is no facility to transform this information in sync with presolve. So you should probably disable presolve when using this since otherwise there is a good chance that the matrix will change and that the given basis will make no sense. Even worse if it happens to be factorizable but doesn't correspond to what was intended.

Create the associated basis state.

Note the change of upper/lower bound between the status of a constraint and the status of its associated slack variable.

Definition at line 280 of file lp_solver.cc.

◆ SetParameters()

void operations_research::glop::LPSolver::SetParameters ( const GlopParameters & parameters )

Sets and gets the solver parameters. See the proto for an extensive documentation.

Definition at line 126 of file lp_solver.cc.

◆ Solve()

ProblemStatus operations_research::glop::LPSolver::Solve ( const LinearProgram & lp )

Solves the given linear program and returns the solve status. See the ProblemStatus documentation for a description of the different values.

The solution can be retrieved afterwards using the getter functions below.

Note: depending on the returned ProblemStatus the solution values may not mean much, so it is important to check the returned status.

Incrementality: From one Solve() call to the next, the internal state is not cleared and the solver may take advantage of its current state if the given lp is only slightly modified. If the modification is too important, or if the solver does not see how to reuse the previous state efficiently, it will just solve the problem from scratch. On the other hand, if the lp is the same, calling Solve() again should basically resume the solve from the last position. To disable this behavior, simply call Clear() before.

Definition at line 144 of file lp_solver.cc.

◆ SolveWithTimeLimit()

ProblemStatus operations_research::glop::LPSolver::SolveWithTimeLimit	(	const LinearProgram &	lp,
		TimeLimit *	time_limit )

Same as Solve() but use the given time limit rather than constructing a new one from the current GlopParameters.

Display a warning if running in non-opt, unless we're inside a unit test.

Setup the logger.

Log some initial info about the input model.

Check some preconditions.

Todo: (user): Unfortunately we are not really helpful with the error message here. We could do a better job. However most client should talk to glop via an input protocol buffer which should have better validation messages.

Make an internal copy of the problem for the preprocessing.

Remove small entries even if presolve is off. This is mainly here to avoid floating point underflow. Keeping them can break many invariant like a * b == 0 iff a == 0 or b == 0.

Note: our presolve/scaling can potentially create smaller entries than this, but the scale should stay reasonable.

Todo: (user): If speed matter, we could do that as we copy the program.

Preprocess.

At this point, we need to initialize a ProblemSolution with the correct size and status.

LoadAndVerifySolution() below updates primal_values_, dual_values_, variable_statuses_ and constraint_statuses_ with the values stored in solution by RunPrimalDualPathFollowingMethodIfNeeded() and RunRevisedSimplexIfNeeded(), and hence clears any results stored in them from a previous run. In contrast, primal_ray_, constraints_dual_ray_, and variable_bounds_dual_ray_ are modified directly by RunRevisedSimplexIfNeeded(), so we explicitly clear them from previous run results.

Do not launch the solver if the time limit was already reached. This might mean that the pre-processors were not all run, and current_linear_program_ might not be in a completely safe state.

LOG some statistics that can be parsed by our benchmark script.

Definition at line 150 of file lp_solver.cc.

◆ variable_bounds_dual_ray()

const DenseRow & operations_research::glop::LPSolver::variable_bounds_dual_ray ( ) const

inline

Definition at line 138 of file lp_solver.h.

◆ variable_statuses()

const VariableStatusRow & operations_research::glop::LPSolver::variable_statuses ( ) const

inline

Definition at line 111 of file lp_solver.h.

◆ variable_values()

const DenseRow & operations_research::glop::LPSolver::variable_values ( ) const

inline

Accessors to information related to variables.

Definition at line 109 of file lp_solver.h.

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

ortools/glop/lp_solver.h
ortools/glop/lp_solver.cc

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ LPSolver() [1/2]

◆ LPSolver() [2/2]

Member Function Documentation

◆ Clear()

◆ constraint_activities()

◆ constraint_statuses()

◆ constraints_dual_ray()

◆ DeterministicTime()

◆ dual_values()

◆ GetMaximumDualInfeasibility()

◆ GetMaximumPrimalInfeasibility()

◆ GetMutableParameters()

◆ GetNumberOfSimplexIterations()

◆ GetObjectiveValue()

◆ GetParameters()

◆ GetSolverLogger()

◆ GlopVersion()

◆ LoadAndVerifySolution()

◆ MayHaveMultipleOptimalSolutions()

◆ operator=()

◆ primal_ray()

◆ reduced_costs()

◆ SetInitialBasis()

◆ SetParameters()

◆ Solve()

◆ SolveWithTimeLimit()

◆ variable_bounds_dual_ray()

◆ variable_statuses()

◆ variable_values()