Minimise pruning cost of a node-weighted directed acyclic graph on applications of management. (4th July 2022)

• Record Type: Journal Article
• Authors: Chen, Zhi-Ming; Lee, Cheng-Hsiung; Lin, Yu-Feng
• Is Part Of: International journal of modelling, identification and control. Volume 40:Number 1(2022)
• Page Start: 18
• Page End: 26
• Publication Date: 2022-07-04
• Subjects: optimisation -- integer programming -- pruning cost -- node-weighted directed acyclic graph -- 2-partition -- partial order set; Engineering -- Methodology -- Periodicals; Science -- Methodology -- Periodicals; 001.42
• Languages: English
• ISSNs: 1746-6172

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.