Is there a way to add constraints in parallel?
Answered
I am trying to solve a large dynamic programming problem, say with 1 million states and 10 actions.
Currently, I have a bottleneck in adding constraints with the following code:
===
self.model.addConstrs(
(
stateval[s]
>=
rew(s, a)
+ gamma*quicksum(Pns(snext, s, a)*stateval[snext] for snext in stateset)
for s in stateset for a in actionset[s]
),
name='constraint'
)
===
Is there a way to add constraints in parallel (using multiple CPUs)? Thank you.
-
You cannot parallelize the calls to addConstrs(). But maybe you can parallelize the construction of the set of constraints that you add. For example, you could try building 8 different sets of constraints using Python parallelism, and after they have all been constructed call addConstrs() 8 times in a sequential fashion.
0 -
Adding some extra detail here since this question comes up from time to time. The short answer is this:
- The usual simple tricks for parallelizing Python code do not work for the term-based modeling patterns in gurobipy.
- You might be able to get some parallel speedup by separating out data handling from model building, and parallelizing data handling steps in your application. The first step to this is constructing a constraint matrix outside gurobipy, which can then be read in to a model using the matrix-friendly API. Incidentally, just making this change without parallelization can speed up model building.
- The changes needed will most likely kill the nice readability you get from gurobipy's term-based modeling patterns, so make you really need to do this first. Be sure the model building time is actually a significant component of total runtime and check for other possible issues like inefficient data handling (profilers like scalene and line_profiler can be helpful here).
Ok, down to the details ...
Why don't the usual tricks work?
Let's assume we're trying to build a set of constraints like this:
\sum_i a_ij x_i <= b_j \forall j \in J
If everything is set up correctly (i.e. proper key-value mappings for all data) we can write this very simply in gurobipy as follows:
x = model.addVars(I)
for j in J:
model.addConstr(gp.quicksum(a[i, j] * x[i] for i in J_i[j]) <= b[j])In Python we could try some naive parallelization using the patterns in concurrent.futures, e.g.
x = model.addVars(I)
def constraint(a, x, J_i, b, j):
return gp.quicksum(a[i, j] * x[i] for i in J_i[j]) <= b[j]
with *Executor() as executor:
f = functools.partial(constraint, a, x, J_i, b)
constraints = list(executor.map(constraint, J))
for constraint in constraints:
model.addConstr(constraint)Here the constraint() function creates a single constraint, so a parallel executor could farm out the work of building the constraints and gathering them into a result list. We would still need to add the constraints to the model in serial since the addConstr call is not thread safe.
However, there are two problems with this approach:
- If we use a ThreadPoolExecutor, Python's GIL effectively limits CPU-bound code to 1 core anyway, so we don't get any benefit.
- If we use a ProcessPoolExecutor, you'll hit an error "Can't pickle local object ...". This occurs because gurobipy's modeling objects reference native Gurobi model structures, so they cannot be copied back and forth between processes.
So, the typical Python parallelization patterns do not work with term-based modeling code in gurobipy.
Can we parallelize model building at all?
Yes, but we need to first separate out data handling (which can be parallelized) from interactions with gurobipy modeling objects (which cannot). This can be done via the matrix-friendly API. The below example constructs the same model by first building a sparse scipy matrix representing the constraints, then reading it into a gurobipy model using a single call.
# Build (A, B) for constraints in matrix form A@X <= B
row = []
col = []
data = []
B = []
for j in J:
for i in J_i[j]:
row.append(j)
col.append(i)
data.append(a[i, j])
B.append(b[j])
A = sp.csr_matrix((data, (row, col)))
B = np.array(B)
# Load the constraint matrix directly into the model
X = model.addMVar(len(I))
model.addMConstr(A, X, "<", B)Some important points here:
- Even though nothing is parallelized yet, this code is ~2x faster than the original (though there is an obvious tradeoff: the nice readable math-like code from the original example is long gone).
- This is a fairly silly example - if you are familiar with numpy and scipy you will notice a and b are already almost in the required form, so there are most likely cleaner and faster ways to create the matrices needed directly from the input data.
Now can we write parallel code?
Yes! We could use multiprocessing in the above code to break up the main loop into chunks and build the constraints in several sub-matrices. Your mileage may vary, but for this specific example, the result is code which is several times slower.
The reason for this is that Python's process parallelization requires serializing (pickling) and copying all necessary inputs to worker subprocesses. In this case, that means copying a and b (i.e. the entire input data for the problem) to worker processes which then proceed to use only some of that data to create a part of the constraint matrix. All this copying produces enough overhead to negate any benefit of parallelization.
If the input data was already split into more convenient chunks, or there were more complex computations involved in constructing the constraint matrix, then it is possible this parallelization would be effective. But for a simple mapping task like the example above, it isn't helpful.
Takeaways
The place to start if you really need to improve model building performance is the matrix-friendly API. This allows you to separate out constraint matrix construction as a pure data manipulation exercise, which has two benefits: (1) you may find some speedups using numpy/scipy functions, and (2) you may then be able to effectively parallelize this data handling and build models faster.
0
Please sign in to leave a comment.
Comments
2 comments