Basics

Consider the benefits of a basis in a linear programming context.  The solution to a linear programming problem generally has one non-zero variable for each constraint.  This means in a model with M constraints all one really needs to know is exactly which M variables are non-zero.

Generally, linear programming solvers take three or more times as many iterations as the number of constraints to reach a solution.  Simplex based linear programming solvers initially guess which M variables should be in the solution then one by one insert better variables into the basis until the ultimate, optimal basis is found.

If one can supply an improved guess specifying the set of variables to be in the basis (those to be non-zero in the final optimal solution) then solution time can be reduced.  An advanced basis is a user-defined suggestion on variables in the solution.  A good advanced basis can reduce solution time by more than an order of magnitude.  In one case within my work advanced basis suggestions caused a reduction in solution time from 36 hours to 1 hour.

Here I cover how to provide such information and also discuss some of the difficulties that may arise when using advanced bases.