Simplex Algorithm

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.

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.