The Deregulated Electricity Market Viewed as a Bilevel Programming Problem

In this paper, we present a bilevel programming formulation of a deregulated electricity market. By examining the electricity market in this format, we achieve two things. First, the relation of the deregulated electricity market to general economic models that can be formulated as bilevel programming problems (e.g. Stackelberg leader-follower games and principal-agency models) becomes clear. Secondly, it provides an explanation of the reason why the so-called “folk theorems” can be proven to be false for electricity networks. The interpretation of the deregulated electricity market as a bilevel program also indicates the magnitude of the error that can be made if the electricity market model studied does not take into account the physical constraints of the electric grid, or oversimplifies the electricity network to a radial network.     

Conservative allocation models for outbound containers in container terminals

This paper examines location assignment for outbound containers in container terminals. It is an extension to the previous modeling work of Kim et al. (2000) and Zhang et al. (2010). The previous model was an “optimistic” handling way and gave a moderate punishment for placing a lighter container onto the top of a stack already loaded with heavier containers. Considering that the original model neglected the stack height and the state-changing magnitude information when interpreting the punishment parameter and hid too much information about the specific configurations for a given stack representation, we propose two new “conservative” allocation models in this paper. One considers the stack height and the state-changing magnitude information by reinterpreting the punishment parameter and the other further considers the specific configurations for a given stack representation. Solution qualities for the “optimistic” and the two “conservative” allocation models are compared on two performance indicators. The numerical experiments indicate that both the first and second “conservative” allocation models outperform the original model in terms of the two performance indicators. In addition, to overcome computational difficulties encountered by the dynamic programming algorithm for large-scale problems, an approximate dynamic programming algorithm is presented as well.     

Stochastic programming: Potential hazards when random variables reflect market interaction

There are two types of random phenomena modeled in stochastic programs. One type is what we may term “external” or “natural” random variables, such as temperature or the roll of a dice. But in many other cases, random variables are used to reflect the behavior of other market participants. This is the case for such as price and demand of a product. Using simple game theoretic models, we demonstrate that stochastic programming may not be appropriate in these cases, as there may be no feasible way to replace the decisions of others by a random variable, and arrive at the correct decision. Hence, this simple note is a warning against certain types of stochastic programming models. Stochastic programming is unproblematic in pure forms of monopoly and perfect competition, and also with respect to external random phenomena. But if market power is involved, such as in oligopolies, the modeling may not be appropriate.     

A Coupled System of Integrodifferential Equations Arising in Liquidity Risk Model

We study the mathematical aspects of the portfolio/consumption choice problem in a market model with liquidity risk introduced in (Pham and Tankov, Math. Finance, 2006, to appear). In this model, the investor can trade and observe stock prices only at exogenous Poisson arrival times. He may also consume continuously from his cash holdings, and his goal is to maximize his expected utility from consumption. This is a mixed discrete/continuous time stochastic control problem, nonstandard in the literature. We show how the dynamic programming principle leads to a coupled system of Integro-Differential Equations (IDE), and we prove an analytic characterization of this control problem by adapting the concept of viscosity solutions. This coupled system of IDE may be numerically solved by a decoupling algorithm, and this is the topic of a companion paper (Pham and Tankov, Math. Finance, 2006, to appear).     

Robust portfolio selection involving options under a “ marginal+joint ” ellipsoidal uncertainty set

In typical robust portfolio selection problems, one mainly finds portfolios with the worst-case return under a given uncertainty set, in which asset returns can be realized. A too large uncertainty set will lead to a too conservative robust portfolio. However, if the given uncertainty set is not large enough, the realized returns of resulting portfolios will be outside of the uncertainty set when an extreme event such as market crash or a large shock of asset returns occurs. The goal of this paper is to propose robust portfolio selection models under so-called “ marginal+joint” ellipsoidal uncertainty set and to test the performance of the proposed models. A robust portfolio selection model under a “marginal + joint” ellipsoidal uncertainty set is proposed at first. The model has the advantages of models under the separable uncertainty set and the joint ellipsoidal uncertainty set, and relaxes the requirements on the uncertainty set. Then, one more robust portfolio selection model with option protection is presented by combining options into the proposed robust portfolio selection model. Convex programming approximations with second-order cone and linear matrix inequalities constraints to both models are derived. The proposed robust portfolio selection model with options can hedge risks and generates robust portfolios with well wealth growth rate when an extreme event occurs. Tests on real data of the Chinese stock market and simulated options confirm the property of both the models. Test results show that (1) under the “ marginal+joint” uncertainty set, the wealth growth rate and diversification of robust portfolios generated from the first proposed robust portfolio model (without options) are better and greater than those generated from Goldfarb and Iyengar’s model, and (2) the robust portfolio selection model with options outperforms the robust portfolio selection model without options when some extreme event occurs.     

Robust multi-market newsvendor models with interval demand data

We present a robust model for determining the optimal order quantity and market selection for short-life-cycle products in a single period, newsvendor setting. Due to limited information about demand distribution in particular for short-life-cycle products, stochastic modeling approaches may not be suitable. We propose the minimax regret multi-market newsvendor model, where the demands are only known to be bounded within some given interval. In the basic version of the problem, a linear time solution method is developed. For the capacitated case, we establish some structural results to reduce the problem size, and then propose an approximation solution algorithm based on integer programming. Finally, we compare the performance of the proposed minimax regret model against the typical average-case and worst-case models. Our test results demonstrate that the proposed minimax regret model outperformed the average-case and worst-case models in terms of risk-related criteria and mean profit, respectively.     

Decomposition methods for a spatial model for long-term energy pricing problem

We consider an energy production network with zones of production and transfer links. Each zone representing an energy market (a country, part of a country or a set of countries) has to satisfy the local demand using its hydro and thermal units and possibly importing and exporting using links connecting the zones. Assuming that we have the appropriate tools to solve a single zonal problem (approximate dynamic programming, dual dynamic programming, etc.), the proposed algorithm allows us to coordinate the productions of all zones. We propose two reformulations of the dynamic model which lead to different decomposition strategies. Both algorithms are adaptations of known monotone operator splitting methods, namely the alternating direction method of multipliers and the proximal decomposition algorithm which have been proved to be useful to solve convex separable optimization problems. Both algorithms present similar performance in theory but our numerical experimentation on real-size dynamic models have shown that proximal decomposition is better suited to the coordination of the zonal subproblems, becoming a natural choice to solve the dynamic optimization of the European electricity market.     

带最小交易单位的Markowitz模型及算法

在证券交易市场中,交易规则要求购买的股票数量为整数.基于这种情况,将Markowitz模型中资产的投资比例改进为资产的投资数量,构造了一个二次整数规划模型.设计了求解该模型的算法,经过实证分析,算法是有效的.     

Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

To solve linear programming problems by interior point methods an approximately centered interior point has to be known. Such a point can be found by an algorithmic approach – a so-called phase 1 algorithm or centering algorithm. For random linear programming problems distributed according to the rotation symmetry model, especially with normal distribution, we present probabilistic results on the quality of the origin as starting point and the average number of steps of a centering algorithm.     

邮路规划与邮车调度最优化理论研究

对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案.问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离;然后以Fijk为决策变量,以邮车工作时间、车辆运载能力为主要约束,建立以总空载损失费用最小为目标的0-1非线性规划模型,运用规划软件Lingo求解.问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解;然后,建立各县区的最短路矩阵,同样建立规划模型IIB求解各县运输方案.问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分;然后采用模型IIB求解.第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址,并运用规划模型II求解的到新方案.最后,我们对两种区域划分调整方法还进行了定量的分析.     

Backfitting neural networks

Summary  Regression and classification problems can be viewed as special cases of the problem of function estimation. It is rather well known that a two-layer perceptron with sigmoidal transformation functions can approximate any continuous function on the compact subsets ofRP if there are sufficient number of hidden nodes. In this paper, we present an algorithm for fitting perceptron models, which is quite different from the usual backpropagation or Levenberg-Marquardt algorithm. This new algorithm based on backfitting ensures a better convergence than backpropagation. We have also used resampling techniques to select an ideal number of hidden nodes automatically using the training data itself. This resampling technique helps to avoid the problem of overfitting that one faces for the usual perceptron learning algorithms without any model selection scheme. Case studies and simulation results are presented to illustrate the performance of this proposed algorithm.     

An Algorithm for Solving the Linear Goal Programming Problem by Solving its Dual

Goal programming, and in particular lexicographic goal programming (i.e. goal programming within a so-called ‘pre-emptive priority’ structure or having non-Archimedean weights), has become one of the most widely used of the approaches for multi-objective mathematical programming. While also applicable to non-linear or integer models, most of the literature has considered the lexicographic linear goal-programming model and its solution via primal simplex-based methods. However, in many cases, enhanced efficiency (and significant additional flexibility) may be gained via an investigation of the dual of this problem. In this paper we consider an algorithm for solving such a dual and also indicate how it may be implemented on conventional (i.e. single objective) simplex software.     

中国数学规划学科发展概述

数学规划又称数学优化, 是运筹学的一个重要分支. 它主要研究在一定约束条件下, 如何求一个实数或者整数变量的实函数的最大值或者最小值. 它是运筹学和管理科学中最常用的一种建模工具和求解问题的方法, 在工程、经济和金融等领域有非常广泛的应用. 首先简单介绍数学规划的发展历史、应用领域及其主要研究方向; 然后简述数学规划的发展现状和在中国的发展进程; 最后, 讨论数学规划若干研究前沿问题与研究展望.     

Multi-objective stochastic programming for portfolio selection

Generally, in the portfolio selection problem the Decision Maker (DM) considers simultaneously conflicting objectives such as rate of return, liquidity and risk. Multi-objective programming techniques such as goal programming (GP) and compromise programming (CP) are used to choose the portfolio best satisfying the DM’s aspirations and preferences. In this article, we assume that the parameters associated with the objectives are random and normally distributed. We propose a chance constrained compromise programming model (CCCP) as a deterministic transformation to multi-objective stochastic programming portfolio model. CCCP is based on CP and chance constrained programming (CCP) models. The proposed program is illustrated by means of a portfolio selection problem from the Tunisian stock exchange market.     

Charging scheduling problem of an M-to-N electric vehicle charger

This study investigates a real case of charging scheduling of an electric vehicle charger with multiple ports called M-to-N charger. The charger is designed for a multi-unit dwelling facility and can charge N electric vehicles simultaneously despite the supplied charging capacity being limited to only M electric vehicles. The electric vehicles arrive at the charger randomly and stay for their desired length of time, during which they must be charged as much as possible with minimum electric cost. The scheduling problem considers four objectives: maximizing the total charging amount, minimizing the total charging cost, minimizing the charging completion time, and maximizing the charging balance among the electric vehicles. A mixed-integer linear programming model and a relaxation-based heuristic algorithm are developed. Computational experiment results show that the proposed heuristic algorithm can generate schedules within 8 s for this case study by using an open-source linear programming solver. Compared with the mixed-integer programming algorithm, the proposed heuristic algorithm can provide solutions with less than 7% charging amount gap and 4% price gap. The proposed heuristic algorithm is successfully implemented in a real M-to-N charger.     

A bicriteria solid transportation problem with fixed charge under stochastic environment

In this paper, a bicriteria solid transportation problem with stochastic parameters is investigated. Three mathematical models are constructed for the problem, including expected value goal programming model, chance-constrained goal programming model and dependent-chance goal programming model. A hybrid algorithm is also designed based on the random simulation algorithm and tabu search algorithm to solve the models. At last, some numerical experiments are presented to show the performance of models and algorithm.     

On approximating complex quadratic optimization problems via semidefinite programming relaxations

In this paper we study semidefinite programming (SDP) models for a class of discrete and continuous quadratic optimization problems in the complex Hermitian form. These problems capture a class of well-known combinatorial optimization problems, as well as problems in control theory. For instance, they include the MAX-3-CUT problem where the Laplacian matrix is positive semidefinite (in particular, some of the edge weights can be negative). We present a generic algorithm and a unified analysis of the SDP relaxations which allow us to obtain good approximation guarantees for our models. Specifically, we give an -approximation algorithm for the discrete problem where the decision variables are k-ary and the objective matrix is positive semidefinite. To the best of our knowledge, this is the first known approximation result for this family of problems. For the continuous problem where the objective matrix is positive semidefinite, we obtain the well-known π /4 result due to Ben-Tal et al. [Math Oper Res 28(3):497–523, 2003], and independently, Zhang and Huang [SIAM J Optim 16(3):871–890, 2006]. However, our techniques simplify their analyses and provide a unified framework for treating those problems. In addition, we show for the first time that the gap between the optimal value of the original problem and that of the SDP relaxation can be arbitrarily close to π /4. We also show that the unified analysis can be used to obtain an Ω(1/ log n)-approximation algorithm for the continuous problem in which the objective matrix is not positive semidefinite. This research was supported in part by NSF grant DMS-0306611.     

Solving the sum-of-ratios problem by a stochastic search algorithm

In spite of the recent progress in fractional programming, the sum-of-ratios problem remains untoward. Freund and Jarre proved that this is an NP-complete problem. Most methods overcome the difficulty using the deterministic type of algorithms, particularly, the branch-and-bound method. In this paper, we propose a new approach by applying the stochastic search algorithm introduced by Birbil, Fang and Sheu to a transformed image space. The algorithm then computes and moves sample particles in the q − 1 dimensional image space according to randomly controlled interacting electromagnetic forces. Numerical experiments on problems up to sum of eight linear ratios with a thousand variables are reported. The results also show that solving the sum-of-ratios problem in the image space as proposed is, in general, preferable to solving it directly in the primal domain.     

Improvements by analyzing the efficient frontier in DEA

In this paper, we suggest four types of improvements for making inefficient DMUs efficient in the CCR model with the minimal change of input and output values. Moreover, we propose an algorithm for calculating such improvements by applying quadratic programming techniques. Furthermore, since all equations constructing the efficient frontiers of the CCR and BCC models are necessary to execute the algorithm, we present a procedure for calculating them.     

A Stochastic Programming Model for Currency Option Hedging

In this paper we use a stochastic programming approach to develop currency option hedging models which can address problems with multiple random factors in an imperfect market. The portfolios considered in our model are rebalanced at the end of each time period, and reinvestments are allowed during the hedging process. These sequential decisions (reinvestments) are based on the evolution of random parameters such as exchange rates, interest rates, etc. We also allow the inclusion of a variety of instruments in the hedging portfolio, including short term derivative securities, short term options, and futures. These instruments help generate strategies that provide good liquidity and low trade intensity. One of the important features of the model is that it incorporates constraints on sensitivity measures such as Delta and Gamma. By ensuring that these hedge parameters track a desired trajectory (e.g., the parameters of a target option), the new model provides investment strategies that are robust with respect to the perturbations measured by Delta and Gamma. In order to manage the explosion of scenarios due to multiple random factors, we incorporate sampling within a scenario aggregation algorithm. We illustrate that when compared with other myopic hedging methods in imperfect markets, the new stochastic programming model can provide better performance. Our examples also illustrate stochastic programming as a practical computational tool for realistic hedging problems.