Re: GLPK Dualprices
On Sun, 2022-05-29 at 18:42 +0200, Harald Mumm wrote: > Hi Andrew, > > thank you very much for your help, but I could solve my problem in > the > meantime alone. > > Instead of glp_simplex I use now glp_exact and all dual prices are > the > same as in CPLEX > > for all my examples. You shouldn't expect this even on using the same package on the same platform. The solver may report different optimal solutions depending, say, on the order of variables and constraints in your LP. All optimal solutions are considered equivalent, so the only what matters is that the solution found is optimal. > > Best regards > > Harald > > Am 29.05.2022 um 18:36 schrieb Andrew Makhorin: > > Hi Harald, > > > > > > On Sun, 2022-05-29 at 08:39 +0200, Harald Mumm wrote: > > > Hallo Andrew, > > > > > > is it possible, that GLPK sometimes calculates wrong dual prices? > > > > > > I send you an example in the attachment, where CPLEX calculates > > > > > > other dual prices than GLPK. > > > > Please note that LP may have multiple optimal solutions (in > > degenerate > > cases). This means that some constraint which happen to be active at > > one > > optimum point may be inactive at other optimum point. > > > > I solved your LP with glpsol: > > > > > > GLPSOL--GLPK LP/MIP Solver 5.0 > > Parameter(s) specified in the command line: > > --lp masterg.lp > > Reading problem data from 'masterg.lp'... > > 46 rows, 17 columns, 62 non-zeros > > 77 lines were read > > GLPK Simplex Optimizer 5.0 > > 46 rows, 17 columns, 62 non-zeros > > Preprocessing... > > ~ 0: obj = 3.52776e+03 infeas = 0.000e+00 > > OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR > > Time used: 0.0 secs > > Memory used: 0.0 Mb (45669 bytes) > > > > > > Since the optimal objective value is the same as for cplex, there is > > no > > error. You also may see this from KKT optimality conditions: > > > > > > Karush-Kuhn-Tucker optimality conditions: > > > > KKT.PE: max.abs.err = 0.00e+00 on row 0 > > max.rel.err = 0.00e+00 on row 0 > > High quality > > > > KKT.PB: max.abs.err = 0.00e+00 on row 0 > > max.rel.err = 0.00e+00 on row 0 > > High quality > > > > KKT.DE: max.abs.err = 0.00e+00 on column 0 > > max.rel.err = 0.00e+00 on column 0 > > High quality > > > > KKT.DB: max.abs.err = 0.00e+00 on row 0 > > max.rel.err = 0.00e+00 on row 0 > > High quality > > > > > > Best, > > > > Andrew Makhorin > > > > > > > Sincerely yours > > > > > > Harald, University of Applied Sciences, Wismar Germany > > > > > > > > > PS CPLEX Dualprices: > > > > > > Dual simplex - Optimal: Objective = 3.527760e+03 > > > Solution time = 0.02 sec. Iterations = 0 (0) > > > Deterministic time = 0.02 ticks (1.47 ticks/sec) > > > > > > CPLEX> display solution dual * > > > Constraint Name Dual Price > > > c1 141.55 > > > c2 330.53 > > > c3 318.28 > > > c5 201.94 > > > c7 237.01 > > > c8 283.71 > > > c9 143.44 > > > c10 221.82 > > > c11 130.99 > > > c12 210.35 > > > c13 205.53 > > > c14 175.15 > > > c15 231.34 > > > c17 155.25 > > > c21 192.06 > > > c25 204.17 > > > c41 144.64 > > > All other dual prices matching '*' are 0. > > > > > > PS GLPK Dualprices > > > > > > c1 = 0.0 > > > c2 = 0.0 > > > c3 = 0.0 > > > c4 = 0.0 > > > c5 = 0.0 > > > c6 = 0.0 > > > c7 = 0.0 > > > c8 = 0.0 > > > c9 = 0.0 > > > c10 = 0.0 > > > c11 = 0.0 > > > c12 = 0.0 > > > c13 = 0.0 > > > c14 = 0.0 > > > c15 = 0.0 > > > c16 = 0.0 > > > c17 = 0.0 > > > c18 = 0.0 > > > c19 = 0.0 > > > c20 = 0.0 > > > c21 = 0.0 > > > c22 = 0.0 > > > c23 = 0.0 > > > c24 = 0.0 > > > c25 = 0.0 > > > c26 = 0.0 > > > c27 = 0.0 > > > c28 = 0.0 > > > c29 = 0.0 > > > c30 = 0.0 > > > c31 = 0.0 > > > c32 = 0.0 > > > c33 = 0.0 > > > c34 = 0.0 > > > c35 = 0.0 > > > c36 = 0.0 > > > c37 = 0.0 > > > c38 = 0.0 > > > c39 = 0.0 > > > c40 = 0.0 > > > c41 = 0.0 > > > c42 = 0.0 > > > c43 = 0.0 > > > c44 = 0.0 > > > c45 = 0.0 > > > c46 = 330.53 > > > > >
[Fwd: Re: GLPK Dualprices]
Forwarded Message From: Andrew Makhorin To: Harald Mumm Subject: Re: GLPK Dualprices Date: Sun, 29 May 2022 19:36:20 +0300 > Hi Harald, > > > On Sun, 2022-05-29 at 08:39 +0200, Harald Mumm wrote: > > Hallo Andrew, > > > > is it possible, that GLPK sometimes calculates wrong dual prices? > > > > I send you an example in the attachment, where CPLEX calculates > > > > other dual prices than GLPK. > > Please note that LP may have multiple optimal solutions (in degenerate > cases). This means that some constraint which happen to be active at > one > optimum point may be inactive at other optimum point. > > I solved your LP with glpsol: > > > GLPSOL--GLPK LP/MIP Solver 5.0 > Parameter(s) specified in the command line: > --lp masterg.lp > Reading problem data from 'masterg.lp'... > 46 rows, 17 columns, 62 non-zeros > 77 lines were read > GLPK Simplex Optimizer 5.0 > 46 rows, 17 columns, 62 non-zeros > Preprocessing... > ~ 0: obj = 3.52776e+03 infeas = 0.000e+00 > OPTIMAL SOLUTION FOUND BY LP PREPROCESSOR > Time used: 0.0 secs > Memory used: 0.0 Mb (45669 bytes) > > > Since the optimal objective value is the same as for cplex, there is > no > error. You also may see this from KKT optimality conditions: > > > Karush-Kuhn-Tucker optimality conditions: > > KKT.PE: max.abs.err = 0.00e+00 on row 0 > max.rel.err = 0.00e+00 on row 0 > High quality > > KKT.PB: max.abs.err = 0.00e+00 on row 0 > max.rel.err = 0.00e+00 on row 0 > High quality > > KKT.DE: max.abs.err = 0.00e+00 on column 0 > max.rel.err = 0.00e+00 on column 0 > High quality > > KKT.DB: max.abs.err = 0.00e+00 on row 0 > max.rel.err = 0.00e+00 on row 0 > High quality > > > Best, > > Andrew Makhorin > > > > > > Sincerely yours > > > > Harald, University of Applied Sciences, Wismar Germany > > > > > > PS CPLEX Dualprices: > > > > Dual simplex - Optimal: Objective = 3.527760e+03 > > Solution time = 0.02 sec. Iterations = 0 (0) > > Deterministic time = 0.02 ticks (1.47 ticks/sec) > > > > CPLEX> display solution dual * > > Constraint Name Dual Price > > c1 141.55 > > c2 330.53 > > c3 318.28 > > c5 201.94 > > c7 237.01 > > c8 283.71 > > c9 143.44 > > c10 221.82 > > c11 130.99 > > c12 210.35 > > c13 205.53 > > c14 175.15 > > c15 231.34 > > c17 155.25 > > c21 192.06 > > c25 204.17 > > c41 144.64 > > All other dual prices matching '*' are 0. > > > > PS GLPK Dualprices > > > > c1 = 0.0 > > c2 = 0.0 > > c3 = 0.0 > > c4 = 0.0 > > c5 = 0.0 > > c6 = 0.0 > > c7 = 0.0 > > c8 = 0.0 > > c9 = 0.0 > > c10 = 0.0 > > c11 = 0.0 > > c12 = 0.0 > > c13 = 0.0 > > c14 = 0.0 > > c15 = 0.0 > > c16 = 0.0 > > c17 = 0.0 > > c18 = 0.0 > > c19 = 0.0 > > c20 = 0.0 > > c21 = 0.0 > > c22 = 0.0 > > c23 = 0.0 > > c24 = 0.0 > > c25 = 0.0 > > c26 = 0.0 > > c27 = 0.0 > > c28 = 0.0 > > c29 = 0.0 > > c30 = 0.0 > > c31 = 0.0 > > c32 = 0.0 > > c33 = 0.0 > > c34 = 0.0 > > c35 = 0.0 > > c36 = 0.0 > > c37 = 0.0 > > c38 = 0.0 > > c39 = 0.0 > > c40 = 0.0 > > c41 = 0.0 > > c42 = 0.0 > > c43 = 0.0 > > c44 = 0.0 > > c45 = 0.0 > > c46 = 330.53
[Fwd: GLPK Dualprices]
Forwarded Message From: Harald Mumm To: m...@gnu.org Subject: GLPK Dualprices Date: Sun, 29 May 2022 08:39:28 +0200 > Hallo Andrew, > > is it possible, that GLPK sometimes calculates wrong dual prices? > > I send you an example in the attachment, where CPLEX calculates > > other dual prices than GLPK. > > Sincerely yours > > Harald, University of Applied Sciences, Wismar Germany > > > PS CPLEX Dualprices: > > Dual simplex - Optimal: Objective = 3.527760e+03 > Solution time = 0.02 sec. Iterations = 0 (0) > Deterministic time = 0.02 ticks (1.47 ticks/sec) > > CPLEX> display solution dual * > Constraint Name Dual Price > c1 141.55 > c2 330.53 > c3 318.28 > c5 201.94 > c7 237.01 > c8 283.71 > c9 143.44 > c10 221.82 > c11 130.99 > c12 210.35 > c13 205.53 > c14 175.15 > c15 231.34 > c17 155.25 > c21 192.06 > c25 204.17 > c41 144.64 > All other dual prices matching '*' are 0. > > PS GLPK Dualprices > > c1 = 0.0 > c2 = 0.0 > c3 = 0.0 > c4 = 0.0 > c5 = 0.0 > c6 = 0.0 > c7 = 0.0 > c8 = 0.0 > c9 = 0.0 > c10 = 0.0 > c11 = 0.0 > c12 = 0.0 > c13 = 0.0 > c14 = 0.0 > c15 = 0.0 > c16 = 0.0 > c17 = 0.0 > c18 = 0.0 > c19 = 0.0 > c20 = 0.0 > c21 = 0.0 > c22 = 0.0 > c23 = 0.0 > c24 = 0.0 > c25 = 0.0 > c26 = 0.0 > c27 = 0.0 > c28 = 0.0 > c29 = 0.0 > c30 = 0.0 > c31 = 0.0 > c32 = 0.0 > c33 = 0.0 > c34 = 0.0 > c35 = 0.0 > c36 = 0.0 > c37 = 0.0 > c38 = 0.0 > c39 = 0.0 > c40 = 0.0 > c41 = 0.0 > c42 = 0.0 > c43 = 0.0 > c44 = 0.0 > c45 = 0.0 > c46 = 330.53 > \* Problem: myProblem *\ Minimize obj: + 141.55 x1 + 330.53 x2 + 283.71 x3 + 130.99 x4 + 143.44 x5 + 144.64 x6 + 205.53 x7 + 237.01 x8 + 221.82 x9 + 210.35 x10 + 204.17 x11 + 231.34 x12 + 192.06 x13 + 155.25 x14 + 201.94 x15 + 175.15 x16 + 318.28 x17 Subject To c1: + x1 = 1 c2: + x2 = 1 c3: + x17 = 1 c4: + x17 = 1 c5: + x15 = 1 c6: + x17 = 1 c7: + x8 = 1 c8: + x3 = 1 c9: + x5 = 1 c10: + x9 = 1 c11: + x4 = 1 c12: + x10 = 1 c13: + x7 = 1 c14: + x16 = 1 c15: + x12 = 1 c16: + x2 = 1 c17: + x14 = 1 c18: + x12 = 1 c19: + x15 = 1 c20: + x10 = 1 c21: + x13 = 1 c22: + x8 = 1 c23: + x7 = 1 c24: + x1 = 1 c25: + x11 = 1 c26: + x9 = 1 c27: + x8 = 1 c28: + x14 = 1 c29: + x3 = 1 c30: + x16 = 1 c31: + x14 = 1 c32: + x2 = 1 c33: + x5 = 1 c34: + x9 = 1 c35: + x16 = 1 c36: + x11 = 1 c37: + x10 = 1 c38: + x2 = 1 c39: + x1 = 1 c40: + x12 = 1 c41: + x6 = 1 c42: + x6 = 1 c43: + x13 = 1 c44: + x4 = 1 c45: + x7 = 1 c46: + x17 + x16 + x15 + x14 + x13 + x12 + x11 + x10 + x9 + x8 + x7 + x6 + x5 + x4 + x3 + x2 + x1 = 17 Bounds 0 <= x1 <= 1 0 <= x2 <= 1 0 <= x3 <= 1 0 <= x4 <= 1 0 <= x5 <= 1 0 <= x6 <= 1 0 <= x7 <= 1 0 <= x8 <= 1 0 <= x9 <= 1 0 <= x10 <= 1 0 <= x11 <= 1 0 <= x12 <= 1 0 <= x13 <= 1 0 <= x14 <= 1 0 <= x15 <= 1 0 <= x16 <= 1 0 <= x17 <= 1 End
