Parallel Computing Systems for the Optimal Selection of Process Equipment
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Parallel Computing Systems for the Optimal Selection of Process Equipment".
Jane: Here's the gist of the paper. The monograph addresses the NP-hard problem of optimal equipment selection for chemical-engineering systems (CES) in multiproduct batch plants, aiming to minimize total capital cost while respecting compatibility and processing time constraints.
Tom: This problem is formulated as a Mixed-Integer Nonlinear Programming (MINLP) problem due to combinatorial explosion.
Jane: The core approach involves developing sequential and parallel variants of the branch-and-bound (B&B) method for solving this optimization challenge.
Tom: The mathematical model defines a CES as a sequence of processing stages, where each stage can be equipped with units from a finite set.
Title and authors: Tom: This paper, "Parallel Computing Systems for the Optimal Selection of Process Equipment," comes from Borisenko, and it’s all about taking this really complex optimization challenge—this NP-hard problem—and figuring out how to solve it using parallel computing techniques.
Jane: So what they're proposing is a way to build sequential and parallel versions of the branch-and-bound method specifically for chemical engineering systems. It seems they’re trying to use parallelism to cut down that massive search space explosion.
Lu: They present a mathematical model that describes how the equipment operates, defining input data, assumptions about batch size and compatibility constraints, operation durations for each stage, and crucially, the schedule of a system cycle and the processing time constraint for each product.
Meng: I see them modeling how production time depends on that schedule; they’re checking this constraint only at the leaves of the search tree for efficiency, which is a smart way to reduce redundant checks.
Lalam: And they also talk about how to separate the immutable data from the mutable state specific to each variant, which they say is really helpful if you want to run this on hardware like a GPU.
The paper's summary: Tom: So, the core idea here is using a mixed-integer nonlinear programming or MINLP formulation because of that combinatorial explosion, and then developing sequential and parallel variants of the branch-and-bound algorithm to tackle it.
Jane: They spend a lot of time on the computational aspects, specifically how they calculate things like the optimality criterion and the compatibility function incrementally, which they say can be done without rebuilding everything from scratch every time.
Lu: The paper details three main parallel implementations: first, shared-memory systems using OpenMP where nodes above a certain granularity G are treated as independent tasks. Then, there’s a distributed-memory approach with an assigned subtrees method using MPI, and finally, they look at GPU implementations where the CPU acts as the master and GPUs handle subtrees below that same granularity G.
Meng: That granularity parameter G is interesting because it lets you tune how much parallelism you get; if you set G too high, you might run into communication issues on distributed systems.
Lalam: And they also introduce a hybrid metaheuristic algorithm using Ant Colony Optimization and Simulated Annealing to find a good starting point, which they say can then be refined by the branch-and-bound method.
The paper's improvements: Tom: One of the key improvements they suggest is optimizing how you check things in the sequential version of the branch-and-bound algorithm. They show that you can reduce run time approximately by half, going from twenty seven hours eighty nine minutes down to thirteen hours fifty two minutes just by checking the optimality criterion before checking the processing time constraint for solutions that definitely aren't optimal.
Jane: That makes sense; it’s a way to prune the search space much earlier in the process. They also introduce a parameter G, which lets you choose how granular your parallel tasks are; if you set G correctly, subtrees below that level are processed sequentially instead of being split into parallel tasks.
Lu: That granularity parameter G is important because it allows practitioners to choose it so that the number of generated subproblems isn't smaller than the number of processing elements you have available, which helps manage the load.
Meng: From a deployment standpoint, tuning that granularity seems like a practical way to get good speedup without needing an impossibly large parallel system right away.
Lalam: And for the hybrid metaheuristic they mention, they found that parameter tuning methods, including a multi-constant approach, significantly reduce the time it takes to tune things across different GPU architectures while still keeping the solution effective.
Conclusion: Tom: So to wrap up this paper on "Parallel Computing Systems for the Optimal Selection of Process Equipment," they show that by using parallel branch-and-bound variants and smart pruning, you can tackle this large NP-hard problem much faster than a purely sequential approach.
Jane: The main implication is that for those dealing with complex equipment selection in chemical plants, having a structure like this model allows you to explore the solution space efficiently even when the numbers get huge.
Lu: The authors point out that while they show good speedup on GPUs—like up to eleven point nine times on eight TITAN Xp accelerators—there are still limitations regarding problem size; their hybrid metaheuristic approach starts to degrade significantly when the number of variants goes above eighty four.
Meng: I'd stress that for real-world production, we need to worry about the master process bottleneck in distributed systems; they mention that adding submasters can help mitigate performance degradation when you have a lot of processors.
Lalam: It’s clear the work shows a path forward for applying these parallel algorithms to large-scale combinatorial problems, but as they state on page eighteen their method still requires careful parameter tuning to achieve the best results across different hardware setups <ref:2611.16290#pg3>.
Tambov State Technical University
cs.DC
Submitted: 2026-11-12
Updated: 2026-11-12
Comments: 99 pages, 29 figures, 9 tables, 18 listings. English translation, by the author, with minor corrections, of the monograph originally published in Russian (Tambov, 2026)
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Importance score: 89/100
The gist: The monograph addresses the NP-hard problem of optimal equipment selection for chemical-engineering systems (CES) in multiproduct batch plants…
Key concepts
- Mixed-Integer Nonlinear Programming (MINLP)
- This is a mathematical model used to solve complex optimization problems where some variables must be whole numbers (integers) and the relationships between them are nonlinear. It's used here to find the best equipment setup by minimizing cost while satisfying various physical constraints like compatibility and processing time.
- Branch-and-Bound (B&B)
- A search algorithm used to solve large optimization problems by systematically exploring a tree of possibilities. It starts with an upper bound (a known feasible solution) and then branches into subproblems, pruning branches that cannot lead to a better solution than the current best one.
- Granularity Parameter (G)
- This parameter controls how the search space is divided for parallel processing. When G is used, only search nodes above a certain level are treated as independent tasks for parallel execution; nodes below this level are processed sequentially. This helps balance parallelism with the overhead of managing many small tasks.
- Hierarchical Master-Worker Paradigm
- A strategy for distributed computing where the main master process delegates work to several submasters. This structure is designed to prevent a single master from becoming a bottleneck, allowing the system to scale efficiently on large distributed memory systems.
Terminology
Summary
The monograph addresses the NP-hard problem of optimal equipment selection for chemical-engineering systems (CES) in multiproduct batch plants, aiming to minimize total capital cost while respecting compatibility and processing time constraints. p. 1 The monograph is devoted to the development and study of parallel algorithms for the optimal
selection of equipment for chemical-engineering systems of multiproduct batch plants, which is a large-scale
NP-hard discrete optimization problem. It presents a mathematical model of the operation of a chemicalengineering system; sequential and parallel variants of the branch-and-bound method for shared-memory
and distributed-memory systems (OpenMP, MPI) and for graphics processing units (CUDA); a hybrid
metaheuristic algorithm combining Ant Colony Optimization and Simulated Annealing; and methods
for tuning its parameters on one or several GPUs. Abbreviations
ACO Ant Colony Optimization
API Application Programming Interface
B&B Branch-and-Bound
BFS Breadth-First Search
CC Compute Capability
CES Chemical-Engineering System
CO Combinatorial Optimization
CPU Central Processing Unit
CSP Constraint Satisfaction Problem
CUDA Compute Unified Device Architecture
DFS Depth-First Search
DOE Design of Experiments
DRAM Dynamic Random-Access Memory
DSP Digital Signal Processor
FP32 32-bit (single-precision) Floating Point
FPGA Field-Programmable Gate Array
GPGPU General-Purpose computing on Graphics Processing Units
GPU Graphics Processing Unit
HLSL High-Level Shading Language
LIFO Last-In, First-Out
MAC Multiple Ant Colonies
MILP Mixed-Integer Linear Programming
MINLP Mixed-Integer Nonlinear Programming
MIR Multiple Independent Runs
MPI Message Passing Interface
NP Nondeterministic Polynomial (time)
NVCC NVIDIA CUDA Compiler
OFAT One-Factor-At-a-Time
OpenCL Open Computing Language
OpenMP Open Multi-Processing
RAM Random-Access Memory
SA Simulated Annealing
SIMD Single Instruction, Multiple Data
SIMT Single Instruction, Multiple Threads
SM Streaming Multiprocessor
SMP Symmetric Multiprocessing
STL Standard Template Library
5 It presents a mathematical model of the operation of a chemicalengineering system; sequential and parallel variants of the branch-and-bound method for shared-memory
and distributed-memory systems (OpenMP, MPI) and for graphics processing units (CUDA); a hybrid
metaheuristic algorithm combining Ant Colony Optimization and Simulated Annealing; and methods
for tuning its parameters on one or several GPUs. Results of computational experiments on multi-core
processors, computing clusters, and GPUs of various architectures are reported.Where the paper says it
Where the paper says it
Where the paper says it
The mathematical model defines a CES as a sequence of processing stages, where each stage can be equipped with units from a finite set. p. 8 A CES is a sequence of I processing stages. Each stage i of the system can be equipped with
a main unit chosen from a finite set Xi containing Ji elements. The chapter is organized as follows. 1 gives the mathematical formulation of the
optimal CES equipment selection problem and describes the representation of the search space
as a tree of variants. 4 Schedule of a System Cycle . 5 Production Time and the Processing Time Constraint . Traditional approaches
to developing parallel programs for CPU-based systems are not sufficient here. Efficient implementation of algorithms on heterogeneous systems is possible only if the specific features and
limitations of their architecture are taken into account, including the interaction between the
CPU and the accelerator, the memory hierarchy and the rules for using it efficiently, and the
orientation towards massively parallel data processing.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Parallel implementations are extensively studied across different paradigms:
-
Shared-Memory Systems (OpenMP): Nodes above a certain granularity level (G) are treated as independent tasks, while nodes below G are processed sequentially. The granularity parameter G controls the degree of parallelism, and results show near-linear speedup and high scalability, provided memory constraints are managed. p. 4
Where the paper says it
Abbreviations ACO Ant Colony Optimization API Application Programming Interface B&B Branch-and-Bound BFS Breadth-First Search CC Compute Capability CES Chemical-Engineering System CO Combinatorial Optimization CPU Central Processing Unit CSP Constraint Satisfaction Problem CUDA Compute Unified Device Architecture DFS Depth-First Search DOE Design of Experiments DRAM Dynamic Random-Access Memory DSP Digital Signal Processor FP32 32-bit (single-precision) Floating Point FPGA Field-Programmable Gate Array GPGPU General-Purpose computing on Graphics Processing Units GPU Graphics Processing Unit HLSL High-Level Shading Language LIFO Last-In, First-Out MAC Multiple Ant Colonies MILP Mixed-Integer Linear Programming MINLP Mixed-Integer Nonlinear Programming MIR Multiple Independent Runs MPI Message Passing Interface NP Nondeterministic Polynomial (time) NVCC NVIDIA CUDA Compiler OFAT One-Factor-At-a-Time OpenCL Open Computing Language OpenMP Open Multi-Processing RAM Random-Access Memory SA Simulated Annealing SIMD Single Instruction, Multiple Data SIMT Single Instruction, Multiple Threads SM Streaming Multiprocessor SMP Symmetric Multiprocessing STL Standard Template Library 5
-
Distributed-Memory Systems (MPI): A master–worker paradigm is employed using an assigned subtrees method, where the master traverses down to level G, and workers recursively solve subproblems. This setup exhibits near-linear speedup and high scalability, though efficiency can degrade when the number of processors surpasses 768 due to the master process becoming a bottleneck.
-
Graphics Processing Units (GPUs): The CPU acts as the master, while independent GPU threads handle subtrees below granularity G. Two traversal approaches are implemented: static partitioning, where subtrees are assigned to separate threads without redistribution (minimizing communication but limiting speedup due to thread divergence), and an iterative traversal utilizing a stack structure on the device.
The study also introduces a hybrid metaheuristic algorithm combining Ant Colony Optimization (ACO) and Simulated Annealing (SA). p. 1 The monograph is devoted to the development and study of parallel algorithms for the optimal
selection of equipment for chemical-engineering systems of multiproduct batch plants, which is a large-scale
NP-hard discrete optimization problem. It presents a mathematical model of the operation of a chemicalengineering system; sequential and parallel variants of the branch-and-bound method for shared-memory
and distributed-memory systems (OpenMP, MPI) and for graphics processing units (CUDA); a hybrid
metaheuristic algorithm combining Ant Colony Optimization and Simulated Annealing; and methods
for tuning its parameters on one or several GPUs. Abbreviations
ACO Ant Colony Optimization
API Application Programming Interface
B&B Branch-and-Bound
BFS Breadth-First Search
CC Compute Capability
CES Chemical-Engineering System
CO Combinatorial Optimization
CPU Central Processing Unit
CSP Constraint Satisfaction Problem
CUDA Compute Unified Device Architecture
DFS Depth-First Search
DOE Design of Experiments
DRAM Dynamic Random-Access Memory
DSP Digital Signal Processor
FP32 32-bit (single-precision) Floating Point
FPGA Field-Programmable Gate Array
GPGPU General-Purpose computing on Graphics Processing Units
GPU Graphics Processing Unit
HLSL High-Level Shading Language
LIFO Last-In, First-Out
MAC Multiple Ant Colonies
MILP Mixed-Integer Linear Programming
MINLP Mixed-Integer Nonlinear Programming
MIR Multiple Independent Runs
MPI Message Passing Interface
NP Nondeterministic Polynomial (time)
NVCC NVIDIA CUDA Compiler
OFAT One-Factor-At-a-Time
OpenCL Open Computing Language
OpenMP Open Multi-Processing
RAM Random-Access Memory
SA Simulated Annealing
SIMD Single Instruction, Multiple Data
SIMT Single Instruction, Multiple Threads
SM Streaming Multiprocessor
SMP Symmetric Multiprocessing
STL Standard Template Library
5 It presents a mathematical model of the operation of a chemicalengineering system; sequential and parallel variants of the branch-and-bound method for shared-memory
and distributed-memory systems (OpenMP, MPI) and for graphics processing units (CUDA); a hybrid
metaheuristic algorithm combining Ant Colony Optimization and Simulated Annealing; and methods
for tuning its parameters on one or several GPUs. Results of computational experiments on multi-core
processors, computing clusters, and GPUs of various architectures are reported. 4 Algorithmic Aspects of Dynamic Load Balancing . 5 Speedup Anomalies and the Search Overhead Factor . , Ethernet or InfiniBand). Most
modern high-performance computing systems have a heterogeneous architecture comprising a
general-purpose multi-core Central Processing Unit (CPU) and a set of various accelerators [33–
35].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The test case involves a CES with 16 stages and 5 equipment sizes per stage, yielding up to 1216 variants. p. 8 3 describes
the test case used in the computational experiments throughout the subsequent chapters. 1 Mathematical Formulation of the Problem
A CES of a multiproduct batch plant is a set of processing stages equipped with reactors, tanks,
filters, dryers, and other process equipment, and intended to carry out the production steps for a
given range of products. The monograph is devoted to the development and study of parallel algorithms for the optimal
selection of equipment for chemical-engineering systems of multiproduct batch plants, which is a large-scale
NP-hard discrete optimization problem. It presents a mathematical model of the operation of a chemicalengineering system; sequential and parallel variants of the branch-and-bound method for shared-memory
and distributed-memory systems (OpenMP, MPI) and for graphics processing units (CUDA); a hybrid
metaheuristic algorithm combining Ant Colony Optimization and Simulated Annealing; and methods
for tuning its parameters on one or several GPUs. 1 Master Process . 2 Worker Process .Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Parallel Branch-and-Bound for Multi-Core Systems allows for solving NP-hard discrete optimization problems like optimal equipment selection on shared-memory systems using OpenMP by treating nodes of upper search tree levels as independent tasks. This enables a parallel implementation where
the nodes of the upper levels of the search tree are treated as independent tasks.
-
Master-Worker Paradigm for Distributed Systems allows for solving the same problem on distributed-memory systems using MPI by having a master process generate tasks and distributing them evenly among worker processes. This structure is based on
the master process (master) generates tasks and distributes them evenly among the worker processes (workers).
-
GPU Implementation of Branch-and-Bound enables solving problems on heterogeneous systems by splitting the search tree into subtrees processed by independent GPU threads, utilizing static partitioning to minimize communication overhead. This approach involves the host splitting the tree into subtrees, where
the part of the tree above this level is processed sequentially on the CPU, while the subtrees below it are turned into parallel tasks and processed by separate threads on the GPU.
-
Optimization of Sequential Branch-and-Bound reduces total run time by checking
the optimality criterion
beforethe processing time constraint
for solutions that are certainly not optimal. This modification was shown to reduce the run timeapproximately by half (13 h 52 min instead of 27 h 11 min).
-
Utilizing a granularity parameter G in parallel implementations allows for tuning the degree of parallelism such that
subtrees below this level are not split into parallel tasks but are processed sequentially.
This allows practitioners to choose G so thatthe number of generated subproblems is at least not smaller than the number of processing elements used.
-
Using a hierarchical master-worker paradigm in distributed-memory systems addresses bottlenecks by adding
several submasters to the main master process,
which can be used to mitigate performance degradation when the master becomes a bottleneck.
Abstract
This monograph addresses the optimal selection of equipment for chemical-engineering systems of multiproduct batch plants, a large-scale NP-hard discrete optimization problem in which, for each processing stage, a unit of standard size must be chosen so that the total capital cost of the equipment is minimized while the system remains operable and produces the required products within a given time horizon. We present the mathematical model of system operation and analyze its computational properties. We then develop a sequential branch-and-bound algorithm and its parallel versions for shared-memory systems (OpenMP), distributed-memory clusters (MPI, master-worker), and graphics processing units (CUDA), including recursive and iterative tree traversal, shared-memory optimization, and branch-divergence reduction. To overcome the exponential growth of the run time, we propose a hybrid metaheuristic in which Ant Colony Optimization finds a feasible initial solution and Simulated Annealing improves it, and we implement it on GPUs with thousands of independent threads. Finally, we propose random, constant, and multi-constant approaches to tuning the parameters of the ant colony algorithm based on statistical analysis of many parallel runs, and we study the program on GPUs of three generations and on nodes with several GPUs. Computational experiments on multi-core processors, clusters, and GPUs show that the parallel hybrid algorithm finds solutions within 0.01% of the branch-and-bound optimum in tens of seconds instead of tens of hours.
Related papers
- Programmable Probabilistic Computer with 1,000,000 p-bits
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- Seamless Reconfiguration for DAG-BFT (Technical Report)
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends