Arrays in Optimization Models and Array Abstraction
Arrays in Optimization Models and Array Abstraction
The textbook description of LP, QP and NLP formulations in the previous chapter depicted the set of decision variables as a one-dimensional vector, along with a linear vector of constraints. However, array-valued variables and array-valued constraints arise naturally in many optimization problems, and it is often more natural and convenient to formulate specific decision variables as multi-dimensional arrays, with dimensionality differing from decision to decision.
Arrays in Optimization Problems
Structured optimization allows you to easily define array-valued decision variables, using the dimensionality that is natural to your problem. Additionally, since the variables appearing in a constraint expression may themselves be array-valued when computed, a single inequality expression may expand to be a multi-dimensional array of scalar constraints. Internally, structured optimization takes care of flattening and concatenating all these decision and constraint arrays for solution by the underlying solver engine so that you don’t have to worry about it.
Array Abstraction
As experienced users know, array abstraction is an important feature of Analytica. Array abstraction allows an index to be added to the input of a computation, such that the original computation is carried out repeatedly for each new input value without having to alter the original computation. Array abstraction in Analytica is a universal concept that derives its power from the fact that it applies at every level, from simple expressions all the way up to entire models. Optimization models are no different. If we have a submodel that solves an optimization problem, we can vary the set of inputs across a new index and repeat the optimization repeatedly for a set of scenario combinations. Thus, array abstraction gives rise to arrays of optimization problems.
Intrinsic and Extrinsic Indexes
Analytica with its Structured Optimization feature therefore provides both the ability to incorporate arrays within an optimization, as well as array abstract to obtain arrays of optimizations. This leads to a distinction, in which we can describe indexes as being either intrinsic or extrinsic. Intrinsic indexes lead to arrays within an optimization problem, while extrinsic indexes lead to arrays of optimizations. An intrinsic index is what other optimization environments would simply call an index. It makes all of its elements available to the optimizer during a single optimization run. An extrinsic index is available for array abstraction in Analytica. If you start with model that performs a single optimization, and then add a new dimension to one of the input variables, Analytica will generally treat the new index as extrinsic and abstract over it. You will now have an array of optimizations corresponding to each element of the extrinsic index. The inherent support for both types of arrays is a key differentiator of Analytica’s Structured Optimization. In this chapter we explain how to control array handling in Analytica and work through a detailed example that handles indexes in both ways.
Narrative Examples
Here are some narrative examples to help clarify what it means for an optimization to handle an index intrinsically or extrinsically:
Breakfast of Champions
Suppose you have a model that decides on the best breakfast for you to eat every day of the wrestling season. Your objective is to win as many matches as possible. The model has an index of Days since there will be a breakfast for each day.
Extrinsic Decision Index
If the Days index is treated extrinsically, the model will perform a separate optimization for each day. If you have a match on a particular day, the model will probably advise you to eat a hearty breakfast to fuel your victory. On rest days, there is no match to win so the model won’t care what you eat. Each optimization is completely oblivious of the existence of any day other than the one it is considering. In this scenario you will probably win your early matches but you also risk gaining weight and getting bumped up to a heavier class later in the season. The total number of matches you win throughout the season will not necessarily be optimized. If fact, it would be impossible for your model to optimize any objective that spans more than a single day.
Intrinsic Decision Index
If the Days index in intrinsic, the model will perform a single optimization that outputs your entire breakfast schedule for the season. The intrinsic character of the index is clear when you consider that each element of the array can influence outcomes across the entire index of Days.
Beer Distribution
Intrinsic Constraint Index
This chapter includes a detailed LP example in which there are multiple breweries shipping to multiple regions. Each brewery has a maximum capacity limit, and each region has a minimum demand to be met. In the example, we express capacity constraints for all breweries as one-dimensional array in the Supply Constraint node, using Brewery as the index for the array. We have a similar array of Demand constraints using Region as the index. The key to the problem is that all constraints must hold simultaneously for the solution to work. Therefore, Brewery and Region are intrinsic indexes. If they were extrinsic instead, we would have an array of optimizations; one for each combination of Brewery and Region. Each optimization would consider a scenario where only a single combination of constraints would apply. For example, “What if the Fairfield brewery is limited to 600k cases of beer, and the Western region must receive at least 500k, but no other supply or demand constraints apply?” Answering a series of these strange questions would not be useful to us.
Extrinsic Index
To demonstrate the role of an extrinsic index in the Beer Distribution example, we imagine that regional beer demand will depend on the winner of the World Series. The index titled World Series Winner includes two mutually exclusive scenarios for which we want to perform separate optimizations. This is an example of an extrinsic index available for array abstraction. While searching for the optimum beer distribution solution for a particular scenario, it is not necessary for the optimizer to know that the other scenario exists.
Setting the Intrinsic Index Attribute
Decision and Constraint nodes contain a special attribute called Intrinsic Indexes. Populating this list will ensure that Analytica Optimizer interprets the array as intended. The process is similar to the way you identify indexes when defining a table.
To see how this works, follow the steps below:
- Create a new Decision or Constraint node.
- Double-click the node you created in step 1 to open the Object window.
- Click the Indexes button next to Intrinsic Indexes to open the Index Selection window.
- Select from the list of indexes on the left and click the Transfer button to move them to the Selected Indexes window on the right.
- Click OK.
Analytica infers Intrinsic Indexes
You can leave the Intrinsic Indexes attribute unspecified in either decisions and constraints, in which case DefineOptimization() infers the intrinsic indexes from the problem formulation. Whenever your intention is different from what these heuristics infer, you will need to specify the intrinsic indexes explicitly. An index that appears only in Constraints, but not in any Decision, are inherently ambiguous, and usually result in a meaningful (but different) optimization problem, whether it is intrinsic or extrinsic. Analytica will assume such indexes are extrinsic, so if you want them to be intrinsic you must specify them explicitly in the Constraint’s intrinsic indexes attribute.
Extrinsic Indexes
Whenever the optimizer does not need to consider the index as a whole -- as when considering only a single index element-- the index is extrinsic to the optimization. If a solution array has an extrinsic dimension it displays the results of multiple independent optimization runs along the extrinsic dimension. This is simply the concept of array abstraction applied to optimizations.
Extrinsic by omission
Extrinsic indexes are never explicitly specified — an index is extrinsic when it is present but not intrinsic. The intrinsic indexes attribute for a Decision variable is inclusive and exhaustive, which means that every index listed is always included as an intrinsic index, and only those listed are intrinsic indexes of the decision. The intrinsic indexes attribute of a constraint is inclusive but not exhaustive. Any index listed there will become an intrinsic index for the constraint, but if other indexes are present that are already intrinsic elsewhere in the optimization, they too will be intrinsic to the constraint. The non-exhaustive nature of the intrinsic index specification allows optimization models to array abstract consistently.
What if all dimensions of an array are extrinsic?
In some cases, you may want to explicitly tell the optimizer that all indexes of the Decision are extrinsic. This means that you intend for the optimizer to treat the Decision as a scalar value. To do this, open the Intrinsic Indexes attribute and click OK without selecting any indexes. Analytica displays a dialog box asking you to confirm whether you want to designate the array as Scalar or leave the list Unspecified.
See Also
Enable comment auto-refresher