|Shortest Path in a Stochastic Weighted Graph using Average, bPOE, and CVaR||Average, bPOE, CVaR (avg, bpoe, cvar)||This case study explains how to formulate and solve stochastic shortest path problems. The shortest path problem findsa shortest route from a starting point to a final point. Weights of arcs in the stochastic graph are random. We solved problems with Average, Buffered Probability of Exceedance (bPOE) and Conditional Value-at-Risk (CVaR) risk measures.|
|Travelling Salesman||Travelling Salesman Problem (TSP)||Several Travelling Salesman Problems (TSPs): plain TSPs and TSPs with constraints.|
|Cell Towers allocation with Probability of Exceedance and VaR functions||Probability of Exceedance (Pr_pen), Mean Absolute Penalty (Meanabs), Value-at-Risk (Var_risk)||This Case study demonstrates a scenario based optimization framework for solving Partial Set Covering problem and Maximal Covering Location problem. We use Probability of Exceedance (POE) and Value-at-Risk (VaR) functions to bound and minimize some fraction of uncovered nodes.|
|Optimal Allocation of Stock Levels and Stochastic Customer Demands to a Capacitated Resource||Average Partial Moment Penalty Normal Independent for Loss (Avg_pm_pen_ni)||A single-period model is defined to solve a joint customer demand allocation and multiple-item stock level problem for a resource that must respond to uncertain customer demands. It is assumed that customer demands are statistically independent and that the demands for items are revealed upon being visited by a repair person (after problem diagnosis). There are m potential customers; the supplier must choose a subset of customers to serve using a capacity constrained resource (e.g., a vehicle) and the optimal resource stock level for each item. It is assumed that during a given customer-service visit, any item required for the customer’s service that is not available results in an item-specific penalty cost for an inability to complete service. For each item carried on the vehicle, a variable cost is incurred (e.g., for loading/unloading and/or transporting the part). A customer-specific revenue is gained for each customer visit. The objective is to maximize the expected profit, or equivalently, to minimize the expected cost (equal to the negative of expected profit). We state objective in minimization form and refer to this objective as the expected cost. Performance is described by the sum of Partial Moments based on normal distributions. This sum of Partial Moments is compactly presented with the Average Partial Moment Penalty Normal Independent for Loss function. Such presentation creates a simple and transparent code.|
|Optimal Crop Production and Insurance Coverage||Average Gain (Avg_g), Probability of Exceedance (Pr_pen), CVaR (Cvar_risk), VaR (Var_risk)||Optimization of crop production scheduling and insurance coverage under risk constraints on CVaR, VaR, and Probability Exceeding Penalty. The optimization provides planting schedule for several crops and selects most profitable insurance policies corresponding to different sets of scenarios based on climate predictions.|
|Optimal Tests Selection||Cvar Component Positive (Cvar_comp_pos), Probability of Exceedance for Gain Multiple Normal Independent (Prmulti_pen_ni_g)||This case study considers the problem of optimal selection of tests subject to several constraints on available resources (e.g. money, times, and people). If each resource estimate is accurate, then the problem of optimal selection of tests is formulated as Deterministic Linear Programming Assignment model with boolean decision variables. To take into account uncertainty in resource estimates two models are used: robust and stochastic models.
The Robust model conservatively increases the need in each resource by 20% of its average consumption for 20% largest consumers.
The Stochastic model is based on the assumption that resource consumption by each test is independent normally distributed random value.
The Robust and Stochastic models provide more realistic solutions than the Deterministic Linear Programming model. Moreover, the Stochastic model reduces many resource constraints to one constraint and allows the sensitivity analysis.
|Production Planning||Fixed Charge Positive (Fxchg_pos)||Optimization setup for a single item capacitated lot size model. For a finite time horizon T, there is demand for a single item in each production period. This demand must be satisfied by the production in that period or by inventory from previous periods, that is, no backlogging is allowed. The production level cannot exceed capacity limit. Two types of costs: production and holding costs. Production, if initiated in a certain period, requires initial setup cost. The objective is to find a feasible production plan that minimizes total costs.|
|Project Selection||Fixed Charge (Fxchg)||Optimization setup for a “project selection” problem. Each project, if chosen, requires an initial capital. Projects are selected to maximize the net present value of the investment subject to constraint on the initial available capital. This problem belongs to the class of “knapsack optimization” problems. Two equivalent problem formulations with different presentation of the knapsack constraint: the first formulation uses a linear function with Boolean decision variables, and the second one uses PSG “fxchg_pos” function.|
|Stochastic Multicommodity Network Flow Problem||Probability of Exceedance Multiple (Prmulti_pen), Cardinality Negative (Cardn_neg)||Optimization of a stochastic multi-commodity network flow problem with a probabilistic constraint based on discrete scenarios. For every commodity a pair of source and absorption vertices is defined. Demands in absorption vertices are random, therefore, flows from the source to absorption vertices are also random. The problem finds optimal capacities of arcs in the network by minimizing the total cost of the networksubject to constraints. The joint distribution of demands for all commodities is given by a set of scenarios. The flow through an arc is defined as the sum of flows of all commodities through this arc. The total cost of arcs is a linear function of arc capacities. The objective is to find capacitiesof arcs minimizing the total cost of the network and satisfying the random flow constraintwith prescribed probability. Three optimization problems with different random flow chance constraints:
1) constraint on probability of insufficient capacity at least one arc;
2) constraint on a fraction of scenarios on which network flows may exceed capacities;
3) constraint on probability that random recourse function exceeds 0.
|Network Optimization by Minimization of Cardinality of Upper Average (CUA)||Cardinality of Upper Average (CUA); Buffered Probability of Exceedance (bPOE)||This case study solves a network flow problem where the goal is to minimize the number of overloaded transshipment nodes as supply moves through a weighted graph (i.e. transportation network) from supply nodes, through transshipment nodes, to ending demand nodes.|