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⋅x, subject to Ax ≥ 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 ∑_i,j X_i,j m_i,j with 0≤ X_i,j≤ 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