operations_research::glop::LPDecomposer Class Reference

#include <lp_decomposer.h>

Public Member Functions
	LPDecomposer ()
	LPDecomposer (const LPDecomposer &)=delete
	This type is neither copyable nor movable.
LPDecomposer &	operator= (const LPDecomposer &)=delete
void	Decompose (const LinearProgram *linear_problem) ABSL_LOCKS_EXCLUDED(mutex_)
int	GetNumberOfProblems () const ABSL_LOCKS_EXCLUDED(mutex_)
	Returns the number of independent problems generated by Decompose().
const LinearProgram &	original_problem () const ABSL_LOCKS_EXCLUDED(mutex_)
	Returns the original problem, i.e. as it was before any decomposition.
void	ExtractLocalProblem (int problem_index, LinearProgram *lp) ABSL_LOCKS_EXCLUDED(mutex_)
DenseRow	AggregateAssignments (absl::Span< const DenseRow > assignments) const ABSL_LOCKS_EXCLUDED(mutex_)
DenseRow	ExtractLocalAssignment (int problem_index, const DenseRow &assignment) ABSL_LOCKS_EXCLUDED(mutex_)

Detailed Description

This class is used to decompose an existing LinearProgram into several independent LinearPrograms. Problems are independent when none of their variables are connected, i.e. appear in the same constraints. Consider for instance the following problem: min: x + 2 y + 3 z + 4 t + 5 u c1: 0 <= x + z <= 1; c2: 0 <= y + t <= 1; c3: 0 <= x + u <= 1; int: x, y, z, t, u Variables x, z and u are connected by constraints c1 and c3. Variables y and t are connected by constraints c2. The problem can be decomposed into two independent problems: min: x + 3 z + 5 u c1: 0 <= x + z <= 1; c3: 0 <= x + u <= 1; int: x, z, u and min: 2 y + 4 t c2: 0 <= y + t <= 1; int: y, t

Note

a solution to those two independent problems is a solution to the original problem.

Definition at line 52 of file lp_decomposer.h.

Constructor & Destructor Documentation

LPDecomposer() [1/2]

operations_research::glop::LPDecomposer::LPDecomposer

(

)

LPDecomposer

Definition at line 37 of file lp_decomposer.cc.

LPDecomposer() [2/2]

operations_research::glop::LPDecomposer::LPDecomposer ( const LPDecomposer & )

delete

This type is neither copyable nor movable.

Member Function Documentation

AggregateAssignments()

DenseRow operations_research::glop::LPDecomposer::AggregateAssignments

(

absl::Span< const DenseRow >

assignments

)

const

Returns an assignment to the original problem based on the assignments to the independent problems. Requires Decompose() to have been called.

Definition at line 144 of file lp_decomposer.cc.

Decompose()

void operations_research::glop::LPDecomposer::Decompose

(

const LinearProgram *

linear_problem

)

Decomposes the problem into independent problems.

Note

a pointer is kept (no copy) on the linear_problem, so the problem should not change during the life of the LPDecomposer object.

Iterate on all constraints, and merge all variables of each constraint.

Definition at line 40 of file lp_decomposer.cc.

ExtractLocalAssignment()

DenseRow operations_research::glop::LPDecomposer::ExtractLocalAssignment	(	int	problem_index,
		const DenseRow &	assignment )

Returns an assignment to the given subproblem based on the assignment to the original problem. Requires Decompose() to have been called.

Definition at line 162 of file lp_decomposer.cc.

ExtractLocalProblem()

void operations_research::glop::LPDecomposer::ExtractLocalProblem	(	int	problem_index,
		LinearProgram *	lp )

Fills lp with the problem_index^th independent problem generated by Decompose().

Note

this method runs in O(num-entries-in-generated-problem).

Create variables and get all constraints of the cluster.

Create the constraints.

Definition at line 83 of file lp_decomposer.cc.

GetNumberOfProblems()

int operations_research::glop::LPDecomposer::GetNumberOfProblems

(

)

const

Returns the number of independent problems generated by Decompose().

Definition at line 73 of file lp_decomposer.cc.

operator=()

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

delete

original_problem()

const LinearProgram & operations_research::glop::LPDecomposer::original_problem

(

)

const

Returns the original problem, i.e. as it was before any decomposition.

Definition at line 78 of file lp_decomposer.cc.

---

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

• ortools/lp_data/lp_decomposer.h
• ortools/lp_data/lp_decomposer.cc