Topic
• 5 replies
• Latest Post - ‏2013-05-31T08:26:44Z by DanielJunglas
hyunwoona
3 Posts

# Pinned topic Finding all possible sub-optimal(not optimal!!!) solutions in a constraint programming

‏2013-05-24T13:21:13Z | constraint integer programming sub-optimal

Hi. I am writing a CPLEX optimization code to generate a matrix, which takes r and n as the command line arguments, but they may be assumed 2 and 4 for now.

The condition for generating the matrix is that the sum of elements in any row or in any column should equal 10, where the elements are integers between 0 and 10. (i.e. doubly-stochastic matrix)

I turned this condition into the constraint, and generated the matrix, but it only gives a matrix with 10s and 0s.

I think it is because CPLEX always finds the "optimal" solution, but for the problem I want to solve, this is not going to help much.

I want matrices with some 6, 7, 8, 9, 10, and 0~5 for the rest.

I want to generate all possible matrices satisfying such condition (and some more condition to be added later) so that I could test all of them and exhaust the case.

How can I do that?

I am looking into this solution pool thing, and it is not easy..

Also,

cplex.out() << "number of solutions = " << cplex.getSolnPoolNsolns() << endl;

this gives 1... meaning that there is only one solution, while I know there are millions of those matrices.

Thank you.

I attached my code in IPGenMat.cpp, and aa.sol was the solution it gave me.

I also copied it here below.

(In short, two questions: 1. how can I find 'less optimal' solutions? 2. how can I find all of such solutions?)

#include<ilcplex/ilocplex.h>
#include<vector>
#include<iostream>
#include<sstream>
#include<string>

using namespace std;

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Error: " << endl;
return 1;
}
else {
int r, n;
stringstream rValue(argv[1]);
stringstream nValue(argv[2]);

rValue >> r;
nValue >> n;

int N=n*r;
int ds = 10; //10 if doubly-stochastic, smaller if sub-doubly stochastic
IloEnv env;

try {
IloModel model(env);

IloArray<IloNumVarArray> m(env, N);

for (int i=0; i<N; i++) {
m[i] = IloNumVarArray(env, N, 0, 10, ILOINT);

}

IloArray<IloExpr> sumInRow(env, N);

for (int i=0; i<N; i++) {
sumInRow[i] = IloExpr(env);
}

for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
sumInRow[i] += m[i][j];
}
}

IloArray<IloRange> rowEq(env, N);

for (int i=0; i<N; i++) {
rowEq[i] = IloRange(env, ds, sumInRow[i], 10); //doubly stochastic
}

IloArray<IloExpr> sumInColumn(env, N);

for (int i=0; i<N; i++) {
sumInColumn[i] = IloExpr(env);
}

for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
sumInColumn[i] += m[j][i];
}
}

IloArray<IloRange> columnEq(env, N);

for (int i=0; i<N; i++) {
columnEq[i] = IloRange(env, ds, sumInColumn[i], 10); //doubly stochastic
}

for (int i=0; i<N; i++) {
}

IloCplex cplex(env);
cplex.extract(model);
cplex.setParam(IloCplex::SolnPoolAGap,0.0);
cplex.setParam(IloCplex::SolnPoolIntensity,4);
cplex.setParam(IloCplex::PopulateLim, 2100000000);
cplex.populate();//.solve();
cplex.out() << "solution status = " << cplex.getStatus() << endl;
cplex.out() << "number of solutions = " << cplex.getSolnPoolNsolns() << endl;
cplex.out() << endl;
cplex.writeSolutions("aa.sol");

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cplex.out() << cplex.getValue(m[i][j]) << " | ";
}
cplex.out() << endl;
}
cplex.out() << endl;

}
catch(IloException& e) {
cerr << " ERROR: " << e << endl;
}
catch(...) {
cerr << " ERROR: " << endl;
}
env.end();
return 0;
}
}

#### Attachments

Updated on 2013-05-24T13:57:25Z at 2013-05-24T13:57:25Z by hyunwoona
• DanielJunglas
243 Posts

#### Re: Finding all possible sub-optimal(not optimal!!!) solutions in a constraint programming

‏2013-05-29T07:26:57Z

What you need to do is to run populate() with SolnPoolIntensity set to 4 (very aggressive).

This is described in the user manual here.

• hyunwoona
3 Posts

#### Re: Finding all possible sub-optimal(not optimal!!!) solutions in a constraint programming

‏2013-05-29T16:13:48Z

What you need to do is to run populate() with SolnPoolIntensity set to 4 (very aggressive).

This is described in the user manual here.

As you see in my code, SolnPoolIntensity is set to 4 and populate() is called in the following line:

IloCplex cplex(env);
cplex.extract(model);
cplex.setParam(IloCplex::SolnPoolAGap,0.0);
cplex.setParam(IloCplex::SolnPoolIntensity,4);
cplex.setParam(IloCplex::PopulateLim, 2100000000);
cplex.populate();

I do not understand why it gives just one solution.

Do you see anything wrong in my code?

Is it the way I print the output that causes this problem? (does not seem to be so to me though)

Can you fix my code so that it runs well and produces multiple solutions on your computer, please?

Thank you.

• DanielJunglas
243 Posts

#### Re: Finding all possible sub-optimal(not optimal!!!) solutions in a constraint programming

‏2013-05-29T17:59:03Z
• hyunwoona
• ‏2013-05-29T16:13:48Z

As you see in my code, SolnPoolIntensity is set to 4 and populate() is called in the following line:

IloCplex cplex(env);
cplex.extract(model);
cplex.setParam(IloCplex::SolnPoolAGap,0.0);
cplex.setParam(IloCplex::SolnPoolIntensity,4);
cplex.setParam(IloCplex::PopulateLim, 2100000000);
cplex.populate();

I do not understand why it gives just one solution.

Do you see anything wrong in my code?

Is it the way I print the output that causes this problem? (does not seem to be so to me though)

Can you fix my code so that it runs well and produces multiple solutions on your computer, please?

Thank you.

Sorry, I missed in your first post that you are already setting things up correctly.

I reproduced the issue here and found that this is a known problem in CPLEX that was recently found and fixed. Unfortunately, the fix is not in any released version yet.

As a workaround you can disable heuristics:

cplex.setParam(IloCplex::HeurFreq, -1);

That should get populate going and produce different feasible solutions.

• hyunwoona
3 Posts

#### Re: Finding all possible sub-optimal(not optimal!!!) solutions in a constraint programming

‏2013-05-30T13:18:09Z

Sorry, I missed in your first post that you are already setting things up correctly.

I reproduced the issue here and found that this is a known problem in CPLEX that was recently found and fixed. Unfortunately, the fix is not in any released version yet.

As a workaround you can disable heuristics:

cplex.setParam(IloCplex::HeurFreq, -1);

That should get populate going and produce different feasible solutions.

Thank you very much.

It now seems to work.

Can I ask you one more question?

I would like to do some things with all the solutions, grabbing one solution by one solution.

More specifically, I want to

1. print the matrix into the command line, and

2. grab a matrix(one solution), and using the values of the entries as an input to another CPLEX function that I wrote.

3. maybe outputting the matrix to a file

How may I do them?

My attempt was

IloArray<IloNumArray> vals(env, N);

for(int i = 0; i < N; ++i) {
vals[i] = IloNumArray(env)
cplex.getValues(vals[i], m[i]);
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cplex.out() << vals[i][j] << " | ";
}
cplex.out() << endl;

which did not print the solution.

Do you know the right way to do this?

(I know how to output it into a .sol file, but it is not in a pretty form, and I cannot access the solution as easily as with vector.)

Thank you.

Updated on 2013-05-30T13:20:30Z at 2013-05-30T13:20:30Z by hyunwoona
• DanielJunglas
243 Posts

#### Re: Finding all possible sub-optimal(not optimal!!!) solutions in a constraint programming

‏2013-05-31T08:26:44Z
• hyunwoona
• ‏2013-05-30T13:18:09Z

Thank you very much.

It now seems to work.

Can I ask you one more question?

I would like to do some things with all the solutions, grabbing one solution by one solution.

More specifically, I want to

1. print the matrix into the command line, and

2. grab a matrix(one solution), and using the values of the entries as an input to another CPLEX function that I wrote.

3. maybe outputting the matrix to a file

How may I do them?

My attempt was

IloArray<IloNumArray> vals(env, N);

for(int i = 0; i < N; ++i) {
vals[i] = IloNumArray(env)
cplex.getValues(vals[i], m[i]);
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cplex.out() << vals[i][j] << " | ";
}
cplex.out() << endl;

which did not print the solution.

Do you know the right way to do this?