COSTECH Integrated Repository

Linear Ordering Problem: An Algorithm for the Optimal Solution

Show simple item record

dc.creator Mushi, Allen R.
dc.date 2016-03-16T15:09:03Z
dc.date 2016-03-16T15:09:03Z
dc.date 2014
dc.date.accessioned 2018-04-18T11:50:13Z
dc.date.available 2018-04-18T11:50:13Z
dc.identifier Mushi, A.R., 2005. The linear ordering problem: an algorithm for the optimal solution. African Journal of Science and Technology, 6(1).
dc.identifier http://hdl.handle.net/123456789/1047
dc.identifier.uri http://hdl.handle.net/123456789/10657
dc.description In this paper we describe and implement an algorithm for the exact solution of the Linear Ordering problem. Linear Ordering is the problem of finding a linear order of the nodes of a graph such that the sum of the weights which are consistent with this order is as large as possible. It is an NP - Hard combinatorial optimisation problem with a large number of applications, including triangulation of input - output matrices in Economics, aggregation of individual preferences and ordering of teams in sports. We implement an algorithm for the exact solution using cutting plane and branch and bound procedures. The program developed is then applied to the triangulation problem for the input - output tables. We have been able to triangulate input - output matrices of size up to 41 x 41.
dc.language en
dc.publisher African Journal of Science and Technology
dc.subject Linear Ordering Problem
dc.subject Algorithm
dc.subject optimal solution
dc.title Linear Ordering Problem: An Algorithm for the Optimal Solution
dc.type Journal Article


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search COSTECH


Advanced Search

Browse

My Account