| |
Records |
Links |
|
Author |
Canessa, G.; Gallego, J.A.; Ntaimo, L.; Pagnoncelli, B.K. |
|
| |
Title |
An algorithm for binary linear chance-constrained problems using IIS |
Type |
|
| |
Year |
2019 |
Publication |
Computational Optimization And Applications |
Abbreviated Journal  |
Comput. Optim. Appl. |
|
| |
Volume |
72 |
Issue |
3 |
Pages |
589-608 |
|
| |
Keywords |
Chance-constrained programming; Infeasible irreducible subsystems; Integer programming |
|
| |
Abstract |
We propose an algorithm based on infeasible irreducible subsystems to solve binary linear chance-constrained problems with random technology matrix. By leveraging on the problem structure we are able to generate good quality upper bounds to the optimal value early in the algorithm, and the discrete domain is used to guide us efficiently in the search of solutions. We apply our methodology to individual and joint binary linear chance-constrained problems, demonstrating the ability of our approach to solve those problems. Extensive numerical experiments show that, in some cases, the number of nodes explored by our algorithm is drastically reduced when compared to a commercial solver. |
|
| |
Address |
[Canessa, Gianpiero] Univ Adolfo Ibanez, Diagonal Torres 2640, Santiago 7941169, Chile, Email: gianpiero.canessa@edu.uai.cl |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Springer |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0926-6003 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000463792400003 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
996 |
|
| Permanent link to this record |
| |
|
| |
|
Author |
Barrera, J.; Homem-De-Mello, T.; Moreno, E.; Pagnoncelli, B.K.; Canessa, G. |
|
| |
Title |
Chance-constrained problems and rare events: an importance sampling approach |
Type |
|
| |
Year |
2016 |
Publication |
Mathematical Programming |
Abbreviated Journal |
Math. Program. |
|
| |
Volume |
157 |
Issue |
1 |
Pages |
153-189 |
|
| |
Keywords |
Chance-constrained programming; Sample average approximation; Importance sampling; Rare-event simulation |
|
| |
Abstract |
We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that variance can be reduced uniformly with respect to the decision variables. We give sufficient conditions to obtain such uniform variance reduction, and prove asymptotic convergence of the combined SAA-IS approach. As it often happens with IS techniques, the practical performance of the proposed approach relies on exploiting the structure of the problem under study; in our case, we work with a telecommunications problem with Bernoulli input distributions, and show how variance can be reduced uniformly over a suitable approximation of the feasibility set by choosing proper parameters for the IS distributions. Although some of the results are specific to this problem, we are able to draw general insights that can be useful for other classes of problems. We present numerical results to illustrate our findings. |
|
| |
Address |
[Barrera, Javiera; Moreno, Eduardo] Univ Adolfo Ibanez, Fac Sci & Engn, Santiago, Chile, Email: javiera.barrera@uai.cl |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Springer Heidelberg |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0025-5610 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000375568400007 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
613 |
|
| Permanent link to this record |
