A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large sized multistage stochastic mixed 0-1 problems

View/ Open
Date
2016-08-26Author
Aldasoro U.
Escudero L.F.
Merino M.
Pérez G.
Metadata
Show full item recordAbstract
A parallel matheuristic algorithm is presented as a spin-off from the exact Branch-and-Fix Coordination
(BFC) algorithm for solving multistage stochastic mixed 0-1 problems. Some steps to guarantee the
solution’s optimality are relaxed in the BFC algorithm, such that an incomplete backward branching scheme
is considered for solving large sized problems. Additionally, a new branching criterion is considered, based
on dynamically-guided and stage-wise ordering schemes, such that fewer Twin Node Families are expected
to be visited during the execution of the so-called H-DBFC algorithm. The inner parallelization IH-DBFC
of the new approach, allows to solve in parallel scenario clusters MIP submodels at different steps of the
algorithm. The outer parallel version, OH-DBFC, considers independent paths and allows iterative incumbent
solution values exchanges to obtain tighter bounds of the solution value of the original problem. A broad
computational experience is reported for assessing the quality of the matheuristic solution for large sized
instances. The instances dimensions that are considered are up to two orders of magnitude larger than in some
other works that we are aware of. The optimality gap of the H-DBFC solution value versus the one obtained
by a state-of-the-artMIP solver is very small, if any. The new approach frequently outperforms it in terms of
solution’s quality and computing time. A comparison with our Stochastic Dynamic Programming algorithm
is also reported. The use of parallel computing provides, on one hand, a perspective for solving very large
sized instances and, on the other hand, an expected large reduction in elapsed time.