Graph Minimizer

The graph minimizer solves an energy minimization problem where we have n nodes \(N_i\), with each node having several possible solutions. Every solution has a self energy \(E_{self}\) and pairwise energies in between nodes are possible. The goal is to select exactly one solution per node to obtain a set \(X=[x_1, x_2, ..., x_n]\) that minimizes:

\[F(X)=\displaystyle\sum_iE_{self}(N_i[x_i]) +\displaystyle \sum_i \displaystyle \sum_{j>i}E_{pair}(N_i[x_i], N_j[x_j])\]
class promod3.core.GraphMinimizer
AddNode(self_energies)

Adds a node to the graph.

Parameters:

self_energies (list of float) – Directly controls the number of possible solutions in that node and assigns the corresponding self energies

Returns:

The idx of the added node

Return type:

int

AddEdge(node_idx_one, node_idx_two, pairwise_energies)

Adds an edge between the specified nodes.

Parameters:

  • node_idx_one (int) – Index of the first node

  • node_idx_two (int) – Index of the second node

  • pairwise_energies (list of list of float) – The pairwise energies that contribute to the overall energy function. There must be a list for every possible solution in node one. All of those lists must have exactly the length of possible solutions in node two.

Returns:

The idx of the added edge

Return type:

int

Raises:

RuntimeError if node_idx_one or node_idx_two specify non existent nodes or when pairwise_energies is inconsistent with the number of solutions in the specified nodes.

ApplyDEE(node_idx[, e_cut=0.0])

Applies dead end elimination on one particular node and potentially deactivates certain solutions. The goldstein criterion is described in [goldstein1994].

Parameters:

  • node_idx (int) – Node to apply dead end elimination

  • e_cut (float) – If set to 0.0, the default goldstein criterion is applied => a solution is removed if it’s dominated by all other solutions in the same node. If you increase this value, a solution must be dominated by at least this e_cut.

Returns:

bool whether any solution has been deactivated.

ApplyEdgeDecomposition(edge_idx, epsilon)

Applies edge decomposition on one particular edge and potentially deactivates it. The exact decomposition procedure is described in [krivov2009].

Parameters:

  • edge_idx (int) – Edge to decompose.

  • epsilon (float) – The energy threshold to perform edge decomposition.

Returns:

bool whether the edge has been decomposed and deactivated

Prune(epsilon[, e_cut=0.0, consider_all_nodes=False])

Performs edge decomposition followed by dead end elimination in an iterative manner until no changes can be observed anymore given epsilon.

Parameters:

  • epsilon (float) – The energy threshold to perform edge decomposition.

  • e_cut (float) – Parameter to control dead end elimination.

  • consider_all_nodes (bool) – Flag, wether the dead end elimination should be applied to all nodes, or only those who are connected with an edge removed by edge decomposition. This is useful if already a Prune operation has been performed => only those nodes connected to a removed edge have the chance for successful dead end elimination.

Reset()

Resets the graph by undoing any pruning operation (DEE and edge decomposition)

TreeSolve([max_complexity=inf, initial_epsilon=0.02])

The method solves a graph using a minimal width tree decomposition approach in an iterative manner. In every iteration, the algorithm performs a pruning step (DEE / Edge Decomposition) and subsequently tries to solve each connected component in the graph separately. If the number of possible enumerations in the tree constructetd from a particular connected component is is larger max_complexity, this component is solved in a later iteration. The algorithm iterates until all connected components are solved and steadily increases the epsilon value resulting in a more and more agressive edge decomposition. Algorithm further descsribed in [krivov2009].

Parameters:

  • max_complexity (int) – Max number of possible permutations, that have to be enumerated in the resulting tree after tree decomposition.

  • initial_epsilon (float) – The initial energy threshold to perform edge decomposition.

Returns:

A tuple with the first element being a list of indices representing the single solutions minimizing the overall energy function. The second element is the according energy value.

AStarSolve(e_thresh[, max_n=100, max_visited_nodes=100000000])

The method solves a graph using the A* algorithm. Besides creating the minimal energy solution, the function produces a maximum of max_n solutions sorted by energy. It aborts as soon as it sees the first solution with an energy difference of e_thresh to the optimal solution or hits max_n. If you’re only interested in the optimal solution you should use the TreeSolve function since it’s much faster and uses less memory. There is no automatic pruning of the graph using DEE or edge decomposition, so you have to do it by yourself, otherwise you’ll have a looooooong runtime or even hit the max_visited_nodes parameter that caps the memory usage. To have a valid solution you have to take care that you set the e_cut parameter in the pruning function to e_tresh. Algorithm is described in [leach1998].

Parameters:

  • e_thresh (float) – Maximal energy difference of a solution to the optimal solution to be considered.

  • max_n (int) – The maximum number of solutions that will be generated.

  • max_visited_nodes (int) – Caps the memory usage of the algorithm. Besides The memory used for pairwise energies and self energies, the algorithm uses about max_visited_nodes * 20 bytes.

Returns:

A tuple with the first element being a list of solutions. The second element is a list of energies for the according solutions.

MCSolve([n=100, mc_steps=100000, start_temperature=1000.0, \                   change_frequency=1000, cooling_factor=0.9, seed=0])

Does a total of n Monte Carlo runs to find low energy solutions of the graph. Each run starts with a random configuration. At each of the mc_steps steps, a random node and a random solution at that location is selected and an energy difference of that random selection relative to the current configuration is estimated. If the difference in energy is negative, the step is accepted. If not, the step is accepted with a probability given by the temperature dependent Metropolis criterion \(exp^{\left(\frac{-e_{diff}}{T}\right)}\). The temperature for every run starts with start_temperature and is multiplied every change_frequency steps with cooling_factor to achieve a simulated annealing effect. There is no automatic pruning of the graph using DEE or edge decomposition, you have to do that by yourself.

Parameters:

  • n (int) – Number of Monte Carlo runs

  • mc_steps (int) – Number of Monte Carlo steps per run

  • start_temperature (float) – Start temperature for the temperature dependent Metropolis criterion

  • change_frequency (int) – Number of steps the temperature stays the same

  • cooling_factor (float) – Factor to multiply temperature each change_frequency steps

  • seed (float) – Seed for random number generator

Returns:

A tuple with the first element being a list of solutions. The second element is a list of energies for the according solutions.

NaiveSolve()

Don’t even think of using this… This function only exists for debug purposes and does the full enumeration of the solution space. It might become faster with the appropriate techniques.

Returns:

A tuple with the first element being a list of indices representing the single solutions minimizing the overall energy function. The second element is the according energy value.

Search

Enter search terms or a module, class or function name.

Contents