Optimizing with Arrays
Arrays in Optimization Models and Array Abstraction
Arrays in Optimization Problems
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. 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 univeral 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.
A Necessary Distinction Comes About
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 aheavier class later in the season. The total number of matches you win throughout theseason 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.
<footer> Optimization Characteristics / Optimizing with Arrays / Key Concepts: The Airline NLP Example</footer>
Enable comment auto-refresher