Originally posted by: AGV-GDM-PT

Hi,

 

I am trying to find the multiple optimal solutions for a given problem with CPLEX. For doing so, I am using the population pool and setting the parameters as follows:

 

 

In a second phase, I change the objective function of the problem and add the previous function as a constraint that forces it not to be worse than the optimal (hierarchical optimization).

 

Everything seemed to work well until I tested an instance that in the second phase could find more optimal solutions than in the first one.

 

e.g.  

 

********Phase 1*********

 

max f1

subj to: set of constraints 1

 

(4 optimal solutions found)

 

******Phase 2******

 

max f2

 

subj to: set of constraints 1 + f1 >= optimal

 

(10 optimal solutions found)

 

The problem is quite small and I confirmed that the extra optimal solutions in 2 are also optimal solutions for 1.

 

Could I get any help from somebody?

 

Thanks

#CPLEXOptimizers
#DecisionOptimization

Did you call the populate function after each solution?

Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Hi,

 

I called it everytime I wanted to solve a new problem. Was that what you meant by "solution"?

Here is the piece of code I use for each problem I solve:

 

double objpool;

             status = CPXgetsolnpoolobjval(env, lp, l, &objpool);

After changing the problem (change objective function and add constraints) I repeat this code.

 

#CPLEXOptimizers
#DecisionOptimization

I couldn't tell from your original post if you were calling populate immediately (which should work), solving the problem and then calling populate (fine), or just solving the problem (which I think would not find all solutions). What you are doing looks correct to me.

Paul

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Thank you for your reply, Paul.

I cannot also find any error in my code - but something has to be wrong. These results do not make sense.

#CPLEXOptimizers
#DecisionOptimization

Try setting the absolute objective gap to 1e-9 in the first run and EpRHS = 1e-9 (it's minimum value) in the second run and see if you still get more solutions.

In your first pass, you have set both the relative and absolute objective gaps in the pool to 0, meaning a solution is retained only if it is exactly optimal. In the second pass, the initial objective function is now constrained, which means satisfaction of the optimality requirement for the initial objective is controlled by the constraint feasibility tolerance (EpRHS), which defaults to 1e-6. In other words, you're being more relaxed about what should be considered optimal for the original objective in the second pass than in the first pass.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Hi Paul,

 

I got the point and really makes sense. Unfortunately, the problem still remains. 

#CPLEXOptimizers
#DecisionOptimization

What if you loosen the absolute and relative pool gaps (absolute to 1e-6) and leave EpRHS at default? Does it still happen?

Also, what size objective value are we looking at for the first objective?

There may be some nagging rounding error issue at play here.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Today I have been playing with the parameters and still it does not work. The interesting thing is that I created a new problem that was a subset of the starting one and that I knew had more optimal solutions than CPLEX was finding for the starting one.

For this subproblem CPLEX found more solutions... The objective value is 8.

 

In the meanwhile, a colleague run the same problem in COIN-OR and could find all the alternative solutions...

 

I really would like to find out which parameters should be set differentely.

#CPLEXOptimizers
#DecisionOptimization

What version of CPLEX are you using? I bumped into a bug in the solution pool feature back in January. I'm not sure it would apply in your situation (but also not sure it would not). I believe the most recent fix pack squashed it.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

#CPLEXOptimizers
#DecisionOptimization

I think that bug was supposed to be fixed in 12.5.1, but I'm not positive ... and I don't know that I still have the code to test for it.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Paul,

 

Thank you very much for your help. I gave up trying to use populate and am now in the process of handling the problem the "old" way, by adding one constraint every time I find an optimal solution (to prevent that that one is selected again).

 

Ana

#CPLEXOptimizers
#DecisionOptimization

As long as the integer variables are binary, the old-fashioned way should work reliably. It might be faster to use the populate method, add cuts for all the solutions it finds, call populate again ... -- essentially a "batch" version of what you are now doing. Also, if you're going to go one cut at a time, I would do it in a lazy constraint callback rather than doing a fresh solve each time.

Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Thank you for your suggestion, Paul. I will definitely consider it when efficiency becomes relevant. For the time being I am only doing some "pedagogical" tests.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: AGV-GDM-PT

Paul,

 

The problem is finally fixed. The reason for the wrong solutions was that parameter CPX_PARAM_POPULATELIM was to small. By default it is set to 20, which is a very small bound. Thus, before using populate, besides setting all the parameters mentioned before, CPX_PARAM_POPULATELIM should also be set to a sufficiently high value.

#CPLEXOptimizers
#DecisionOptimization

This all sounds really weird. Although I saw that you gave up on that, would you be willing to send us your model (and maybe your code) so that we can take a close look at this issue?

In case you don't want to reveal anything in public you can send the stuff directly to me: daniel(dot)junglas(at)de(dot)ibm(dot)com.

#CPLEXOptimizers
#DecisionOptimization