Maximize diversity of binary variables in CPLEX java API's populate method with constraint on optimality

Question

I am trying to produce many solutions to a mixed-integer problem in CPLEX with all integer variables as binary. The problem has roughly 1000 continuous variables and 1000 binary variables, serving as indicators, with roughly 2500 linear constraints.

My objective function is a minimization of the indicator variables, and I want to produce many close-to-optimal solutions that differ from one another regarding the values chosen for the binary variables. My current code could be summarized to -

IloCplex cplexModel = new IloCplex(); 
---build the problem, set objective---
cplexModel.setParam(IloCplex.IntParam.SolnPoolCapacity, N);
cplexModel.setParam(IloCplex.IntParam.PopulateLim, K*N);
cplexModel.setParam(IloCplex.IntParam.SolnPoolReplace, 2);
cplexModel.setParam(IloCplex.DoubleParam.SolnPoolGap, D);
cplexModel.setParam(IloCplex.IntParam.MIPEmphasis, 0);
cplexModel.populate();

Where N, K and D are the shortened names for the number of desired solutions, the factor by which I'm willing to scale the number of generated solutions while solving and the relative gap I am willing to accept from the optimal minimization, respectively. I also play with several other CPLEX parameters that do not seem relevant to the issue.

My problem is that the diversity of solutions is measured across all variables, including continuous ones, while I am only interested in solutions that differ in their binary variable values. That means that most of the results I am getting share the same values for binary variables, and are indistinguishable for me (as I am only interested in the binary values). My current workaround is by setting -

cplexModel.setParam(IloCplex.IntParam.SolnPoolCapacity, T*N);
cplexModel.setParam(IloCplex.IntParam.PopulateLim, T*K*N);

with T typically being 50, and then (hopefully) choosing N results from the solution pool which differ from one another in the binary variables' values.

I've checked diversity filters as a way of restricting the diversity calculation to the binary variables, but I don't see how it can be used to enforce diversity among solutions, instead of between each solution and a reference solution. Besides that, I am clueless as to what else can be done.

Help is appreciated. Also, this is my first question, so I apologize if I formatted it wrong.

Answer 1

I've got the answer needed on IBM's forums - link.

The solution pool diversity replacement strategy, SolnPoolReplace=2, only counts binary variables regarding the diversity of the solutions.

It thus seems that my solutions are not diverse, in terms of binary variables, from different reasons, and this strategy is nevertheless the right approach.

Answer 2

Apologies, but my background is doing this the old way, and I was usually working in C# or C++. I've never tried to use this new-fangled "populate" stuff... but I probably should! But maybe some of what I have done in the past might help.

The way that I'd have done this "by hand" is to solve the problem repeatedly in a loop, adding constraints each time round to force some of the binary variables to be different. This could be as simple as adding a constraint to force a single variable to be different (if it is 1 in the solution, try adding a constraint to force it to zero (and vice versa)). Or get a bit more clever and add a constraint that at least n out of m variables must be different. The nice thing about this approach is that it gives you direct control over what and how much of the solution must be different.

Now, it may be possible to achieve something similar inside the "populate" approach by adding constraints via one of the cplex callbacks. I don't have the recent docs to hand, so I am just guessing from memory...

Hope this helps