Title: Minimise pruning cost of a node-weighted directed acyclic graph on applications of management

Authors: Zhi-Ming Chen; Cheng-Hsiung Lee; Yu-Feng Lin

Addresses: Department of Computer Science and Information Engineering, National Central University, No. 300, Zhongda Rd., Zhongli District, Taoyuan City 320317, Taiwan ' Department of International Trade, Chihlee University of Technology, 313, Sec. 1, Wunhua Rd., Banciao District, New Taipei City, 22050, Taiwan ' Department of International Trade, Chihlee University of Technology, 313, Sec. 1, Wunhua Rd., Banciao District, New Taipei City, 22050, Taiwan

Abstract: A novel optimisation problem is proposed in this research. In the proposed model, a corporation is represented as a directed acyclic graph (DAG) with weight. A directed edge in the DAG represents the relationship between a division and its subdivision. The weight denotes the pruning cost of each node. The objective is to partition the graph into two parts so that one of the parts would be pruned to minimise total pruning cost. The proposed model can be formulated as an integer linear programming problem which is hard to find the optimal solution. In this research, we show that it can be solved in polynomial time by using a general linear programming solver. Furthermore, we propose an improvement method which the optimal solution can be solved much more quickly than only using a general LP solver.

Keywords: optimisation; integer programming; pruning cost; node-weighted directed acyclic graph; 2-partition; partial order set.

DOI: 10.1504/IJMIC.2022.124070

International Journal of Modelling, Identification and Control, 2022 Vol.40 No.1, pp.18 - 26

Received: 10 Mar 2021
Accepted: 14 Jul 2021
Published online: 12 Jul 2022 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article