Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2402.18795 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915878709231616 |
|---|---|
| author | Lv, Wei Chen, Wei-Kun Chen, Yi-Long Dai, Yu-Hong |
| author_facet | Lv, Wei Chen, Wei-Kun Chen, Yi-Long Dai, Yu-Hong |
| contents | In this paper, we investigate the probabilistic set covering problem (PSCP) in which the right-hand side is a binary random vector and the covering constraint is required to be satisfied with a prespecified probability. We consider the case with a finite discrete distribution of the random vector, which usually arises in the context of the sample average approximation approach. We develop an effective Benders decomposition (BD) algorithm for solving large-scale PSCPs, which enjoys two key advantages: (i) the number of variables in the underlying Benders reformulation is independent of the scenario size; and (ii) the Benders cuts can be separated by an efficient combinatorial algorithm. For the special case that random vector is a combination of several independent random blocks/subvectors, we explicitly take this kind of block structure into consideration and develop a more efficient BD algorithm. Moreover, to further speed up the two proposed BD algorithms, we develop a class of strong valid inequalities, which are guaranteed to be facet-defining for the polytope induced by the probabilistic constraint. Numerical results on instances with up to one million scenarios demonstrate the effectiveness of the proposed BD algorithms over a black-box mixed integer programming solver's branch-and-cut and automatic BD algorithms and a state-of-the-art algorithm in the literature. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18795 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards large-scale probabilistic set covering problems: an efficient Benders decomposition approach Lv, Wei Chen, Wei-Kun Chen, Yi-Long Dai, Yu-Hong Optimization and Control In this paper, we investigate the probabilistic set covering problem (PSCP) in which the right-hand side is a binary random vector and the covering constraint is required to be satisfied with a prespecified probability. We consider the case with a finite discrete distribution of the random vector, which usually arises in the context of the sample average approximation approach. We develop an effective Benders decomposition (BD) algorithm for solving large-scale PSCPs, which enjoys two key advantages: (i) the number of variables in the underlying Benders reformulation is independent of the scenario size; and (ii) the Benders cuts can be separated by an efficient combinatorial algorithm. For the special case that random vector is a combination of several independent random blocks/subvectors, we explicitly take this kind of block structure into consideration and develop a more efficient BD algorithm. Moreover, to further speed up the two proposed BD algorithms, we develop a class of strong valid inequalities, which are guaranteed to be facet-defining for the polytope induced by the probabilistic constraint. Numerical results on instances with up to one million scenarios demonstrate the effectiveness of the proposed BD algorithms over a black-box mixed integer programming solver's branch-and-cut and automatic BD algorithms and a state-of-the-art algorithm in the literature. |
| title | Towards large-scale probabilistic set covering problems: an efficient Benders decomposition approach |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2402.18795 |