operations_research::pdlp::internal Namespace Reference

Utility functions for internal use only. More...

Classes
class	DualTrustRegionProblem
class	PrimalTrustRegionProblem

Functions
glop::ProblemSolution	ComputeStatuses (const QuadraticProgram &qp, const PrimalAndDualSolution &solution)
absl::Status	TestableCanFitInMpModelProto (const QuadraticProgram &qp, const int64_t largest_ok_size)
void	CombineRepeatedTripletsInPlace (std::vector< Eigen::Triplet< double, int64_t > > &triplets)
template<typename TrustRegionProblem >
double	DistanceAtCriticalStepSize (const TrustRegionProblem &problem, const int64_t index)
template<typename TrustRegionProblem >
double	CriticalStepSize (const TrustRegionProblem &problem, const int64_t index)
template<typename TrustRegionProblem >
double	ProjectedValue (const TrustRegionProblem &problem, const int64_t index, const double step_size)
template<typename ArrayType , typename ValueFunction >
double	EasyMedian (ArrayType array, ValueFunction value_function)
template<typename TrustRegionProblem >
double	ComputeInitialUndecidedComponents (const TrustRegionProblem &problem, int64_t start_index, int64_t end_index, std::vector< int64_t > &undecided_components)
template<typename TrustRegionProblem >
double	RadiusSquaredOfUndecidedComponents (const TrustRegionProblem &problem, const double step_size, const std::vector< int64_t > &undecided_components)
template<typename TrustRegionProblem >
double	RemoveCriticalStepsAboveThreshold (const TrustRegionProblem &problem, const double step_size_threshold, std::vector< int64_t > &undecided_components)
template<typename TrustRegionProblem >
double	RemoveCriticalStepsBelowThreshold (const TrustRegionProblem &problem, const double step_size_threshold, std::vector< int64_t > &undecided_components)

Detailed Description

Utility functions for internal use only.

Function Documentation

CombineRepeatedTripletsInPlace()

void operations_research::pdlp::internal::CombineRepeatedTripletsInPlace

(

std::vector< Eigen::Triplet< double, int64_t > > &

triplets

)

Modifies triplets in place, combining consecutive entries with the same row and column, summing their values. This is most effective if triplets are sorted by row and column, so that multiple entries for the same entry will be consecutive.

*output_iter is the last output value, so erase everything after that.

Definition at line 462 of file quadratic_program.cc.

ComputeInitialUndecidedComponents()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::ComputeInitialUndecidedComponents	(	const TrustRegionProblem &	problem,
		int64_t	start_index,
		int64_t	end_index,
		std::vector< int64_t > &	undecided_components )

Lists the undecided components (from [start_index, end_index) as those with finite critical step sizes. The components with infinite critical step sizes will never hit their bounds, so returns their contribution to square of the radius.

Todo

(user): Evaluate dropping this reserve(), since it wastes space if many components are decided.

Simplified from norm_weight * (objective / norm_weight)^2.

Definition at line 251 of file trust_region.h.

ComputeStatuses()

glop::ProblemSolution operations_research::pdlp::internal::ComputeStatuses	(	const QuadraticProgram &	qp,
		const PrimalAndDualSolution &	solution )

Computes variable and constraint statuses. This determines if primal variables are at their bounds based on exact comparisons and therefore may not work with unscaled solutions. The primal and dual solution in the returned ProblemSolution are NOT set.

This doesn't matter much as glop's preprocessor doesn't use this much. We pick IMPRECISE since we are often calling this code early in the solve.

Note

ShardedWeightedAverage is designed so that variables at their bounds will be exactly at their bounds even with floating-point roundoff.

Definition at line 2970 of file primal_dual_hybrid_gradient.cc.

CriticalStepSize()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::CriticalStepSize	(	const TrustRegionProblem &	problem,
		const int64_t	index )

The critical step size is the step size at which the indexed element hits its bound (or infinity if that doesn't happen).

Definition at line 209 of file trust_region.h.

DistanceAtCriticalStepSize()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::DistanceAtCriticalStepSize	(	const TrustRegionProblem &	problem,
		const int64_t	index )

These functions templated on TrustRegionProblem compute values useful to the trust region solve. The templated TrustRegionProblem type should provide methods: double Objective(int64_t index) const; double LowerBound(int64_t index) const; double UpperBound(int64_t index) const; double CenterPoint(int64_t index) const; double NormWeight(int64_t index) const; See trust_region.cc for more details and several implementations. The distance (in the indexed element) from the center point to the bound, in the direction that reduces the objective.

Definition at line 194 of file trust_region.h.

EasyMedian()

template<typename ArrayType , typename ValueFunction >

double operations_research::pdlp::internal::EasyMedian	(	ArrayType	array,
		ValueFunction	value_function )

An easy way of computing medians that's slightly off when the length of the array is even. array is intentionally passed by value. value_function maps an element of array to its (double) value. Returns the value of the median element.

Definition at line 235 of file trust_region.h.

ProjectedValue()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::ProjectedValue	(	const TrustRegionProblem &	problem,
		const int64_t	index,
		const double	step_size )

The value of the indexed element at the given step_size, projected onto the bounds.

Definition at line 221 of file trust_region.h.

RadiusSquaredOfUndecidedComponents()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::RadiusSquaredOfUndecidedComponents	(	const TrustRegionProblem &	problem,
		const double	step_size,
		const std::vector< int64_t > &	undecided_components )

Definition at line 272 of file trust_region.h.

RemoveCriticalStepsAboveThreshold()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::RemoveCriticalStepsAboveThreshold	(	const TrustRegionProblem &	problem,
		const double	step_size_threshold,
		std::vector< int64_t > &	undecided_components )

Points whose critical step sizes are greater than or equal to step_size_threshold are eliminated from the undecided components (we know they'll be determined by center_point - step_size * objective / norm_weights). Returns the coefficient of step_size^2 that accounts of the contribution of the removed variables to the radius squared.

Simplified from norm_weight * (objective / norm_weight)^2.

Definition at line 291 of file trust_region.h.

RemoveCriticalStepsBelowThreshold()

template<typename TrustRegionProblem >

double operations_research::pdlp::internal::RemoveCriticalStepsBelowThreshold	(	const TrustRegionProblem &	problem,
		const double	step_size_threshold,
		std::vector< int64_t > &	undecided_components )

Points whose critical step sizes are smaller than or equal to step_size_threshold are eliminated from the undecided components (we know they'll always be at their bounds). Returns the weighted distance squared from the center point for the removed components.

Definition at line 318 of file trust_region.h.

TestableCanFitInMpModelProto()

absl::Status operations_research::pdlp::internal::TestableCanFitInMpModelProto	(	const QuadraticProgram &	qp,
		int64_t	largest_ok_size )

Like CanFitInMpModelProto() but has an extra argument for the largest number of variables, constraints, or objective non-zeros that should be counted as convertible. CanFitInMpModelProto() passes 2^31 - 1 for this argument and unit tests pass small values.

Definition at line 224 of file quadratic_program.cc.