Invited Session Wed.3.MA 141

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

Cluster 22: Stochastic optimization [...]

Algorithms and applications for stochastic programming


Chair: Yongpei Guan



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

Zhili Zhou
A network based model for traffic sensor placement with implications on congestion observation


In this paper, we define and solve the traffic sensor placement problem for congestion observation, which targets to place
the minimum number and location of traffic sensors in order to infer all traffic flow information in a dynamic changing congestion area. To handle uncertain traffic flow, we formulate this problem as a stochastic mixed-integer programming
problem. We first study the combinatorial structure for traffic arc sensor placement to achieve full network coverage without historical data in a given traffic network. Then, we present the relationship between the traffic sensor placement for full network coverage in the deterministic setting and for dynamic congestion area observation. A sampling approximation algorithm is developed to solve the problem with budget constraints. The paper also provides a number of illustrative examples to demonstrate the effectiveness of the proposed methodology.



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

Ruiwei Jiang
Optimization under data-driven chance constraints

Coauthor: Yongpei Guan


Chance constraint is an effective and convenient modeling tool of decision making in uncertain environment. Unfortunately, the solution obtained from a chance-constrained optimization problem might be questionable due to the accessibility of the probability distribution of the random parameters. Usually, decision makers have no access to the distribution itself, but can only observe a series of data sampled from the true (while ambiguous) distribution. In this talk, we develop exact approaches to deal with the data-driven chance constraints (DCC). Starting from the historical data, we construct two types of confidence sets for the ambiguous distribution through statistical estimation of its moments and density functions, respectively. We then formulate DCC as a robust version of chance constraints by allowing the ambiguous distribution to run adversely within its confidence set. By deriving equivalent reformulations, we show that DCC with both (moment- and density-based) confidence sets can be efficiently solved. In addition, we depict the relation between the risk level of DCC and the sample size of historical data, which can a priori determine the robustness of DCC.



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

Guzin Bayraksan
A sequential bounding method for a class of two-stage stochastic programs

Coauthors: David P. Morton, Peguy Pierre-Louis


In this talk, we present an algorithm for two-stage stochastic programming with a convex second stage program and with uncertainty in the right-hand side. The algorithm draws on techniques from deterministically-valid bounding and approximation methods as well as sampling-based approaches. In particular, we sequentially refine a partition of the support of the random vector and, through Jensen’s inequality, generate deterministically-valid lower bounds on the optimal objective function value. An upper bound estimator is formed through a stratified Monte Carlo sampling procedure that includes the use of a control variate variance reduction scheme. We present stopping rules that ensure an asymptotically valid confidence interval on the quality of the proposed solution and illustrate the algorithm via computational results.


  . On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.