Shortest path problem

Question

At the beginning of year 1, a new machine must be purchased. The cost of maintaining a machine $i$ years old is given in Table 5. The cost of purchasing a machine at the beginning of each year is given in Table 6. There is no trade-in value when a machine is replaced. Your goal is to minimize the total cost (purchase plus maintenance) of having a machine for five years. Determine the years in which a new machine should be purchased.

The solution (from Chegg solutions) is given by:

1) What is the logic behind creating this massive objective function, if we could just calculate the optimal cost using dynamic programming?

2) Why is the sum of the first row equal to 1? Why is the second row of $X$'s equal to $X_{1,2}$ ?

3) I don't understand the logic behind the other equalities. If someone could explain, that would be great.

Answer 1

What is the logic behind creating this massive objective function, if we could just calculate the optimal cost using dynamic programming?

You pay for each arc you use, so all arcs have to appear in the objective function. If an arc variable (and its respective cost) weren't in the objective function, you could use it "for free".

The question about dynamic programming is separate. Solving an integer formulation or using a dynamic programming algorithm are two ways to approach the same problem. Both are valid, and any of them might outperform the other on specific instances.

2) Why is the sum of the first row equal to 1? Why is the second row of $X$'s equal to $X_{1,2}$?

3) I don't understand the logic behind the other equalities. If someone could explain, that would be great.

All constraints refer to flow. The first constraint says that one unit of flow is sent out from the first node. This is analogous to the last constraint, which says that one unit of flow is ultimately arriving at the sixth node. Each of the other constraints in the middle refer to a node, from node 2 to node 5. On the left-hand side you have arcs incoming to the node, and on the right-hand side you have arcs outgoing from the node. Because you want to conserve flow (as much goes in as goes out) you have equality constraints.

Imagine you didn't have these constraints. Then a valid solution would be $X_{12} = 1$ to satisfy the first constraint, $X_{46} = 1$ to satisfy the last constraint, and all other variables would be equal to zero. So the only selected arcs would be $1 \to 2$ and $4 \to 6$. This would give you an "artificially cheap" solution: you are not paying for any of the arcs linking node 2 with node 4. But one unit of flow cannot disappear at node 2 (after $1 \to 2$) and magically appear at node 4 (before $4 \to 6$)... it needs to follow a path from 2 to 4.

Now by adding constraint $X_{23} + X_{24} + X_{25} + X_{26} = X_{12}$ you are forcing one unit of flow to move out from node 2, because $X_{12} = 1$ will force one of the variables on the left-hand side to take value one. For example, if $X_{24} = 1$, then you would obtain a feasible solution corresponding to path $1 \to 2 \to 4 \to 6$.

Answer 2

1/ this is just the classical formulation of the shortest path problem as a linear program.

2/ the first equality equals 1, as you need exactly one unit of flow to enter the first node

3/ these are flow conservation constraints : what goes in must come out of a node

Answer 3

Problems solvable using dynamic programming (including the machine replacement problem) could be viewed as shortest path problems, although usually in more than two dimensions (see chapter 2 of "The Art and Theory of Dynamic Programming" by Dreyfus and Law for the relevant discussion). Therefore, those problems could also be solved using the mathematical formulation or appropriate algorithms for the shortest path problem.