Static solver for Variable Placement with Separation Constraints problem instance. More...

#include <solve_VPSC.h>

Inheritance diagram for vpsc::Solver:

Collaboration diagram for vpsc::Solver:

Public Member Functions
virtual bool	satisfy ()
	Results in an approximate solution subject to the constraints. More...

virtual bool	solve ()
	Results in an optimum solution subject to the constraints. More...

Variables const &	getVariables ()
	Returns the Variables in this problem instance. More...

Protected Member Functions
void	copyResult ()

Detailed Description

Static solver for Variable Placement with Separation Constraints problem instance.

This class attempts to solve a least-squares problem subject to a set of separation constraints. The solve() and satisfy() methods return true if any constraints are active, in both cases false means an unconstrained optimum has been found.

See also: IncSolver

Member Function Documentation

◆ copyResult()

void vpsc::Solver::copyResult ( )

protected

Stores the relative positions of the variables in their finalPosition field.

◆ getVariables()

Variables const& vpsc::Solver::getVariables ( )

inline

Returns the Variables in this problem instance.

Returns: A vector of Variable objects.

◆ satisfy()

bool vpsc::Solver::satisfy ( )

virtual

Results in an approximate solution subject to the constraints.

Returns: true if any constraints are active, or false if an unconstrained optimum has been found.

Produces a feasible - though not necessarily optimal - solution by examining blocks in the partial order defined by the directed acyclic graph of constraints. For each block (when processing left to right) we maintain the invariant that all constraints to the left of the block (incoming constraints) are satisfied. This is done by repeatedly merging blocks into bigger blocks across violated constraints (most violated first) fixing the position of variables inside blocks relative to one another so that constraints internal to the block are satisfied.

Reimplemented in vpsc::IncSolver.

◆ solve()

bool vpsc::Solver::solve ( )

virtual

Results in an optimum solution subject to the constraints.

Returns: true if any constraints are active, or false if an unconstrained optimum has been found.

Calculate the optimal solution. After using satisfy() to produce a feasible solution, refine() examines each block to see if further refinement is possible by splitting the block. This is done repeatedly until no further improvement is possible.