# Best Bound of LP during column generation?

 0 Hi, I am solving an minimization LP with a subset of variables, and then calculating the reduced costs of all the variables in the master problem using shadow prices, then adding those to the master problem and iteratively re-solving until there are no variables with good reduced costs. My problem is, many of the last iterations of the column generation loop only add a few variables and only improve the objective function by an infinitesimal and meaningless amount. My question is, is there any way to calculate a best bound using results from the initial solve, so that I can terminate the column gen when the objective converges to that number? I remember reading something about taking the objective of the initial solve and subtracting/adding all the dual costs or something, but I keep getting a negative number. Thanks, Nathan Petty asked 11 Jan '18, 11:29 gtg489p 33●1●4 accept rate: 0%

 1 Each restricted master feasible solution yields an upper bound. Each restricted master LP lower bound + subproblem lower bound yields a lower bound. See Section 11.3 of Wolsey's Integer Programming, where the objective sense is maximization instead. answered 11 Jan '18, 12:54 Rob Pratt 1.2k●2●6 accept rate: 28% Thanks Rob, do you happen to have an excerpt handy from 11.3 of Wosley's IP? I have checked 2 libraries nearby and neither have it. I am not running a subproblem, per se. I evaluate variables not in the master problem by taking their obj coef and subtracting corresponding shadow prices. (15 Jan '18, 09:07) gtg489p No, I cannot post copyrighted material here. But the basic idea to generating a bound is to construct a dual feasible solution. If $$\pi_i$$ is the dual variable for master linking constraint $$i$$, $$\mu_k$$ is the dual variable for the master convexity constraint for block $$k$$, and $$\zeta_k$$ is the minimum reduced cost for block $$k$$, then $$(\pi, \mu + \zeta)$$ is dual feasible. (15 Jan '18, 10:51) Rob Pratt
 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:

Seen: 432 times

Last updated: 15 Jan '18, 13:26