simplex algorithm

Work in Progress

Summary

Simplex algorithm
TODO

Finding a feasible solution

given Ax = b
1. multiply the equations such that b>=0
2. construct an auxiliary problem, add m auxiliary variables
3. solve the auxiliary problem using the simplex algorithm
4. if z = 0, return the feasible solution to the original problem
5. else, return "infeasible"

Concept

Simplex algorithm

  • finds the optimal solution given a basic feasible solution
  • pick non-basic variable where the corresponding entry in the objective matrix is >0
𝟘

For a feasible basis in canonical form, simplex moves between BFSs.

repeat
  if every reduced cost c̄_j ≤ 0: return current BFS (optimal)
  choose entering k with c̄_k > 0
  if Ā_k ≤ 0: return unbounded ray
  t <- min { b̄_i/Ā_ik : Ā_ik > 0 }
  choose a minimizing basic index to leave; pivot

Optimality follows because . If , increasing preserves nonnegativity and improves without bound. Degeneracy can cause cycling; Bland’s rule chooses the smallest eligible entering and leaving indices and guarantees termination.

Bland’s rule

  • prevent cycling in the simplex algorithm
  • ensures termination
  • choose the smallest element to enter and leave the basis

Simplex tableau

Finding a feasible solution

  • the simplex algorithm finds the optimal solution given a feasible solution
  • we first need to find a feasible solution

canonical form is insufficient, we might see a solution that is infeasible due to negative coefficients

Auxiliary problem

  • add auxiliary variables to have a very obvious feasible solution
  • try to reduce the auxiliary variables to 0

we want to minimize the effect that the auxiliary variables have on the problem
note: the auxiliary problem is not in SEF, we have to convert it to SEF and then to canonical form

Non-zero auxiliary variables implies infeasibility

if there is a feasible solution, this step always gives a basic solution

Two-phase simplex

Phase I: minimize sum of artificial variables
if z > 0: report infeasible
extract a feasible original basis
Phase II: restore original objective and run simplex

With Bland’s rule, this proves an SEF LP is infeasible, unbounded, or has an optimal BFS. See LP outcomes.

Application

Finding a better the optimal solution

note that the new feasible solutions are all basic solutions

the -1 term does not restict , since any value of will gaurentee

stop the algorithm, since there are no more non-basic variables with

Unbounded LP

and can be considered the certificate for the LP’s unboundedness
notice, if the column of the chosen non-basic solution is <=0, then the LP is unbounded

Finding a feasible solution

Detect infeasibility

Simplex tableau

Extra

Octave function to solve an LP using two-phase simplex

octave
function [x, z, B, status] = simplex_lp(c, A, b)
  % Solve:
  %   maximize c' * x
  %   subject to A*x = b, x >= 0
  %
  % status: "optimal", "infeasible", or "unbounded"
  %
  % Uses two-phase primal simplex with Bland's pivot rule.
  % Intended for small classroom problems.

  tol = 1e-9;
  maxiter = 10000;

  c = c(:);
  b = b(:);
  [m, n] = size(A);

  if length(c) != n || length(b) != m
    error("Dimensions of c, A, and b do not match.");
  endif

  if any(!isfinite(A(:))) || any(!isfinite(b)) ...
      || any(!isfinite(c))
    error("Inputs must contain only finite numbers.");
  endif

  x = [];
  z = NaN;
  B = [];

  % Make every RHS nonnegative.
  neg = (b < 0);
  A(neg, :) = -A(neg, :);
  b(neg) = -b(neg);

  % Phase I:
  % Add artificial variables a >= 0:
  %   A*x + I*a = b
  % Maximize -sum(a), initially using a as the basis.
  Awork = [A, eye(m)];
  cphase1 = [zeros(n, 1); -ones(m, 1)];
  B = n + (1:m);

  [B, phase_status] = simplex_pivots( ...
      cphase1, Awork, b, B, tol, maxiter);

  if !strcmp(phase_status, "optimal")
    error("Numerical failure during Phase I.");
  endif

  [Ac, bc, ~, phase_value] = ...
      canonical_lp(cphase1, Awork, b, B);

  if phase_value < -tol
    status = "infeasible";
    B = [];
    return;
  endif

  % Remove any zero-valued artificial variables still basic.
  % Pivot in an original variable when possible.
  % Otherwise, the transformed row is redundant.
  while any(B > n)
    [Ac, bc] = canonical_lp(cphase1, Awork, b, B);
    r = find(B > n, 1);

    if abs(bc(r)) > tol
      error("Numerical failure removing artificial variables.");
    endif

    nonbasic = setdiff(1:n, B);
    candidates = nonbasic(abs(Ac(r, nonbasic)) > tol);

    if !isempty(candidates)
      B(r) = candidates(1);
    else
      % Work with the equivalent canonical equations.
      Awork = Ac;
      b = bc;
      Awork(r, :) = [];
      b(r) = [];
      B(r) = [];
    endif
  endwhile

  % Delete all artificial-variable columns.
  Awork = Awork(:, 1:n);

  % Phase II: optimize the original objective.
  [B, status] = simplex_pivots( ...
      c, Awork, b, B, tol, maxiter);

  [~, bc] = canonical_lp(c, Awork, b, B);
  bc(abs(bc) < tol) = 0;

  x = zeros(n, 1);
  x(B) = bc;

  if strcmp(status, "unbounded")
    z = Inf;
  else
    z = c' * x;
  endif
endfunction


function [B, status] = simplex_pivots(c, A, b, B, tol, maxiter)
  % Primal simplex from a feasible basis.

  n = columns(A);

  for iteration = 1:maxiter
    [Ac, bc, cc] = canonical_lp(c, A, b, B);

    if any(bc < -tol)
      error("The current basis is not feasible.");
    endif

    bc(abs(bc) < tol) = 0;

    % Bland's rule: smallest-index improving variable enters.
    nonbasic = setdiff(1:n, B);
    improving = nonbasic(cc(nonbasic) > tol);

    if isempty(improving)
      status = "optimal";
      return;
    endif

    entering = improving(1);
    d = Ac(:, entering);

    % x_B = bc - d*t, so only d_i > 0 limits t.
    eligible = find(d > tol);

    if isempty(eligible)
      status = "unbounded";
      return;
    endif

    ratios = bc(eligible) ./ d(eligible);
    theta = min(ratios);

    % Break minimum-ratio ties using basic-variable indices.
    tied = eligible(abs(ratios - theta) <= tol);
    [~, k] = min(B(tied));
    leaving_row = tied(k);

    B(leaving_row) = entering;
  endfor

  error("Iteration limit reached.");
endfunction