A note on connection between PNS and set covering problems

Blázsik Zoltán and Imreh Balázs: A note on connection between PNS and set covering problems. In: Acta cybernetica, (12) 3. pp. 309-312. (1996)

[thumbnail of cybernetica_012_numb_003_309-312.pdf]
Cikk, tanulmány, mű

Download (486kB) | Preview


Process network synthesis (PNS) has enormous practical impact; however, its mixed integer programming model is tedious to solve because it usually involves a large number of binary variables. Using a combinatorial approach, a structural model of PNS can be given, and a branch-and-bound technique can be applied for searching an optimal solution. In some realistic examples of PNS, this method is efficient. Nevertheless, efficient methods are unavailable for solving these models generally. In this note, we describe a special class of PNS-problems as set-covering or set-partitioning problems. These problems are well-known to be NP-complete, thus, a PNS-problem is NP-hard.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1996
Volume: 12
Number: 3
ISSN: 0324-721X
Page Range: pp. 309-312
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38501/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 312. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 13:56
URI: http://acta.bibl.u-szeged.hu/id/eprint/12563

Actions (login required)

View Item View Item