Contributed Session Wed.3.MA 144

Wednesday, 15:15 - 16:45 h, Room: MA 144

Cluster 22: Stochastic optimization [...]

Network design, reliability, and PDE constraints


Chair: Olga Myndyuk



Wednesday, 15:15 - 15:40 h, Room: MA 144, Talk 1

Olga Myndyuk
Stochastic network design under probabilistic constraint with continuous random variables.


Stochastic network optimization problem is formulated, where the demands at the nodes are continuously distributed random variables. The problem is to find optimal node and arc capacities under probabilistic constraint that insures the satisfiability of all demands on a high probability level. The large number of feasibility inequalities is reduced to a much smaller number (elimination by network topology), equivalent reformulation takes us to a specially structured LP. It is solved by the combination of an inner and an outer algorithm providing us with both lower and upper bounds for the optimum in each iteration. Numerical example is presented. The network design method is applicable to find optimal capacity expansion problems in interconnected power systems, water supply, traffic, transportation, evacuation and other networks.



Wednesday, 15:45 - 16:10 h, Room: MA 144, Talk 2

Zuzana ҆abartov√°
Spatial decomposition for differential equation constrained stochastic programs

Coauthor: Pavel Popela


When optimization models are constrained by ordinary or partial differential equations (ODE or PDE), numerical method based on discretising domain are required to obtain non-differential numerical description of the differential parts; we chose the finite element method. The real problems are often very large and exceed computational capacity. Hence, we employ the progressive hedging algorithm (PHA) - an efficient decomposition method for solving scenario-based stochastic programs - which can be implemented in parallel to reduce the computing time. A modified PHA was used for an original concept of spatial decomposition based on mesh created for approximating differential constraints. We solve our problem with raw discretization, decompose it into overlapping parts of the domain, and solve it again iteratively by PHA with finer discretization - using values from the raw discretization as boundary conditions - until a given accuracy is reached.
The spatial decomposition is applied to a civil engineering problem: design of beam cross section dimensions. The algorithms are implemented in GAMS and the results are evaluated by width of overlap and computational complexity.



Wednesday, 16:15 - 16:40 h, Room: MA 144, Talk 3

Rasool Tahmasbi
Network flow problems with random arc failures

Coauthor: S. Mehdi Hashemi


Networks have been widely used for modeling real-world problems such as communication, transportation, power, and water networks, which are subject to component failures. We consider stochastic network flows, in which the arcs fail with some known probabilities. In contrast to previous research that focuses on the evaluation of the expected maximum flow value in such networks, we consider the situation in which a flow must be implemented before the realization of the uncertainty. We present the concept of expected value of a given flow and seek for a flow with maximum expected value.
We show the problem of computing the expected value of a flow is NP-hard.
We examine the "value of information'', as the relative increase in the expected flow value if we allow implementing a maximum flow after the uncertainty is revealed. We show that the value of information can be around 61,% on some instances. While it is significantly hard to compute the expected maximum flow value and to determine a flow with maximum expected value, we apply a simple simulation-based method to approximate these two values. We give computational results to demonstrate the ability of this method.


  The majority of financial loan companies provide the service of getting Payday Loans North Carolina for U.S. citizens. Since its introduction in the market buying Buy Generic Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.