Minimise pruning cost of a node-weighted directed acyclic graph on applications of management Online publication date: Tue, 12-Jul-2022
by Zhi-Ming Chen; Cheng-Hsiung Lee; Yu-Feng Lin
International Journal of Modelling, Identification and Control (IJMIC), Vol. 40, No. 1, 2022
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Modelling, Identification and Control (IJMIC):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com