Analytical investigations of the process planning problem

Shabbir Ahmed, Nikolaos V. Sahinidis

Research output: Contribution to journalArticlepeer-review

Abstract

The combinatorial nature of problems in process systems engineering has led to the establishment of mixed-integer optimization techniques as a major paradigm in this area. Despite the success of these methods in tackling practical sized problems, the issue of exponential increase of the computational effort with the problem size has been of great concern. A major open question has been whether there is any hope of ever designing 'efficient' exact algorithms for this class of problems. Further, if such algorithms are not possible, one would like to know whether provably good approximation schemes can be devised. In this paper, we pursue analytical investigations to provide answers to these two questions in the context of the process planning problem. By means of a computational complexity analysis, we first prove that the general process planning problem is NP-hard, and thus efficient exact algorithms for this class of problems are unlikely to exist. Subsequently, we develop an approximation scheme for this problem and prove, via probabilistic analysis, that the error of the heuristic vanishes asymptotically with probability one as the problem size increases. Finally, we present computational results to substantiate the theoretical findings. (C) 2000 Elsevier Science Ltd. All rights reserved.

Original languageEnglish (US)
Pages (from-to)1605-1621
Number of pages17
JournalComputers and Chemical Engineering
Volume23
Issue number11-12
DOIs
StatePublished - Jan 5 2000

Keywords

  • Computational complexity
  • Heuristics
  • Probabilistic analysis

ASJC Scopus subject areas

  • Chemical Engineering(all)
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Analytical investigations of the process planning problem'. Together they form a unique fingerprint.

Cite this