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 resolving 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 
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 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
