Spaces:
Runtime error
Runtime error
| import numpy as np | |
| import sys | |
| from .solve_lp_via_dual import solve_lp_via_dual | |
| from .solve_primal_directly import solve_primal_directly | |
| import gradio as gr | |
| from maths.operations_research.utils import parse_matrix | |
| from maths.operations_research.utils import parse_vector | |
| def parse_relations(input_str: str) -> list[str]: | |
| """Parses a comma-separated string of relations into a list of strings.""" | |
| if not input_str: | |
| return [] | |
| try: | |
| relations = [r.strip() for r in input_str.split(',')] | |
| valid_relations = {"<=", ">=", "="} | |
| if not all(r in valid_relations for r in relations): | |
| invalid_rels = [r for r in relations if r not in valid_relations] | |
| gr.Warning(f"Invalid relation(s) found: {', '.join(invalid_rels)}. Allowed relations are: '<=', '>=', '='.") | |
| return [] | |
| return relations | |
| except Exception as e: # Catch any other unexpected errors during parsing | |
| gr.Warning(f"Error parsing relations: '{input_str}'. Error: {e}") | |
| return [] | |
| TOLERANCE = 1e-9 | |
| class DualSimplexSolver: | |
| """ | |
| Solves a Linear Programming problem using the Dual Simplex Method. | |
| Assumes the problem is provided in the form: | |
| Maximize/Minimize c^T * x | |
| Subject to: | |
| A * x <= / >= / = b | |
| x >= 0 | |
| The algorithm works best when the initial tableau (after converting all | |
| constraints to <=) is dual feasible (objective row coefficients >= 0 for Max) | |
| but primal infeasible (some RHS values are negative). | |
| """ | |
| def __init__(self, objective_type, c, A, relations, b): | |
| """ | |
| Initializes the solver. | |
| Args: | |
| objective_type (str): 'max' or 'min'. | |
| c (list or np.array): Coefficients of the objective function. | |
| A (list of lists or np.array): Coefficients of the constraints LHS. | |
| relations (list): List of strings ('<=', '>=', '=') for each constraint. | |
| b (list or np.array): RHS values of the constraints. | |
| """ | |
| self.objective_type = objective_type.lower() | |
| self.original_c = np.array(c, dtype=float) | |
| self.original_A = np.array(A, dtype=float) | |
| self.original_relations = relations | |
| self.original_b = np.array(b, dtype=float) | |
| self.num_original_vars = len(c) | |
| self.num_constraints = len(b) | |
| self.tableau = None | |
| self.basic_vars = [] # Indices of basic variables (column index) | |
| self.var_names = [] # Names like 'x1', 's1', etc. | |
| self.is_minimized_problem = False # Flag to adjust final Z | |
| self.log_messages = [] | |
| self._preprocess() | |
| def _preprocess(self): | |
| """ | |
| Converts the problem to the standard form for Dual Simplex: | |
| - Maximization objective | |
| - All constraints are <= | |
| - Adds slack variables | |
| - Builds the initial tableau | |
| """ | |
| # --- 1. Handle Objective Function --- | |
| if self.objective_type == 'min': | |
| self.is_minimized_problem = True | |
| current_c = -self.original_c | |
| else: | |
| current_c = self.original_c | |
| # --- 2. Handle Constraints and Slack Variables --- | |
| num_slacks_added = 0 | |
| processed_A = [] | |
| processed_b = [] | |
| self.basic_vars = [] # Will store column indices of basic vars | |
| # Create variable names | |
| self.var_names = [f'x{i+1}' for i in range(self.num_original_vars)] | |
| slack_var_names = [] | |
| for i in range(self.num_constraints): | |
| A_row = self.original_A[i] | |
| b_val = self.original_b[i] | |
| relation = self.original_relations[i] | |
| if relation == '>=': | |
| # Multiply by -1 to convert to <= | |
| processed_A.append(-A_row) | |
| processed_b.append(-b_val) | |
| elif relation == '=': | |
| # Convert Ax = b into Ax <= b and Ax >= b | |
| # First: Ax <= b | |
| processed_A.append(A_row) | |
| processed_b.append(b_val) | |
| # Second: Ax >= b --> -Ax <= -b | |
| processed_A.append(-A_row) | |
| processed_b.append(-b_val) | |
| elif relation == '<=': | |
| processed_A.append(A_row) | |
| processed_b.append(b_val) | |
| else: | |
| raise ValueError(f"Invalid relation symbol: {relation}") | |
| # Update number of effective constraints after handling '=' | |
| effective_num_constraints = len(processed_b) | |
| # Add slack variables for all processed constraints (which are now all <=) | |
| num_slack_vars = effective_num_constraints | |
| final_A = np.zeros((effective_num_constraints, self.num_original_vars + num_slack_vars)) | |
| final_b = np.array(processed_b, dtype=float) | |
| # Populate original variable coefficients | |
| final_A[:, :self.num_original_vars] = np.array(processed_A, dtype=float) | |
| # Add slack variable identity matrix part and names | |
| for i in range(effective_num_constraints): | |
| slack_col_index = self.num_original_vars + i | |
| final_A[i, slack_col_index] = 1 | |
| slack_var_names.append(f's{i+1}') | |
| self.basic_vars.append(slack_col_index) # Initially, slacks are basic | |
| self.var_names.extend(slack_var_names) | |
| # --- 3. Build the Tableau --- | |
| num_total_vars = self.num_original_vars + num_slack_vars | |
| # Rows: 1 for objective + number of constraints | |
| # Cols: 1 for Z + number of total vars + 1 for RHS | |
| self.tableau = np.zeros((effective_num_constraints + 1, num_total_vars + 2)) | |
| # Row 0 (Objective Z): [1, -c, 0_slacks, 0_rhs] | |
| self.tableau[0, 0] = 1 # Z coefficient | |
| self.tableau[0, 1:self.num_original_vars + 1] = -current_c | |
| # Slack coefficients in objective are 0 initially | |
| # RHS of objective row is 0 initially | |
| # Rows 1 to m (Constraints): [0, A_final, b_final] | |
| self.tableau[1:, 1:num_total_vars + 1] = final_A | |
| self.tableau[1:, -1] = final_b | |
| # Ensure the initial objective row is dual feasible (non-negative coeffs for Max) | |
| # We rely on the user providing a problem where this holds after conversion. | |
| if np.any(self.tableau[0, 1:-1] < -TOLERANCE): | |
| self.log_messages.append("\nWarning: Initial tableau is not dual feasible (objective row has negative coefficients).") | |
| self.log_messages.append("The standard Dual Simplex method might not apply directly or may require Phase I.") | |
| # For this implementation, we'll proceed, but it might fail if assumption is violated. | |
| def _print_tableau(self, iteration): | |
| """Formats the current state of the tableau into a string.""" | |
| tableau_str_lines = [] | |
| tableau_str_lines.append(f"\n--- Iteration {iteration} ---") | |
| header = ["BV"] + ["Z"] + self.var_names + ["RHS"] | |
| tableau_str_lines.append(" ".join(f"{h:>8}" for h in header)) | |
| tableau_str_lines.append("-" * (len(header) * 9)) | |
| basic_var_map = {idx: name for idx, name in enumerate(self.var_names)} | |
| row_basic_vars = ["Z"] + [basic_var_map.get(bv_idx, f'col{bv_idx}') for bv_idx in self.basic_vars] | |
| for i, row_bv_name in enumerate(row_basic_vars): | |
| row_str_parts = [f"{row_bv_name:>8}"] | |
| row_str_parts.extend([f"{val: >8.3f}" for val in self.tableau[i]]) | |
| tableau_str_lines.append(" ".join(row_str_parts)) | |
| tableau_str_lines.append("-" * (len(header) * 9)) | |
| return "\n".join(tableau_str_lines) | |
| def _find_pivot_row(self): | |
| """Finds the index of the leaving variable (pivot row).""" | |
| rhs_values = self.tableau[1:, -1] | |
| # Find the index of the most negative RHS value (among constraints) | |
| if np.all(rhs_values >= -TOLERANCE): | |
| return -1 # All RHS non-negative, current solution is feasible (and optimal) | |
| pivot_row_index = np.argmin(rhs_values) + 1 # +1 because we skip obj row 0 | |
| # Check if the minimum value is actually negative | |
| if self.tableau[pivot_row_index, -1] >= -TOLERANCE: | |
| return -1 # Should not happen if np.all check passed, but safety check | |
| self.log_messages.append(f"\nStep: Select Pivot Row (Leaving Variable)") | |
| self.log_messages.append(f" RHS values (b): {rhs_values}") | |
| leaving_var_idx = self.basic_vars[pivot_row_index - 1] | |
| leaving_var_name = self.var_names[leaving_var_idx] | |
| self.log_messages.append(f" Most negative RHS is {self.tableau[pivot_row_index, -1]:.3f} in Row {pivot_row_index} (Basic Var: {leaving_var_name}).") | |
| self.log_messages.append(f" Leaving Variable: {leaving_var_name} (Row {pivot_row_index})") | |
| return pivot_row_index | |
| def _find_pivot_col(self, pivot_row_index): | |
| """Finds the index of the entering variable (pivot column).""" | |
| pivot_row = self.tableau[pivot_row_index, 1:-1] # Exclude Z and RHS cols | |
| objective_row = self.tableau[0, 1:-1] # Exclude Z and RHS cols | |
| ratios = {} | |
| min_ratio = float('inf') | |
| pivot_col_index = -1 | |
| self.log_messages.append(f"\nStep: Select Pivot Column (Entering Variable) using Ratio Test") | |
| self.log_messages.append(f" Pivot Row (Row {pivot_row_index}) coefficients (excluding Z, RHS): {pivot_row}") | |
| self.log_messages.append(f" Objective Row coefficients (excluding Z, RHS): {objective_row}") | |
| self.log_messages.append(f" Calculating ratios = ObjCoeff / abs(PivotRowCoeff) for PivotRowCoeff < 0:") | |
| found_negative_coeff = False | |
| for j, coeff in enumerate(pivot_row): | |
| col_var_index = j # This is the index within the var_names list | |
| col_tableau_index = j + 1 # This is the index in the full tableau row | |
| if coeff < -TOLERANCE: # Must be strictly negative | |
| found_negative_coeff = True | |
| obj_coeff = objective_row[j] | |
| ratio = obj_coeff / (-coeff) | |
| ratios[col_var_index] = ratio | |
| self.log_messages.append(f" Var {self.var_names[col_var_index]} (Col {col_tableau_index}): Coeff={coeff:.3f}, ObjCoeff={obj_coeff:.3f}, Ratio = {obj_coeff:.3f} / {-coeff:.3f} = {ratio:.3f}") | |
| if ratio < min_ratio: | |
| min_ratio = ratio | |
| pivot_col_index = col_tableau_index | |
| if not found_negative_coeff: | |
| self.log_messages.append(" No negative coefficients found in the pivot row.") | |
| return -1 | |
| min_ratio_vars = [idx for idx, r in ratios.items() if abs(r - min_ratio) < TOLERANCE] | |
| if len(min_ratio_vars) > 1: | |
| self.log_messages.append(f" Tie detected for minimum ratio ({min_ratio:.3f}) among variables: {[self.var_names[idx] for idx in min_ratio_vars]}.") | |
| pivot_col_index = min(min_ratio_vars) + 1 | |
| self.log_messages.append(f" Applying Bland's rule: Choosing variable with smallest index: {self.var_names[pivot_col_index - 1]}.") | |
| elif pivot_col_index != -1: | |
| entering_var_name = self.var_names[pivot_col_index - 1] | |
| self.log_messages.append(f" Minimum ratio is {min_ratio:.3f} for variable {entering_var_name} (Column {pivot_col_index}).") | |
| self.log_messages.append(f" Entering Variable: {entering_var_name} (Column {pivot_col_index})") | |
| else: | |
| self.log_messages.append("Error in ratio calculation or tie-breaking.") | |
| return -2 | |
| return pivot_col_index | |
| def _pivot(self, pivot_row_index, pivot_col_index): | |
| """Performs the pivot operation.""" | |
| pivot_element = self.tableau[pivot_row_index, pivot_col_index] | |
| self.log_messages.append(f"\nStep: Pivot Operation") | |
| self.log_messages.append(f" Pivot Element: {pivot_element:.3f} at (Row {pivot_row_index}, Col {pivot_col_index})") | |
| if abs(pivot_element) < TOLERANCE: | |
| self.log_messages.append("Error: Pivot element is zero. Cannot proceed.") | |
| raise ZeroDivisionError("Pivot element is too close to zero.") | |
| self.log_messages.append(f" Normalizing Pivot Row {pivot_row_index} by dividing by {pivot_element:.3f}") | |
| self.tableau[pivot_row_index, :] /= pivot_element | |
| self.log_messages.append(f" Eliminating other entries in Pivot Column {pivot_col_index}:") | |
| for i in range(self.tableau.shape[0]): | |
| if i != pivot_row_index: | |
| factor = self.tableau[i, pivot_col_index] | |
| if abs(factor) > TOLERANCE: | |
| self.log_messages.append(f" Row {i} = Row {i} - ({factor:.3f}) * (New Row {pivot_row_index})") | |
| self.tableau[i, :] -= factor * self.tableau[pivot_row_index, :] | |
| old_basic_var_index = self.basic_vars[pivot_row_index - 1] | |
| new_basic_var_index = pivot_col_index - 1 | |
| self.basic_vars[pivot_row_index - 1] = new_basic_var_index | |
| self.log_messages.append(f" Updating Basic Variables: {self.var_names[new_basic_var_index]} replaces {self.var_names[old_basic_var_index]} in the basis for Row {pivot_row_index}.") | |
| def solve(self, use_fallbacks=True): | |
| """ | |
| Executes the Dual Simplex algorithm. | |
| Returns: | |
| tuple: (final_solution_str, final_objective_str, log_messages, is_fallback_used_str) | |
| """ | |
| self.log_messages = [] # Clear log for this run | |
| self.log_messages.append("--- Starting Dual Simplex Method ---") | |
| is_fallback_used_str = "No" | |
| if self.tableau is None: | |
| self.log_messages.append("Error: Tableau not initialized.") | |
| return "Error", "Tableau not initialized", self.log_messages, is_fallback_used_str | |
| iteration = 0 | |
| tableau_str = self._print_tableau(iteration) | |
| self.log_messages.append(tableau_str) | |
| while iteration < 100: | |
| iteration += 1 | |
| pivot_row_index = self._find_pivot_row() | |
| if pivot_row_index == -1: | |
| self.log_messages.append("\n--- Optimal Solution Found ---") | |
| self.log_messages.append(" All RHS values are non-negative.") | |
| objective_str, solution_details_str = self._print_results() | |
| # _print_results already appends to log, so just return them | |
| return solution_details_str, objective_str, self.log_messages, is_fallback_used_str | |
| pivot_col_index = self._find_pivot_col(pivot_row_index) | |
| if pivot_col_index == -1: | |
| self.log_messages.append("\n--- Primal Problem Infeasible ---") | |
| self.log_messages.append(f" All coefficients in Pivot Row {pivot_row_index} are non-negative, but RHS is negative.") | |
| self.log_messages.append(" The dual problem is unbounded, implying the primal problem has no feasible solution.") | |
| if use_fallbacks: | |
| is_fallback_used_str = "Yes" | |
| return self._handle_fallback_results("primal_infeasible") | |
| return "Infeasible", "N/A", self.log_messages, is_fallback_used_str | |
| elif pivot_col_index == -2: | |
| self.log_messages.append("\n--- Error during pivot column selection ---") | |
| if use_fallbacks: | |
| is_fallback_used_str = "Yes" | |
| return self._handle_fallback_results("pivot_error") | |
| return "Error", "Pivot selection error", self.log_messages, is_fallback_used_str | |
| try: | |
| self._pivot(pivot_row_index, pivot_col_index) | |
| except ZeroDivisionError as e: | |
| self.log_messages.append(f"\n--- Error during pivot operation: {e} ---") | |
| if use_fallbacks: | |
| is_fallback_used_str = "Yes" | |
| return self._handle_fallback_results("numerical_instability") | |
| return "Error", "Numerical instability", self.log_messages, is_fallback_used_str | |
| tableau_str = self._print_tableau(iteration) | |
| self.log_messages.append(tableau_str) | |
| self.log_messages.append("\n--- Maximum Iterations Reached ---") | |
| self.log_messages.append(" The algorithm did not converge within the iteration limit.") | |
| self.log_messages.append(" This might indicate cycling or a very large problem.") | |
| if use_fallbacks: | |
| is_fallback_used_str = "Yes" | |
| return self._handle_fallback_results("iteration_limit") | |
| return "Error", "Max iterations reached", self.log_messages, is_fallback_used_str | |
| def _handle_fallback_results(self, error_type_for_primary_solver): | |
| """ Helper to process results from _try_fallback_solvers and structure return for solve() """ | |
| fallback_results = self._try_fallback_solvers(error_type_for_primary_solver) | |
| final_solution_str = "Fallback attempted." | |
| final_objective_str = "N/A" | |
| is_fallback_used_str = f"Yes, due to {error_type_for_primary_solver}." | |
| # Check dual_approach_result first | |
| if fallback_results.get("dual_approach_result"): | |
| res = fallback_results["dual_approach_result"] | |
| is_fallback_used_str += f" Dual Approach: {res['message']}." | |
| if res["status"] == 0 and res["primal_solution"] is not None: | |
| final_objective_str = f"{res['objective_value']:.6f} (via Dual Approach)" | |
| final_solution_str = ", ".join([f"x{i+1}={v:.3f}" for i, v in enumerate(res["primal_solution"])]) | |
| return final_solution_str, final_objective_str, self.log_messages, is_fallback_used_str | |
| # Then check direct_solver_result | |
| if fallback_results.get("direct_solver_result"): | |
| res = fallback_results["direct_solver_result"] | |
| is_fallback_used_str += f" Direct Solver: {res['message']}." | |
| if res["status"] == 0 and res["primal_solution"] is not None: | |
| final_objective_str = f"{res['objective_value']:.6f} (via Direct Solver)" | |
| final_solution_str = ", ".join([f"x{i+1}={v:.3f}" for i, v in enumerate(res["primal_solution"])]) | |
| return final_solution_str, final_objective_str, self.log_messages, is_fallback_used_str | |
| # If both fallbacks failed or didn't yield a solution | |
| final_solution_str = "All solvers failed or problem is infeasible/unbounded." | |
| self.log_messages.append(final_solution_str) | |
| return final_solution_str, final_objective_str, self.log_messages, is_fallback_used_str | |
| def _try_fallback_solvers(self, error_type): | |
| """ | |
| Tries alternative solvers. Appends to self.log_messages. | |
| Returns dict of results. | |
| """ | |
| self.log_messages.append(f"\n--- Using Fallback Solvers due to '{error_type}' ---") | |
| results = { | |
| "error_type": error_type, | |
| "dual_simplex_result": None, # This would be the state if Dual Simplex had a result | |
| "dual_approach_result": None, | |
| "direct_solver_result": None | |
| } | |
| self.log_messages.append("\n=== Attempting to solve via Dual Approach with Complementary Slackness ===") | |
| status, message, primal_sol, dual_sol, obj_val = solve_lp_via_dual( | |
| self.objective_type, self.original_c, self.original_A, | |
| self.original_relations, self.original_b | |
| ) | |
| results["dual_approach_result"] = { | |
| "status": status, "message": message, "primal_solution": primal_sol, | |
| "dual_solution": dual_sol, "objective_value": obj_val | |
| } | |
| self.log_messages.append(f"Dual Approach Result: {message}") | |
| if status == 0 and primal_sol is not None: | |
| self.log_messages.append(f"Objective Value (Dual Approach): {obj_val}") | |
| # No early return, let solve() decide based on this dict | |
| self.log_messages.append("\n=== Attempting direct solution using SciPy's linprog solver ===") | |
| status_direct, message_direct, primal_sol_direct, _, obj_val_direct = solve_primal_directly( | |
| self.objective_type, self.original_c, self.original_A, | |
| self.original_relations, self.original_b | |
| ) | |
| results["direct_solver_result"] = { | |
| "status": status_direct, "message": message_direct, | |
| "primal_solution": primal_sol_direct, "objective_value": obj_val_direct | |
| } | |
| self.log_messages.append(f"Direct Solver Result: {message_direct}") | |
| if status_direct == 0 and primal_sol_direct is not None: | |
| self.log_messages.append(f"Objective Value (Direct Solver): {obj_val_direct}") | |
| return results | |
| def _print_results(self): | |
| """Formats the final solution into strings and appends to log_messages.""" | |
| self.log_messages.append("\n--- Final Solution (from Dual Simplex Tableau) ---") | |
| tableau_str = self._print_tableau("Final") # This method now returns a string | |
| self.log_messages.append(tableau_str) | |
| final_obj_value = self.tableau[0, -1] | |
| obj_type_str = "Min Z" if self.is_minimized_problem else "Max Z" | |
| if self.is_minimized_problem: | |
| final_obj_value = -final_obj_value | |
| objective_str = f"Optimal Objective Value ({obj_type_str}): {final_obj_value:.6f}" | |
| self.log_messages.append(objective_str) | |
| solution_details_parts = ["Optimal Variable Values:"] | |
| num_total_vars = len(self.var_names) | |
| final_solution_vector = np.zeros(num_total_vars) | |
| for i, basis_col_idx in enumerate(self.basic_vars): | |
| final_solution_vector[basis_col_idx] = self.tableau[i + 1, -1] | |
| for i in range(self.num_original_vars): | |
| var_name = self.var_names[i] | |
| value = final_solution_vector[i] | |
| solution_details_parts.append(f" {var_name}: {value:.6f}") | |
| solution_details_parts.append("Slack/Surplus Variable Values:") | |
| for i in range(self.num_original_vars, num_total_vars): | |
| var_name = self.var_names[i] | |
| value = final_solution_vector[i] | |
| if abs(value) > TOLERANCE: | |
| solution_details_parts.append(f" {var_name}: {value:.6f}") | |
| solution_details_str = "\n".join(solution_details_parts) | |
| self.log_messages.append(solution_details_str) | |
| return objective_str, solution_details_str | |
| def solve_dual_simplex_interface(objective_type_str, c_str, A_str, relations_str, b_str): | |
| """ | |
| Wrapper function to connect DualSimplexSolver with Gradio interface. | |
| """ | |
| current_log = ["Initializing Dual Simplex Solver Interface..."] | |
| c = parse_vector(c_str) | |
| if not c: | |
| current_log.append("Error: Objective coefficients (c) could not be parsed or are empty.") | |
| return "Error parsing c", "Error parsing c", "\n".join(current_log) | |
| A = parse_matrix(A_str) | |
| if A.size == 0: | |
| current_log.append("Error: Constraint matrix (A) could not be parsed or is empty.") | |
| return "Error parsing A", "Error parsing A", "\n".join(current_log) | |
| b = parse_vector(b_str) | |
| if not b: | |
| current_log.append("Error: Constraint bounds (b) could not be parsed or are empty.") | |
| return "Error parsing b", "Error parsing b", "\n".join(current_log) | |
| relations = parse_relations(relations_str) | |
| if not relations: | |
| current_log.append("Error: Constraint relations could not be parsed, are empty, or contain invalid symbols.") | |
| return "Error parsing relations", "Error parsing relations", "\n".join(current_log) | |
| # Basic dimensional validation | |
| if A.shape[0] != len(b): | |
| current_log.append(f"Dimension mismatch: Number of rows in A ({A.shape[0]}) must equal length of b ({len(b)}).") | |
| return "Dimension Error", "Dimension Error", "\n".join(current_log) | |
| if A.shape[1] != len(c): | |
| current_log.append(f"Dimension mismatch: Number of columns in A ({A.shape[1]}) must equal length of c ({len(c)}).") | |
| return "Dimension Error", "Dimension Error", "\n".join(current_log) | |
| if A.shape[0] != len(relations): | |
| current_log.append(f"Dimension mismatch: Number of rows in A ({A.shape[0]}) must equal length of relations ({len(relations)}).") | |
| return "Dimension Error", "Dimension Error", "\n".join(current_log) | |
| current_log.append("Inputs parsed and validated successfully.") | |
| try: | |
| solver = DualSimplexSolver(objective_type_str, c, A, relations, b) | |
| current_log.append("DualSimplexSolver instantiated.") | |
| # The solve method now returns: final_solution_str, final_objective_str, log_messages, is_fallback_used_str | |
| solution_str, objective_str, solver_log_messages, fallback_info = solver.solve() | |
| current_log.extend(solver_log_messages) | |
| current_log.append(f"Fallback Status: {fallback_info}") | |
| return solution_str, objective_str, "\n".join(current_log) | |
| except Exception as e: | |
| gr.Error(f"An error occurred during solving with Dual Simplex: {e}") | |
| current_log.append(f"Runtime error in Dual Simplex: {e}") | |
| return "Solver error", "Solver error", "\n".join(current_log) | |
| dual_simplex_interface = gr.Interface( | |
| fn=solve_dual_simplex_interface, | |
| inputs=[ | |
| gr.Radio(label="Objective Type", choices=["max", "min"], value="max"), | |
| gr.Textbox(label="Objective Coefficients (c)", info="Comma-separated, e.g., 4,1"), | |
| gr.Textbox(label="Constraint Matrix (A)", info="Rows separated by ';', elements by ',', e.g., 3,1; 4,3; 1,2"), | |
| gr.Textbox(label="Constraint Relations", info="Comma-separated, e.g., >=,>=,>="), # Dual simplex typically starts from Ax >= b for max problems if to be converted to <= | |
| gr.Textbox(label="Constraint RHS (b)", info="Comma-separated, e.g., 3,6,4") | |
| ], | |
| outputs=[ | |
| gr.Textbox(label="Optimal Solution (Variables)"), | |
| gr.Textbox(label="Optimal Objective Value"), | |
| gr.Textbox(label="Solver Log, Tableau Steps, and Fallback Info", lines=15, interactive=False) | |
| ], | |
| title="Dual Simplex Solver for Linear Programs (LP)", | |
| description="Solves LPs using the Dual Simplex method. This method is often efficient when an initial basic solution is dual feasible but primal infeasible (e.g. after adding cuts). Input Ax R b where R can be '>=', '<=', or '='.", | |
| examples=[ | |
| [ # Example 1: Max problem, standard form for dual simplex often has >= constraints initially | |
| # Maximize Z = 4x1 + x2 | |
| # Subject to: | |
| # 3x1 + x2 >= 3 --> -3x1 - x2 <= -3 | |
| # 4x1 + 3x2 >= 6 --> -4x1 - 3x2 <= -6 | |
| # x1 + 2x2 >= 4 --> -x1 - 2x2 <= -4 (Mistake in common example, should be <= to be interesting for dual or needs specific setup) | |
| # Let's use a more typical dual simplex starting point: | |
| # Min C = 2x1 + x2 (so Max -2x1 -x2) | |
| # s.t. x1 + x2 >= 5 | |
| # 2x1 + x2 >= 6 | |
| # x1, x2 >=0 | |
| # Becomes: Max Z' = -2x1 -x2 | |
| # -x1 -x2 <= -5 | |
| # -2x1 -x2 <= -6 | |
| "max", "-2,-1", "-1,-1;-2,-1", "<=,<=", "-5,-6" # This is already in <= form, good for dual if RHS is neg. | |
| ], | |
| [ # Example 2: (Taken from a standard textbook example for Dual Simplex) | |
| # Minimize Z = 3x1 + 2x2 + x3 | |
| # Subject to: | |
| # 3x1 + x2 + x3 >= 3 | |
| # -3x1 + 3x2 + x3 >= 6 | |
| # x1 + x2 + x3 <= 3 (This constraint makes it interesting) | |
| # x1,x2,x3 >=0 | |
| # For Gradio: obj_type='min', c="3,2,1", A="3,1,1;-3,3,1;1,1,1", relations=">=,>=,<=", b="3,6,3" | |
| "min", "3,2,1", "3,1,1;-3,3,1;1,1,1", ">=,>=,<=", "3,6,3" | |
| ], | |
| [ # Example from problem description (slightly modified for typical dual simplex) | |
| # Maximize Z = 3x1 + 2x2 | |
| # Subject to: | |
| # 2x1 + x2 <= 18 (Original) | |
| # x1 + x2 <= 12 (Original) | |
| # x1 <= 5 (Original) | |
| # To make it a dual simplex start, we might have transformed it from something else, | |
| # or expect some RHS to be negative after initial setup. | |
| # For a direct input that might be dual feasible but primal infeasible: | |
| # Max Z = x1 + x2 | |
| # s.t. -2x1 - x2 <= -10 (i.e. 2x1 + x2 >= 10) | |
| # -x1 - 2x2 <= -10 (i.e. x1 + 2x2 >= 10) | |
| "max", "1,1", "-2,-1;-1,-2", "<=,<=", "-10,-10" | |
| ] | |
| ], | |
| flagging_mode="manual" | |
| ) | |