maths/operations_research/BranchAndBoundSolver.py

import cvxpy as cp
import numpy as np
import math
from queue import PriorityQueue
import networkx as nx
import matplotlib.pyplot as plt
from tabulate import tabulate
from scipy.optimize import linprog
import gradio as gr
from maths.operations_research.utils import parse_matrix
from maths.operations_research.utils import parse_vector


class BranchAndBoundSolver:
    def __init__(self, c, A, b, integer_vars=None, binary_vars=None, maximize=True):
        """
        Initialize the Branch and Bound solver
        
        Parameters:
        - c: Objective coefficients (for max c'x)
        - A, b: Constraints Ax <= b
        - integer_vars: Indices of variables that must be integers
        - binary_vars: Indices of variables that must be binary (0 or 1)
        - maximize: True for maximization, False for minimization
        
        Raises:
        - ValueError: If input dimensions are inconsistent or invalid indices provided
        - TypeError: If inputs are not numeric arrays
        """
        # Input validation
        if not hasattr(c, '__len__') or len(c) == 0:
            raise ValueError("Objective coefficients 'c' must be a non-empty array-like object")
        
        if not hasattr(A, 'shape') or A.size == 0:
            raise ValueError("Constraint matrix 'A' must be a non-empty 2D array")
        
        if not hasattr(b, '__len__') or len(b) == 0:
            raise ValueError("Constraint bounds 'b' must be a non-empty array-like object")
        
        # Convert inputs to numpy arrays for consistency
        try:
            self.c = np.asarray(c, dtype=float)
            self.A = np.asarray(A, dtype=float)
            self.b = np.asarray(b, dtype=float)
        except (ValueError, TypeError) as e:
            raise TypeError(f"All inputs must be convertible to numeric arrays: {e}")
        
        # Validate dimensions
        if self.A.ndim != 2:
            raise ValueError(f"Constraint matrix 'A' must be 2D, got {self.A.ndim}D")
        
        if self.c.ndim != 1:
            raise ValueError(f"Objective coefficients 'c' must be 1D, got {self.c.ndim}D")
        
        if self.b.ndim != 1:
            raise ValueError(f"Constraint bounds 'b' must be 1D, got {self.b.ndim}D")
        
        if self.A.shape[0] != len(self.b):
            raise ValueError(f"Number of rows in A ({self.A.shape[0]}) must match length of b ({len(self.b)})")
        
        if self.A.shape[1] != len(self.c):
            raise ValueError(f"Number of columns in A ({self.A.shape[1]}) must match length of c ({len(self.c)})")
        
        self.n = len(self.c)
        
        # Process binary and integer variables with validation
        self.binary_vars = [] if binary_vars is None else list(binary_vars)
        
        # Validate binary variable indices
        for idx in self.binary_vars:
            if not isinstance(idx, (int, np.integer)) or idx < 0 or idx >= self.n:
                raise ValueError(f"Binary variable index {idx} is invalid. Must be integer in range [0, {self.n-1}]")
        
        # If integer_vars not specified, assume all non-binary variables are integers
        if integer_vars is None:
            self.integer_vars = list(range(self.n))
        else:
            self.integer_vars = list(integer_vars)
            # Validate integer variable indices
            for idx in self.integer_vars:
                if not isinstance(idx, (int, np.integer)) or idx < 0 or idx >= self.n:
                    raise ValueError(f"Integer variable index {idx} is invalid. Must be integer in range [0, {self.n-1}]")
        
        # Add binary variables to integer variables list if they're not already there
        for idx in self.binary_vars:
            if idx not in self.integer_vars:
                self.integer_vars.append(idx)
        
        # Best solution found so far
        self.best_solution = None
        self.best_objective = float('-inf') if maximize else float('inf')
        self.maximize = maximize
        
        # Track nodes explored
        self.nodes_explored = 0
        
        # Graph for visualization
        self.graph = nx.DiGraph()
        self.node_id = 0
        
        # For tabular display of steps
        self.steps_table = []
        
        # Set of active nodes
        self.active_nodes = set()        # For logging messages
        self.log_messages = []

    def is_integer_feasible(self, x):
        """Check if the solution satisfies integer constraints
        
        Args:
            x: Solution vector to check
            
        Returns:
            bool: True if solution satisfies integer constraints, False otherwise
        """
        if x is None:
            return False
        
        try:
            for idx in self.integer_vars:
                if idx >= len(x):
                    raise IndexError(f"Integer variable index {idx} exceeds solution vector length {len(x)}")
                if abs(round(x[idx]) - x[idx]) > 1e-6:
                    return False
            return True
        except (IndexError, TypeError) as e:
            self.log_messages.append(f"Error checking integer feasibility: {e}")
            return False
    
    def get_branching_variable(self, x):
        """Select most fractional variable to branch on
        
        Args:
            x: Solution vector
            
        Returns:
            int: Index of variable to branch on, or -1 if no fractional variables found
        """
        if x is None:
            return -1
        
        max_fractional = -1
        branching_var = -1
        
        try:
            for idx in self.integer_vars:
                if idx >= len(x):
                    self.log_messages.append(f"Warning: Integer variable index {idx} exceeds solution vector length {len(x)}")
                    continue
                    
                fractional_part = abs(x[idx] - round(x[idx]))
                if fractional_part > max_fractional and fractional_part > 1e-6:
                    max_fractional = fractional_part
                    branching_var = idx
        except (IndexError, TypeError) as e:
            self.log_messages.append(f"Error finding branching variable: {e}")
            return -1
        
        return branching_var

    def solve_relaxation(self, lower_bounds, upper_bounds):
        """Solve the continuous relaxation with given bounds
        
        Args:
            lower_bounds: List of lower bounds for variables
            upper_bounds: List of upper bounds for variables
            
        Returns:
            tuple: (solution_vector, objective_value) or (None, inf/-inf) if infeasible
        """
        try:
            # Validate bounds
            if len(lower_bounds) != self.n or len(upper_bounds) != self.n:
                raise ValueError(f"Bounds must have length {self.n}, got {len(lower_bounds)}, {len(upper_bounds)}")
            
            x = cp.Variable(self.n)
            
            # Set the objective - maximize c'x or minimize -c'x
            if self.maximize:
                objective = cp.Maximize(self.c @ x)
            else:
                objective = cp.Minimize(self.c @ x)
            
            # Basic constraints Ax <= b
            constraints = [self.A @ x <= self.b]
            
            # Add bounds with validation
            for i in range(self.n):
                if lower_bounds[i] is not None:
                    if not np.isfinite(lower_bounds[i]):
                        raise ValueError(f"Lower bound for variable {i} must be finite, got {lower_bounds[i]}")
                    constraints.append(x[i] >= lower_bounds[i])
                if upper_bounds[i] is not None:
                    if not np.isfinite(upper_bounds[i]):
                        raise ValueError(f"Upper bound for variable {i} must be finite, got {upper_bounds[i]}")
                    constraints.append(x[i] <= upper_bounds[i])
                    
                # Check for contradictory bounds
                if (lower_bounds[i] is not None and upper_bounds[i] is not None and 
                    lower_bounds[i] > upper_bounds[i]):
                    self.log_messages.append(f"Warning: Contradictory bounds for variable {i}: [{lower_bounds[i]}, {upper_bounds[i]}]")
            
            prob = cp.Problem(objective, constraints)
            
            # Solve with error handling
            objective_value = prob.solve()
            
            # Check solver status
            if prob.status in ['infeasible', 'unbounded']:
                self.log_messages.append(f"Relaxation problem status: {prob.status}")
                return None, float('-inf') if self.maximize else float('inf')
            elif prob.status != 'optimal':
                self.log_messages.append(f"Relaxation solver warning: {prob.status}")
              # Validate solution
            if x.value is None:
                return None, float('-inf') if self.maximize else float('inf')
            
            # Check for numerical issues
            if not np.isfinite(objective_value):
                self.log_messages.append(f"Warning: Non-finite objective value: {objective_value}")
                return None, float('-inf') if self.maximize else float('inf')
            
            return x.value, objective_value
            
        except cp.error.SolverError as e:
            self.log_messages.append(f"CVXPY solver error: {e}")
            return None, float('-inf') if self.maximize else float('inf')
        except Exception as e:
            self.log_messages.append(f"Unexpected error in solve_relaxation: {e}")
            return None, float('-inf') if self.maximize else float('inf')

    def add_node_to_graph(self, node_name, objective_value, x_value, parent=None, branch_var=None, branch_cond=None):
        """Add a node to the branch and bound graph
        
        Args:
            node_name: Unique identifier for the node
            objective_value: Objective value at this node
            x_value: Solution vector at this node
            parent: Parent node name (for edges)
            branch_var: Variable being branched on
            branch_cond: Branching condition string
            
        Returns:
            str: The node name that was added
        """
        try:
            # Validate inputs
            if not isinstance(node_name, str):
                raise ValueError(f"Node name must be string, got {type(node_name)}")
            
            if objective_value is not None and not np.isfinite(objective_value):
                self.log_messages.append(f"Warning: Non-finite objective value for node {node_name}: {objective_value}")
            
            self.graph.add_node(node_name, obj=objective_value, x=x_value, 
                            branch_var=branch_var, branch_cond=branch_cond)
            
            if parent is not None:
                if parent not in self.graph.nodes:
                    self.log_messages.append(f"Warning: Parent node {parent} not found in graph")
                else:
                    # Use branch_var + 1 to show 1-indexed variables in the display                    if branch_var is not None and branch_cond is not None:
                        label = f"x_{branch_var + 1} {branch_cond}"
                        self.graph.add_edge(parent, node_name, label=label)
            
            return node_name
            
        except Exception as e:
            self.log_messages.append(f"Error adding node {node_name} to graph: {e}")
            return node_name  # Return the name even if there was an error

    def visualize_graph(self):
        """Visualize the branch and bound graph
        
        Returns:
            matplotlib.figure.Figure: The graph visualization figure
        """
        try:
            if len(self.graph.nodes) == 0:
                # Create empty plot if no nodes
                fig = plt.figure(figsize=(10, 6))
                plt.text(0.5, 0.5, 'No nodes to display', ha='center', va='center', transform=plt.gca().transAxes)
                plt.title("Branch and Bound Tree (Empty)", fontsize=14)
                plt.axis('off')
                return fig
            
            fig = plt.figure(figsize=(20, 8))
            
            # Use hierarchical layout if possible, fall back to spring layout
            try:
                pos = nx.nx_agraph.graphviz_layout(self.graph, prog='dot')
            except:
                try:
                    pos = nx.spring_layout(self.graph, k=3, iterations=50)
                except:
                    # Fallback to simple circular layout
                    pos = nx.circular_layout(self.graph)

            # Node labels: Node name, Objective value and solution
            labels = {}
            for node, data in self.graph.nodes(data=True):
                try:
                    if data.get('x') is not None and len(data['x']) > 0:
                        x_str = ', '.join([f"{x:.2f}" for x in data['x']])
                        obj_val = data.get('obj', 'N/A')
                        if isinstance(obj_val, (int, float)) and np.isfinite(obj_val):
                            labels[node] = f"{node}\n({obj_val:.2f}, ({x_str}))"
                        else:
                            labels[node] = f"{node}\n(N/A, ({x_str}))"
                    else:
                        labels[node] = f"{node}\nInfeasible"
                except Exception as e:
                    labels[node] = f"{node}\nError: {str(e)[:20]}..."
            
            # Edge labels: Branching conditions
            edge_labels = nx.get_edge_attributes(self.graph, 'label')
            
            # Draw components with error handling
            try:
                nx.draw_networkx_nodes(self.graph, pos, node_size=2000, node_color='skyblue')
            except Exception as e:
                self.log_messages.append(f"Warning: Could not draw nodes: {e}")
            
            try:
                nx.draw_networkx_edges(self.graph, pos, width=1.5, arrowsize=20, edge_color='gray')
            except Exception as e:
                self.log_messages.append(f"Warning: Could not draw edges: {e}")
            
            try:
                nx.draw_networkx_labels(self.graph, pos, labels, font_size=10, font_family='sans-serif')
            except Exception as e:
                self.log_messages.append(f"Warning: Could not draw node labels: {e}")
            
            try:
                nx.draw_networkx_edge_labels(self.graph, pos, edge_labels=edge_labels, 
                                           font_size=10, font_family='sans-serif')
            except Exception as e:
                self.log_messages.append(f"Warning: Could not draw edge labels: {e}")
            
            plt.title("Branch and Bound Tree", fontsize=14)
            plt.axis('off')
            plt.tight_layout()
            return fig
            
        except Exception as e:
            self.log_messages.append(f"Error creating graph visualization: {e}")
            # Return a simple error plot
            fig = plt.figure(figsize=(10, 6))
            plt.text(0.5, 0.5, f'Error creating visualization:\n{str(e)}', 
                    ha='center', va='center', transform=plt.gca().transAxes)
            plt.title("Branch and Bound Tree (Error)", fontsize=14)
            plt.axis('off')
            return fig

    def display_steps_table(self):
        """Display the steps in tabular format
          Returns:
            str: Formatted table string
        """
        try:
            if not self.steps_table:
                return "No steps recorded."
            
            headers = ["Node", "z", "x", "z*", "x*", "UB", "LB", "Z at end of stage"]
            return tabulate(self.steps_table, headers=headers, tablefmt="grid")
        except Exception as e:
            self.log_messages.append(f"Error creating steps table: {e}")
            return f"Error displaying steps table: {e}"

    def solve(self, verbose=True, max_iterations=1000):
        """Solve the problem using branch and bound
        
        Args:
            verbose: Whether to log detailed information
            max_iterations: Maximum number of iterations to prevent infinite loops
            
        Returns:
            tuple: (best_solution, best_objective, log_messages, visualization_figure)
        """
        self.log_messages = []  # Initialize log for this run
        
        try:
            # Initialize bounds with validation
            lower_bounds = [0.0] * self.n
            upper_bounds = [None] * self.n  # None means unbounded
            
            # Set upper bounds for binary variables
            for idx in self.binary_vars:
                if idx < len(upper_bounds):
                    upper_bounds[idx] = 1.0
                else:
                    raise IndexError(f"Binary variable index {idx} exceeds problem dimension {self.n}")
            
            # Create a priority queue for nodes
            node_queue = PriorityQueue()
            iteration_count = 0
            
            # Solve the root relaxation
            self.log_messages.append("Step 1: Solving root relaxation (continuous problem)")
            
            try:
                x_root, obj_root = self.solve_relaxation(lower_bounds, upper_bounds)
            except Exception as e:
                self.log_messages.append(f"Error solving root relaxation: {e}")
                fig = self.visualize_graph()
                return None, float('-inf') if self.maximize else float('inf'), self.log_messages, fig
            
            if x_root is None:
                self.log_messages.append("Root problem infeasible")
                fig = self.visualize_graph()
                return None, float('-inf') if self.maximize else float('inf'), self.log_messages, fig
            
            # Add root node to the graph
            root_node = "S0"
            self.add_node_to_graph(root_node, obj_root, x_root)
            
            self.log_messages.append(f"Root relaxation objective: {obj_root:.6f}")
            self.log_messages.append(f"Root solution: {x_root}")
            
            # Initial upper bound is the root objective
            upper_bound = obj_root
            
            # Check if the root solution is already integer-feasible
            if self.is_integer_feasible(x_root):
                self.log_messages.append("Root solution is integer-feasible! No need for branching.")
                self.best_solution = x_root.copy()
                self.best_objective = obj_root
                
                # Add to steps table
                try:
                    active_nodes_str = "∅" if not self.active_nodes else "{" + ", ".join(self.active_nodes) + "}"
                    self.steps_table.append([
                        root_node, f"{obj_root:.2f}", f"({', '.join([f'{x:.2f}' for x in x_root])})", 
                        f"{self.best_objective:.2f}", f"({', '.join([f'{x:.2f}' for x in self.best_solution])})",
                        f"{upper_bound:.2f}", f"{self.best_objective:.2f}", active_nodes_str
                    ])
                except Exception as e:
                    self.log_messages.append(f"Error updating steps table: {e}")
                
                steps_table_string = self.display_steps_table()
                self.log_messages.append(steps_table_string)
                fig = self.visualize_graph()
                return self.best_solution, self.best_objective, self.log_messages, fig
            
            # Add root node to the queue and active nodes set
            priority = -obj_root if self.maximize else obj_root
            node_queue.put((priority, self.nodes_explored, root_node, lower_bounds.copy(), upper_bounds.copy()))
            self.active_nodes.add(root_node)
            
            # Add entry to steps table for root node
            try:
                active_nodes_str = "{" + ", ".join(self.active_nodes) + "}"
                lb_str = "-" if self.best_objective == float('-inf') else f"{self.best_objective:.2f}"
                x_star_str = "-" if self.best_solution is None else f"({', '.join([f'{x:.2f}' for x in self.best_solution])})"
                
                self.steps_table.append([
                    root_node, f"{obj_root:.2f}", f"({', '.join([f'{x:.2f}' for x in x_root])})",
                    lb_str, x_star_str, f"{upper_bound:.2f}", lb_str, active_nodes_str
                ])
            except Exception as e:
                self.log_messages.append(f"Error updating initial steps table: {e}")
            
            self.log_messages.append("\nStarting branch and bound process:")
            node_counter = 1
            
            while not node_queue.empty() and iteration_count < max_iterations:
                iteration_count += 1
                
                try:
                    # Get the node with the highest objective (for maximization)
                    priority, _, node_name, node_lower_bounds, node_upper_bounds = node_queue.get()
                    self.nodes_explored += 1
                    
                    self.log_messages.append(f"\nStep {self.nodes_explored + 1}: Exploring node {node_name}")
                    
                    # Remove from active nodes
                    if node_name in self.active_nodes:
                        self.active_nodes.remove(node_name)
                    
                    # Branch on most fractional variable
                    if node_name not in self.graph.nodes:
                        self.log_messages.append(f"Warning: Node {node_name} not found in graph")
                        continue
                        
                    current_solution = self.graph.nodes[node_name].get('x')
                    if current_solution is None:
                        self.log_messages.append(f"Warning: No solution found for node {node_name}")
                        continue
                    
                    branch_var = self.get_branching_variable(current_solution)
                    if branch_var == -1:
                        self.log_messages.append(f"Warning: No branching variable found for node {node_name}")
                        continue
                        
                    branch_val = current_solution[branch_var]
                    
                    # Process branches with enhanced error handling
                    self._process_branches(node_name, branch_var, branch_val, node_lower_bounds, 
                                         node_upper_bounds, node_queue, node_counter)
                    node_counter += 2  # Two new nodes created
                    
                    # Update upper bound
                    if not node_queue.empty():
                        next_priority = node_queue.queue[0][0]
                        upper_bound = -next_priority if self.maximize else next_priority
                    else:
                        upper_bound = self.best_objective
                    
                    # Add to steps table
                    self._add_step_to_table(node_name, upper_bound)
                    
                except Exception as e:
                    self.log_messages.append(f"Error processing node {node_name if 'node_name' in locals() else 'unknown'}: {e}")
                    continue
            
            # Check for max iterations exceeded
            if iteration_count >= max_iterations:
                self.log_messages.append(f"Warning: Maximum iterations ({max_iterations}) reached. Solution may not be optimal.")
            
            self.log_messages.append("\nBranch and bound completed!")
            self.log_messages.append(f"Nodes explored: {self.nodes_explored}")
            self.log_messages.append(f"Iterations: {iteration_count}")
            
            if self.best_solution is not None:
                self.log_messages.append(f"Optimal objective: {self.best_objective:.6f}")
                self.log_messages.append(f"Optimal solution: {self.best_solution}")
            else:
                self.log_messages.append("No feasible integer solution found")
            
            # Append steps table string to log
            steps_table_string = self.display_steps_table()
            self.log_messages.append(steps_table_string)
            
            # Visualize the graph
            fig = self.visualize_graph()
            
            return self.best_solution, self.best_objective, self.log_messages, fig
            
        except Exception as e:
            self.log_messages.append(f"Critical error in solve method: {e}")
            fig = self.visualize_graph()
            return None, float('-inf') if self.maximize else float('inf'), self.log_messages, fig


def solve_branch_and_bound_interface(c_str, A_str, b_str, integer_vars_str, binary_vars_str, maximize_bool):
    """
    Enhanced wrapper function to connect BranchAndBoundSolver with Gradio interface.
    Provides comprehensive input validation, error handling, and user-friendly error messages.
    """
    log_messages = []
    
    try:
        # Enhanced input validation with detailed error messages
        log_messages.append("Starting input validation...")
        
        # Validate and parse objective coefficients
        if not c_str or not c_str.strip():
            log_messages.append("Error: Objective coefficients (c) cannot be empty. Please provide comma-separated values (e.g., '3,2').")
            return "Error: Empty objective coefficients", "Error: Invalid input", "\n".join(log_messages), None
            
        try:
            c = parse_vector(c_str)
            if not c or len(c) == 0:
                log_messages.append("Error: Objective coefficients (c) could not be parsed or resulted in empty vector.")
                log_messages.append("Please ensure format is comma-separated numbers (e.g., '3,2,1').")
                return "Error parsing c", "Error parsing c", "\n".join(log_messages), None
        except Exception as e:
            log_messages.append(f"Error parsing objective coefficients (c): {str(e)}")
            log_messages.append("Expected format: comma-separated numbers (e.g., '3,2,1')")
            return "Error parsing c", "Error parsing c", "\n".join(log_messages), None

        # Validate and parse constraint matrix
        if not A_str or not A_str.strip():
            log_messages.append("Error: Constraint matrix (A) cannot be empty. Please provide semicolon-separated rows with comma-separated values.")
            log_messages.append("Example format: '1,2;3,4' for a 2x2 matrix.")
            return "Error: Empty constraint matrix", "Error: Invalid input", "\n".join(log_messages), None
            
        try:
            A = parse_matrix(A_str)
            if A.size == 0:
                log_messages.append("Error: Constraint matrix (A) could not be parsed or is empty.")
                log_messages.append("Expected format: rows separated by ';', elements by ',' (e.g., '1,2;3,4')")
                return "Error parsing A", "Error parsing A", "\n".join(log_messages), None
        except Exception as e:
            log_messages.append(f"Error parsing constraint matrix (A): {str(e)}")
            log_messages.append("Expected format: rows separated by ';', elements by ',' (e.g., '1,2;3,4')")
            return "Error parsing A", "Error parsing A", "\n".join(log_messages), None

        # Validate and parse constraint bounds
        if not b_str or not b_str.strip():
            log_messages.append("Error: Constraint bounds (b) cannot be empty. Please provide comma-separated values.")
            log_messages.append("Example format: '10,8,3' for three constraints.")
            return "Error: Empty constraint bounds", "Error: Invalid input", "\n".join(log_messages), None
            
        try:
            b = parse_vector(b_str)
            if not b or len(b) == 0:
                log_messages.append("Error: Constraint bounds (b) could not be parsed or resulted in empty vector.")
                log_messages.append("Expected format: comma-separated numbers (e.g., '10,8,3')")
                return "Error parsing b", "Error parsing b", "\n".join(log_messages), None
        except Exception as e:
            log_messages.append(f"Error parsing constraint bounds (b): {str(e)}")
            log_messages.append("Expected format: comma-separated numbers (e.g., '10,8,3')")
            return "Error parsing b", "Error parsing b", "\n".join(log_messages), None

        # Enhanced dimension validation
        if A.shape[0] != len(b):
            log_messages.append(f"Error: Dimension mismatch between constraints matrix and bounds.")
            log_messages.append(f"Matrix A has {A.shape[0]} rows but vector b has {len(b)} elements.")
            log_messages.append("Each row in A represents one constraint, so A and b must have matching dimensions.")
            return "Dimension mismatch A vs b", "Dimension mismatch A vs b", "\n".join(log_messages), None
            
        if A.shape[1] != len(c):
            log_messages.append(f"Error: Dimension mismatch between objective and constraints.")
            log_messages.append(f"Matrix A has {A.shape[1]} columns but objective vector c has {len(c)} elements.")
            log_messages.append("Each column in A represents one variable, so A and c must have matching dimensions.")
            return "Dimension mismatch A vs c", "Dimension mismatch A vs c", "\n".join(log_messages), None

        # Enhanced integer variables parsing with better error handling
        integer_vars = []
        if integer_vars_str and integer_vars_str.strip():
            try:
                # Handle special case for "all"
                if integer_vars_str.strip().lower() == "all":
                    integer_vars = list(range(len(c)))
                    log_messages.append(f"All {len(c)} variables set as integer variables.")
                else:
                    integer_vars = [int(x.strip()) for x in integer_vars_str.split(',') if x.strip()]
                    if not integer_vars:
                        log_messages.append("Warning: Integer variables string provided but no valid indices found.")
                    elif not all(0 <= i < len(c) for i in integer_vars):
                        invalid_indices = [i for i in integer_vars if not (0 <= i < len(c))]
                        log_messages.append(f"Error: Integer variable indices out of bounds: {invalid_indices}")
                        log_messages.append(f"Valid range is 0 to {len(c)-1} (0-indexed).")
                        return "Error: Invalid integer variable indices", "Error: Invalid input", "\n".join(log_messages), None
                    elif len(set(integer_vars)) != len(integer_vars):
                        duplicates = [i for i in set(integer_vars) if integer_vars.count(i) > 1]
                        log_messages.append(f"Warning: Duplicate integer variable indices found: {duplicates}. Removing duplicates.")
                        integer_vars = list(set(integer_vars))
            except ValueError as e:
                log_messages.append(f"Error parsing integer variable indices: {str(e)}")
                log_messages.append("Please use comma-separated 0-indexed integers (e.g., '0,1,2') or 'all' for all variables.")
                return "Error parsing integer_vars", "Error parsing integer_vars", "\n".join(log_messages), None

        # Enhanced binary variables parsing with better error handling
        binary_vars = []
        if binary_vars_str and binary_vars_str.strip():
            try:
                binary_vars = [int(x.strip()) for x in binary_vars_str.split(',') if x.strip()]
                if not binary_vars:
                    log_messages.append("Warning: Binary variables string provided but no valid indices found.")
                elif not all(0 <= i < len(c) for i in binary_vars):
                    invalid_indices = [i for i in binary_vars if not (0 <= i < len(c))]
                    log_messages.append(f"Error: Binary variable indices out of bounds: {invalid_indices}")
                    log_messages.append(f"Valid range is 0 to {len(c)-1} (0-indexed).")
                    return "Error: Invalid binary variable indices", "Error: Invalid input", "\n".join(log_messages), None
                elif len(set(binary_vars)) != len(binary_vars):
                    duplicates = [i for i in set(binary_vars) if binary_vars.count(i) > 1]
                    log_messages.append(f"Warning: Duplicate binary variable indices found: {duplicates}. Removing duplicates.")
                    binary_vars = list(set(binary_vars))
            except ValueError as e:
                log_messages.append(f"Error parsing binary variable indices: {str(e)}")
                log_messages.append("Please use comma-separated 0-indexed integers (e.g., '0,1,2').")
                return "Error parsing binary_vars", "Error parsing binary_vars", "\n".join(log_messages), None

        # Check for overlap between integer and binary variables
        if integer_vars and binary_vars:
            overlap = set(integer_vars) & set(binary_vars)
            if overlap:
                log_messages.append(f"Warning: Variables {list(overlap)} are specified as both integer and binary.")
                log_messages.append("Binary variables are automatically treated as integer. Removing from integer list.")
                integer_vars = [i for i in integer_vars if i not in overlap]

        # Log successful parsing
        log_messages.append("✓ Input validation completed successfully.")
        log_messages.append(f"✓ Problem size: {len(c)} variables, {A.shape[0]} constraints")
        if integer_vars:
            log_messages.append(f"✓ Integer variables: {integer_vars}")
        if binary_vars:
            log_messages.append(f"✓ Binary variables: {binary_vars}")
        log_messages.append(f"✓ Optimization direction: {'Maximize' if maximize_bool else 'Minimize'}")
        log_messages.append("Starting solver...")

        # Create solver with enhanced error handling
        try:
            solver = BranchAndBoundSolver(
                c=np.array(c), 
                A=A, 
                b=np.array(b),
                integer_vars=integer_vars if integer_vars else None,
                binary_vars=binary_vars if binary_vars else None,
                maximize=maximize_bool
            )
        except Exception as e:
            log_messages.append(f"Error creating solver instance: {str(e)}")
            log_messages.append("This could indicate incompatible problem dimensions or invalid parameter values.")
            return "Solver creation error", "Solver creation error", "\n".join(log_messages), None

        # Solve with enhanced error handling
        try:
            best_solution, best_objective, solver_log, fig = solver.solve()
            log_messages.extend(solver_log)  # Add solver's internal log
        except Exception as e:
            log_messages.append(f"Error during solving: {str(e)}")
            log_messages.append("The solver encountered an unexpected error. Check input validity and problem formulation.")
            # Try to get partial results
            try:
                fig = solver.visualize_graph() if hasattr(solver, 'visualize_graph') else None
            except:
                fig = None
            return "Solver execution error", "Solver execution error", "\n".join(log_messages), fig

        # Enhanced result formatting with better error handling
        try:
            if best_solution is not None:
                solution_str = ", ".join([f"{val:.6f}" for val in best_solution])
                objective_str = f"{best_objective:.6f}"
                log_messages.append(f"✓ Optimal solution found: x = ({solution_str})")
                log_messages.append(f"✓ Optimal objective value: {objective_str}")
            else:
                solution_str = "No feasible integer solution found."
                if best_objective == float('-inf'):
                    objective_str = "Unbounded (maximization)"
                    log_messages.append("Problem appears to be unbounded for maximization.")
                elif best_objective == float('inf'):
                    objective_str = "Unbounded (minimization)" 
                    log_messages.append("Problem appears to be unbounded for minimization.")
                else:
                    objective_str = "Infeasible"
                    log_messages.append("No feasible solution exists for the given constraints.")
        except Exception as e:
            log_messages.append(f"Error formatting results: {str(e)}")
            solution_str = "Result formatting error"
            objective_str = "Result formatting error"

        return solution_str, objective_str, "\n".join(log_messages), fig

    except Exception as e:
        # Catch-all error handler for unexpected exceptions
        log_messages.append(f"Unexpected error in interface function: {str(e)}")
        log_messages.append("Please check your input format and try again.")
        log_messages.append("If the problem persists, there may be an issue with the solver implementation.")
        return "Unexpected error", "Unexpected error", "\n".join(log_messages), None


branch_and_bound_interface = gr.Interface(
    fn=solve_branch_and_bound_interface,
    inputs=[
        gr.Textbox(label="Objective Coefficients (c)", info="Comma-separated, e.g., 3,2"),
        gr.Textbox(label="Constraint Matrix (A)", info="Rows separated by ';', elements by ',', e.g., 2,1; 1,1; 1,0"),
        gr.Textbox(label="Constraint RHS (b)", info="Comma-separated, e.g., 10,8,3. Must be Ax <= b form."),
        gr.Textbox(label="Integer Variable Indices (optional)", info="Comma-separated, 0-indexed. If empty and no binary vars, all vars are continuous for B&B (effectively LP). If empty but binary vars exist, only binary are integer. If 'all', all vars are integer."), # Adjusted info
        gr.Textbox(label="Binary Variable Indices (optional)", info="Comma-separated, 0-indexed, e.g., 0,1"),
        gr.Checkbox(label="Maximize?", value=True)
    ],
    outputs=[
        gr.Textbox(label="Optimal Solution (x)"),
        gr.Textbox(label="Optimal Objective Value (z)"),
        gr.Textbox(label="Solver Log and Steps", lines=15, interactive=False),
        gr.Plot(label="Branch and Bound Tree")
    ],
    title="Branch and Bound Solver for Mixed Integer Linear Programs (MILP)",
    description="Solves MILPs (Ax <= b) using the Branch and Bound method. Specify integer/binary variables or leave empty if not applicable (for pure LP).",
    examples=[
        [ # Example 1: Knapsack-like problem (from a common example)
            "8,11,6,4", # c: Objective (maximize)
            "5,7,4,3; 1,1,1,1", # A: Constraints matrix
            "14, 4", # b: Constraints RHS
            "", # integer_vars: all variables are effectively integer due to binary constraint if specified, or by default if integer_vars=None
            "0,1,2,3", # binary_vars: All variables are binary
            True # Maximize
        ],
        [ # Example 2: Simple MILP
            "3,2,4", # c
            "1,1,1; 2,1,0", # A
            "10,5", # b
            "0,2", # integer_vars: x0 and x2 are integer
            "", # binary_vars
            True # Maximize
        ],
        [ # Example 3: Minimization problem (from a common example)
            "3,5", # c (minimize)
            "-1,0; 0,-1; 3,2", # A (original constraints might be >=, converted to <= by multiplying with -1)
            "0,0,18", # b (original might be >=0, >=0, <=18. For >=0, we write -x <= 0)
            "0,1", # integer_vars
            "", # binary_vars
            False # Minimize
        ],
         [ # Example 4: Provided in task description
            "5,4", #c
            "1,1;2,0;0,1", #A
            "5,6,3", #b
            "0,1", #integer
            "", #binary
            True #maximize
        ]
    ],
    flagging_mode="manual"
)