Topic
4 replies Latest Post - ‏2013-05-28T20:36:59Z by hyunwoona
hyunwoona
hyunwoona
3 Posts
ACCEPTED ANSWER

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

‏2013-05-23T20:38:27Z |

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++) {
                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

  • Philippe_Refalo
    Philippe_Refalo
    5 Posts
    ACCEPTED ANSWER

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

    ‏2013-05-24T07:15:38Z  in response to hyunwoona

     

    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
      hyunwoona
      3 Posts
      ACCEPTED ANSWER

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

      ‏2013-05-24T21:30:05Z  in response to Philippe_Refalo

      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++) {
                      model.add(rowEq[i]);
                      model.add(columnEq[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
        ol
        32 Posts
        ACCEPTED ANSWER

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

        ‏2013-05-27T09:06:07Z  in response to hyunwoona

        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
          hyunwoona
          3 Posts
          ACCEPTED ANSWER

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

          ‏2013-05-28T20:36:59Z  in response to ol

          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!