Parallel solving of CP subproblems
Instead of solving the CP single-machine subproblems at every MIP node sequentially, we can modify our Mosel models to solve the subproblems in parallel—especially when working on a multiprocessor machine this may speed up the cut generation process and hence shorten the total run time. We modify the algorithm of Section Implementation as follows:
| Define the MIP machine assignment problem. Define the operations of the CP model. Start the MIP Branch-and-Bound search. At every node of the MIP search: while function generate_cuts returns true re-solve the LP-relaxation Function generate_cuts Collect all machines that are fully assigned into set ToSolve for all machines m ∈ ToSolve call start_CP_model(m) Wait for the solution status messages from all submodels if submodel m is infeasible Add an infeasibility cut for machine m to the MIP if at least one cut has been generated Return true otherwise Return false Procedure start_CP_model(m) Collect all operations assigned to machine m Write data for this machine to memory Start the submodel execution |
The modified version of the function generate_cuts looks as follows. For the full example code the reader is referred to the set of User Guide examples provided with the Xpress Kalis distribution (files sched_mainp.mos and sched_subp.mos).
procedure products_on_machine(m: integer)
NumOp(m):=0
forall(p in PRODS) do
val:=getsol(use(p,m))
if (! not isintegral(use(p,m)) !) (val > 0 and val < 1) then
NumOp(m):=0
break
elif val>0.5 then
NumOp(m)+=1
OpMach(m,NumOp(m)):= p
end-if
end-do
end-procedure
!-----------------------------------------------------------------
! Add an infeasibility cut for machine m to the MIP problem
procedure add_cut_machine(m: integer)
Cut:= sum(p in 1..NumOp(m)) use(OpMach(m,p),m) - (NumOp(m)-1)
if VERBOSE > 1 then
write(m,": ")
forall(p in 1..NumOp(m)) write(OpMach(m,p), " ")
writeln(" <= ", NumOp(m)-1)
end-if
addcut(1, CT_LEQ, Cut)
end-procedure
The implementation of the CP submodels remains largely unchanged, with the exception of the labels employed for passing data via shared memory: we append the machine index to every data item to be able to distinguish between the data used by the different subproblems running in parallel.
For the data set sched_3_12.dat we have observed only a few percent decrease of the total running time on a dual processor machine using the parallel implementation: in many nodes only a single CP subproblem is solved and if there are several subproblems to be solved their execution may be of quite different length. For instances with a larger number of machines the parallelization is likely to show more effect.