| 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 |
|