Originally posted by: abhzap

Hi All,

      I have a column generation model which works optimally for small problem instances.

      However, I have noticed that when I use larger problem instances, I get different results for the same set of inputs i.e. same CG model gives different results when run multiple times for the same input parameters.

      Note : I have 4 pricing problems which are in a round-robin fashion with the master problem.

      I read somewhere that CPLEX introduces random starts while looking for solutions, and since my problem is making multiple calls to CPLEX, is it affecting the way the final master ILP is solved?

      Any insight on this behavior of my CG model will be much appreciated.

Best,

Abhishek Gupta

Just to clarify: You solve the same problem instance on the same machine with the exact same setup and see different results?

Is the difference in the objective value or do you get different solution vectors that have the same objective value?

In any part of your algorithm, do you use anything that may cause non-deterministic behavior? Things like time limits, setting CPX_PARAM_PARALLELMODE to -1, or using some sort of multi-threading that is not deterministic?

Originally posted by: abhzap

Hi Daniel,

      Thank you for the response.

      I solve the same problem instance on the same machine but with different initial solutions and see different results. 

      I wanted to check whether the CG terminates at close to the same solution even when a 2 different initial solution.

      The difference  is both in the RMP ILP objective value and RMP ILP solution vectors.

       I do not use any parallelism/multi-threading.

       The pricing problems are solved in a round-robin fashion, meaning I solve 1 pricing problem and after making the reducing cost non-negative, move on to the next-one.

       The sequence of solving the pricing problem i.e.  pp1 -->  pp2 -->pp3 also remains the same between different runs of the same problem instance.

If you start from two different solutions then it is quite expected that the solution path looks different. However, if your algorithm is correct then it should  arrive at a solution with the same objective value. From what you describe this looks like a potential problem in your algorithm rather than CPLEX.