Simplex Algorithm

The algorithm operates by moving from one vertex (corner point) of the feasible region—the geometric space defined by all constraints—to an adjacent vertex. Each move is guaranteed to improve (or at least not worsen) the value of the objective function. This traversal continues until no adjacent vertex offers improvement, indicating an optimal solution has been found. This geometric interpretation is key to its efficiency, as the optimum in a linear program always lies at a vertex.

The algorithm requires the linear program to be in standard form: maximization objective, non-negative variables, and equality constraints. It is executed using a simplex tableau, a structured matrix that organizes all problem data (coefficients of the objective function and constraints, right-hand side values). Pivoting operations on this tableau mathematically represent the move from one vertex to the next. The tableau's bottom row, the objective row or indicator row, reveals whether optimality has been reached and which variable should enter the basis next.

At any iteration, the algorithm maintains a basis—a set of basic variables that are positive and correspond to linearly independent constraint columns. The variables not in the basis are non-basic and set to zero. The current solution defined by the basis is called a Basic Feasible Solution (BFS), which corresponds directly to a vertex of the feasible region. The algorithm's iterations are, therefore, a systematic search through adjacent BFSs.

• Entering Variable: Selected from non-basic variables to improve the objective.
• Leaving Variable: Selected from basic variables to maintain feasibility as the entering variable increases.

The algorithm uses clear mathematical tests to guide its execution:

• Optimality Condition (for maximization): The current BFS is optimal if all coefficients in the objective row of the tableau are non-negative. A negative coefficient indicates a non-basic variable that, if increased, would improve the objective.
• Feasibility Condition (Minimum Ratio Test): When selecting the leaving variable, the algorithm calculates ratios of the right-hand side values to the positive coefficients in the entering variable's column. The basic variable associated with the smallest non-negative ratio leaves the basis. This test ensures the new solution remains within the feasible region.

A key theoretical and practical characteristic is its handling of degeneracy. A degenerate BFS occurs when a basic variable has a value of zero. This can lead to cycling, where the algorithm moves through a sequence of BFSs without improving the objective, potentially failing to terminate. While proven to be rare in practice, anti-cycling rules like Bland's rule (a specific, deterministic order for selecting entering and leaving variables) guarantee finite termination. Degeneracy can also cause stalling, slowing convergence.

The standard Simplex Algorithm requires an initial BFS to start. If none is readily available, these auxiliary methods are used:

• Two-Phase Method: Phase I introduces artificial variables to create an obvious starting point and minimizes their sum. If this sum reaches zero, a feasible BFS for the original problem is found, and Phase II begins. If not, the problem is infeasible.
• Big-M Method: A single, large penalty coefficient M is assigned to artificial variables in the objective function. The algorithm then drives these variables to zero if possible. While conceptually simpler, it can cause numerical instability due to the large M value.

Linear Programming is the fundamental optimization framework for which the Simplex Algorithm was invented. An LP problem seeks to maximize or minimize a linear objective function (e.g., profit or cost) subject to a set of linear inequality or equality constraints (e.g., resource limits).

• Key Components: Decision variables, linear objective, linear constraints defining a convex feasible region (a polytope).
• Relation to Simplex: The Simplex Algorithm operates by traversing the vertices of this feasible region, moving from one basic feasible solution to an adjacent one with improved objective value until the optimum is found.
• Example: Optimizing a product mix to maximize profit given limited raw materials and machine time.

Integer Programming is an extension of linear programming where some or all decision variables are constrained to be integers. This is critical for modeling discrete decisions (e.g., yes/no, number of vehicles).

• Complexity: IP is generally NP-hard, unlike LP which is solvable in polynomial time.
• Connection to Simplex: The most common exact method for solving IP is Branch and Bound, which uses the Simplex Algorithm to solve continuous linear programming relaxations at each node of the search tree to provide bounds.
• Use Case: Crew scheduling, where you cannot schedule a fraction of a person.

Branch and Bound is a general algorithm paradigm for finding optimal solutions to combinatorial optimization and integer programming problems. It systematically explores candidate solutions by dividing the problem into subproblems (branching) and using bounds to prune subproblems that cannot contain the optimum.

• Mechanism: It constructs a search tree. For each node, it solves a relaxation (often via Simplex) to get a bound. If the bound is worse than the best-known solution, the entire branch is pruned.
• Synergy with Simplex: The Simplex Algorithm is the workhorse for calculating the upper bound (for maximization) in the linear relaxation at each node, making the overall Branch and Bound search efficient.

A Constraint Optimization Problem generalizes constraint satisfaction by adding an objective function to be maximized or minimized. The goal is to find a feasible assignment of values to variables that yields the best objective value.

• Contrast with LP: While LP uses linear constraints and objectives, COP allows for arbitrary, non-linear constraints and objectives defined over finite domains.
• Algorithmic Approaches: Solved using techniques like Branch and Bound with constraint propagation or by translating to Integer Programming.
• Example: Scheduling tasks to minimize total completion time while respecting precedence and resource constraints.

For every linear programming problem (the primal), there exists a corresponding Dual Problem. The dual provides a different perspective on the same optimization scenario, often with valuable economic interpretations (e.g., shadow prices).

• Duality Theorem: The optimal objective value of the primal problem equals the optimal objective value of the dual.
• Simplex Connection: The Simplex Algorithm inherently solves both problems simultaneously. As it progresses toward the primal optimum, it also generates feasible solutions for the dual.
• Application: Sensitivity analysis—understanding how the optimal solution changes with perturbations in constraint coefficients or resource limits—is performed using dual variables.

Interior-Point Methods are an alternative class of algorithms for solving linear programming problems. Unlike the Simplex Algorithm, which traverses the exterior (vertices) of the feasible region, these methods travel through the interior of the feasible region.

• History: Gained prominence in the 1980s with Karmarkar's algorithm, proving polynomial-time solvability for LP.
• Comparison with Simplex:
  • Simplex: Often performs remarkably well in practice, excels at warm starts, and provides basis information useful for integer programming.
  • Interior-Point: Has superior worst-case time complexity and can be more efficient for very large, sparse problems. However, solutions are not naturally vertex-based.
• Modern Use: Many commercial solvers (like Gurobi, CPLEX) implement both Simplex and interior-point methods, using a crossover procedure to convert an interior-point solution to a basic one.