Hi, I am a beginner and Iam trying to solve a VRPTW model on cplex but the model that I have contains only a reduced subset of tours (columns) and a set-partitioning formulation is used because requests must be served exactly once. in this case do i need to generate a subproblem and use the column generation methode with cplex?

asked 27 Feb '15, 05:19

dadad's gravatar image

dadad
112
accept rate: 0%

converted to question 27 Feb '15, 09:16

fbahr's gravatar image

fbahr ♦
4.6k716


If the initial collection of tours is sufficient robust that a feasible solution exists using them, and if you are content to settle for the best solution using only those tours, then I do not think you will need to do column generation. On the other hand, if you are looking for the best overall solution, and you have no assurance that the initial collection of tours includes all tours from the optimal solution, then you probably will need to use column generation.

As an aside, CPLEX is not designed for column generation, in the sense that you cannot alter a model (add columns) while it is being solved. Using one of the programming APIs, you can write code that iterates back and forth between a master model and a subproblem, adding tours to the master problem and then solving it (again) before switching back to the subproblem, etc., ad nauseum. You might also get some mileage out of one of the projects at COIN-OR (in the "Optimization deterministic linear discrete" section), some of which I believe can use CPLEX as the LP solver.

link

answered 27 Feb '15, 16:49

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

2

adding to what @Paul says: column generation is one thing, but obtaining integer solutions is another, and CPLEX (not even the APIs) is made for this. For true branch-and-price, go for COIN-OR or (I prefer) SCIP.

(27 Feb '15, 18:18) Marco Luebbecke ♦

Hello,

Back to Paul answer, in the case of trying column generation with CPLEX, as you mentioned repeting the steps - Solve RMP - Solve subproblem - Add new columns if possible and restart until an stopping criteria is met

Can be done with CPLEX? and you are referring with your answer that a B&P cannot be done, right?

On the other hand, I am implemeting my first column generation, and I wonder once the column generation is over and I can have a fractional solution and I require an integer one, what to do you advice in that case, use for example cplex conversion command, to redefine the variables associated to the columns that can be real value, would that be a good option, or what do you advice

Thanks!!

P.S: Any further advice for a really interested self-learner would be very good welcome!

link

answered 18 Apr '15, 11:44

thinkOR's gravatar image

thinkOR
11116
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:

×191
×8

Asked: 27 Feb '15, 05:19

Seen: 1,995 times

Last updated: 18 Apr '15, 11:44

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