Simplex Algorithm with enhanced feature)
1)Anti-Cycling (Step 2):
¨To avoid cycling the spanning tree must be strongly feasible. On each iteration the algorithm
maintains strong feasibility by removing an appropriate arc..
2)A mixture of heuristic approach and memory technique (Step 1):
¨Arcs in the graph are divided into several
blocks (Like Arc Blocking scheme).
iteration, a sorted packet of the
violated arcs is collected. The most
violated arc at top of the packet is added to the spanning tree. Pelements
at the top of the packet are kept for the next iteration(The memory
¨Circularly scan the blocks for violating the
optimality condition. The first block
is chosen randomly or heuristically.
At each scan, one violating arc from each block is added to the