A parallelised distributed implementation of a Branch and Fix Coordination algorithm

• Published in: European journal of operational research 2015-07, Vol.244 (1), p.77-85
• Main Authors: Pagès-Bernaus, Adela, Pérez-Valdés, Gerardo, Tomasgard, Asgeir
• Format: Article
• Language: English
• Subjects: Algorithms; Branch & bound algorithms; Branch and fix coordination algorithm; Clusters; Computation; Decomposition; Mathematical models; Mathematical problems; Mixed integer; Operational research; Parallel programming; Stochastic mixed-integer problems; Stochastic models; Stochasticity; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2015.01.004

•Large-scale stochastic mixed-integer programming (SMIP) instances are hard to solve.•Branch and Fix Coordination (BFC) algorithm can solve such SMIP instances.•The decomposition appears to play an important role.•Parallelizing BFC obtains solutions in instances than commercial solvers do not. Branch and Fix Coordination is an algorithm intended to solve large scale multi-stage stochastic mixed integer problems, based on the particular structure of such problems, so that they can be broken down into smaller subproblems. With this in mind, it is possible to use distributed computation techniques to solve the several subproblems in a parallel way, almost independently. To guarantee non-anticipativity in the global solution, the values of the integer variables in the subproblems are coordinated by a master thread. Scenario ‘clusters’ lend themselves particularly well to parallelisation, allowing us to solve some problems noticeably faster. Thanks to the decomposition into smaller subproblems, we can also attempt to solve otherwise intractable instances. In this work, we present details on the computational implementation of the Branch and Fix Coordination algorithm.