A review of E. Munapo’s See-Saw heuristic: how it extends a method for the assignment problem to the general transportation problem, and why its moves can be computed in parallel.
Review by Artur Łaski based on: E. Munapo, Development of a heuristic to solve the general transportation problem, Eastern-European Journal of Enterprise Technologies, 6/4 (114), 2021, pp. 44–51. DOI: 10.15587/1729-4061.2021.243735
What the paper is about
The transportation problem is one of the classic problems in operations research: how to ship goods from several sources to several destinations at the lowest total cost. It has long been solved with linear programming, the Hungarian method, the modified distribution method (MODI) and the network simplex.
Elias Munapo points out that these methods are sequential — each step depends on the previous one — which makes it hard to use many processors at once. He proposes the See-Saw heuristic, which extends an earlier approach for the assignment problem to the general transportation problem and allows part of the computation to run independently, i.e. in parallel.
Problem formulation
There are sources S₁…Sₘ with supply, destinations D₁…Dₙ with demand, and unit costs cᵢⱼ of shipping from source i to destination j:
| D1 D2 ... Dn | Supply
-------+--------------------+-------
S1 | c11 c12 ... c1n | S1
S2 | c21 c22 ... c2n | S2
... | ... ... ... ... | ...
Sm | cm1 cm2 ... cmn | Sm
-------+--------------------+
Demand | D1 D2 ... Dn |We look for quantities xᵢⱼ that minimise the total cost:
min Z = Σᵢ Σⱼ cᵢⱼ · xᵢⱼ
subject to:
Σⱼ xᵢⱼ = Sᵢ (supply of each source)
Σᵢ xᵢⱼ = Dⱼ (demand of each destination)
xᵢⱼ ≥ 0The problem is balanced when total supply equals total demand; otherwise a dummy row or column is added. The author also notes that the constraint matrix is unimodular, so the optimal solution is integral.
The See-Saw move
The name comes from a see-saw: when one side goes down, the other goes up. In the assignment problem each column has exactly one allocation, so a shift in one column forces the opposite shift in another. In the transportation problem a column can hold several allocations, so a move is considered for each of them separately.
Columns are paired, and the method checks whether shifting part of the shipment between them would lower the cost. To evaluate a move, it is enough to compare cross sums — sums of costs on the diagonals of the 2×2 sub-matrix formed by two rows and two columns. For example, for rows 2 and 3 and columns 1 and 3, compare:
c₂₁ + c₃₃ and c₃₁ + c₂₃A move is:
- profitable when the sum before the move is greater than after it — the cost goes down,
- costly when the sum before the move is smaller,
- neutral when both sums are equal — this signals an alternative solution with the same cost.
A key advantage: evaluating a move does not require knowing the quantity being shifted. Adding and subtracting unit costs is enough.
The algorithm
- Find an initial solution, e.g. with the Least Cost method or Vogel’s approximation method (VAM).
- Pair columns, starting from the left, and perform the best profitable See-Saw move.
- Repeat while profitable moves exist. When no move lowers the cost, the solution is optimal.
Why it suits parallel computing
Moves for different column pairs can be evaluated independently of each other. In the author’s example, the four columns in the first iteration could be assigned to four separate processors. This is the main advantage over classic methods — although the author stresses that, for now, it is a theoretical possibility.
The numerical example from the paper
The author illustrates the method with a problem with three sources. The initial Least Cost solution has six allocations. In the first iteration:
- in column 1 the move is profitable (5 + 17 = 22 is greater than 7 + 12 = 19), so 10 units are shifted,
- in column 2 both sums equal 27 — a neutral move, meaning an alternative solution exists,
- columns 3 and 4 have no profitable moves.
After the first iteration the cost drops to 1360. In the second iteration there are no profitable moves left, so the solution is optimal. The alternative solution has the same cost of 1360. In total, five column-pair comparisons were made.
The paper gives the initial cost once as 1390 and once as 1370; the allocations in the table give 1390.
Conclusions and limitations
According to the author:
- the See-Saw rule from the assignment problem can be generalised to the transportation problem, because any transportation problem can be expressed as a combination of assignment problems,
- in the transportation problem a single column can have several moves, so more indicators per column are used,
- the independence of moves allows computation time to be reduced through parallelisation.
The author openly states the main limitation: there are no computational results for larger problems. The method is demonstrated on one small example, and its running time is not compared with classic methods.
Practical commentary
From an IT and logistics perspective, the paper is interesting above all as a direction. Delivery planning, distributing stock between warehouses or allocating orders to carriers are everyday transportation problems, and modern servers have dozens of cores that sequential methods leave unused. Before the See-Saw heuristic reaches production systems, however, it needs testing on realistically sized problems — hundreds of sources and thousands of destinations — and a comparison with mature linear programming solvers.
Source
E. Munapo, Development of a heuristic to solve the general transportation problem, Eastern-European Journal of Enterprise Technologies, 6/4 (114), 2021, pp. 44–51. DOI: 10.15587/1729-4061.2021.243735 · full text (PDF)