A parallelised distributed implementation of a Branch and Fix Coordination algorithm

•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. Branc...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•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.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2015.01.004