TY - JOUR

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

AU - Velez, Sara

AU - Maravelias, Christos T.

N1 - Funding Information:
The authors would like to acknowledge financial support from the National Science Foundation under Grant CBET-1066206 .

PY - 2013/8/8

Y1 - 2013/8/8

N2 - 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.

AB - 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.

KW - Chemical production scheduling

KW - Mixed-integer programming

KW - Parallel computing

UR - http://www.scopus.com/inward/record.url?scp=84877663545&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877663545&partnerID=8YFLogxK

U2 - 10.1016/j.compchemeng.2013.03.030

DO - 10.1016/j.compchemeng.2013.03.030

M3 - Article

AN - SCOPUS:84877663545

SN - 0098-1354

VL - 55

SP - 28

EP - 39

JO - Computers and Chemical Engineering

JF - Computers and Chemical Engineering

ER -