canonical form

Work in Progress

Concept

Basis

  • similar to the traditional definition in linear algebra

a non-singular matrix is one with independent columns

Basic variables

  • basic variables are the ones corresponding to the independent columns

Basic solution

non-basic variables are zero
basic solutions are feasible if all values are non-negative

Uniqueness of basic solution

Canonical form

  • choose basic variables that form an identity matrix, so they can be expressed in terms of non-basic variables
𝟘

Every linear program has a canonical form

  • feasible solutions have the same objective value

Converting to canonical form

  1. make the desired basis submatrix an identity
  1. remove basis variables from the objective function

Application

Finding a basic solution

Canonical form with different basis

recall that matrix transpose swaps the operands over matrix multiplication

Extra

Column sub-matrix notation

Working to derive the objectvie function rewrite step

Extra

Octave function to convert an LP into canonical form

octave
function [Ac, bc, cc, z0] = canonical_lp(c, A, b, B)
  % Canonical form of:
  %   maximize c' * x
  %   subject to A*x = b, x >= 0
  %
  % B: indices of the basic variables.
  %
  % Output:
  %   Ac*x = bc
  %   z = z0 + cc'*x
  %
  % Ac(:, B) is the identity; cc(B) is zero.

  c = c(:);
  b = b(:);
  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 length(B) != m || length(unique(B)) != m ...
      || any(B < 1) || any(B > n) || any(B != fix(B))
    error("B must contain m distinct valid column indices.");
  endif

  AB = A(:, B);

  if rank(AB) < m
    error("The selected basis matrix is singular.");
  endif

  Ac = AB \ A;
  bc = AB \ b;

  cB = c(B);
  cc = c - Ac' * cB;
  z0 = cB' * bc;

  % Remove numerical noise in the basis columns.
  Ac(:, B) = eye(m);
  cc(B) = 0;
endfunction