Topic
• 5 replies
• Latest Post - ‏2014-08-06T17:58:45Z by ZohraZohra
hyunwoona
3 Posts

Pinned topic Finding all possible sub-optimal solutions in a constraint programming

‏2013-05-23T20:38:27Z | 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.

If you have any ideas how to generate all the 'sub-optimal' matrices, please help me.

Thank you.

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

I also copied it here below.

Thank you.

#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

• Philippe_Refalo
9 Posts

Re: Finding all possible sub-optimal solutions in a constraint programming

‏2013-05-24T07:15:38Z

Hi,

This is a constraint programming forum, if you want to use CPLEX for your problem, you need to post your question to one of these forums : https://www.ibm.com/developerworks/community/forums/html/category?id=33333333-0000-0000-0000-000000000261

However, constraint porgramming is a good approach for finding many or all solutions to a mathematical model. To use CP Optimizer (included in the COS software) all you need to do it to include <cp.h> and to use IloCP to solve the model:

IloCP cp(model);

if you need to find all solutions then a loop like this can do the job:

cp.startNewSearch();
while(cp.next()){
// Handle solution
}

For efficiency reasons, CP optimizer will not necessarily find distinct solutions. To find all district solutions you need to use depth-first search by setting the parameter:

cp.setParameter(IloCP::SearchType, IloCP::DepthFirst);

Additionally, to constrain the occurences of some values you can use the IloCount constraint. For instance IloCount(varArray, 6) >= 4 ensures that, among the variables of the array varArray, at least 4 are assigned to the value 6.

Hope this helps

Philippe

• hyunwoona
3 Posts

Re: Finding all possible sub-optimal solutions in a constraint programming

‏2013-05-24T21:30:05Z

Hi,

This is a constraint programming forum, if you want to use CPLEX for your problem, you need to post your question to one of these forums : https://www.ibm.com/developerworks/community/forums/html/category?id=33333333-0000-0000-0000-000000000261

However, constraint porgramming is a good approach for finding many or all solutions to a mathematical model. To use CP Optimizer (included in the COS software) all you need to do it to include <cp.h> and to use IloCP to solve the model:

IloCP cp(model);

if you need to find all solutions then a loop like this can do the job:

cp.startNewSearch();
while(cp.next()){
// Handle solution
}

For efficiency reasons, CP optimizer will not necessarily find distinct solutions. To find all district solutions you need to use depth-first search by setting the parameter:

cp.setParameter(IloCP::SearchType, IloCP::DepthFirst);

Additionally, to constrain the occurences of some values you can use the IloCount constraint. For instance IloCount(varArray, 6) >= 4 ensures that, among the variables of the array varArray, at least 4 are assigned to the value 6.

Hope this helps

Philippe

Hi.

Do you mean that if I add the same model to IloCP instead of IloCPLEX, and do the things you said, it gives what I want?

Well... then, could you check the code I modified?

I am having errors, but all of them are coming from linking.

The compiling command I used is:

g++ -DIL_STD -I/util/cplex/cplex/include -I/util/cplex/concert/include -I/util/cplex/cpoptimizer/include IPGenMatCP.cpp -L/util/cplex/cplex/lib/x86-64_sles10_4.1/static_pic -L/util/cplex/cpoptimizer/lib/x86-64_sles10_4.1/static_pic -L/util/cplex/concert/lib/x86-64_sles10_4.1/static_pic -lconcert -lilocplex -lcplex -lcp -lm -pthread

Do you see any problem either in my compiling command or in my code, or both?

If you know the way to accomplish what I want to do, could you actually try running it?

If you can't, just your correction for the code would be greatly appreciated.

Thank you very much.

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

using namespace std;

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Error: command-line arguments r and n not given" << 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++) {
}

IloCP cp(env);
cp.extract(model);
cp.solve();

cp.startNewSearch();

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

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

Attachments

Updated on 2013-05-24T21:30:35Z at 2013-05-24T21:30:35Z by hyunwoona
• ol
51 Posts

Re: Finding all possible sub-optimal solutions in a constraint programming

‏2013-05-27T09:06:07Z
• hyunwoona
• ‏2013-05-24T21:30:05Z

Hi.

Do you mean that if I add the same model to IloCP instead of IloCPLEX, and do the things you said, it gives what I want?

Well... then, could you check the code I modified?

I am having errors, but all of them are coming from linking.

The compiling command I used is:

g++ -DIL_STD -I/util/cplex/cplex/include -I/util/cplex/concert/include -I/util/cplex/cpoptimizer/include IPGenMatCP.cpp -L/util/cplex/cplex/lib/x86-64_sles10_4.1/static_pic -L/util/cplex/cpoptimizer/lib/x86-64_sles10_4.1/static_pic -L/util/cplex/concert/lib/x86-64_sles10_4.1/static_pic -lconcert -lilocplex -lcplex -lcp -lm -pthread

Do you see any problem either in my compiling command or in my code, or both?

If you know the way to accomplish what I want to do, could you actually try running it?

If you can't, just your correction for the code would be greatly appreciated.

Thank you very much.

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

using namespace std;

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Error: command-line arguments r and n not given" << 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++) {
}

IloCP cp(env);
cp.extract(model);
cp.solve();

cp.startNewSearch();

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

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

Hello,

your code compiles links and runs on my machine, you can remove #include<ilcplex/ilocplex.h>.

For the link problem, you can take the compilation flags for the cpotimizer examples,

Regards,

Olivier

• hyunwoona
3 Posts

Re: Finding all possible sub-optimal solutions in a constraint programming

‏2013-05-28T20:36:59Z
• ol
• ‏2013-05-27T09:06:07Z

Hello,

your code compiles links and runs on my machine, you can remove #include<ilcplex/ilocplex.h>.

For the link problem, you can take the compilation flags for the cpotimizer examples,

Regards,

Olivier

Thank you.

It worked fine with a correct compiling command.

I lastly have a couple of questions.

1. Do you know how this differs from CPLEX solution pool thing?(that one involved setting more parameters and settings)

2. If I decide to use this, how do I make sure that this exhausts all possible cases?(I will add some more constraints and make the pool of possible values manageable)

3. I tested it with a small input, ./a.out 1 2, and it seemed to exhaust the possible cases but it gave 5~6 same matrices for each case.

For example, I found the same 2 X 2 matrix

2 8

8 2

for 5 times. (Also, 2 8 / 8 2 matrix is equivalent with 8 2 / 2 8 for the case I want to test)

Is this because the input size is too small? or is it something else? (my input will be larger than that, e. g. 2 4, 2 8, 2 12, 3 4, 3 8, etc) Is there any way to fix it?

Sorry for asking too many questions, and thank you very much!

• ZohraZohra
2 Posts

Re: Finding all possible sub-optimal solutions in a constraint programming

‏2014-08-06T17:58:45Z
• hyunwoona
• ‏2013-05-28T20:36:59Z

Thank you.

It worked fine with a correct compiling command.

I lastly have a couple of questions.

1. Do you know how this differs from CPLEX solution pool thing?(that one involved setting more parameters and settings)

2. If I decide to use this, how do I make sure that this exhausts all possible cases?(I will add some more constraints and make the pool of possible values manageable)

3. I tested it with a small input, ./a.out 1 2, and it seemed to exhaust the possible cases but it gave 5~6 same matrices for each case.

For example, I found the same 2 X 2 matrix

2 8

8 2

for 5 times. (Also, 2 8 / 8 2 matrix is equivalent with 8 2 / 2 8 for the case I want to test)

Is this because the input size is too small? or is it something else? (my input will be larger than that, e. g. 2 4, 2 8, 2 12, 3 4, 3 8, etc) Is there any way to fix it?

Sorry for asking too many questions, and thank you very much!

Hello,

I have the same problem but I use the java API of cp optimizer. The problem is described as follows

I have a set of lists of integers which are:

- list1 = {12,43,5,0,9,10,13}

-list2 = {18,12,4,56,1}

- list3 = {25,90,0,47,33,15}

-list4 = {45,290,7}

and i have 2 variables (domain1 = {12,19,22,0} and domain2 = {100,2,45,33,25,13})

the constraint is : the 2 variables must be in the same list for example {12,13} because both 12 and 13 are in list1, also {0,33} because 0 and 33 are in list3

I want to obtain all the possible solutions, also i want to have distinct solutions (without repetition)

I execute the code but it gives some repeated solutions.

The code what i use is:

import ilog.cp.*;
import ilog.concert.*;

import java.util.ArrayList;

public class Test2 {

public static void main(String[] args) throws IloException {

ArrayList<int[]> lists=new ArrayList<int[]>();

int[] domain1=new int[]{12,19,22,0,13};
int[] domain2=new int[]{100,2,45,33,25,13};

IloCP cp=new IloCP();
IloIntVar[] vars=new IloIntVar[2];
vars[0]=cp.intVar(domain1);
vars[1]=cp.intVar(domain2);
IloConstraint constraint=cp.and(cp.member(vars[0],lists.get(0)),cp.member(vars[1],lists.get(0)));
for(int i=1;i<lists.size();i++)
constraint=cp.or(constraint,cp.and(cp.member(vars[0],lists.get(i)),cp.member(vars[1],lists.get(i))));
cp.setParameter(IloCP.IntParam.LogVerbosity,
IloCP.ParameterValues.Quiet);
cp.startNewSearch();
while(cp.next())
{
System.out.println("Solution: "+cp.getValue(vars[0])+" and "+cp.getValue(vars[1]));
}
}
}

the displayed result is:

Solution: 0.0 and 13.0
Solution: 0.0 and 13.0
Solution: 0.0 and 13.0
Solution: 0.0 and 13.0
Solution: 0.0 and 25.0
Solution: 0.0 and 25.0
Solution: 0.0 and 33.0
Solution: 0.0 and 25.0
Solution: 0.0 and 33.0
Solution: 0.0 and 33.0
Solution: 13.0 and 13.0
Solution: 0.0 and 33.0
Solution: 12.0 and 13.0
Solution: 12.0 and 13.0
Solution: 0.0 and 33.0
Solution: 12.0 and 13.0
Solution: 13.0 and 13.0

Thanks for your help