Method for solving linear programs

A computer-implemented method for reducing an amount of memory space required for a kernel matrix, the method comprising the steps of:

• reducing an amount of memory space required for variables of a linear program (LP) on a processing device with limited memory upon receiving a linear program, a canonical form of the linear program being:
• minimize cTx;
• subject to Ax≧b;
• x≧0,
• whereby x represents the vector of variables to be determined, b in Rm and c in Rm respectively represent a vector of given coefficients and original matrix (A) represents a matrix of given coefficients, where reducing the amount of memory space required on the processing device with limited memory, comprises a processor of the processing device:
• determining a kernel K and determining a kernel matrix G of the kernel K, wherein the kernel K=(D, B), wherein the kernel matrix G is calculated as G=ADB, wherein B is a set of basis variable indices, D is a set of defining constraint indices such that D⊂{1, . . . , m}, B⊂{1, . . . , n}, |D|=|B|, and the kernel matrix is a non-singular submatrix of the original matrix;
• determining a set of non-basic variable indices N and a set of extra constraint indices E, wherein N={1, . . . , n}\B and E={1, . . . , m}\D;
• computing a primal kernel vector (xK) from the determined kernel such that GxBK=bD, xNK=0;
• computing a dual kernel vector (yK) from the determined kernel such that YEK=0, (yDK)TG=cBT;
• evaluating the feasibility of the primal kernel vector and of the dual kernel vector;
• executing, in response to a case when the primal kernel vector is feasible and the dual kernel vector is infeasible, a modified primal simplex algorithm wherein the kernel and the kernel matrix are updated to increase feasibility of the dual kernel vector in one or more modified simplex iterations until the dual kernel vector is also feasible or a first termination condition is reached;
• executing, in response to a case when the primal kernel vector is infeasible and the dual kernel vector is feasible, a modified dual simplex algorithm wherein the kernel and the kernel matrix are updated to increase feasibility of the primal kernel vector in one or more modified simplex iterations until the primal kernel vector is also feasible or until a second termination condition is reached;
• returning, in response to a case when the primal and the dual kernel vectors are feasible as a result of executing the modified primal or dual simplex algorithm, the primal kernel vector (xK) as the vector of variables x to be determined.