# Lower bound during column generation

 3 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 53●5 accept rate: 0%

 2 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 Pratt 1.2k●2●6 accept rate: 28% 1 I see your point, makes sense. (01 Dec '15, 15:39) davidrey123
 toggle preview community wiki

By Email:

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: