Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only

  • 1.  Finding all possible sub-optimal solutions in a constraint programming

    Posted 05/23/13 04:38 PM

    Originally posted by: hyunwoona


    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;
        }
    }

    #ConstraintProgramming-General
    #DecisionOptimization


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

    Posted 05/24/13 03:16 AM

    Originally posted by: Philippe_Refalo


     

    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
     

    #ConstraintProgramming-General
    #DecisionOptimization


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

    Posted 05/24/13 05:30 PM

    Originally posted by: hyunwoona


    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;
        }
    }

    #ConstraintProgramming-General
    #DecisionOptimization


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

    Posted 05/27/13 05:06 AM

    Originally posted by: ol


    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


    #ConstraintProgramming-General
    #DecisionOptimization


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

    Posted 05/28/13 04:37 PM

    Originally posted by: hyunwoona


    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!


    #ConstraintProgramming-General
    #DecisionOptimization


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

    Posted 08/06/14 01:59 PM

    Originally posted by: ZohraZohra


    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[]>();
     lists.add(new int[]{12,43,5,0,9,10,13});
     lists.add(new int[]{18,12,4,56,1});
     lists.add(new int[]{25,90,0,47,33,15});
     lists.add(new int[]{45,290,7});
     
     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.add(constraint);
     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


    #ConstraintProgramming-General
    #DecisionOptimization


Related Content