Robust Optimization for Power Systems Capacity Expansion under Uncertainty

We develop a robust optimization model for planning power system capacity expansion in the face of uncertain power demand. The model generates capacity expansion plans that are both solution and model robust. That is, the optimal solution from the model is ‘almost’ optimal for any realization of the demand scenarios (i.e. solution robustness). Furthermore, the optimal solution has reduced excess capacity for any realization of the scenarios (i.e. model robustness). Experience with a characteristic test problem illustrates not only the unavoidable trade-offs between solution and model robustness, but also the effectiveness of the model in controlling the sensitivity of its solution to the uncertain input data. The experiments also illustrate the differences of robust optimization from the classical stochastic programming formulation.     

A robust optimization model for multi-site production planning problem in an uncertain environment

This paper addresses the multi-site production planning problem for a multinational lingerie company in Hong Kong subject to production import/export quotas imposed by regulatory requirements of different nations, the use of manufacturing factories/locations with regard to customers’ preferences, as well as production capacity, workforce level, storage space and resource conditions at the factories. In this paper, a robust optimization model is developed to solve multi-site production planning problem with uncertainty data, in which the total costs consisting of production cost, labor cost, inventory cost, and workforce changing cost are minimized. By adjusting penalty parameters, production management can determine an optimal medium-term production strategy including the production loading plan and workforce level while considering different economic growth scenarios. The robustness and effectiveness of the developed model are demonstrated by numerical results. The trade-off between solution robustness and model robustness is also analyzed.     

Robust supply chain network design with multi-products for a company in the food sector

The paper aims to solve a problem faced by a company competing in the snacks market in Turkey. In line with the growth in this market, the company needs to make important decisions over the next few years about the timing and location of a new plant, its initial capacity, the timing and amount of additional capacity to be installed at the new and existing plants, the assignment of demand points to plants and the amount of raw materials to be shipped from suppliers to the plants in each period. The objective is to minimize the total cost of various components. The problem is formulated as a multi-period supply chain network design model with multi products. The resulting mixed-integer linear programming model is solved by the commercial solver CPLEX. This model enables us to carry out all analyses requested by the company in an efficient way. After this deterministic model is solved on the basis of a 9% annual increase in demand, it is extended to a minimax regret model to deal with uncertainty in demand quantities. The results suggest that opening the new plant in the city of İzmir is indeed a robust solution that is unaffected in different scenarios that are based on three distinct demand increase rates. Even though the location of the new plant remains unchanged with respect to scenarios, the optimal robust solution differs from the optimal solution of each scenario in terms of the capacity expansion decisions. After all obtained results had been communicated to the company managers and executives, the new plant construction was started in 2016 very close to the city that the mathematical model had determined. The new plant is expected to start operating in 2018.     

3.1. OR in banking

In this paper, we describe a deterministic multiperiod capacity expansion model in which a single facility serves the demand for many products. Potential applications for the model can be found in the capacity expansion planning of communication systems as well as in the production planning of heavy process industries. The model assumes that each capacity unit simultaneously serves a prespecified (though not necessarily integer) number of demand units of each product. Costs considered include capacity expansion costs, idle capacity holding costs, and capacity shortage costs. All cost functions are assumed to be nondecreasing and concave. Given the demand for each product over the planning horizon, the objective is to find the capacity expansion policy that minimizes the total cost incurred. We develop a dynamic programming algorithm that finds optimal policies. The required computational effort is a polynomial function of the number of products and the number of time periods. When the number of products equals one, the algorithm reduces to the well-known algorithm for the classical dynamic lot size problem.     

A model of clinker capacity expansion

This paper describes a model which has been applied in practice to determine an optimal plan for clinker capacity expansion. The problem was formulated as an integer linear program aiming to determine the optimal number, size and location of kilns to be introduced each year during a given planning horizon. The optimal solution is defined as the one which maximises the net present value (NPV) of the cash flow generated by the introduction and operation of new kilns subject to capacity and demand constraints. Various demand scenarios and capital expenditure structures were tested by means of the model and a number of possible locations for new kilns were evaluated. Finally, the benefits derived by the company where the application took place are listed.     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

Asymptotic analysis for target asset portfolio allocation with small transaction costs

In this paper we discuss the asset allocation in the presence of small proportional transaction costs. The objective is to keep the asset portfolio close to a target portfolio and at the same time to reduce the trading cost in doing so. We derive the variational inequality and prove a verification theorem. Furthermore, we apply the second order asymptotic expansion method to characterize explicitly the optimal no transaction region when the transaction cost is small and show that the boundary points are asymmetric in relation to the target portfolio position, in contrast to the symmetric relation when only the first order asymptotic expansion method is used, and the leading order is a constant proportion of the cubic root of the small transaction cost. In addition, we use the asymptotic results for the boundary points and obtain an expansion for the value function. The results are illustrated in the numerical example.     

Production lot-sizing with dynamic capacity adjustment

In this paper we study a single-item lot-sizing model in which production capacity can be adjusted from time to time. There are a number of different production capacity levels available to be acquired in each period, where each capacity level is assumed to be a multiple of a base capacity unit. To reduce the waste of excess of capacity but guarantee meeting the demand, it is important to decide which level of capacity should be acquired and how many units of the item should be produced for every period in the planning horizon. Capacity adjustment cost incurs when capacity acquired in the current period differs from the one acquired in the previous period. Capacity acquisition costs, capacity adjustment costs, and production costs in each period are all time-varying and depend on the capacity level acquired in that period. Backlogging is allowed. Both production costs and inventory costs are assumed to be general concave. We provide optimal properties and develop an efficient exact algorithm for the general model. For the special cases with zero capacity adjustment costs or fixed-plus-linear production costs, we present a faster exact algorithm. Computational experiments show that our algorithm is able to solve medium-size instances for the general model in a few seconds, and that cost can be reduced significantly through flexible capacity adjustment.     

Solution sensitivity-based scenario reduction for stochastic unit commitment

A two-stage stochastic program is formulated for day-ahead commitment of thermal generating units to minimize total expected cost considering uncertainties in the day-ahead load and the availability of variable generation resources. Commitments of thermal units in the stochastic reliability unit commitment are viewed as first-stage decisions, and dispatch is relegated to the second stage. It is challenging to solve such a stochastic program if many scenarios are incorporated. A heuristic scenario reduction method termed forward selection in recourse clusters (FSRC), which selects scenarios based on their cost and reliability impacts, is presented to alleviate the computational burden. In instances down-sampled from data for an Independent System Operator in the US, FSRC results in more reliable commitment schedules having similar costs, compared to those from a scenario reduction method based on probability metrics. Moreover, in a rolling horizon study, FSRC preserves solution quality even if the reduction is substantial.     

Stochastic and minimum regret formulations for transmission network expansion planning under uncertainties

After deregulation of the Power sector, uncertainty has increased considerably. Vertically integrated utilities were unbundled into independent generation, transmission and distribution companies. Transmission network expansion planning (TNEP) is now performed independent from generation planning. In this environment TNEP must include uncertainties of the generation sector as well as its own. Uncertainty in generation costs affecting optimal dispatch and uncertainty in demand loads are captured through composite scenarios. Probabilities are assigned to different scenarios. The effects of these uncertainties are transferred to the objective function in terms of total costs, which include: generation (dispatch), transmission expansion and load curtailment costs. Two formulations are presented: stochastic and minimum regret. The stochastic formulation seeks a design with minimum expected cost. The minimum regret formulation seeks a design with robust performance in terms of variance of the operational costs. Results for a test problem and a potential application to a real system are presented.     

A production planning model for an unreliable production facility: Case of finite horizon and single demand

We study a two-level inventory system that is subject to failures and repairs. The objective is to minimize the expected total cost so as to determine the production plan for a single quantity demand. The expected total cost consists of the inventory carrying costs for finished and unfinished items, the backlog cost for not meeting the demand due-date, and the planning costs associated with the ordering schedule of unfinished items. The production plan consists of the optimal number of lot sizes, the optimal size for each lot, the optimal ordering schedule for unfinished items, and the optimal due-date to be assigned to the demand. To gain insight, we solve special cases and use their results to device an efficient solution approach for the main model. The models are solved to optimality and the solution is either obtained in closed form or through very efficient algorithms.     

A modified active set algorithm for transportation discrete network design bi-level problem

Transportation discrete network design problem (DNDP) is about how to modify an existing network of roads and highways in order to improve its total system travel time, and the candidate road building or expansion plan can only be added as a whole. DNDP can be formulated into a bi-level problem with binary variables. An active set algorithm has been proposed to solve the bi-level discrete network design problem, while it made an assumption that the capacity increase and construction cost of each road are based on the number of lanes. This paper considers a more general case when the capacity increase and construction cost are specified for each candidate plan. This paper also uses numerical methods instead of solvers to solve each step, so it provides a more direct understanding and control of the algorithm and running procedure. By analyzing the differences and getting corresponding solving methods, a modified active set algorithm is proposed in the paper. In the implementation of the algorithm and the validation, we use binary numeral system and ternary numeral system to avoid too many layers of loop and save storage space. Numerical experiments show the correctness and efficiency of the proposed modified active set algorithm.     

A restriction and feasible direction algorithm for a capacity expansion problem

This paper examines the problem of optimally expanding existing capacity in order to meet an expected load in the context of an electric utility. A pre-optimization (Phase I) analysis is presented in order to easily determine (a) the capacities of existing equipments which will be used at an optimal solution; (b) the optimal (nonnegative) capacities of a subset of the new equipments to be purchased, and (c) a good quality starting solution. Having thus restricted a part of the solution to its optimal value, the problem is transformed into one of minimizing a convex, differentiable function, subject to a single generalized upper bounding constraint along with nonnegativity restrictions. An efficient specialization of a feasible directions algorithm (Phase II) is presented to solve this problem. The algorithm is versatile in that it provides a preview of whether or not all existing equipment capacity will be used in the light of available equipments, and which new equipments may be used in the optimal expansion plan. The algorithm can also solve the problem which enforces the use of all existing equipment capacity. Furhtermore, Phase I, which is the principal part of this algorithm, provides the user with insightful information. A numerical problem is analyzed to illustrate the effectiveness of the procedure.     

A new approach for solving fully intuitionistic fuzzy transportation problems

In this paper, a well-known network-structured problem called the transportation problem (TP) is considered in an uncertain environment. The transportation costs, supply and demand are represented by trapezoidal intuitionistic fuzzy numbers (TrIFNs) which are the more generalized form of trapezoidal fuzzy numbers involving a degree of acceptance and a degree of rejection. We formulate the intuitionistic fuzzy TP (IFTP) and propose a solution approach to solve the problem. The IFTP is converted into a deterministic linear programming (LP) problem, which is solved using standard LP algorithms. The main contributions of this paper are fivefold: (1) we convert the formulated IFTP into a deterministic classical LP problem based on ordering of TrIFNs using accuracy function; (2) in contrast to most existing approaches, which provide a crisp solution, we propose a new approach that provides an intuitionistic fuzzy optimal solution; (3) in contrast to existing methods that include negative parts in the obtained intuitionistic fuzzy optimal solution and intuitionistic fuzzy optimal cost, we propose a new method that provides non-negative intuitionistic fuzzy optimal solution and optimal cost; (4) we discuss about the advantages of the proposed method over the existing methods for solving IFTPs; (5) we demonstrate the feasibility and richness of the obtained solutions in the context of two application examples.     

A heuristic approach for capacity expansion of packet networks

We address the problem of expanding transmission capacity of an existing packet network over a multiperiod planning horizon, the objective being low total cost of expansion. Discrete capacity choices, interaction with routing decisions, and economy of scale in the cost of capacity make it extremely difficult to decide when, where and how much capacity to add. A fast heuristic solution method is developed based on the well established Flow Deviation routing algorithm. The heuristic begins by making myopic expansion decisions, which are then subsequently adjusted to account for economies of scale in the cost of capacity. Heuristic solutions are compared to a benchmark which approximates the real cost function by its linear lower envelope. Since the number of possible expansion plans is an exponential function of the number of edges, capacity choices, and periods in the planning horizon, a fast heuristic allows one to look beyond small problems at more realistically sized ones.     

Optimal replacement policies for two-unit machines with increasing running costs 1

A machine consists of two stochastically failing units. Failure of either of the units causes a failure of the machine and the failed unit has to be replaced immediately. Associated with the units are running costs which increase with the age of the unit because of increasing maintenance costs, decreasing output, etc.A preventive replacement policy is proposed under which, at failure points, we also replace the second unit if its age exceeds a predetermined control limit. It is proved that, for two identical units with exponential life-time distributions and linear running costs, this policy is optimal and the optimal control limit is calculated. In an additional model we take into consideration the length of time it takes to replace one unit or both units.The method of solution is a variation of dynamic semi-Markov programming. Analytical results are obtained and the influence of the various parameters on them is investigated. Finally, we study the saving due to our policy in comparison with a policy in which only failed units are replaced.     

Optimal operation for a bi-fuel thermal power plant by mathematical programming

This study is an attempt to provide the management of the Electricity Generating Authority of Thailand with an effective tool for determining the best operation of thermal units. A bi-fuel thermal power plant at North Bangkok, consisting of three thermal units, is considered. One of these units is adaptable to both lignite and fuel oil use, while the others use only fuel oil. A general optimization model, applicable to most power plants, is developed and a simplified version is applied to the North Bangkok Power Plant. A 0–1 mixed integer linear programming technique is used to find a method of operating the thermal units, which minimizes total fuel costs. Comparing the optimal solutions with actual operating strategies shows that savings in costs can be realised by implementing the model solution. Moreover, since the framework developed is quite general, it may be usefully applied to other power plant studies.     

A large-scale multilocation capacity planning model

In this paper, a large-scale multilocation capacity planning model is described. The model chooses a multiperiod schedule of openings, expansions, and closings of facilities, and assigns demand locations to these facilities. Although generic in nature, this model was developed to plan the evolution of material logistics systems over time. In order to have a truly practical tool, numerous features are considered including existing configuration, arbitrary demand patterns, concave operating costs, single-source assignments, demand location reassignment costs, and others.Such capacity planning models are highly combinatorial in nature, and are solved, in general, by heuristics. Our solution method has three major modules. First, an initial solution is generated by solving successively single-period problems using network optimization techniques complemented by other heuristics. Next, opening and closing decisions are adjusted and improved. Finally, demand location assignment decisions throughout the planning horizon are modified. The heuristic was tested on many problems of various sizes; computational experience is described.     

Strategic capability investments and competition for supply contracts

Suppliers often make proactive investments to strategically position themselves to win contracts with a large buyer. Such investments reduce the suppliers’ variable costs of serving the buyer’s demand. We show that an auction mechanism does not always benefit the buyer, the supply chain, or the society. We identify scenarios where the buyer can implement the supply chain and socially optimal solution by committing to a bilateral relationship with fair reimbursement, and forgoing the benefits of competition altogether. We explore the role of commitment by the buyer (to a procurement mechanism) and by the suppliers (to an investment level) by analyzing different timing games under symmetric and asymmetric information about suppliers’ types. We show that it never benefits anyone for the suppliers to commit first. Equilibrium investments and cost structures depend upon the buyer’s bargaining power (opportunity cost). However, the winning supplier’s investments are almost always below the supply chain optimal level.     

The multi-source Weber problem with constant opening cost

A constant fixed cost of establishing a facility is introduced within the framework of minisum facility location in the continuous space. The solution method developed uses a multi-phase heuristic that first solves a discrete version of the problem by existing methods to obtain an estimate of the optimal number of facilities. Some results are presented for test problems taken from the literature and compared with best-known solutions of the multi-source Weber problem with the addition of the appropriate fixed costs.