Decision Optimization

Decision Optimization

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

 View Only
Expand all | Collapse all

Questions on parallel solving in Java API

Archive User

Archive UserThu February 06, 2020 08:10 PM

  • 1.  Questions on parallel solving in Java API

    Posted Thu February 06, 2020 08:10 PM

    Originally posted by: brown_rice


    Hello,

     

    I have some questions and would really appreciate if someone could answer. 

     

    i) Is it possible to do parallel solving within a callback function? Suppose I implement lazy constraint callback function, and would like to solve multiple problems concurrently rather than iteratively. 

    ii) If it is possible, is there an example shipped by CPLEX on parallel solving?

    iii) As far as I know, when CPLEX solves an LP, it implements four methods all together. If I have four cores on my computer, does that mean CPLEX uses all of them? In other words, can't I take advantage of parallel solving in such a case? 


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Questions on parallel solving in Java API

    Posted Fri February 07, 2020 05:01 AM

    For 1 and 2 I am not clear what you mean. If you register a LazyConstraintCallback then CPLEX will automatically swith to single-threaded mode. You can revert this by setting the Threads parameter to a number larger than 1 (for example to IloCplex.getNcores()). This way you can use a LazyConstraintCallback in a multi-threaded solve. If you want to solve multiple problems in parallel then just create multiple instances of IloCplex and one callback instance for each of them.

    For 3: by default CPLEX uses all threads available to solve the initial root relaxation.


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Questions on parallel solving in Java API

    Posted Fri February 07, 2020 08:24 AM

    Originally posted by: brown_rice


    Daniel, thanks for your answers and I'm sorry if my questions were not clear. 

     

    " If you register a LazyConstraintCallback then CPLEX will automatically swith to single-threaded mode. You can revert this by setting the Threads parameter to a number larger than 1 (for example to IloCplex.getNcores())." Yes, I am familiar with this and plan to go with the single-threaded mode. 

     

    "If you want to solve multiple problems in parallel then just create multiple instances of IloCplex and one callback instance for each of them."  This is exactly what my question was. My initial thought was that I should create a single callback function and solve all the sub problems in parallel within that function. This actually leads me to the second question. Is there an example provided by CPLEX showing how to do parallel solving? For instance, there is an example provided for OPL here.  or Did you actually mean that when implementing multiple callback functions, CPLEX automatically solves them in parallel?

     

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: Questions on parallel solving in Java API

    Posted Mon February 10, 2020 03:27 AM

    There is no example for this in CPLEX since it heavily depends on the programming API you use *and* because this should be simple enough. The definition of your callback class is completely independent of the fact that you solve multiple models in parallel. You don't need a different class definition for each thread. You only need a different instance for each thread.

    A very simple (untested) code to solve multiple models in parallel could be this:

    Thread threads = new Thread[NTHREADS];
    // Initialize the threads
    for (int i = 0; i < NTRHEADS; ++i) {
      threads[i] = new Thread(new Runnable() {
          public void run() {
            IloCplex cplex = new IloCplex();
            try {
              ... // construct or load the model here
              cplex.use(new MyLazyConstraintCallback());
              if ( cplex.solve() ) {
                ... // process the results here
              }
            }
            finally { cplex.end(); }
          }
        });
    }
    // Launch the threads
    for (int i = 0; i < NTHREADS; ++i) { threads[i].start(); }
    // Wait until all threads are complete
    for (int i = 0; i < NTHREADS; ++i) { threads[i].join(); }

    Note that depending on how you create the models and how you process the results, you may have to add proper locking to your code.


    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: Questions on parallel solving in Java API

    Posted Mon February 10, 2020 09:08 PM

    Originally posted by: brown_rice


    Daniel, 

    Thanks for the detailed explanation.  I am trying to associate your example with the BendersATSP2 example provided by CPLEX, but could not figure out. 

    Suppose I can separate the worker LP for each time period. The callback function is attached to the master problem within the main function. Then, the worker instance is generated within the BendersATSPCallback class where the separate method is used to create the Benders cut. Where exactly should I place the code block that you shared?

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 6.  Re: Questions on parallel solving in Java API

    Posted Tue February 11, 2020 12:34 AM

    That depends on what problems you want to solve in parallel. So which problems do you want to solve in parallel? Do you want to solve multiple master problems in parallel or do you want to solve in parallel multiple workers within the same master?


    #CPLEXOptimizers
    #DecisionOptimization


  • 7.  Re: Questions on parallel solving in Java API

    Posted Tue February 11, 2020 08:32 AM

    Originally posted by: brown_rice


    Daniel,

    My intention is to solve multiple sub problems (workers) in parallel with the same master problem. If I create a for loop for the multiple sub problems, CPLEX will solve them one by one. That is why I would like to see if parallel solving would help me to decrease the solution time. 


    #CPLEXOptimizers
    #DecisionOptimization


  • 8.  Re: Questions on parallel solving in Java API

    Posted Mon February 17, 2020 10:18 AM

    Ok, I understand. But then I am not quite clear you are stuck with CPLEX specific stuff?

    I suggest you first implement your code using a plain loop. Once this is running without problems/bugs, you parallelize the loop usind standard parallelization techniques.


    #CPLEXOptimizers
    #DecisionOptimization


  • 9.  Re: Questions on parallel solving in Java API

    Posted Mon February 17, 2020 09:07 PM

    Originally posted by: brown_rice


    I believe my question was more related to coding rather than CPLEX. I am not expert when it comes to parallel programming. That is why I was just trying to figure out whether CPLEX provides a toy example on parallel solving in Java API. 

     

    Thanks for the help. Hopefully I will look for online sources.


    #CPLEXOptimizers
    #DecisionOptimization


  • 10.  Re: Questions on parallel solving in Java API

    Posted Tue February 18, 2020 07:02 AM

    There is no example for CPLEX since, as you say, this is about general software engineering, rather than CPLEX.

    Assume you have a loop like this:

    for (int i = 0; i < nSubproblems; ++i) {
      IloCplex sub = new IloCplex();
      try {
        // setup the i-th subproblem
        sub.solve();
        // do something with the solution
      }
      finally { sub.end(); }
    }

    That solves each sub problem after each other. Then a very simple way to turn this into a parallal loop is this:

    // Create a vector of sub problems that have to be solved
    final Vector<Integer> v = new Vector<Integer>();
    for (int i = 0; i < nSubproblems; ++i) v.add(i);
    final Iterator<Integer> it = v.iterator();
    // Create threads that pick problems to be solved from the queue as long
    // as there any.
    Thread[] threads = new Thread[NTHREADS];
    for (int t = 0; t < NTHREADS; ++t) {
      threads[t] = new Thread(new Runnable() {
        public void run() {
          while (true) {
            int i;
            synchronized (it) {
              if ( !it.hasNext() ) return;
              i = it.next();
              IloCplex sub = new IloCplex();
              try {
                // setup the i-th subproblem
                sub.solve();
                // process the results for the i-th subproblem
              }
              finally { sub.end(); }
            }
          }
        }
      });
    }

    // Start the threads
    for (int t = 0; t < NTHREADS; ++t) { threads[t].start(); }
    // Wait until threads are complete

    for (int t = 0; t < NTHREADS; ++t) { threads[t].join(); }

    An obvious improvement would be, to not create a vector of indices but a vector of sub problem data.


    #CPLEXOptimizers
    #DecisionOptimization


  • 11.  Re: Questions on parallel solving in Java API

    Posted Mon March 09, 2020 03:51 PM

    Originally posted by: brown_rice


    Hi Daniel,

     

    I am trying to implement the framework that you suggested. As an example, I implemented the model provided here and modeled the scalable warehouse problem. I created 20 instanced and CPLEX took 408.413 second when solving each instance one by one. When I went into the parallel solving, it looks like the instances are still being solved one by one. I was wondering if you could help me to figure out what I might be doing wrong. 

     

    import java.util.Iterator;
    import java.util.Vector;
    
    import ilog.concert.IloException;
    import ilog.concert.IloIntVar;
    import ilog.concert.IloLinearNumExpr;
    import ilog.concert.IloNumVar;
    import ilog.cplex.IloCplex;
    
    public class concurrent {
            public static final double convert = 0.001;
            public static int Fixed;
            public static int NbWarehouses;
            public static int NbStores;
            public static void main(String[] args) throws IloException, InterruptedException {
                    // TODO Auto-generated method stub
                    long start = System.currentTimeMillis();
                    int nProblems = 20;
                    final Vector<Integer> v = new Vector<Integer>();
                    for (int i = 1; i <= nProblems; ++i) v.add(i);
                    final Iterator<Integer> it = v.iterator();
    
                    int NTHREADS = 4; //numofCores
                    Thread[] threads = new Thread[NTHREADS];
                    for (int t = 0; t < NTHREADS; ++t) {
                              threads[t] = new Thread(new Runnable() {
                                public void run() {
                                while (true) {
                                    int i;
                                    synchronized (it) {
                                      if ( !it.hasNext() ) return;
                                      i = it.next();
                                      IloCplex sub = null;
                                            try {
                                                    sub = new IloCplex();
                                            } catch (IloException e) {
                                                    e.printStackTrace();
                                            }
                                      try {                                        
                                                    Fixed = 400 + i;
                                                    NbWarehouses = 400 ;
                                                    NbStores     = 800 + i;
                                                    int[] Capacity = new int[NbWarehouses]; 
                                                    int[][]  SupplyCost= new int[NbStores][NbWarehouses]; 
                                                    
                                                    for(int w=0; w< NbWarehouses ; w++) {
                                                            Capacity[w] = (NbStores/ NbWarehouses) + (w % ( NbStores/ NbWarehouses));
                                                            for(int s=0; s< NbStores ; s++) {
                                                                    SupplyCost[s][w] = 1 + ( ( s + 10 * w) % 100 );
                                                            }
                                                    }
                                                    
                                                    IloIntVar[] open = new IloIntVar[NbWarehouses]; 
                                                    IloNumVar[][] supply = new IloNumVar[NbStores][NbWarehouses]; 
    
                                                    IloLinearNumExpr expr = sub.linearNumExpr();
                                                    IloLinearNumExpr expr2 = sub.linearNumExpr();
                                                    
                                                    
                                                    for(int w=0; w< NbWarehouses ; w++) {
                                                            open[w] = sub.boolVar("open_"+w);
                                                            sub.add(open[w]);
                                                            expr.addTerm(Fixed, open[w]);
                                                            for(int s=0; s< NbStores ; s++) {
                                                                    supply[s][w] = sub.numVar(0, 1, "supply"+s + "_" + w);
                                                                    sub.add(supply[s][w]);
                                                                    expr.addTerm(SupplyCost[s][w], supply[s][w]);
                                                                    expr2.addTerm(1, supply[s][w]);
                                                            }
                                                            sub.addLe(expr2, sub.prod(open[w], Capacity[w]) , "ctOpen_"+ w );
                                                            expr2.clear();
                                                    }
                                                    sub.addMinimize(expr);
                                                    expr.clear();
                                                    
                                                    for(int s=0; s< NbStores ; s++) {
                                                            for(int w=0; w< NbWarehouses ; w++) {
                                                                    expr.addTerm(1, supply[s][w]);
                                                            }
                                                            sub.addEq(1, expr, "ctStoreHasOneWarehouse_"+s);
                                                            expr.clear();
                                                    }
                                                    System.out.println(i + "th problem is being solved.");
                                                    sub.setOut(null);
                                                    sub.solve();
                                                    System.out.println(i + "th problem is " + sub.getStatus());
                                      } catch (IloException e) {
                                                    e.printStackTrace();
                                            }
                                      finally { sub.end(); } 
                                   
                                    }
                                }
                        }
                      });
                    }
                    
                    for (int t = 0; t < NTHREADS; ++t) { threads[t].start(); }
                    
                    for (int t = 0; t < NTHREADS; ++t) { threads[t].join(); }
                    
                    System.out.println("Total solution time is " + (System.currentTimeMillis() - start) * convert );
                    
            }
            
    }
    

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 12.  Re: Questions on parallel solving in Java API

    Posted Tue March 10, 2020 10:21 AM

    It looks like you are holding the lock on 'it' for too long. The synchronized block should end immediately after reading the iterator:

    synchronized (it) {
      if ( !it.hasNext() ) return;
      i = it.next();
    } // close the block here

    In your code you hold the lock for the whole solve, so no other solve can run unless the first one is finished.


    #CPLEXOptimizers
    #DecisionOptimization


  • 13.  Re: Questions on parallel solving in Java API

    Posted Tue March 10, 2020 12:02 PM

    Originally posted by: brown_rice


    Hi,

    Thanks for the answer. I made the change you suggested. I first receive some error, and then JAVA continues to solve the problems one by one. 

     

    Exception in thread "Thread-0" Exception in thread "Thread-1" java.lang.ArrayIndexOutOfBoundsException: 802
            at concurrent$1.run(concurrent.java:50)
            at java.lang.Thread.run(Thread.java:748)
    java.lang.ArrayIndexOutOfBoundsException: 802
            at concurrent$1.run(concurrent.java:50)
            at java.lang.Thread.run(Thread.java:748)
    3th problem is being solved.
    4th problem is being solved.
    4th problem is Optimal
    3th problem is Optimal
    Exception in thread "Thread-3" java.lang.ArrayIndexOutOfBoundsException: 805
            at concurrent$1.run(concurrent.java:66)
            at java.lang.Thread.run(Thread.java:748)
    6th problem is being solved.
    6th problem is Optimal
    

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 14.  Re: Questions on parallel solving in Java API

    Posted Tue March 10, 2020 12:30 PM

    You have to figure out the reason for this exception. Maybe it is a good idea to first get the model right for one thread and only then go parallel.


    #CPLEXOptimizers
    #DecisionOptimization