The solution to the 'optimal change' problem analyzed in the previous post is further examined from a practice perspective. Again, we use CPLEX to do this since it is quite convenient for such analyses.

Problem 1 is an integer knapsack problem that is known to be theoretically NP-Hard but fairly easy to solve in practice using Dynamic Programming. For this specific coin instance, enumeration with simple pruning rules that exploit the problem structure would work too.

Problem 2 is relatively trickier. It attempts to minimize the maximum weight across the feasible solutions to each of the change scenarios. The value of the 10-coin min-weight solution in the previous post:

However, while an optimal solution to Problem 2 is

We only used a single goal within the optimization formulations: either min-sum, min-count, or min-weight. As mentioned in a recent post, practical optimization models almost never go into production carrying just a single goal. Consider these alternative optimal optimal solutions for 96c:

v # wt p n d q

96 9 24.046 1 0 7 1

96 6 24.046 1 0 2 3

The second solution has the same weight but fewer quarters + dimes, and does the same job a little more efficiently. On the other hand, the first solution perhaps allows greater flexibility in terms of meeting other change requests (e.g. 30c, 40c).

Continuing along this path,

a) if we set the lower bound on the number of dimes in Problem 2 = 7, we obtain the following 13-coin alternative to the 4-3-2-1 answer, having the same weight and value (36.546g, $1.04)

b) If we want a least-value solution to Problem 2, then an optimal objective function value whose corresponding weight is only 1.5g more than the min-weight is 1.0$ (37.912g)

Interestingly, these 1$ solutions include five pennies (a feasible 4-penny solution has a value of 1.04$ or more).

Depending on the context, one of these solutions is more preferable than the others, and this preference can be quantified by suitably incorporating secondary and tertiary goals within the objective function. In contrast, a pure constraint satisfaction model will solely focus on generating feasible solutions ignoring

Problem 1 is an integer knapsack problem that is known to be theoretically NP-Hard but fairly easy to solve in practice using Dynamic Programming. For this specific coin instance, enumeration with simple pruning rules that exploit the problem structure would work too.

**Globally Robust versus Scenario-Optimal**Problem 2 is relatively trickier. It attempts to minimize the maximum weight across the feasible solutions to each of the change scenarios. The value of the 10-coin min-weight solution in the previous post:

**Pennies:Quarters:Dimes:Nickels::4:3:2:1**is slightly more than a dollar (1.04$). This coin mix will be able to satisfy

*any*

*random*change request in the range 1-100c. Note: If we only cared about change between 1-99c, an optimal solution (35.412g, 99c) is:

**PQDN::4241.**

*robust*in terms of this ability to meet any request, it is not necessarily optimal in terms of meeting*specific*coin requests. For example, if we only ever use change for a 3pm $1.68 cup of Starbucks in the cafeteria, then the 4-3-2-1 solution may not be the best. However, if by chance, we choose to downsize to a smaller $1.29 cup one day, then the 68c solution may not work.**First Among Equals**We only used a single goal within the optimization formulations: either min-sum, min-count, or min-weight. As mentioned in a recent post, practical optimization models almost never go into production carrying just a single goal. Consider these alternative optimal optimal solutions for 96c:

v # wt p n d q

96 9 24.046 1 0 7 1

96 6 24.046 1 0 2 3

The second solution has the same weight but fewer quarters + dimes, and does the same job a little more efficiently. On the other hand, the first solution perhaps allows greater flexibility in terms of meeting other change requests (e.g. 30c, 40c).

Continuing along this path,

a) if we set the lower bound on the number of dimes in Problem 2 = 7, we obtain the following 13-coin alternative to the 4-3-2-1 answer, having the same weight and value (36.546g, $1.04)

**PQDN::4171**

b) If we want a least-value solution to Problem 2, then an optimal objective function value whose corresponding weight is only 1.5g more than the min-weight is 1.0$ (37.912g)

**PQDN::****5241****or PQDN::****5091****(If you ever change a dollar bill in the future, do so in a robust manner via this mnemonic: PQDN 5241 :)**Interestingly, these 1$ solutions include five pennies (a feasible 4-penny solution has a value of 1.04$ or more).

Depending on the context, one of these solutions is more preferable than the others, and this preference can be quantified by suitably incorporating secondary and tertiary goals within the objective function. In contrast, a pure constraint satisfaction model will solely focus on generating feasible solutions ignoring

*any*preference. These principles are the cornerstone of many mission-critical optimal planning systems and operational decision support applications deployed across industries.
## Comments

## Post a Comment