cell elevator

Based on the image you've provided, here's an easy-to-understand elaboration of how to find the "value of a cell evaluator" and how to use it for both minimization and maximization problems.

What is a "Cell Evaluator"?

A "cell evaluator" is just another name for what we previously called the "improvement index" in the Stepping-Stone method.

* Purpose: Its purpose is to tell you if the cost of your solution can be improved by moving units into an empty cell.

* How it's calculated: You calculate the cell evaluator by tracing a closed loop for an unoccupied cell and summing the costs of the cells in the loop, alternating signs (+ and -).

Let's break down the rules for minimization (cost) and maximization (profit) problems.

1. For a Minimization (Cost) Problem

In a cost problem, your goal is to reduce the total cost.

How to interpret the cell evaluator:

* If the cell evaluator is positive (> 0) or zero (= 0): This means that if you were to move units into this empty cell, the total cost would either stay the same or increase. Therefore, there is no improvement potential for this cell.

* If the cell evaluator is negative (< 0): This means that moving units into this empty cell will decrease the total cost. This empty cell has an improvement potential. The more negative the value, the greater the potential to reduce the cost.

Analysis of the Test:

* You must calculate the cell evaluator for all the empty (unoccupied) cells.

* The solution is optimal (you're done!) if... all of the cell evaluators are positive or zero. You can't make the total cost any lower.

* The solution is not optimal (you can improve it!) if... at least one of the cell evaluators is negative.

How to find a better solution if it's not optimal:

* Identify the "incoming" cell: This is the empty cell with the most negative cell evaluator. This is the best place to start because it offers the largest potential cost reduction.

* Design an improved solution: You "shift units" into this incoming cell by adjusting the allocations along the closed loop you traced for it. You shift the minimum number of units from the cells in the loop that have a minus (-) sign.

2. For a Maximization (Profit) Problem

In a profit problem, your goal is to increase the total profit. This is the reverse of a minimization problem.

How to interpret the cell evaluator:

* If the cell evaluator is negative (< 0) or zero (= 0): This means that moving units into this empty cell would either keep the total profit the same or decrease it. There is no improvement potential.

* If the cell evaluator is positive (> 0): This means that moving units into this empty cell will increase the total profit. This empty cell has an improvement potential. The larger the positive value, the greater the potential to increase the profit.

Analysis of the Test (The Reverse Case):

* The solution is optimal (you're done!) if... all of the cell evaluators are negative or zero. You can't make the total profit any higher.

* The solution is not optimal (you can improve it!) if... at least one of the cell evaluators is positive.

How to find a better solution if it's not optimal:

* Identify the "incoming" cell: This is the empty cell with the most positive cell evaluator. This is the best place to start because it offers the largest potential profit increase.

* Design an improved solution: You shift units into this incoming cell, again by adjusting the allocations along the closed loop. You shift the minimum number of units from the cells in the loop that have a minus (-) sign.

In simple terms, a negative value is good for costs (you want costs to go down) and a positive value is good for profits (you want profits to go up).