Let \(A\) be a rational matrix with \(n\) rows and \(m\) columns, \(rhs\) a (column) vector of dimension \(n\) and \(obj\) is a (row) vector of dimension \(m\).
We consider the Linear Programming problem
maximize/minimize \(obj\cdot{x}\), subject to \(Ax \geq rhs\).
‣ LRS_LPSolveMax( A, rhs, obj ) | ( function ) |
‣ LRS_LPSolveMin( A, rhs, obj ) | ( function ) |
If the problem has a solution then the function returns the pair [ x, val ], where \(x\) is the vector of dimension \(m\) which realizes the optimum value \(val\). If the problem is not feasible or not bounded then the function returns [ fail, "No feasible solution" ] or [ fail, "Unbounded solution" ] and the respective info warning will be given.
‣ LRS_Export2FreeMPS( A, rhs, obj, filename ) | ( function ) |
This function exports the LP problem to the free MPS format. This format is used by several more sophisticated LP solvers, for example the GNU Linear Programming Kit GLPK. See the documentation glpk-refman.pdf for detailed description of this format. Moreover, GLPK can be used to convert to problem data in several other formats.
‣ LRS_MaxWeightMatching( m ) | ( function ) |
‣ LRS_MinWeightMatching( m ) | ( function ) |
Let m be a square matrix over the rationals. These commands return the solution of the assigment problem of maximizing/minimizing the objective function \(\sum_{i,j} X_{i,j} m_{i,j}\) with \(0\leq X_{i,j}\leq 1\).
gap> A := [ [ 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2 ], [ -1, -1, 0, -1, -2, -1, -1, -1, 0, -1, -1, 0 ], > [ 5, 0, 0, 3, -1, -1, 1, 1, 1, -3, 0, -2 ], [ 5, 0, 0, 3, -1, -1, 1, 1, 1, -3, 0, -2 ], > [ -9, 1, -1, 0, 0, 0, 3, 0, 0, -1, -1, 2 ], [ -9, 1, -1, 0, 0, 0, 3, 0, 0, -1, -1, 2 ], > [ 12, 2, -2, 0, 0, 0, 0, 0, 0, 4, 1, -2 ], [ -11, -1, 0, 1, 2, 1, 1, 1, -2, -3, 0, 0 ], > [ 3, -2, 2, 0, 0, 0, 3, 0, 0, 3, 0, 0 ], [ 10, 0, 0, -7, 0, 1, -2, 1, 0, 2, -1, -1 ], > [ 10, 0, 0, -7, 0, 1, -2, 1, 0, 2, -1, -1 ], [ -10, 0, 0, 3, -1, -1, -2, 1, -1, 6, 0, 2 ], > [ -10, 0, 0, 3, -1, -1, -2, 1, -1, 6, 0, 2 ], [ 35, 0, 0, 6, -2, 2, 3, 0, -2, 3, 0, 0 ], > [ -5, 0, 0, -3, 1, 1, -1, -1, 0, 3, 0, 0 ], [ -5, 0, 0, -3, 1, 1, -1, -1, 0, 3, 0, 0 ], > [ -15, 0, 0, 8, 2, 0, -3, 0, 0, -7, -1, 0 ], [ 11, 1, 2, 7, 0, -1, -1, -1, 0, 3, 0, 0 ], > [ 24, -1, -2, 8, 2, 0, 0, 0, 2, 8, -1, 0 ], [ -19, 1, 0, 6, -2, 2, -3, 0, 0, -3, 0, 0 ], > [ 16, 1, 0, -6, 2, -2, 0, 0, -2, 0, 0, 0 ], [ 0, 0, 0, -8, -2, 0, 0, 0, 2, 0, 0, 2 ], > [ 9, -1, 0, 0, 0, 0, -3, 0, 0, 1, 1, 0 ], [ 24, -1, -2, 0, 0, 0, 0, 0, 0, -8, 1, 2 ], > [ 36, 1, 2, 0, 0, 0, 0, 0, 0, -4, -1, 0 ], [ -45, 0, 0, 0, 0, 0, 3, 0, 0, 3, 0, -2 ] ];; gap> rhs := [ -1, -23, -45, -45, -231, -231, -252, -253, -483, -770, -770, -990, -990, -1035, -1035, > -1035, -1265, -1771, -2024, -2277, -3312, -3520, -5313, -5544, -5796, -10395 ];; gap> obj := [ 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 1, 2 ];; gap> LRS_LPSolveMax(A,rhs,obj); [ [ 4163/16, -2967/4, -2967/4, 37007/112, 20217/14, 24403/16, -14053/16, 15847/4, 9177/4, 3657/8, -31119/4, -2577/2 ], 551 ]
gap> ma:=RandomMat(5,5); [ [ 0, 2, 1, 0, -1 ], [ 2, -1, 2, 3, 4 ], [ -1, 0, -4, 2, 2 ], [ 0, 3, 2, 3, -4 ], [ 5, 0, 0, 1, -1 ] ] gap> LRS_MinWeightMatching(ma); [ [ [ 1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 0, 1 ], [ 0, 0, 0, 1, 0 ] ], -8 ]
generated by GAPDoc2HTML