A stochastic multiscale model for electricity generation capacity expansion

Long-term planning for electric power systems, or capacity expansion, has traditionally been modeled using simplified models or heuristics to approximate the short-term dynamics. However, current trends such as increasing penetration of intermittent renewable generation and increased demand response requires a coupling of both the long and short term dynamics. We present an efficient method for coupling multiple temporal scales using the framework of singular perturbation theory for the control of Markov processes in continuous time. We show that the uncertainties that exist in many energy planning problems, in particular load demand uncertainty and uncertainties in generation availability, can be captured with a multiscale model. We then use a dimensionality reduction technique, which is valid if the scale separation present in the model is large enough, to derive a computationally tractable model. We show that both wind data and electricity demand data do exhibit sufficient scale separation. A numerical example using real data and a finite difference approximation of the Hamilton–Jacobi–Bellman equation is used to illustrate the proposed method. We compare the results of our approximate model with those of the exact model. We also show that the proposed approximation outperforms a commonly used heuristic used in capacity expansion models.     

Robust shift generation in workforce planning

In this paper we apply robust optimization techniques to the shift generation problem in workforce planning. At the time that the shifts are generated, there is often much uncertainty in the workload predictions. We propose a model to generate shifts that are robust against this uncertainty. An adversarial approach is used to solve the resulting robust optimization model. In each iteration an integer nonlinear knapsack problem is solved to calculate the worst case workload scenario. We apply the approach to generate shifts in a real-life Air Traffic Controller workforce planning problem. The numerical results show the value of our approach.     

A planning and routing model for patient transportation in health care

In this paper, a problem concerning both the planning of health care services and the routing of vehicles, for patients transportation is addressed. An integrated approach, based on the column generation technique, is proposed to solve the planning and routing problem. Preliminary results on real data show the effectiveness of the proposed approach.     

Solving generation expansion planning problems with environmental constraints by a bundle method

We discuss the energy generation expansion planning with environmental constraints, formulated as a nonsmooth convex constrained optimization problem. To solve such problems, methods suitable for constrained nonsmooth optimization need to be employed. We describe a recently developed approach, which applies the usual unconstrained bundle techniques to a dynamically changing ??improvement function??. Numerical results for the generation expansion planning are reported.     

Parameter estimation in stochastic scenario generation systems

Scenario analysis offers an effective tool for addressing the stochastic elements in multi-period financial planning models. Critical to any scenario generation process is the estimation of the input parameters of the underlying stochastic model for economic factors. In this paper, we propose a new approach for estimation, known as the integrated parameter estimation (IPE). This approach combines the significant features of other well-known estimation techniques within a non-convex multiple objective optimization framework, with the objective weights controlling the relative importance of the features. We solve the non-convex optimization problem using adaptive memory programming – a variation of tabu search. Based on a short interest rate model using UK treasury rates from 1980 to 1995, the integrated approach compares favorably with maximum likelihood and the generalized method of moments. We also evaluate performance with Towers Perrin's CAP:Link scenario generation system.     

Lagrangian relaxation based algorithm for trigeneration planning with storages

Trigeneration is a booming power production technology where three energy commodities are simultaneously produced in a single integrated process. Electric power, heat (e.g. hot water) and cooling (e.g. chilled water) are three typical energy commodities in the trigeneration system. The production of three energy commodities follows a joint characteristic. This paper presents a Lagrangian relaxation (LR) based algorithm for trigeneration planning with storages based on deflected subgradient optimization method. The trigeneration planning problem is modeled as a linear programming (LP) problem. The linear cost function poses the convergence challenge to the LR algorithm and the joint characteristic of trigeneration plants makes the operating region of trigeneration system more complicated than that of power-only generation system and that of combined heat and power (CHP) system. We develop an effective method for the long-term planning problem based on the proper strategy to form Lagrangian subproblems and solve the Lagrangian dual (LD) problem based on deflected subgradient optimization method. We also develop a heuristic for restoring feasibility from the LD solution. Numerical results based on realistic production models show that the algorithm is efficient and near-optimal solutions are obtained.     

Shipment planning at oil refineries using column generation and valid inequalities

In this paper we suggest an optimization model and a solution method for a shipment planning problem. This problem concerns the simultaneous planning of how to route a fleet of ships and the planning of which products to transport in these ships. The ships are used for moving products from oil refineries to storage depots. There are inventory levels to consider both at the refineries and at the depots. The inventory levels are affected by the process scheduling at the refineries and demand at the depots. The problem is formulated using an optimization model including an aggregated representation of the process scheduling at the refineries. Hence, we integrate the shipment planning and the process scheduling at the refineries. We suggest a solution method based on column generation, valid inequalities, and constraint branching. The solution method is tested on data provided by the Nynas oil refinery company and solutions are obtained within 4 hours, for problem instances of up to 3 refineries, 15 depots, and 4 products when considering a time horizon of 42 days.     

Airline crew scheduling from planning to operations

Crew scheduling problems at the planning level are typically solved in two steps: first, creating working patterns, and then assigning these to individual crew. The first step is solved with a set covering model, and the second with a set-partitioning model. At the operational level, the (re) planning period is considerably smaller than during the strategic planning phase. We integrate both models to solve time critical crew recovery problems arising on the day of operations. We describe how pairing construction and pairing assignment are done in a single step, and provide solution techniques based on simple tree search and more sophisticated column generation and shortest-path algorithms.     

Large-scale optimization planning methods for the distribution of United States army munitions

Coordinating the distribution of ammunition and scheduling strategic transportation resources during military contingency operations is a complex process. This paper presents a large-scale optimization-based planning method that uses column generation to schedule the movement of ammunition and transportation resources through a time-space network representation of the distribution system. The optimization-based planner is initialized using a feasible solution generated by a heuristic planning method. Both the optimization-based planner and the heuristic planner generate plans with improved ship utilization and delivery tardiness values as compared to plans generated using current planning techniques. In addition, the heuristic planner is implemented within a closed-loop planning and control framework, and is used to generate plans on a rolling horizon basis.     

Heuristic algorithms for a multi-period multi-stop transportation planning problem

We consider a multi-period multi-stop transportation planning problem (MPMSTP) in a one-warehouse multi-retailer distribution system where a fleet of homogeneous vehicles delivers products from a warehouse to retailers. The objective of the MPMSTP is to minimize the total transportation distance for product delivery over the planning horizon while satisfying demands of the retailers. We suggest two heuristic algorithms based on the column generation method and the simulated annealing algorithm. Computational experiments on randomly generated test problems showed that the suggested algorithms gave better solutions than an algorithm currently used in practice and algorithms modified from existing algorithms for vehicle routing problems.     

Exact methods for large-scale multi-period financial planning problems

A relevant financial planning problem is the periodical rebalance of a portfolio of assets such that the portfolio’s total value exhibits certain characteristics. This problem can be modelled using a transition graph G to represent the future state space evolution of the corresponding economy and mathematically formulated as a linear programming problem. We present two different mathematical formulations of the problem. The first considers explicitly the set of the possible scenarios (scenario-based approach), while the second considers implicitly the whole set of scenarios provided by the graph G (graph-based approach). Unfortunately, for both the formulations the size of the corresponding linear programs can be huge even for simple financial problems. However, the graph-based approach seems to be a more powerful model, since it allows to consider a huge number of scenarios in a very compact formulation. The purpose of this paper is to present both heuristic and exact methods for the solution of large-scale multi-period financial planning problems using the graph-based model. In particular, in this paper we propose lower and upper bounds and three exact methods based on column, row and column/row generation, respectively. Since the methods based on column/row generation exploits simultaneously both the primal and the dual structure of the problem we call it Criss-Cross generation method. Computational results are given to prove the effectiveness of the proposed methods.      

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

Integrated lot-sizing and one-dimensional cutting stock problem with usable leftovers

This paper addresses the integration of the lot-sizing problem and the one-dimensional cutting stock problem with usable leftovers (LSP-CSPUL). This integration aims to minimize the cost of cutting items from objects available in stock, allowing the bringing forward production of items that have known demands in a future planning horizon. The generation of leftovers, that will be used to cut future items, is also allowed and these leftovers are not considered waste in the current period. Inventory costs for items and leftovers are also considered. A mathematical model for the LSP-CSPUL is proposed to represent this problem and an approach, using the simplex method with column generation, is proposed to solve the linear relaxation of this model. A heuristic procedure, based on a relax-and-fix strategy, was also proposed to find integer solutions. Computational tests were performed and the results show the contributions of the proposed mathematical model, as well as, the quality of the solutions obtained using the proposed method.

     

A variant of the dynamic programming algorithm for unit commitment of combined heat and power systems

The paper addresses the unit commitment in multi-period combined heat and power (CHP) production planning under the deregulated power market. In CHP plants (units), generation of heat and power follows joint characteristics, which means that production planning must be done in coordination. We introduce in this paper the DP-RSC1 algorithm, which is a variant of the dynamic programming (DP) algorithm based on linear relaxation of the ON/OFF states of the units and sequential commitment of units one by one. The time complexity of DP-RSC1 is proportional to the number of generating units in the system, the number of periods over the planning horizon and the time for solving a single-period economic dispatch problem. We have compared the DP-RSC1 algorithm with realistic power plants against the unit decommitment algorithm and the traditional priority listing method. The results show that the DP-RSC1 algorithm gives somewhat more accurate results (0.08–0.5% on average, maximum 10% for the individual sub-case) and executes 3–5 times faster on average than the unit decommitment algorithm. It is not surprising that the solution quality of the DP-RSC1 algorithm is much better than that of the priority listing method.     

Optimizing human activity patterns using global sensitivity analysis

Implementing realistic activity patterns for a population is crucial for modeling, for example, disease spread, supply and demand, and disaster response. Using the dynamic activity simulation engine, DASim, we generate schedules for a population that capture regular (e.g., working, eating, and sleeping) and irregular activities (e.g., shopping or going to the doctor). We use the sample entropy (SampEn) statistic to quantify a schedule’s regularity for a population. We show how to tune an activity’s regularity by adjusting SampEn, thereby making it possible to realistically design activities when creating a schedule. The tuning process sets up a computationally intractable high-dimensional optimization problem. To reduce the computational demand, we use Bayesian Gaussian process regression to compute global sensitivity indices and identify the parameters that have the greatest effect on the variance of SampEn. We use the harmony search (HS) global optimization algorithm to locate global optima. Our results show that HS combined with global sensitivity analysis can efficiently tune the SampEn statistic with few search iterations. We demonstrate how global sensitivity analysis can guide statistical emulation and global optimization algorithms to efficiently tune activities and generate realistic activity patterns. Though our tuning methods are applied to dynamic activity schedule generation, they are general and represent a significant step in the direction of automated tuning and optimization of high-dimensional computer simulations.     

Combining column generation and constraint programming to solve the tail assignment problem

Within the area of short term airline operational planning, Tail Assignment is the problem of assigning flight legs to individual identified aircraft while satisfying all operational constraints, and optimizing some objective function. In this article, we propose that Tail Assignment should be solved as part of both the short and the long term airline planning. We further present a hybrid column generation and constraint programming solution approach. This approach can be used to quickly produce solutions for operations management, and also to produce close-to-optimal solutions for long and mid term planning scenarios. We present computational results which illustrate the practical usefulness of the approach.     

A stochastic model for operating room planning with elective and emergency demand for surgery

This paper describes a stochastic model for Operating Room (OR) planning with two types of demand for surgery: elective surgery and emergency surgery. Elective cases can be planned ahead and have a patient-related cost depending on the surgery date. Emergency cases arrive randomly and have to be performed on the day of arrival. The planning problem consists in assigning elective cases to different periods over a planning horizon in order to minimize the sum of elective patient related costs and overtime costs of operating rooms. A new stochastic mathematical programming model is first proposed. We then propose a Monte Carlo optimization method combining Monte Carlo simulation and Mixed Integer Programming. The solution of this method is proved to converge to a real optimum as the computation budget increases. Numerical results show that important gains can be realized by using a stochastic OR planning model.     

Matching patient and physician preferences in designing a primary care facility network

This paper introduces an integer programming model for planning primary care facility networks, which accounts for the interests of different stakeholders while maximizing access to health care. Physician allocation to health-care facilities is explicitly modelled, which allows consideration of physician incentives in the planning phase. An illustrative case study in the Turkish primary care system is presented to show the implications of focusing on patient or physician preferences in the planning phase. A discussion of trade-offs between the different stakeholder preferences and some recommendations for modelling choices to match these preferences are provided. In the context of this case, we found that using an access measure that decays with distance, and incorporating nearest allocation constraints improves performance for all stakeholders. We also show that increasing the number of physicians may have adverse affects on access measures when physician preferences are addressed.     

Feasibility of motion planning on acyclic and strongly connected directed graphs

Motion planning is a fundamental problem of robotics with applications in many areas of computer science and beyond. Its restriction to graphs has been investigated in the literature, for it allows one to concentrate on the combinatorial problem abstracting from geometric considerations. In this paper, we consider motion planning over directed graphs, which are of interest for asymmetric communication networks. Directed graphs generalize undirected graphs, while introducing a new source of complexity to the motion planning problem: moves are not reversible. We first consider the class of acyclic directed graphs and show that the feasibility can be solved in time linear in the product of the number of vertices and the number of arcs. We then turn to strongly connected directed graphs. We first prove a structural theorem for decomposing strongly connected directed graphs into strongly biconnected components. Based on the structural decomposition, we show that the feasibility of motion planning on strongly connected directed graphs can be decided in linear time.     

Cooperative Cross-Entropy method for generating entangled networks

Survivability is rapidly becoming an important criterion in network design and planning. This is due to our increased dependence on ever more complex communication networks. Another important criterion which plays a central role in design and planning decisions is cost. As a result, network planners tend to design sparse networks to minimise cost. There is a class of networks known as entangled networks which seems to satisfy both criteria of survivability and sparseness. In this paper, we demonstrate how the Cross-Entropy method may be utilised to generate entangled networks. We also propose a cooperative optimisation approach to further improve the generation of an optimal entangled network.