maths/operations_research/simplex_solver_with_steps.py

import numpy as np
from tabulate import tabulate
import gradio as gr
from maths.operations_research.utils import parse_matrix
from maths.operations_research.utils import parse_vector


def simplex_solver_with_steps(c, A, b, bounds):
    """
    Solve LP using simplex method and display full tableau at each step
    
    Parameters:
    - c: Objective coefficients (for maximizing c'x)
    - A: Constraint coefficients matrix
    - b: Right-hand side of constraints
    - bounds: Variable bounds as [(lower_1, upper_1), (lower_2, upper_2), ...]
    
    Returns:
    - x: Optimal solution
    - optimal_value: Optimal objective value
    - steps_log: List of strings detailing each step
    """
    steps_log = []
    steps_log.append("\n--- Starting Simplex Method ---")
    steps_log.append(f"Objective: Maximize {' + '.join([f'{c[i]}x_{i}' for i in range(len(c))])}")
    steps_log.append(f"Constraints:")
    for i in range(len(b)):
        constraint_str = ' + '.join([f"{A[i,j]}x_{j}" for j in range(A.shape[1])])
        steps_log.append(f"  {constraint_str} <= {b[i]}")
    
    # Convert problem to standard form (for tableau method)
    # First handle bounds by adding necessary constraints
    A_with_bounds = A.copy()
    b_with_bounds = b.copy()
    
    for i, (lb, ub) in enumerate(bounds):
        if lb is not None and lb > 0:
            # For variables with lower bounds > 0, we'll substitute x_i = x_i' + lb
            # This affects all constraints where x_i appears
            for j in range(A.shape[0]):
                b_with_bounds[j] -= A[j, i] * lb
    
    # Number of variables and constraints
    n_vars = len(c)
    n_constraints = A.shape[0]
    
    # Add slack variables to create standard form
    # The tableau will have: [objective row | RHS]
    #                        [-------------|----]
    #                        [constraints  | RHS]
    
    # Initial tableau: 
    # First row is -c (negative of objective coefficients) and 0s for slack variables, then 0 (for max)
    # The rest are constraint coefficients, then identity matrix for slack variables, then RHS
    tableau = np.zeros((n_constraints + 1, n_vars + n_constraints + 1))
    
    # Set the objective row (negated for maximization)
    tableau[0, :n_vars] = -c
    
    # Set the constraint coefficients
    tableau[1:, :n_vars] = A_with_bounds
    
    # Set the slack variable coefficients (identity matrix)
    for i in range(n_constraints):
        tableau[i + 1, n_vars + i] = 1
    
    # Set the RHS
    tableau[1:, -1] = b_with_bounds
    
    # Base and non-base variables
    base_vars = list(range(n_vars, n_vars + n_constraints))  # Slack variables are initially basic
    
    # Function to print current tableau
    def print_tableau(tableau, base_vars, steps_log_func):
        headers = [f"x_{j}" for j in range(n_vars)] + [f"s_{j}" for j in range(n_constraints)] + ["RHS"]
        rows = []
        row_labels = ["z"] + [f"eq_{i}" for i in range(n_constraints)]
        
        for i, row in enumerate(tableau):
            rows.append([row_labels[i]] + [f"{val:.3f}" for val in row])
        
        steps_log_func.append("\nCurrent Tableau:")
        steps_log_func.append(tabulate(rows, headers=headers, tablefmt="grid"))
        steps_log_func.append(f"Basic variables: {[f'x_{v}' if v < n_vars else f's_{v-n_vars}' for v in base_vars]}")
    
    # Print initial tableau
    steps_log.append("\nInitial tableau:")
    print_tableau(tableau, base_vars, steps_log)
    
    # Main simplex loop
    iteration = 0
    max_iterations = 100  # Prevent infinite loops
    
    while iteration < max_iterations:
        iteration += 1
        steps_log.append(f"\n--- Iteration {iteration} ---")
        
        # Find the entering variable (most negative coefficient in objective row for maximization)
        entering_col = np.argmin(tableau[0, :-1])
        if tableau[0, entering_col] >= -1e-10:  # Small negative numbers due to floating-point errors
            steps_log.append("Optimal solution reached - no negative coefficients in objective row")
            break
        
        steps_log.append(f"Entering variable: {'x_' + str(entering_col) if entering_col < n_vars else 's_' + str(entering_col - n_vars)}")
        
        # Find the leaving variable using min ratio test
        ratios = []
        for i in range(1, n_constraints + 1):
            if tableau[i, entering_col] <= 0:
                ratios.append(np.inf)  # Avoid division by zero or negative
            else:
                ratios.append(tableau[i, -1] / tableau[i, entering_col])
        
        if all(r == np.inf for r in ratios):
            steps_log.append("Unbounded solution - no leaving variable found")
            return steps_log, None, float('inf')  # Problem is unbounded
        
        # Find the row with minimum ratio
        leaving_row = np.argmin(ratios) + 1  # +1 because we skip the objective row
        leaving_var = base_vars[leaving_row - 1]
        
        steps_log.append(f"Leaving variable: {'x_' + str(leaving_var) if leaving_var < n_vars else 's_' + str(leaving_var - n_vars)}")
        steps_log.append(f"Pivot element: {tableau[leaving_row, entering_col]:.3f} at row {leaving_row}, column {entering_col}")
        
        # Perform pivot operation
        # First, normalize the pivot row
        pivot = tableau[leaving_row, entering_col]
        tableau[leaving_row] = tableau[leaving_row] / pivot
        
        # Update other rows
        for i in range(tableau.shape[0]):
            if i != leaving_row:
                factor = tableau[i, entering_col]
                tableau[i] = tableau[i] - factor * tableau[leaving_row]
        
        # Update basic variables
        base_vars[leaving_row - 1] = entering_col
        
        # Print updated tableau
        steps_log.append("\nAfter pivot:")
        print_tableau(tableau, base_vars, steps_log)
    
    if iteration == max_iterations:
        steps_log.append("Max iterations reached without convergence")
        return steps_log, None, None
    
    # Extract solution
    x = np.zeros(n_vars)
    for i, var in enumerate(base_vars):
        if var < n_vars:  # If it's an original variable and not a slack
            x[var] = tableau[i + 1, -1]
    
    # Account for variable substitutions (if lower bounds were applied)
    for i, (lb, _) in enumerate(bounds):
        if lb is not None and lb > 0:
            x[i] += lb
    
    # Calculate objective value
    optimal_value = np.dot(c, x)
    
    steps_log.append("\n--- Simplex Method Complete ---")
    steps_log.append(f"Optimal solution found: {x}")
    steps_log.append(f"Optimal objective value: {optimal_value}")
    
    return steps_log, x, optimal_value

# Gradio interface

def parse_input_list(s):
    # Helper to parse comma/space/semicolon separated numbers
    return [float(x) for x in s.replace(';', ' ').replace(',', ' ').split() if x.strip()]

def parse_matrix(s):
    # Helper to parse matrix input as rows separated by newlines, columns by comma/space
    return np.array([parse_input_list(row) for row in s.strip().split('\n') if row.strip()])

def parse_bounds(s):
    # Helper to parse bounds as (lower, upper) per variable, e.g. "0, None\n0, None"
    bounds = []
    for row in s.strip().split('\n'):
        parts = row.replace('None', 'None').replace('none', 'None').split(',')
        lb = float(parts[0]) if parts[0].strip().lower() != 'none' else None
        ub = float(parts[1]) if len(parts) > 1 and parts[1].strip().lower() != 'none' else None
        bounds.append((lb, ub))
    return bounds

def gradio_simplex(c_str, A_str, b_str, bounds_str):
    try:
        c = parse_input_list(c_str)
        A = parse_matrix(A_str)
        b = parse_input_list(b_str)
        bounds = parse_bounds(bounds_str)
        steps_log, x, optimal_value = simplex_solver_with_steps(c, A, b, bounds)
        steps = '\n'.join(steps_log)
        if x is not None:
            solution = f"Optimal solution: {x}\nOptimal value: {optimal_value}"
        else:
            solution = "No optimal solution found."
        return steps, solution
    except Exception as e:
        return f"Error: {e}", ""

with gr.Blocks() as demo:
    gr.Markdown("""
    # Simplex Solver with Steps (Gradio)
    Enter your LP problem below. All inputs are required.
    - **Objective coefficients (c):** e.g. `3, 2`
    - **Constraint matrix (A):** one row per line, e.g. `1, 2`\n`2, 1`
    - **RHS vector (b):** e.g. `6, 8`
    - **Bounds:** one row per variable, lower and upper bound separated by comma, e.g. `0, None`\n`0, None`
    """)
    c_in = gr.Textbox(label="Objective coefficients (c)", value="3, 2")
    A_in = gr.Textbox(label="Constraint matrix (A)", value="1, 2\n2, 1")
    b_in = gr.Textbox(label="RHS vector (b)", value="6, 8")
    bounds_in = gr.Textbox(label="Bounds", value="0, None\n0, None")
    btn = gr.Button("Solve")
    steps_out = gr.Textbox(label="Simplex Steps", lines=20)
    sol_out = gr.Textbox(label="Solution")
    btn.click(gradio_simplex, inputs=[c_in, A_in, b_in, bounds_in], outputs=[steps_out, sol_out])

def main():
    demo.launch()

if __name__ == "__main__":
    main()


def run_simplex_solver_interface(c_str, A_str, b_str, bounds_str):
    """
    Wrapper function to connect simplex_solver_with_steps with Gradio interface.
    """
    current_log_list = ["Initializing Simplex Solver (with Steps) Interface..."]

    c = parse_vector(c_str)
    if not c:
        current_log_list.append("Error: Objective coefficients (c) could not be parsed or are empty.")
        return "Error parsing c", "Error parsing c", "\n".join(current_log_list)

    A = parse_matrix(A_str)
    if A.size == 0:
        current_log_list.append("Error: Constraint matrix (A) could not be parsed or is empty.")
        return "Error parsing A", "Error parsing A", "\n".join(current_log_list)

    b = parse_vector(b_str)
    if not b:
        current_log_list.append("Error: Constraint bounds (b) could not be parsed or are empty.")
        return "Error parsing b", "Error parsing b", "\n".join(current_log_list)

    variable_bounds = parse_bounds(bounds_str) # This returns a list of tuples or []
    # parse_bounds includes gr.Warning on failure and returns []
    if bounds_str and not variable_bounds: # If input was given but parsing failed
        current_log_list.append("Error: Variable bounds string could not be parsed. Please check format.")
        # parse_bounds already issues a gr.Warning
        return "Error parsing var_bounds", "Error parsing var_bounds", "\n".join(current_log_list)


    # Dimensional validation
    if A.shape[0] != len(b):
        current_log_list.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_list)
    if A.shape[1] != len(c):
        current_log_list.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_list)
    if variable_bounds and len(variable_bounds) != len(c):
        current_log_list.append(f"Dimension mismatch: Number of variable bounds pairs ({len(variable_bounds)}) must equal number of objective coefficients ({len(c)}).")
        return "Dimension Error", "Dimension Error", "\n".join(current_log_list)

    # If bounds_str is empty, parse_bounds returns [], which is fine for the solver if it expects default non-negativity or specific handling.
    # The simplex_solver_with_steps expects a list of tuples, and an empty list if no specific bounds beyond non-negativity are implied by problem setup.
    # For this solver, bounds are crucial. If not provided, we should create default non-negative bounds.
    if not variable_bounds:
        variable_bounds = [(0, None) for _ in range(len(c))]
        current_log_list.append("Defaulting to non-negative bounds for all variables as no specific bounds were provided.")


    current_log_list.append("Inputs parsed and validated successfully.")

    try:
        # Ensure inputs are NumPy arrays as expected by some solvers (though this one might be flexible)
        np_c = np.array(c)
        np_b = np.array(b)

        # Call the solver
        # simplex_solver_with_steps returns: steps_log, x, optimal_value
        steps_log, x_solution, opt_val = simplex_solver_with_steps(np_c, A, np_b, variable_bounds)

        current_log_list.extend(steps_log) # steps_log is already a list of strings

        solution_str = "N/A"
        objective_str = "N/A"

        if x_solution is not None:
            solution_str = ", ".join([f"{val:.3f}" for val in x_solution])
        else: # Check specific messages in log if solution is None
            if any("Unbounded solution" in msg for msg in steps_log):
                solution_str = "Unbounded solution"
            elif any("infeasible" in msg.lower() for msg in steps_log): # More general infeasibility check
                solution_str = "Infeasible solution"


        if opt_val is not None:
            if opt_val == float('inf') or opt_val == float('-inf'):
                 objective_str = str(opt_val)
            else:
                objective_str = f"{opt_val:.3f}"

        return solution_str, objective_str, "\n".join(current_log_list)

    except Exception as e:
        gr.Error(f"An error occurred during solving with Simplex Method: {e}")
        current_log_list.append(f"Runtime error in Simplex Method: {e}")
        return "Solver error", "Solver error", "\n".join(current_log_list)

simplex_solver_interface = gr.Interface(
    fn=run_simplex_solver_interface,
    inputs=[
        gr.Textbox(label="Objective Coefficients (c)", info="Comma-separated for maximization problem, e.g., 3,5"),
        gr.Textbox(label="Constraint Matrix (A)", info="Rows separated by ';', elements by ',', e.g., 1,0;0,2;3,2. Assumes Ax <= b."),
        gr.Textbox(label="Constraint RHS (b)", info="Comma-separated, e.g., 4,12,18"),
        gr.Textbox(label="Variable Bounds (L,U) per variable", info="Pairs like L1,U1; L2,U2;... Use 'None' for no bound. E.g., '0,None;0,10'. If empty, defaults to non-negative for all variables (0,None).")
    ],
    outputs=[
        gr.Textbox(label="Optimal Solution (x)"),
        gr.Textbox(label="Optimal Objective Value"),
        gr.Textbox(label="Solver Steps and Tableaus", lines=20, interactive=False)
    ],
    title="Simplex Method Solver (with Tableau Steps)",
    description="Solves Linear Programs (maximization, Ax <= b) using the Simplex method and displays detailed tableau iterations. Assumes variables are non-negative if bounds not specified.",
    examples=[
        [ # Classic example from many textbooks (e.g., Taha, Operations Research)
            "3,5", # c (Max Z = 3x1 + 5x2)
            "1,0;0,2;3,2", # A
            "4,12,18", # b
            "0,None;0,None" # x1 >=0, x2 >=0 (explicitly stating non-negativity)
        ],
        [ # Another common example
            "5,4", # c (Max Z = 5x1 + 4x2)
            "6,4;1,2; -1,1;0,1", # A
            "24,6,1,2", #b
            "0,None;0,None" # x1,x2 >=0
        ],
        [ # Example that might be unbounded if not careful or show interesting steps
            "1,1",
            "1,-1;-1,1",
            "1,1",
            "0,None;0,None" # x1-x2 <=1, -x1+x2 <=1
        ]
    ],
    flagging_mode="manual"
)