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's gravatar image

bcai
4113
accept rate: 0%

retagged 07 Dec '11, 08:33

fbahr's gravatar image

fbahr ♦
4.6k716


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.

link

answered 30 Oct '11, 21:31

Brian%20Borchers's gravatar image

Brian Borchers
1.3k15
accept rate: 21%

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.

link

answered 31 Oct '11, 02:56

Erling's gravatar image

Erling
4404
accept rate: 0%

edited 01 Nov '11, 02:14

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.1-32.

Olivier du Merle, Daniel Villeneuve, Jacques Desrosiers, Pierre Hansen Stabilized column generation. Discrete Mathematics 194(1-3): 229-237 (1999)

link

answered 21 Dec '11, 18:22

Marco%20Luebbecke's gravatar image

Marco Luebbecke ♦
3.4k1615
accept rate: 16%

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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:

×231
×18
×2

Asked: 30 Oct '11, 21:13

Seen: 3,048 times

Last updated: 21 Dec '11, 18:22

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