Stochastic network optimization models for investment planning

We describe and compare stochastic network optimization models for investment planning under uncertainty. Emphasis is placed on multiperiod a sset allocation and active portfolio management problems. Myopic as well as multiple period models are considered. In the case of multiperiod models, the uncertainty in asset returns filters into the constraint coefficient matrix, yielding a multi-scenario program formulation. Different scenario generation procedures are examined. The use of utility functions to reflect risk bearing attitudes results in nonlinear stochastic network models. We adopt a newly proposed decomposition procedure for solving these multiperiod stochastic programs. The performance of the models in simulations based on historical data is discussed.Research partially supported by National Science Foundation Grant No. DCR-861-4057 and IBM Grant No. 5785. Also, support from Pacific Financial Companies is gratefully acknowledged.     

On capacity expansion planning under strategic and operational uncertainties based on stochastic dominance risk averse management

A new scheme for dealing with uncertainty in scenario trees is presented for dynamic mixed 0–1 optimization problems with strategic and operational stochastic parameters. Let us generically name this type of problems as capacity expansion planning (CEP) in a given system, e.g., supply chain, production, rapid transit network, energy generation and transmission network, etc. The strategic scenario tree is usually a multistage one, and the replicas of the strategic nodes root structures in the form of either a special scenario graph or a two-stage scenario tree, depending on the type of operational activity in the system. Those operational scenario structures impact in the constraints of the model and, thus, in the decomposition methodology for solving usually large-scale problems. This work presents the modeling framework for some of the risk neutral and risk averse measures to consider for CEP problem solving. Two types of risk averse measures are considered. The first one is a time-inconsistent mixture of the chance-constrained and second-order stochastic dominance (SSD) functionals of the value of a given set of functions up to the strategic nodes in selected stages along the time horizon, The second type is a strategic node-based time-consistent SSD functional for the set of operational scenarios in the strategic nodes at selected stages. A specialization of the nested stochastic decomposition methodology for that problem solving is outlined. Its advantages and drawbacks as well as the framework for some schemes to, at least, partially avoid those drawbacks are also presented.     

Stochastic multi-site supply chain planning in textile and apparel industry under demand and price uncertainties with risk aversion

A multi-product, multi-period, multi-site supply chain production and transportation planning problem, in the textile and apparel industry, under demand and price uncertainties is considered in this paper. The problem is formulated using a two-stage stochastic programming model taking into account the production amount, the inventory and backorder levels as well as the amounts of products to be transported between the different plants and customers in each period. Risk management is addressed by incorporating a risk measure into the stochastic programming model as a second objective function, which leads to a multi-objective optimization model. The objectives aim to simultaneously maximize the expected net profit and minimize the financial risk measured. Two risk measures are compared: the conditional-value-at-risk and the downside risk. As the considered objective functions conflict with each other’s, the problem solution is a front of Pareto optimal robust alternatives, which represents the trade-off among the different objective functions. A case study using real data from textile and apparel industry in Tunisia is presented to illustrate the effectiveness of the proposed model and the robustness of the obtained solutions.     

An innovative approach for strategic capacity portfolio planning under uncertainties

This research studies multi-generation capacity portfolio planning problems under various uncertainty factors. These uncertainty factors include price uncertainties, demand fluctuation and uncertain product life cycle. The objective of this research is to develop an efficient algorithm that generates capacity portfolio policies robust to aforementioned uncertainties.     

Robust optimization for relief logistics planning under uncertainties in demand and transportation time

Emergency logistics is an essential component of post-disaster relief campaigns. However, there are always various uncertainties when making decisions related to planning and implementing post-disaster relief logistics. Considering the particular environmental conditions during post-disaster relief after a catastrophic earthquake in a mountainous area, this paper proposes a stochastic model for post-disaster relief logistics to guide the tactical design for mobilizing relief supply levels, planning initial helicopter deployments, and creating transportation plans within the disaster region, given the uncertainties in demand and transportation time. We then introduce a robust optimization approach to cope with these uncertainties and deduce the robust counterpart of the proposed stochastic model. A numerical example based on disaster logistics during the Great Sichuan Earthquake demonstrates that the model can help post-disaster managers to determine the initial deployments of emergency resources. Sensitivity analyses explore the trade-off between optimization and robustness by varying the robust optimization parameter values.     

A robust optimization model for agile and build-to-order supply chain planning under uncertainties

Supply chain planning as one of the most important processes within the supply chain management concept, has a great impact on firms’ success or failure. This paper considers a supply chain planning problem of an agile manufacturing company operating in a build-to-order environment under various kinds of uncertainty. An integrated optimization approach of procurement, production and distribution costs associated with the supply chain members has been taken into account. A robust optimization scenario-based approach is used to absorb the influence of uncertain parameters and variables. The formulation is a robust optimization model with the objective of minimizing the expected total supply chain cost while maintaining customer service level. The developed multi-product, multi-period, multi-echelon robust mixed-integer linear programming model is then solved using the CPLEX optimization studio and guidance related to future areas of research is given.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

Two improved formulations for the minimum latency problem

In network problems, latency is associated with the metric used to evaluate the length of the path from a root vertex to each vertex in the network. In this work we are dealing with two applications or variations of the minimum latency problem known as the repairman problem and the deliveryman problem. We have developed two integer formulations for the minimum latency problem and compared them with other two formulations from the literature for the time-dependent traveling salesman problem. The present work highlights the similarities and differences between the different formulations. In addition, we discuss the convenience of including a set of constraints in order to reduce the computation time needed to reach the optimal solution. We have carried out extensive computational experimentation on asymmetrical instances, since they provide the characteristics of the deliveryman and repairman problems in a better way.     

Second-order expansion for the expected regret risk in classification of one-parametric distributions

The plug-in rule is used for the classification of random observations into one of two regular one-parametric distributions. The maximum likelihood estimates of unknown parameters obtained from the stratified training sample are used. The second-order asymptotic expansion in terms of the inverses of the training sample sizes is derived for the expected regret risk. The closed-form expressions of the expansion coefficients are applicable for the performance evaluation of the proposed classification rule. Klaipėda University, H. Manto 84, 5808 Klaipėda; Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Published in Lietuvos Matematikos Rinkinys, Vol. 39, No. 2, pp. 220–230, April–June, 1999.     

Integer programming formulations for the minimum weighted maximal matching problem

Given an undirected graph, the problem of finding a maximal matching that has minimum total weight is NP-hard. This problem has been studied extensively from a graph theoretical point of view. Most of the existing literature considers the problem in some restricted classes of graphs and give polynomial time exact or approximation algorithms. On the contrary, we consider the problem on general graphs and approach it from an optimization point of view. In this paper, we develop integer programming formulations for the minimum weighted maximal matching problem and analyze their efficacy on randomly generated graphs. We also compare solutions found by a greedy approximation algorithm, which is based on the literature, against optimal solutions. Our results show that our integer programming formulations are able to solve medium size instances to optimality and suggest further research for improvement.     

Allocation of long-term financial transmission rights for transmission expansion

Long-term financial transmission rights (FTRs) could be used to create incentives for small-scale transmission investments. However, these new investments may cause negative externalities on existing FTRs. Therefore the system operator needs a protocol for awarding incremental FTRs for new transmission capacity that maximize investors’ preferences while simultaneously accounting for under-allocation of the existing network capacity by existing FTRs. To preserve revenue adequacy, the system operator calculates a minimum amount of currently unallocated FTRs (or proxy FTRs) that satisfies the power flow constraints in the existing network. The challenge is to define the proxy awards. Hogan proposes to define them as the best use of the current network along the same direction as the incremental FTR awards. This includes allowing positive or negative incremental FTR awards. In this paper we present an implementation through bi-level programming of Hogan’s proposal for allocation of long-term FTRs and apply it to a radial line and one of Hogan’s examples. Our results show that the simultaneous feasibility of the transmission investment depends on factors such as investor and preset proxy preferences, existing FTRs, and transmission capacity in both the existing network and all proposed expansions of it.     

Plane wave expansion and extended plane wave expansion formulations for Mindlin-Reissner elastic metamaterial thick plates

The plane wave expansion (PWE) and the extended plane wave expansion (EPWE) formulations are derived in order to obtain the complex dispersion relation of flexural waves in a metamaterial Mindlin-Reissner thick plate with multiple periodic resonators. These new formulations are useful to obtain more accurate results at higher frequencies than those based on Kirchhoff-Love thin plate theory. Multiple periodic resonators with multiple degrees of freedom (M-DOF) attached to metamaterial thick plates broaden the applications for wave attenuation in high frequencies.     

Hierarchical decision making in production and repair/replacement planning with imperfect repairs under uncertainties

In this paper, we analyse an optimal production, repair and replacement problem for a manufacturing system subject to random machine breakdowns. The system produces parts, and upon machine breakdown, either an imperfect repair is undertaken or the machine is replaced with a new identical one. The decision variables of the system are the production rate and the repair/replacement policy. The objective of the control problem is to find decision variables that minimize total incurred costs over an infinite planning horizon. Firstly, a hierarchical decision making approach, based on a semi-Markov decision model (SMDM), is used to determine the optimal repair and replacement policy. Secondly, the production rate is determined, given the obtained repair and replacement policy. Optimality conditions are given and numerical methods are used to solve them and to determine the control policy. We show that the number of parts to hold in inventory in order to hedge against breakdowns must be readjusted to a higher level as the number of breakdowns increases or as the machine ages. We go from the traditional policy with only one high threshold level to a policy with several threshold levels, which depend on the number of breakdowns. Numerical examples and sensitivity analyses are presented to illustrate the usefulness of the proposed approach.     

Symmetric boundary integral formulations for Helmholtz transmission problems

In this work we propose and analyze numerical methods for the approximation of the solution of Helmholtz transmission problems in two or three dimensions. This kind of problems arises in many applications related to scattering of acoustic, thermal and electromagnetic waves. Formulations based on boundary integral methods are powerful tools to deal with transmission problems in unbounded media. Different formulations using boundary integral equations can be found in the literature. We propose here new symmetric formulations based on a paper by Martin Costabel and Ernst P. Stephan (1985), that uses the Calderón projector for the interior and exterior problems to develop closed expressions for the interior and exterior Dirichlet-to-Neumann operators. These operators are then matched to obtain an integral system that is equivalent to the Helmholtz transmission problem and uses Cauchy data on the transmission boundary as unknowns. We show how to simplify the aspect and analysis of the method by employing an additional mortar unknown with respect to the ones used in the original paper, writing it in an appropriate way to devise Krylov type iterations based on the separate Dirichlet-to-Neumann operators.     

The minimum distance superset problem: formulations and algorithms

The partial digest problem consists in retrieving the positions of a set of points on the real line from their unlabeled pairwise distances. This problem is critical for DNA sequencing, as well as for phase retrieval in X-ray crystallography. When some of the distances are missing, this problem generalizes into a “minimum distance superset problem”, which aims to find a set of points of minimum cardinality such that the multiset of their pairwise distances is a superset of the input. We introduce a quadratic integer programming formulation for the minimum distance superset problem with a pseudo-polynomial number of variables, as well as a polynomial-size integer programming formulation. We investigate three types of solution approaches based on an available integer programming solver: (1) solving a linearization of the pseudo-polynomial-sized formulation, (2) solving the complete polynomial-sized formulation, or (3) performing a binary search over the number of points and solving a simpler feasibility or optimization problem at each step. As illustrated by our computational experiments, the polynomial formulation with binary search leads to the most promising results, allowing to optimally solve most instances with up to 25 distance values and 8 solution points.     

A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data

This paper deals with the strongly NP-hard minmax regret version of the minimum spanning tree problem with interval costs. The best known exact algorithms solve the problem in reasonable time for rather small graphs. In this paper an algorithm based on the idea of tabu search is constructed. Some properties of the local minima are shown. Exhaustive computational tests for various classes of graphs are performed. The obtained results suggest that the proposed tabu search algorithm quickly outputs optimal solutions for the smaller instances, previously discussed in the existing literature. Furthermore, some arguments that this algorithm performs well also for larger instances are provided.     

Activity network for planning and scheduling

A procedure for constructing a planning and scheduling network is given, where each activity to be scheduled is represented uniquely by a line. No events need be defined manually. Input is the set of activities with a list of preceding (but not necessarily immediately preceding) activities for each of them. Some comparisons with events network of Pert type are made.     

Models for planning capacity expansion of convenience stores under uncertain demand and the value of information

Several stochastic optimization models for planning capacity expansion for convenience store chains (or other similar businesses) are developed that incorporate uncertainty in future demand. All of these models generate schedules for capacity expansion, specifying the size, location, and timing of these expansions in order to maximize the expected profit to the company and to remain within a budget constraint on available resources. The models differ in how uncertainty is incorporated, specifically they differ in the point in the decision-making process that the uncertainty in the demand is resolved. Several measures of the value of information are defined by comparing the results from the different models. Two sample problems are given and their solutions for the various approaches compared.     

Modelling and analysis for capacity expansion planning in warehousing

In this paper, a dynamic programming model is developed for the purpose of establishing a warehouse capacity expansion schedule and underlying multi-item inventory policy that are jointly optimal. The optimal warehouse size over any segment of the planning horizon is obtained by solving a nonlinear optimisation problem, this being accomplished efficiently by exploiting the Kuhn–Tucker conditions. Repeating this procedure between each pair of time periods results in a discrete state space, so that the optimal capacity expansion schedule corresponds to a shortest path in a network. Managerial insights are provided through experimentation with the model.     

Variational formulations for transmission problems of the electromagnetic field

The subject of this article is a review of all possible transmission problems for electromagnetic phenomena. In particular, we study the case of a perfect dielectric and a perfect conductor via a (formal) limit with conductivity approaching zero or infinity and discuss the expected regularity of the involved unknowns. Finally, we formulate equivalent variational formulations for each considered problem.