We propose a novel hybrid method to solve the network-constrained stochastic unit commitment problem. We target realistic large-scale instances including hundreds of thermal generation units, thousands of transmission...
详细信息
We propose a novel hybrid method to solve the network-constrained stochastic unit commitment problem. We target realistic large-scale instances including hundreds of thermal generation units, thousands of transmission lines and nodes, and a large number of stochastic renewable generation units. This scheduling problem is formulated as a two-stage stochastic programming problem with continuous and binary variables in the first stage and only continuous variables in the second stage. We develop a hybrid solution method that decomposes the original problem into a master problem including unit commitment and dispatch decisions, and decomposed subproblems representing dispatch with transmission constraints per scenario. The proposed decomposition embeds a column-and-constraintgeneration step within the traditional Benders decomposition framework. The performance of the proposed decomposition technique is contrasted with the solution of the extensive form via branch-and-cut and Benders decomposition available in commercial solvers, and with conventional Benders decomposition variants. Our computational experiments show that the proposed method generates bounds of superior quality and finds solutions for instances where other approaches fail.
We study a network interdiction problem involving two agents: a defender and an evader. The evader seeks to traverse a path from a source node to a terminus node in a directed network without being detected. The game ...
详细信息
We study a network interdiction problem involving two agents: a defender and an evader. The evader seeks to traverse a path from a source node to a terminus node in a directed network without being detected. The game takes place in two stages. In the first stage, the defender removes a set of arcs in the network. In the second stage, the defender and evader play a simultaneous game. The defender monitors a set of arcs, thus increasing the probability that the evader will be detected on that arc (if the evader uses the arc). The evader selects a source-terminus path. Because the second stage is played simultaneously, both agents use mixed-strategy solutions. We approach the solution of the second-stage problem by proposing a constraint-and-column generation algorithm. We show that both the constraint-generation and column-generation problems are NP-hard. Accordingly, we prescribe approximate versions of these problems that can be solved more efficiently. Our algorithm relies on solving the approximate versions until it is necessary to obtain an exact solution of the constraint-generation and column-generation problems. Then, to link the first- and second-stage problems, we model the original problem using an epigraph reformulation, which we solve using a Benders-decomposition based approach. The efficacy of our approach is demonstrated on a set of randomly generated test instances.
Over the past two decades, bike-sharing systems have grown significantly worldwide. Compared with that of other business sectors, the means by which revenue is obtained in the bike-sharing industry is unique. When the...
详细信息
Over the past two decades, bike-sharing systems have grown significantly worldwide. Compared with that of other business sectors, the means by which revenue is obtained in the bike-sharing industry is unique. When the market in a region or city is saturated, an efficient way for a firm to increase revenue is to enter a new market. In this study, we design a revenue maximization-oriented decision tool to support the operational decisions of a new competitor firm entering into competition against a local firm. It is assumed that operational-level information from the local firm is unknown to the competitor firm. A new multi-stage max-min-max robust maximization model is proposed. It aims to optimize the dynamic bike inventory to maximize the worst-case revenue that the competitor firm may achieve. The worst-case revenue is treated as the baseline revenue for the competitor firm according to which rational decisions can be made. Specifically, we construct an uncertainty set to capture the uncertainty in the bike distribution of the local firm. To work with this nonconvex model, we design a myopic method, inspired by a special two-stage model that can be solved with a customized constraint-and-column approach, for obtaining the upper and lower bounds of the potential optimal revenue in our multistage model. The results of numerical experiments illustrate that the approximation approach has satisfactory computational efficiency and generates a tight bound of the optimal baseline revenue. Sensitivity analyses show that the new competitor firm should not increase its investment in bikes when the local firm increases its quantity of bikes because of high depreciation costs. Moreover, the two firms would allocate a similar proportion of bikes to each zone when either of them provides a large number of bikes. When the firms both provide a small number of bikes, the allocation of bikes by the new competitor firm is widely dispersed, while the local firm tends to allocate bikes
暂无评论