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.
© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.