I am using Python's PULP and CBC solver.

Does col gen for TSP make sense? If so, would the sub problem be a knapsack problem? (the knapsack is the sub problem for the cutting stock problem) which is the only example of col gen I could find anywhere.

The aim is to start with some subset of edges, solve the TSP and deal with subtours, and then solve a sub problem to determine good candidate edges to enter the primal.

PS. I understand that branch and price does this in a way during each step. My concern there is that branch and price would run slower, and I would like to have more control over which columns enter the problem and have the option to save these columns in my database for future solves to be added from the get-go.

asked 13 Sep '17, 11:39

gtg489p's gravatar image

gtg489p
3314
accept rate: 0%


This depends partly on your formulation. If your variables represent arcs and your constraints are "enter node once", "leave node once" and assorted subtour elimination constraints, you would not really need a subproblem, because you would just be pricing heretofore excluded arcs to see which one(s) to add. So you would could so something like solve the restricted master problem (IP), fix the variables for unused arcs to zero, solve the LP relaxation of what's left (to get shadow prices for the enter-once and exit-once constraints), use the shadow prices to get reduced costs for arcs not in the restricted master, pick one or more with favorable reduced costs, add them to the restricted master and iterate. If you use the Miller-Tucker-Zemlin formulation to eliminate subtours, you would also need to incorporate the shadow prices of those constraints.

Another approach would be to use, in the restricted master, 0-1 variables not for individual edges but for simple (cycle-free) paths between pairs of nodes. The subproblem then would be to search for path with most favorable reduced cost.

Do either of those make sense in terms of speeding up the solution process relative to "standard" formulations? I have no idea.

link

answered 13 Sep '17, 14:36

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thanks Paul. Col gen for 0/1 binary variables may actually not make much sense in this case because the very act of including it in the basis (the result of some sub problem) is in fact the decision in its entirety and there would be no follow up "decision of magnitude" per se for the master problem to do after that.

As for your second suggestion, it's interesting but I would like to confirm this would add (n choose 2) more variables. For a problem size of 500 nodes, this adds about 125k variables. The base problem has 250k variables already so this about a 50% increase in the number of variables. Since subtours are not a significant problem for my particular problem, it may not be worth it.

Essentially I am looking for a way to quickly analyze the problem before solving to identify a subset of edges that would likely never be in the basis. If less than 1% of 1% of the edges are in any given solution, there must be some way to audit the edges beforehand for goodness.

(14 Sep '17, 09:41) gtg489p

A key aspect of column generation (when it works) is that you are embedding the original problem in a larger variable space (i.e., zillions of potential columns), but the vast majority of the potential columns never see the light of day. That's how it works with cutting stock: there are more potential patterns (the new variables) than cut points (original variables), but only a small fraction of patterns are ever generated.

(14 Sep '17, 15:54) Paul Rubin ♦♦

Thinking a bit more about the path generator subproblem, you'd have to be a bit careful. The cost of an arc would be the true cost adjusted by the shadow prices of leaving the source and entering the sink, and would (frequently?) be negative. So you'd need a shortest path algorithm that was comfortable with negative arc lengths. That said, I really have no idea if this would do anything useful. I think Rob's reference is worth checking.

(14 Sep '17, 15:59) Paul Rubin ♦♦

See Chapter 12 of The Traveling Salesman Problem: A Computational Study by Applegate, Bixby, Chvatal, and Cook for a discussion of the "core LP" approach.

link

answered 14 Sep '17, 14:24

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

1

Bought the book and have been reading. No silver bullet yet... but it's got some interesting practical implementation descriptions. Will reply back with solution if I find one, and will remain open for suggestions form anyone here during the next few weeks as I work on it. Thanks, Nathan

(22 Sep '17, 10:47) gtg489p

As far as I know, one of the most successful exact solution methods for the TSP with Time Windows is exactly based on column generation. See New state-space relaxation for solving the travelling salesman problem with time windows available here. If I am not mistaken, the columns correspond to elementary (although not necessarily Hamiltonian) tours.

link

answered 25 Sep '17, 04:57

Alberto%20Santini's gravatar image

Alberto Santini
11
accept rate: 0%

Thanks Albert! Thankfully my problem does not require time windows. Nevertheless this is an interesting read and perhaps useful if I restructure my decision variables away from representing edges and into representing paths/tours. Thanks, Nathan

(25 Sep '17, 07:54) gtg489p

I have made some gains on this problem, which I plan on explaining in detail here after testing proves, but I had another question related: Does anyone have any good ideas for deciding which variables to price to enter problem? Obviously I'm doing col gen because there's too many variables, so I start with a subset of vars containing a nearest neighbor initial solution and then I price the other variables to see which should enter. but there are so many variables to price, even that takes a while (albeit and thankfully no where near as long as including them in the first place, but still pretty slow)

So, looking for suggestions on how to decide for complete graph ATSP, which edges to price. I'm reading the book Rob suggested, and it discusses this, but I wanted to know if anyone here had an idea too. Thanks, Nahtan

link
This answer is marked "community wiki".

answered 06 Oct '17, 12:28

gtg489p's gravatar image

gtg489p
3314
accept rate: 0%

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
×56
×18
×3

Asked: 13 Sep '17, 11:39

Seen: 633 times

Last updated: 06 Oct '17, 14:42

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