When solving a linear program with Column Generation (CG), is it possible to obtain a valid lower bound on the Linear relaxation of the Restricted Master Problem (LRMP) at any point during the CG algorithm without solving the pricing subproblem to optimality?

In the paper "Selected Topics in Column Generation" by Lubbecke and Desrosiers (2005), two lower bounds are provided in Section 2.1 but it seems that both require the pricing subproblem to be solved exactly.

asked 30 Nov '15, 19:21

davidrey123's gravatar image

davidrey123
535
accept rate: 0%


If you don't minimize the pricing subproblem, you can instead use a lower bound on the subproblem objective to obtain a lower bound on the master objective. More generally, for bounding purposes you can use any relaxation of the subproblem, although the resulting columns might not be feasible to the subproblem.

link

answered 01 Dec '15, 10:32

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

1

I see your point, makes sense.

(01 Dec '15, 15:39) davidrey123
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
×14

Asked: 30 Nov '15, 19:21

Seen: 723 times

Last updated: 01 Dec '15, 15:39

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