dbranch Solver

Overview

This Python code provides a solution to the d-MBV (d-Branch Vertex) problem using graph theory. The d-MBV problem involves finding the minimum number of vertices to remove from a graph to eliminate all d-branch vertices.

Problem Description

The d-Minimum Branch Vertices (d-MBV) problem involves finding a spanning tree of a connected graph G = (V, E) with the minimum number of vertices having a degree strictly greater than d. In this context, the degree represents the number of adjacent edges to a vertex. We have developed an efficient Miller–Tucker–Zemlin based formulation with valid inequalities to address this problem.

Methodology

Our approach demonstrates effectiveness in solving instances of the d-MBV problem for various values of d. The proposed method, based on mathematical optimization, has proven to outperform previous methods, achieving faster solutions. Additionally, we introduce a heuristic specifically designed for the d-MBV problem, particularly when d equals 2.

Usage

To use this code, create an instance of the Graph class and add edges to represent the input graph. Then, create a Solver object with the graph and the desired value of d. Finally, call the solve_model() method to obtain the solution.

To add an instance using the given code, you can follow these steps:

1. Initialize a Graph Instance:

   # Create a Graph instance with 8 vertices
   graph = Graph(8)

2. Add Edges to the Graph:

   # Add edges to the graph using add_edge method
   graph.add_edge(0, 3)
   graph.add_edge(0, 1)
   graph.add_edge(0, 4)
   graph.add_edge(0, 6)
   graph.add_edge(0, 7)
   graph.add_edge(0, 2)
   graph.add_edge(0, 5)
   graph.add_edge(7, 5)
   graph.add_edge(2, 5)
   graph.add_edge(3, 1)
   graph.add_edge(4, 6)

   The above code adds edges to the graph, connecting the specified vertices.

Pseudocode - Main Program (main.py)

graph = Graph(8)
# Add edges to the graph

solver = Solver(graph, d=1)
solver.solve_model()

Pseudocode - Solver Module (solver.py)

class Solver:
    def __init__(self, graph: Graph, d: int):
        # Initialization code

    def solve_model(self):
        # Main algorithm to solve the d-MBV problem

    def solve_sub_graph(self, G: Graph):
        # Solve the d-MBV problem for a subgraph

    def solve_cutted_graph(self, G: Graph = None):
        # Solve the d-MBV problem for a cutted graph

    def resolve_mathematical_model(self, G: Graph):
        # Use mathematical optimization to solve the d-MBV problem

The code you provided implements a solver for the d-Minimum Branch Vertices (d-MBV) problem. Here's an explanation of how the mathematical model is called for each subgraph:

1. Initialization:

   • The Solver class is initialized with a graph (_instance) and the parameter d.
   • Various attributes like _time_solver, _num_oh, _num_on, _exact, and _solution are initialized.

2. Solving the Model:

   • The solve_model method is called to solve the d-MBV problem.
   • If there are no bridges in the graph (num_bridges == 0), the solve_cutted_graph method is called.
   • Otherwise, for each vertex, a subgraph is created without bridges, and the solve_cutted_graph method is called for this subgraph.

3. Subgraph Solver (solve_sub_graph):

   • This method is responsible for solving the d-MBV problem for subgraphs obtained by eliminating bridges from the original graph.
   • If the subgraph has no cut vertices (G.LCut_H is empty), the mathematical model is directly solved using resolve_mathematical_model.
   • Otherwise, for each cut vertex v, a new graph G2 is created by removing v. The connected components of this modified graph are obtained, and the solve_sub_graph method is recursively called for each component.

4. Applying Cuts and Resolving:

   • In the process of solving subgraphs, one cut vertex is removed, and the graph is resolved.
   • A copy of the original graph is made (G2), and modifications are applied to create a new graph (H).
   • The solve_sub_graph method is called recursively for the new graph (H).

5. Result Aggregation:

   • The results from each subgraph solution are aggregated, and the final solution and time are returned.

6. Mathematical Model Resolution (resolve_mathematical_model):

   • This method is responsible for creating and solving the mathematical model for a given graph using the Gurobi solver.
   • The model formulation involves adding variables, constraints, and creating an objective function.
   • The Gurobi solver is then used to optimize the model and obtain a solution.

In summary, the mathematical model is invoked for each subgraph created during the process of eliminating bridges from the original graph, providing solutions specific to each subgraph.

Dependencies

• Gurobi: The code relies on Gurobi for mathematical optimization. Make sure to have the Gurobi Python package installed.
• Dependencies are specified in the requirements.txt file. To install them, use the following command within your virtual environment:

pip install -r requirements.txt

Additional Information

The algorithm further decomposes the graph by considering articulation points. The number of connected components is increased by removing these points, leading to more effective solutions. The algorithm "SolveGraph" is designed to address the d-MBV problem for subgraphs obtained by eliminating bridges from the original graph G.

Pseudocode - Algorithm 1: SolveGraph

Input: A graph without bridges G = (V, E) and the value l(v) associated with each vertex v ∈ V and the set CutD.
Output: The optimal solution for the d-MBV problem

1. s ← 0
2. if CutD = ∅ then
3.    s ← SolveModel(G)
4. else
5.    Choose any v ∈ CutD and delete it from G
6.    Obtain the connected components Gk = (Vk, Ek) for k = 1,..., cG(v)
7.    Let Cut(k)D = CutD ∩ Vk for k = 1,..., cG(v)
8.    for k from 1 to cG(v) do
9.        /* create a copy of vertex v in each component k */
10.       Vk ← Vk ∪ {vk}
11.       Ek := Ek ∪ {{u, vk} | u ∈ Vk and {u, vk} ∈ E}
12.       l(vk) ← l(vk) + dG(v) - dGk(vk)
13.       s ← s + SolveGraph(Gk, Cut(k)D)
14.   s ← s - cG(v) + 1
15. return s

Melo et al. [11] demonstrated the decomposition of the graph considering articulation points (cutting vertices), which increases the number of connected components when removed.

Reference

For more details, refer to the work by Melo et al. [11].

Author

---

Feel free to customize the README to provide more details or include specific instructions as needed.