Related Experiment Video
Updated: Jan 8, 2026
04:58
A Rapid Method for Modeling a Variable Cycle Engine
Published on: August 13, 2019
7.9K
Minimum flow decomposition in graphs with cycles using integer linear programming
Fernando H C Dias1, Lucia Williams2, Brendan Mumey3
1Department of Mathematics and Systems Analysis, Aalto University, 02150 Espoo, Finland.
Journal of Global Optimization : an International Journal Dealing with Theoretical and Computational Aspects of Seeking Global Optima and Their Applications in Science, Management and Engineering
|December 22, 2025
Summary
This study introduces the first exact Integer Linear Programming (ILP) formulation for minimum flow decomposition (MFD) on graphs with cycles. This novel approach provides accurate solutions for complex flow decomposition problems in various scientific fields.
Area of Science:
- Computer Science
- Operations Research
- Bioinformatics
- Transportation Science
Background:
- Minimum Flow Decomposition (MFD) is a classical problem, crucial for modeling in Bioinformatics and Transportation.
- Existing solutions for MFD on graphs with cycles are heuristic or approximate, lacking exactness.
- The MFD problem is NP-hard even on acyclic graphs, highlighting the complexity of finding exact solutions.
Purpose of the Study:
- To present the first Integer Linear Programming (ILP) formulation for Minimum Flow Decomposition (MFD) on graphs containing cycles.
- To address three variants of MFD, focusing on decompositions into paths, cycles, trails, and walks.
Main Methods:
- Developed novel Integer Linear Programming (ILP) formulations for Minimum Flow Decomposition (MFD) on cyclic graphs.
- Tested the ILP formulations on three datasets of increasing complexity from Bioinformatics and Transportation.
Main Results:
- The proposed ILP formulations provide the first exact solutions for MFD on graphs with cycles.
- All tested instances across diverse datasets were solved within 12 minutes, demonstrating computational efficiency.
- The study offers a significant advancement over existing heuristic and approximation methods for MFD.
Conclusions:
- The presented ILP approach offers a robust and exact method for solving Minimum Flow Decomposition problems on cyclic graphs.
- This work provides a powerful new tool for applications in Bioinformatics, Transportation, and other fields reliant on flow analysis.
- Freely available implementations facilitate further research and application of these exact MFD solutions.
Related Concept Videos
01:24Fast Decoupled and DC Powerflow
705
The fast decoupled power flow method addresses contingencies in power system operations, such as generator outages or transmission line failures. This method provides quick power flow solutions, essential for real-time system adjustments. Fast decoupled power flow algorithms simplify the Jacobian matrix by neglecting certain elements, leading to two sets of decoupled equations:
705
01:18Uniform Depth Channel Flow: Problem Solving
415
To calculate the flow rate for a trapezoidal channel, first, identify the bottom width, side slope, and flow depth of the channel. The cross-sectional area (A) corresponding to the depth of flow (y), channel bottom width (B), and side slope (θ) is determined by:Next, calculate the wetted perimeter, which includes the bottom width and the sloped side lengths in contact with the water. Using the values of the cross-sectional area and the wetted perimeter, determine the hydraulic radius by...
415
01:26The Power Flow Problem and Solution
776
Power flow problem analysis is fundamental for determining real and reactive power flows in network components, such as transmission lines, transformers, and loads. The power system's single-line diagram provides data on the bus, transmission line, and transformer. Each bus k in the system is characterized by four key variables: voltage magnitude Vk, phase angle δk, real power Pk, and reactive power Qk. Two of these four variables are inputs, while the power flow program computes...
776
01:24Laminar Flow: Problem Solving
478
Laminar flow occurs when a fluid moves smoothly in parallel layers with minimal mixing and turbulence. In fluid mechanics, ensuring laminar flow within a pipe is essential for precise control of flow characteristics, especially in engineering applications. The key factor in determining whether flow remains laminar is the Reynolds number, a dimensionless quantity that depends on the fluid's velocity, density, viscosity, and the pipe's diameter. A Reynolds number of 2100 or lower...
478
01:09Turbulent Flow: Problem Solving
363
Carbonation is a process used to dissolve carbon dioxide gas in a liquid, commonly used in the production of carbonated beverages. Achieving efficient carbonation requires careful control of temperature, pressure, and flow conditions. By adjusting these parameters, carbonation efficiency can be maximized, producing a higher concentration of CO2 in the liquid.
Temperature is a key factor in CO2 solubility. In this case, the CO2 gas and the liquid are cooled to 20°C. Lower temperatures enhance...
Temperature is a key factor in CO2 solubility. In this case, the CO2 gas and the liquid are cooled to 20°C. Lower temperatures enhance...
363
01:23Maximum Power Flow and Line Loadability
570
The maximum power flow for lossy transmission lines is derived using ABCD parameters in phasor form. These parameters create a matrix relationship between the sending-end and receiving-end voltages and currents, allowing the determination of the receiving-end current. This relationship facilitates calculating the complex power delivered to the receiving end, from which real and reactive power components are derived.
570