I'm trying to implement column generation for an inventory-routing type model in AMPL, using CPLEX 11 as the solver. I'm finding that my pricing problem is generating columns that have been generated in previous iterations, or that were part of the initial set of columns in the restricted master problem. Is this a definite indication that I've made a mistake in formulating my problems, in my AMPL code, or is this theoretically possible? I've tried to look for examples of this in the literature, but can't find anything.

asked 04 Aug '10, 17:04

AnORStudent's gravatar image

AnORStudent
323315
accept rate: 0%

Update: thanks for confirming what I thought was the case - with a linear master problem I can't possibly be adding the same column multiple times. I'll look at my formulation and code carefully and if I still can't find an answer I'll post more details about the model.

(04 Aug '10, 19:42) AnORStudent

It was in fact a stupid mistake in my code. I made a mistake when passing the values of the dual variables from the master problem to the pricing problem.

(05 Aug '10, 17:59) AnORStudent

If your master problem is a linear program, then it's almost surely an error in your code. The objective function in the column generation problem is typically the reduced cost of a new column in the master problem. If the reduced cost has the correct sign, the new column cannot be one that you've already seen, because that column is already in the master problem and must have a zero or unfavorable reduced cost. If the reduced cost is zero, the new column might or might not be one you've already seen, but in any case you will not want to add it. If the reduced cost has an unfavorable sign (and is off zero by more than rounding error), than your code is wrong (i.e., this can't happen legitimately). The only exception would be if you were dropping columns from the master problem if they had not recently been basic, in which case there would be a distinct possibility of rediscovering them.

Be sure that your subproblem objective is the full reduced cost, which frequently includes a constant term -- or else, rather than testing the sign of the subproblem objective, test whether it is greater than (or less than, whichever is relevant) the appropriate constant.

link

answered 04 Aug '10, 18:18

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k513
accept rate: 19%

As Paul says, in the linear case, you use the objective returned from the subproblem as a termination criteria. But I suspect you already know this, since you must have read up on column generation before using it. I think we need more information on what you actually do, otherwise it's hard to help. What type of restricted master and sub problem do you have ?

link

answered 04 Aug '10, 18:25

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

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

Tags:

×231
×190

Asked: 04 Aug '10, 17:04

Seen: 3,576 times

Last updated: 04 Aug '10, 18:25

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