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's gravatar image

accept rate: 0%

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%20Pratt's gravatar image

Rob Pratt
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
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: 11 Jan '18, 11:29

Seen: 209 times

Last updated: 15 Jan '18, 13:26

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