Contributed Session Thu.3.MA 144

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

Cluster 22: Stochastic optimization [...]

Chance constrained stochastic optimization


Chair: Yongjia Song



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

Yongjia Song
A branch-and-cut algorithm for the chance-constrained knapsack problem

Coauthors: Simge Küçükyavuz, James Luedtke


We consider a probabilistic version of classical 0-1 knapsack problem, where we have a set of items with random weight and a random knapsack capacity. The objective is to choose a set of items that maximizes profit while ensuring the knapsack constraint is satisfied with probability higher than a given threshold. We introduce a simple decomposition algorithm based on a probabilistic extension of cover inequalities to solve a sample average approximation (SAA) of this problem. We propose a probabilistic sequential lifting procedure to strengthen them, leveraging successful computational strategies for the deterministic knapsack problem. Exact lifting is hard, but we obtain an effective upper bound for the lifting problem using a scenario decomposition approach. Additional valid inequalities are proposed to further strengthen the bounds. A key advantage of our algorithm is that the number of branch-and-bound nodes searched is nearly independent of the number of scenarios used in the SAA, which is in stark contrast to formulations with a binary variable for each scenario.



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

Jessie Birman
Overall aircraft design based on chance-constrained programming


Preliminary Overall Aircraft Design (OAD) is classically carried out using a deterministic optimisation of a strategic criterion under operational constraints. The risk, which may appear all along the aircraft development, is mitigated by using a "margin philosophy'' applied to some design parameters. A robustness study has highlighted the shortcomings of this way of doing, which does not offer the best protection possible against deviation to ensure requirement satisfaction. In the last decades, many researches have been done in the area of optimisation of complex processes under uncertainty. Attention has been put on methods reported in Stochastic Programming or Chance-Constrained Programming (CCP). The aim of the study is to propose a new methodology based on CCP to perform OAD. For this purpose, the main source of uncertainty affecting the system is identified and quantified. Then, a new formulation of the aircraft pre-design optimisation is stated according to the CCP framework. Particular attention is put on the choice of the objective function and the design parameters. This method is also used to assess the uncertainty involving an unconventional aircraft configuration.



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

Jianqiang Cheng
Stochastic linear programming with joint chance constraints

Coauthor: Abdel Lisser


This paper deals with a special linear programs with joint chance
constraints, where the left-hand side of chance constraints is
normally distributed stochastic coefficients and the columns s of
the matrix are assumed independent to each other. We approximate
this problem by solving its corresponding stochastic dual problem
and there is a weak duality between them, i.e., the optimum
objective value of the dual problem is a lower bound of the primal
minimum problem. For the dual problem, it can be approximated by one
SOCP problem. Furthermore, the optimum of the SOCP problem provides
an upper bound of the dual problem. Finally, numerical experiments on
random data are given to evaluate the approximation.


  Getting Payday Loans In California should be thought of many times. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.