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

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.


answered 01 Dec '15, 10:32

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%


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



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



Asked: 30 Nov '15, 19:21

Seen: 857 times

Last updated: 01 Dec '15, 15:39

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