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? 

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.

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?

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.

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?

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?

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. 

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.

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.

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.

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

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.

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

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.