Reformulations and branching methods for mixed-integer programming chemical production scheduling models

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Mixed-integer programs for chemical production scheduling are computationally challenging. One characteristic that makes them hard is that they typically have many symmetric solutions, that is, solutions that are different in terms of the values of the decision variables but have the same objective function value, which means that the algorithms used to solve these models must search through all such solutions before improving the bound on the objective. To address this challenge, we propose three reformulations of the widely used state-task network formulation. Specifically, we introduce additional constraints to define the number of batches of each task as an integer variable. Branching on this new integer variable quickly eliminates schedules that have the same number of batches, which, in turn, leads to the elimination of many symmetric solutions. We also study different branching strategies and variable selection rules and compare them. The proposed solution methods lead to orders-of-magnitude reductions in the computational requirements for the solution of scheduling problems.

Original languageEnglish (US)
Pages (from-to)3832-3841
Number of pages10
JournalIndustrial and Engineering Chemistry Research
Volume52
Issue number10
DOIs
StatePublished - Mar 13 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Chemistry(all)
  • Chemical Engineering(all)
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'Reformulations and branching methods for mixed-integer programming chemical production scheduling models'. Together they form a unique fingerprint.

Cite this