Originally posted by: SixtineB

I have coded a column generation procedure with cplex in c++ for solving a vehicle routing problem but at the first iteration, when I get the optimal solution for the primal, everything is fine (objective value = -1697, as expected) but dual variables obtained with cplex.getDuals are all equal to zero and I don't know the reason why.

These values should be non-zero (we should have the sum of the dual variables equal to -1697).

Any ideas for where it can come from? How can I fix this?

You will find enclosed the data file as well as the source file (.cpp) I used to solve only the first iteration (I got inspiration from the ilodiet.cpp file).

Thank you for your explanations and your solution as quickly as possible. I am stuck in this problem since a week.

Originally posted by: T_O

First of all: I did not yet look into your code, so this is just a guess.

A common mistake is not to consider the reduced costs which are the duals of the variable bounds. Did you do this?

Best regards,
Thomas

Originally posted by: SixtineB

What do you mean by "Considering the reduced costs"?

I am just using the function getDuals.

Can you explain me what you mean exactly?

Thank you.

Best regards.

Sixtine

Originally posted by: T_O

An LP in CPLEX typically has the following form:

min  c'x
s.t. Ax <= / == / >= b
     l <= x <= u (where l/u can be infinite)

Now l <= x <= u are variable bounds, but in LP-theory they must be considered as constraints. If you use getDuals, you only obtain the duals for the Ax ... b part, not for the bounds. Their duals are the reduced costs.

If you don't have any variable bounds (typically upper bounds), you can forget my post.

Best regards,
Thomas

Originally posted by: SixtineB

Thank you very much for your answer. Indeed, I had non negative values for these reduced costs.

I thus removed my x<=u constraints and it works.

Thank you so much.

Best regards.

Sixtine

Originally posted by: T_O

You could also leave the bounds as they are, if you use the vector that consists of both the duals and the reduced costs as your dual vector.

What did you do with these upper bounds? Did you move them to the constraints? Are there lower bounds? Are they zero or nonzero?

Best regards,
Thomas

Originally posted by: SixtineB

Yes, now, I got it. I understand that I forgot some dual variables and thus I will have to make some changes. I will take a look at it tomorrow morning.

Thanks again and I won't hesitate to contact you again if necessary.

Best regards.

Sixtine