Originally posted by: drmorr
I have written a model to solve the maximum independent set problem, and I want to use populate to generate multiple solutions to the problem, subject to two additional constraints:
1. A particular (user-specified) vertex must be contained in the solution
2. I do not want to find a certain (user-specified) independent set
I implement this by establishing an LP model for the MIS problem, and adding additional constraints/modifying bounds to encode the above criteria. I want to be able to call this multiple times for different values for the above criteria. When I call this function once, it works fine, but when I call it multiple times, I get really weird output. Here's my code:
// Force the solution to contain a particular vertex
x[containing].setBounds(1, 1);
// Restrict a particular independent set from the solution
IloExpr expr(env);
int count = 0;
for (int j = 0; j < restricted.size(); ++j)
if (restricted[j] == 1) { expr += x[j]; ++count; }
IloRange restrCons(env, expr, count - 1);
model.add(restrCons);
cplex.extract(model);
cplex.populate();
// Print out all solutions in the pool
for (int i = 0; i < cplex.getSolnPoolNsolns(); ++i)
{
printf("{ ");
for (int j = 0; j < x.size(); ++j)
if (cplex.getValue(x[j], i) == 1)
printf("%d ", j);
printf("}\n");
}
// Remove the additional constraints
x[containing].setBounds(0, 1);
model.remove(restrCons);
In the above, x is a vector of IndNumVars indicating whether vertex i is contained in the independent set or not, and restricted is a boolean vector that describes a restricted set. I have a very simple graph I call this on:
2--1--4--3 5--6
I call the function the first time with containing = 1 and restricted = {1,3,5}. The output from this function is as expected:
{ 1 3 6 }
However, when I call this function a second time with containing = 2 and restricted = {1,3,5}, I get the following output:
{ 1 3 6 }
{ 2 4 5 }
{ 2 3 6 }
{ 2 4 6 }
As you can see, the first produced solution does not contain vertex 2. For some reason, it seems to have been holding on to a solution from the previous pool, and printing it out somehow. The weird thing is that adding the following bit of code immediately after the populate call fixes it:
for (int j = 0; j < x.size(); ++j)
cplex.getValue(x[j], -1);
Then the output from the first call is
{ 1 3 6 }
and the output from the second call is
{ 2 3 5 }
{ 2 4 5 }
{ 2 3 6 }
{ 2 4 6 }
Am I doing something wrong either with the model set up or solution methods, or is this some weird bug with CPLEX? Any suggestions for how to fix this?
#CPLEXOptimizers#DecisionOptimization