The invention provides for a computer-implemented method for solving a linear program (LP), the method comprising the steps of: receiving (100) the linear program; determining (101) a kernel K and determining a kernel matrix G of the kernel K, wherein the kernel matrix is a non-singular submatrix of the original matrix; determining (102) a set of non-basic variable indices and a set of extra constraint indices; computing (103) a primal kernel vector (xK) from the determined kernel; computing (104) a dual kernel vector (yK) from the determined kernel; and evaluating (105) the feasibility of the primal kernel vector and of the dual kernel vector.
Please help me write a proper abstract based on the patent claims. CLAIM: 1.-16. (canceled) 17. A non-volatile storage medium with computer-interpretable instructions for reducing an amount of memory space required for a kernel matrix, the computer-interpretable instructions when executed causes a processor of a processing device to: reduce an amount of memory space required for variables of a linear program (LP) on the 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; determine 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; determine 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; compute a primal kernel vector (xK) from the determined kernel such that GxEK=bD, xNK=0; compute a dual kernel vector (yK) from the determined kernel such that yEK=0, (yDK)TG=cBT; evaluate the feasibility of the primal kernel vector and of the dual kernel vector; execute, 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; execute, 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; and, return, 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. 18. The non-volatile storage medium of claim 17, wherein a kernel slack vector sK is calculated such that sK=AxK−b; wherein a kernel reduced cost vector dK is calculated such that (dK)T=cT−(yK)TA; wherein the primal kernel vector is feasible if xK≧0 and sK≧0; and, wherein the dual kernel vector is feasible if yK≧0 and dK≧0. 19. The non-volatile storage medium of claim 17, wherein the matrix of given coefficients is stored in a first copy in a row-wise data structure and in a second copy in a column-wise data structure for executing the modified primal simplex algorithm and the modified dual simplex algorithm respectively, the row-wise data structure and the column-wise data structure being of a same data structure type. 20. The non-volatile storage medium of claim 17, wherein the kernel matrix is stored as part of a data structure comprising the matrix of given coefficients, wherein all nonzero elements in each column of the matrix of given coefficients which are also contained in the kernel matrix are sorted in such a way that all said nonzero elements are grouped together to form an adjacent sequence of rows in each kernel column; wherein all nonzero elements in each row of the matrix of given coefficients which are also contained in the kernel matrix are sorted in such a way that all said nonzero elements are grouped together to form an adjacent sequence of columns in each kernel row; and, wherein the adjacent sequence of rows in each kernel column and also the adjacent sequence of columns in each kernel row are stored in succeeding memory blocks of the data structure. 21. The non-volatile storage medium of claim 17, further comprising computer-interpretable instructions when executed causes the processor of the processing device to: execute the modified dual and the modified primal simplex algorithm, wherein in response to a case when pointers to columns of the kernel matrix are used as input arguments, the modified primal simplex algorithm is executed and wherein in response to a case when pointers to rows of the kernel matrix are used as input arguments, the modified dual simplex algorithm is executed. 22. The non-volatile storage medium of claim 17, further comprising computer-interpretable instructions when executed causes the processor of the processing device to factorize the kernel matrix and storing the generated factorization in a factorization data structure, wherein the factorization is an LU-factorization. 23. The non-volatile storage medium of claim 22, wherein a same factorization data type is used for storing the factors resulting from the factorization and for storing for each of the factors a respective transpose. 24. The non-volatile storage medium of claim 22, further comprising computer-interpretable instructions when executed causes the processor of the processing device to automatically evaluate whether updating the factors with results provided by one of the one or more modified simplex iterations is computationally more expensive than creating the factors in a new factorization step, and to execute a factorization for each modified simplex iteration unless the evaluation returns as result that updating the factors is computationally less expensive than a new factorization. 25. The non-volatile storage medium of claim 17, wherein the computer-interpretable instructions to update the kernel and the kernel matrix when executing modified primal simplex algorithm comprises computer-interpretable instructions to shrink the kernel and the kernel matrix, wherein shrinking comprises removing one first row index (i) from the set of defining constraint indices D, thereby removing a first row being indicated by the first row index from the kernel matrix, and removing one first column index (q) from the set of basic variable indices B, thereby removing a first column being indicated by the first column index from the kernel matrix. 26. The non-volatile storage medium of claim 25, wherein the computer-interpretable instructions to execute each of the modified primal simplex iterations comprises computer-interpretable instructions to execute a pricing step and a ratio test step, wherein in the pricing step the second column index (j) or the first row index (i) is determined, wherein the second column index (j) is determined by selecting a column index (j) such that a dKj≦0 and wherein the first row index (i) is determined by selecting a row index (i) such that yKi≦0; wherein in the ratio test step the second row index (p) and the first column index (q) is determined, wherein the second row index (p) is selected such that p=argmin{λi:iεE} and the first column index (q) is selected such that q=argmin{μj:jεB}, wherein λ and μ represent the step length obtained by fulfilling a bound of the corresponding variable or slack index with equality, wherein in case the first column index (q) is smaller than the second row index (p), the first column index (q) is returned, and wherein in case the first column index (q) is larger than the second row index (p) the second row index (p) is returned. 27. The non-volatile storage medium of claim 26, wherein the computer-interpretable instructions to execute one of the modified primal simplex iterations comprises computer-interpretable instructions to execute a kernel update step, wherein to execute the kernel update step comprises one of the following steps: in a case when the first row index (i) was determined and the first column index (q) was returned, the kernel matrix is shrunk; in a case when the second column index (j) was determined and the second row index (p) was returned, the kernel matrix is extended; in a case when the second column index (j) was determined and the first column index (q) was returned, the column exchange is executed on the kernel matrix; in a case when the first row index (i) was determined and the second row index (p) was returned, the row exchange is executed on the kernel matrix. 28. The non-volatile storage medium of claim 25, wherein the kernel matrix is factorized, thereby generating a LU-factorization, the LU-factorization being updated upon an update of the kernel matrix at least for one modified simplex iteration, wherein updating the LU factorization when exchanging a column or a row is executed according to a Forrest-Tomlin update and wherein updating the LU factorization when shrinking the kernel matrix comprises computer-interpretable instructions to: update the LU factorization, thereby propagating the removal of said determined row and column to the LU factorization, the update of the LU factorization being executed according to either applying a column-wise Forrest-Tomlin update suitable for replacing the first column with a first unit vector having the element 1 in the position of the first row; or to apply a row-wise Forrest-Tomlin update suitable for replacing the first row with a second unit: vector having the element 1 in the position of the first column to be removed from the kernel matrix; or to apply a column-wise Forrest-Tomlin update suitable for replacing the first column with a first unit vector having the element 1 in the position of first row, and to apply a row-wise Forrest-Tomlin update suitable for replacing the first row with a second unit vector having the element 1 in the position of the first column to be removed from the kernel matrix. 29. The non-volatile storage medium of claim 28, wherein the computer-interpretable instructions to execute the LU-factorization when extending the kernel matrix comprises computer-interpretable instructions to: upon determining that the second row has in a previous kernel update step been removed from the kernel matrix while the LU factorization has been updated, the LU factorization is updated by applying a Forrest-Tomlin update suitable for replacing the first unit vector with said second column; upon determining that the second column has in a previous kernel update step been removed from the kernel matrix while the LU factorization has been updated, the LU factorization is updated by applying a Forrest-Tomlin update suitable for replacing the second unit vector introduced with said second row; upon determining that the LU factorization has been updated in a previous kernel update step, the LU factorization is updated by applying a Forrest-Tomlin update being suitable for replacing the first unit vector introduced with said second column and being suitable for replacing the second unit vector introduced in the previous step C) with said second row; and, in all other cases, adding a new row to be computed from the second row to a lower triangular matrix L and adding a new column to be computed from the second column to an upper triangular matrix U, the upper triangular matrix and the lower triangular matrix having been created by the LU-factorization from the kernel matrix. 30. The non-volatile storage medium of claim 17, wherein the computer-interpretable instructions to update the kernel and the kernel matrix when executing modified primal simplex algorithm comprises computer-interpretable instructions to extend the kernel and the kernel matrix, wherein the extension comprises adding a second row index (p) to the set of defining constraint indices D, thereby adding a second row being indicated by the second row index to the kernel matrix, and adding a second column index (j) to the set of basic variable indices B, thereby adding a second column being indicated by the second column index to the kernel matrix. 31. The non-volatile storage medium of claim 17, wherein the computer-interpretable instructions to update the kernel and the kernel matrix when executing modified primal simplex algorithm comprises computer-interpretable instructions to extend the kernel and the kernel matrix, wherein the extension comprises exchanging a column index of the kernel and exchanging a column indicated by said index of the kernel matrix, the exchange comprising removing a first column index (q) from the set of basic variable indices B, thereby removing a first column being indicated by the first column index from the kernel matrix, and adding a second column index (j) to the set of basic variable indices B, thereby adding a second column being indicated by the second column index to the kernel matrix. 32. The non-volatile storage medium of claim 17, wherein the computer-interpretable instructions to update the kernel and the kernel matrix when executing modified primal simplex algorithm comprises computer-interpretable instructions to extend the kernel and the kernel matrix, wherein the extension comprises exchanging a row index of the kernel and exchanging a row indicated by said index of the kernel matrix, the exchange comprising removing a first row index (i) from the set of defining constraint indices D, thereby removing a first row being indicated by the first row index from the kernel matrix, and adding a second row index (p) to the set of defining constraint indices D, thereby adding a second row being indicated by the second row index to the kernel matrix. 33. A data processing system for reducing an amount of memory space required for a kernel matrix, comprising: a processing device with limited memory and a computer processor, the computer processor configured to: reduce an amount of memory space required for variables of a linear program (LP) on the 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; determine 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; determine 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; compute a primal kernel vector (xK) from the determined kernel such that GxBK=bD, xNK=0; compute a dual kernel vector (yK) from the determined kernel such that yEK=0, (yDK)TG=cBT; evaluate the feasibility of the primal kernel vector and of the dual kernel vector; execute, 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; execute, 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; and, return, 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.