An optimization model need not have a unique optimal solution. As we have pointed out in Section 12.1.1, the following can occur:
- There are multiple optimal solutions. In such a case we may afford the luxury of using a secondary objective, which is optimized over the set of optimal solutions with respect to the original objective.
- The solution goes to infinity. If so, it is quite likely that there is something wrong with the model itself, probably a missing constraint.
- A common and much less pleasing occurrence, however, is when no feasible solution is found, because the constraints are too demanding and the feasible set is empty. To see a practically relevant example, consider the production planning model (12.27), whereby we want to satisfy demand at minimum cost. It is easy to see that if demand is too large with respect to available capacity, we may fail to satisfy it completely.
Commercial solvers are able to spot infeasible mathematical programs, but, from a practical perspective, we cannot just report that, leaving the decision maker without a clue. It would be nice to provide her with some usable information about what is causing infeasibility. This can be accomplished by an elastic model formulation. For the sake of concreteness, we illustrate the approach in the specific case of production planning, but the idea is quite general: We relax critical constraints and introduce a penalty term into the objective function. In our case, the infeasibility may be regarded as the result of excessive high demand or insufficient capacity. We may either relax the requirement that demand be completely satisfied, or we may relax capacity constraints.
The first route can be pursued by introducing a decision variable zit representing unmet (i.e., unsatisfied) demand of item i during time bucket t. Now, rather than issuing dit from inventory during each time bucket, we just issue dit − zit. We also need to adjust the objective function by penalizing unmet demand; if we fail to do so, the obvious optimal solution would be to just shut down production. The resulting model is
The coefficient ω in the objective (12.46) is a penalty coefficient, representing the cost of unmet demand. It is important to stress that ω is not just missed profit; if we want to maximize profit, we should use model (12.26). The penalty coefficient must be suitably large, so that in the optimal solution we have some 
, only if there is really no way to satisfy demand. Information about which items are critical, as well as when they are, allows us to spot which customer orders are creating the problem; this is helpful in supporting a negotiation process with customers, who may be willing to wait a little more for delivery or may accept a substitute product. All of these adjustments can actually be modeled and explicitly represented in an optimization model, but some decision makers may find themselves in trouble when required to quantify the costs of these actions. Of course, if some items are strategically more important than others, we may use different penalty coefficients ωi.
As an alternative, we may relax capacity constraints by introducing auxiliary variables Omt. The resulting model is
The nonnegative variables Omt play the role of overtime capacity added to available capacity Rmt in constraint (12.50) and suitably penalized in the objective function (12.49). Observing which resources are critical, as well as when they are, may help in figuring out a way out of the dilemma. It is also possible to formulate a planning model allowing for true overtime work; in such a case, the variables Omt should be multiplied by the actual cost of overtime, rather than by a large penalty coefficient. The model should also express limits on overtime, reflecting constraints on the amount and type of allowable overtime work.
Leave a Reply