# Inquiry about linear programming solvers and dual variables

 2 I just used Matlab Toolbox `linprog’ and CPLEX to solve a large-scale 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. asked 30 Oct '11, 21:13 bcai 41●1●3 accept rate: 0% fbahr ♦ 4.6k●7●16

 5 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 1.3k●1●5 accept rate: 21% Not just possible, but very common. Sounds like the model is dual degenerate. (01 Nov '11, 17:58) Greg Glockner
 5 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 440●4 accept rate: 0% 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
 1 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.1-32. Olivier du Merle, Daniel Villeneuve, Jacques Desrosiers, Pierre Hansen Stabilized column generation. Discrete Mathematics 194(1-3): 229-237 (1999) answered 21 Dec '11, 18:22 Marco Luebbecke ♦ 3.4k●1●6●15 accept rate: 16%
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 30 Oct '11, 21:13

Seen: 3,048 times

Last updated: 21 Dec '11, 18:22

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.