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

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

‏2013-05-24T13:21:13Z |

 

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.

(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++) {
                model.add(rowEq[i]);
                model.add(columnEq[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
    DanielJunglas
    149 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
    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.

    Thank you for your answer.

    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
    DanielJunglas
    149 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

    Thank you for your answer.

    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
    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?

    If so, please give me some advice.

    (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
    DanielJunglas
    149 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?

    If so, please give me some advice.

    (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.

    There is a 3-argument overload of the getValues() function (see there reference documentation). The 3rd argument in this overload is the index of the solution in the solution pool. Using this overload you should be able to query any solution from the solution pool.