Optimizing with Arrays
This chapter shows you how to:
- Optimize using Decision and Constraint arrays
- Identify indexes that are intrinsic to the optimization
- Enter intrinsic arrays in Intrinsic Index lists
- Use Analytica’s Intelligent Array logic to set up multiple optimizations
- Refine a model by changing dimensions of the decision array
- Incorporate piecewise-linear (PWL) relationships into an LP.
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.
Intrinsic Constraint Index
Beer Distribution
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, create a new Decision or Constraint node and double-click it to open the Object Window. Press the Indexes button next to Intrinsic Indexes. This opens the index selection window. Select from the indexes list on the left and press 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 indexes that appear only in Constraints, but not in any Decision, is inherently ambiguous, and usually results 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.
<Tip="Tip"> It is good practice to always populate Intrinsic Index lists in all Decisions and Constraints used in an optimization problem.</Tip>
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.
Example 1: Beer Distribution LP, Base Case
Model Description
We start with an adaptation of a classic Linear Programming (LP) example: A large brewing company operates five breweries nationwide. Each brewery distributes product among four regions. Routes include all combinations of Breweries and Market regions. The challenge is to find the shipping pattern that minimizes distribution cost while a) meeting demand in each region, and b) observing production limits at each brewery. We assume that distribution cost per case of beer is proportional to the distance between the brewery and the region.
Setting up the Model
To explore and follow this example in Analytica, find the Beer Distribution LP1.ana model in the Optimizer Examples folder.
Brewery and Market (indexes)
There are five Breweries and four Market regions:
Index Brewery := ['Fairfield','Fort Collins','Jacksonville','Merrimack','St Louis'] Index Market := ['North','South','East','West']
Distance (input array)
Distance between breweries and markets is represented as a table dimensioned by Brewery and Market. Units are thousands of miles:
Variable Distance := Table(Brewery,Market)(1.8,2.2,3.4,0.1,0.3,1.2,2.4,1,2.9,1.8,0.6,3.3, 1.2,2.1,0.2,3.5,0.5,1.1,0.8,2.5)
Freight Price (input scalar value)
Freight Price is a simple scalar value of $5 per 1,000 miles per case of beer.
Variable Freight_price := 5
Production Limits (input array)
Production Limits indicate maximum capacity for each brewery in cases of beer: Variable Production_limits := Table(Brewery)(600K,250K,450K,300K,240K)
Delivery Targets (input array)
Delivery Targets indicate the minimum quota that each Market region must receive: Variable Delivery_target := Table(Market)(240K,280K,700K,500K)
Distribution Cost (intermediate array)
Distribution Cost per Case is Freight Price multiplied by Distance: Variable Dist_per_case := Freight_price * Distance
Shipment Quantities (input decision array)
The input decision array represents Shipment Quantities from each brewery to each region. It is a two-dimensional array indexed by Brewery and Market. The non-optimized values are not used anywhere else in the model so we can simply insert 1 as a dummy value across the array.(Initial guesses do not apply since this is a Linear Program.)
Units are cases of beer.
Staying Positive
We set the Lower Bound attribute to zero to disallow negative shipping values, along with the undesirable implication of turning perfectly good beer back into barley and hops.
Set Brewery and Market as intrinsic indexes
Finally and perhaps most importantly, we consider the index status for this array. The optimized solution should be in the same form as this table. It should also be integrated such that every array element has simultaneous influence over all other elements. Brewery and Market are both intrinsic indexes in this case.
Decision Shipment_Quantity := Array([Brewery, Market],1)
Shipment_Quantity attribute Lower Bound := 0
Shipment_Quantity attribute Intrinsic Indexes := [Brewery, Market]
Total Distribution (Objective)
Our goal is to minimize the total distribution cost. For each route, distribution cost is the Distribution Cost per Case multiplied by the Shipment Quantity for each route. The final objective is the sum for all routes: Objective Total_dist_cost := Sum(Shipment_Quantity * Dist_per_case, Brewery, Market)
Summing over Brewery and Market makes the objective a scalar value. This is a necessary condition for the optimization.
<Tip="Tip">Tip Every minimizing or maximizing optimization is based on a scalar objective value. In other words, intrinsic dimensions are not allowed in the Objective. If the Objective is not scalar, Analytica assumes the dimensions are extrinsic and performs independent optimizations for each scalar element in the Objective array. (For some optimization problems, the challenge is simply to find a solution that satisfies all constraints. This type of optimization has no objective at all.)</Tip>
Supply Constraint
The Supply Constraint ensures that shipment quantities from a single brewery to all available markets do not exceed the production limit for the brewery.
The Production Limit array is already dimensioned by Brewery. Since this array is an input to Supply Constraint, we expect Brewery to be a dimension of Supply Constraint as well, even though we don’t explicitly mention the index in the defining expression. This is the basic principle of array abstraction in Analytica.
The Supply Constraint array actually defines five constraints; one for each Brewery.
Set Brewery as an intrinsic index
Is Brewery an intrinsic index for the Supply Constraint array? The answer is YES because we need to enforce the respective Supply Constraints on all breweries simultaneously. Make sure to include Brewery in the Intrinsic Indexes list for the Supply Constraint node.
Constraint Supply_constraint := Sum(Shipment_Quantity, Market)<=Production_Limits Supply_constraint attribute Intrinsic Indexes := [Brewery]
Is Market an intrinsic index for the Supply Constraint? The answer is NO because Market is not a dimension of the array at all. The Sum() function eliminates it, leaving the array with only one dimension.
Demand Constraint
The Demand Constraint ensures that each market region receives a total quantity from all breweries greater than or equal to the market demand. The input array Delivery Targets is dimensioned by Market, and therefore the Demand Constraint will also have this dimension. The Demand Constraint array defines four constraints; one for each Market.
Set Market as an intrinsic index
Market is an intrinsic index for the Demand Constraint because the solution should meet quotas for all markets. Make sure to include Market in the Intrinsic Indexes list for the Demand Constraint node.
Constraint Demand_constraint := Sum(Shipment_Quantity, Brewery) >= Delivery_Target Demand_constraint attribute Intrinsic Indexes := [Market]
The Sum() function eliminates Brewery from the array.
Optimization Node
Remembering required attributes of the DefineOptimization() function as described in Chapter 1, we need to identify Decisions, Constraints, and the Objective to be minimized/maximized. Variable Optimization := DefineOptimization (Decision:Shipment_Quantity, Constraints:Supply_Constraint, Demand_Constraint, Minimize: Total_Dist_Cost)
Solution Node
We obtain the solution using the OptSolution() function. The first parameter identifies the optimization node. The second parameter (optional) identifies a specific Decision for which the solution should be represented.
Decision Optimized_Solution := OptSolution(Optimization, Shipment_Quantity)
Optimized Objective
The OptObjective() function calculates the minimized or maximized quantity. In this case, it represents the total distribution cost.
Variable Optimized_Objective := OptObjective(Optimization)
Status
Status text will confirm that the optimizer has found a solution
Variable Status := OptStatusText(Optimization)
Verifying the Optimization Setup
Evaluate the Optimization node
It is always a good idea to evaluate the Optimization node to confirm that the optimization is interpreting your problem as intended. The DefineOptimization() function evaluates as a special symbol, or array of symbols, indicating the type of optimization problem presented. In this case, «LP» confirms that this is a Linear Program as expected. Furthermore, the result shows only a single «LP» symbol. This confirms that the solution is the result of a single optimization run.
Evaluate Status
The OptStatusText() function confirms that the optimizer has found a feasible solution satisfying all constraints.
Checking the Result
Optimized Solution as an Array
Evaluate the Optimized Solution array to check the final result.
In this example we used the optional second parameter of the OptSolution() function to reference the Shipment Quantities array. This formats the output to match the same dimensions as the Decision input array. It is a two-dimensional table indexed by Market and Brewery.
Optimized Solution as a List
If you omit the second parameter of OptSolution(), Analytica creates a local index called DecisionVector and presents the result as a one-dimensional array. You can experiment with this output format by removing the second parameter from the OptSolution() function.
Variable Optimized_solution := OptSolution(Optimization)
Summary: Basic Beer Distribution LP
The basic beer distribution example demonstrates a simple Linear Program with a twodimensional decision array. There are two one-dimensional Constraint arrays, each over a different index. The model has only two indexes overall: Brewery and Market. Both indexes are intrinsic to the optimization. The example does not include any extrinsic indexes.
Example 2: Beer Distribution with Added Scenario
<footer> Optimization Characteristics / Optimizing with Arrays / Key Concepts: The Airline NLP Example</footer>
Enable comment auto-refresher