Spaces:
Runtime error
Runtime error
| 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" | |
| ) | |