I just used Matlab Toolbox `linprog’ and CPLEX to solve a largescale linear program with more than 10000 variables. I got different dual values from the two solvers. Since I use column generation to solve my problem, dual variable is important for the problem solving. Thus, I wonder if it is possible that the numerical errors cause different dual variable values for large scale linear programming. Or, is there other reasons cause the difference of dual values? Thank you very much. 
Are the optimal primal and dual objective values from the two solvers equal? If not, then something weird is going on, but if they are equal, then it's still not suprising that you don't get the same solution, since it's possible for a primal or dual LP to have multiple optimal solutions. answered 30 Oct '11, 21:31 Brian Borchers Not just possible, but very common. Sounds like the model is dual degenerate.
(01 Nov '11, 17:58)
Greg Glockner

The LP min x+y st x+y=1 x,y >= 0 has many optimal solution as Brian writes. One optimizer may report (1,0) and another (0,1) and they could both be totally right. Since the dual problem is an LP then also the dual can have many optimal solutions. Normally column generation will work independent of which dual solution you use. One could for instance argue that you should use a convex combination of all optimal dual solutions because that way the dual solution would contain as much information as possible. All I am saying is that what is the right optimal dual solution to use is not obvious. answered 31 Oct '11, 02:56 Erling Isn't the dual of that: max z st z <= 1 and thus there is only one dual solution? Probably not a good example...
(31 Oct '11, 16:31)
Iain Dunning
1
But you can consider the LP min x+y st x+y=1 x,y >= 0 for the dual problem. Next you can form the primal problem and start the discussion from there.
(01 Nov '11, 02:13)
Erling
Ahhh I see what you meant, OK :)
(01 Nov '11, 13:27)
Iain Dunning
So, I wonder if the column generation could get the optimal solution for the LP if use different optimal dual solution, in case there is many optimal solutions to the LP.
(02 Dec '11, 01:54)
bcai
I do not understand what you are asking but column generation works also in the case the dual optimal solution is unique.
(02 Dec '11, 02:09)
Erling
My previous comment should have been: I do not understand what you are asking but column generation works also in the case the dual optimal solution is NOT unique.
(05 Dec '11, 03:39)
Erling
showing 5 of 6
show 1 more comments

As Erling pointed out, column generation works for every dual optimal solution, it may not even need to be an optimal one, and yes, there may be many of these dual solutions (there may be a whole face of optimal solutions, and the simplex method may terminate in an "arbitrary" vertex of that face). I would like to add: this is actually good news. It has been realized that it may help column generation performace a lot if you take careful choice of the dual solution you use. Here are some pointers to the literature on the topic, but there are many more: J.Desrosiers and M.E.Lübbecke. A primer in column generation. In Column Generation, G.Desaulniers, J.Desrosiers, and M.M.Solomon (Eds.), Springer, 2005, pp.132. Olivier du Merle, Daniel Villeneuve, Jacques Desrosiers, Pierre Hansen Stabilized column generation. Discrete Mathematics 194(13): 229237 (1999) answered 21 Dec '11, 18:22 Marco Luebbecke ♦ 