A branch-and-bound algorithm for the solution of chemical production scheduling MIP models using parallel computing

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

Exploiting multiple cores in a computer or grid of computers can reduce the time required to solve a mixed-integer programming (MIP) model. Here, we develop a parallel branch-and-bound algorithm for a chemical production scheduling problem using a discrete-time model. The algorithm consists of initialization, submission, branching, collection, bounding, and pruning steps. We branch by adding a constraint to bound the total number of times each task runs. Each subproblem is solved as an MIP on a single core of a computer, so that many sub problems can be solved simultaneously. Also, we propose an algorithm, executed at each node of our branch-and-bound tree, to improve the bounds on the number of times a task is run based on the current objective value. We present computational results for several instances to show the parallel algorithm with the proposed branching strategy can solve more challenging problems than simply using the default parallel option.

Original languageEnglish (US)
Pages (from-to)28-39
Number of pages12
JournalComputers and Chemical Engineering
Volume55
DOIs
StatePublished - Aug 8 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Chemical Engineering(all)
  • Computer Science Applications

Keywords

  • Chemical production scheduling
  • Mixed-integer programming
  • Parallel computing

Fingerprint Dive into the research topics of 'A branch-and-bound algorithm for the solution of chemical production scheduling MIP models using parallel computing'. Together they form a unique fingerprint.

Cite this