Solving two-stage stochastic linear program based set cover

Hong Zhen Zheng; Dian Hui Chu; De Chen Zhan

doi:10.1109/ICMLC.2006.258825

Solving two-stage stochastic linear program based set cover

Hong Zhen Zheng^*
, Dian Hui Chu
, De Chen Zhan

^*Corresponding author for this work

Faculty of Computing

Harbin Institute of Technology Weihai

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This paper formalizes the Two-stage recourse model and focuses on a stochastic generalization of the ordinary set cover problem to illustrate our technique for solving Two-stage stochastic linear programs. The integrality constraints can be relaxed to yield a linear program. We give a compact formulation where only have the stage-1 variables and explain the basic idea by considering the Two-stage stochastic set cover problem(SSC) and its formulation given by (SSC-P2). Furthermore, theorem forms for tacking various Two-stage stochastic optimization problem be presented.

Original language	English
Title of host publication	Proceedings of the 2006 International Conference on Machine Learning and Cybernetics
Pages	1543-1546
Number of pages	4
DOIs	https://doi.org/10.1109/ICMLC.2006.258825
State	Published - 2006
Event	2006 International Conference on Machine Learning and Cybernetics - Dalian, China Duration: 13 Aug 2006 → 16 Aug 2006

Publication series

Name	Proceedings of the 2006 International Conference on Machine Learning and Cybernetics
Volume	2006

Conference

Conference	2006 International Conference on Machine Learning and Cybernetics
Country/Territory	China
City	Dalian
Period	13/08/06 → 16/08/06

Keywords

Clustering
Set cover
Stochastic linear program

Access to Document

10.1109/ICMLC.2006.258825

Cite this

Zheng, H. Z., Chu, D. H., & Zhan, D. C. (2006). Solving two-stage stochastic linear program based set cover. In Proceedings of the 2006 International Conference on Machine Learning and Cybernetics (pp. 1543-1546). Article 4028309 (Proceedings of the 2006 International Conference on Machine Learning and Cybernetics; Vol. 2006). https://doi.org/10.1109/ICMLC.2006.258825

@inproceedings{680176d4aec44aa5bea468cf97c52deb,

title = "Solving two-stage stochastic linear program based set cover",

abstract = "This paper formalizes the Two-stage recourse model and focuses on a stochastic generalization of the ordinary set cover problem to illustrate our technique for solving Two-stage stochastic linear programs. The integrality constraints can be relaxed to yield a linear program. We give a compact formulation where only have the stage-1 variables and explain the basic idea by considering the Two-stage stochastic set cover problem(SSC) and its formulation given by (SSC-P2). Furthermore, theorem forms for tacking various Two-stage stochastic optimization problem be presented.",

keywords = "Clustering, Set cover, Stochastic linear program",

author = "Zheng, \{Hong Zhen\} and Chu, \{Dian Hui\} and Zhan, \{De Chen\}",

year = "2006",

doi = "10.1109/ICMLC.2006.258825",

language = "英语",

isbn = "1424400619",

series = "Proceedings of the 2006 International Conference on Machine Learning and Cybernetics",

pages = "1543--1546",

booktitle = "Proceedings of the 2006 International Conference on Machine Learning and Cybernetics",

note = "2006 International Conference on Machine Learning and Cybernetics ; Conference date: 13-08-2006 Through 16-08-2006",

}

Zheng, HZ, Chu, DH & Zhan, DC 2006, Solving two-stage stochastic linear program based set cover. in Proceedings of the 2006 International Conference on Machine Learning and Cybernetics., 4028309, Proceedings of the 2006 International Conference on Machine Learning and Cybernetics, vol. 2006, pp. 1543-1546, 2006 International Conference on Machine Learning and Cybernetics, Dalian, China, 13/08/06. https://doi.org/10.1109/ICMLC.2006.258825

Solving two-stage stochastic linear program based set cover. / Zheng, Hong Zhen; Chu, Dian Hui ; Zhan, De Chen.
Proceedings of the 2006 International Conference on Machine Learning and Cybernetics. 2006. p. 1543-1546 4028309 (Proceedings of the 2006 International Conference on Machine Learning and Cybernetics; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Solving two-stage stochastic linear program based set cover

AU - Zheng, Hong Zhen

AU - Chu, Dian Hui

AU - Zhan, De Chen

PY - 2006

Y1 - 2006

N2 - This paper formalizes the Two-stage recourse model and focuses on a stochastic generalization of the ordinary set cover problem to illustrate our technique for solving Two-stage stochastic linear programs. The integrality constraints can be relaxed to yield a linear program. We give a compact formulation where only have the stage-1 variables and explain the basic idea by considering the Two-stage stochastic set cover problem(SSC) and its formulation given by (SSC-P2). Furthermore, theorem forms for tacking various Two-stage stochastic optimization problem be presented.

AB - This paper formalizes the Two-stage recourse model and focuses on a stochastic generalization of the ordinary set cover problem to illustrate our technique for solving Two-stage stochastic linear programs. The integrality constraints can be relaxed to yield a linear program. We give a compact formulation where only have the stage-1 variables and explain the basic idea by considering the Two-stage stochastic set cover problem(SSC) and its formulation given by (SSC-P2). Furthermore, theorem forms for tacking various Two-stage stochastic optimization problem be presented.

KW - Clustering

KW - Set cover

KW - Stochastic linear program

UR - https://www.scopus.com/pages/publications/33947268168

U2 - 10.1109/ICMLC.2006.258825

DO - 10.1109/ICMLC.2006.258825

M3 - 会议稿件

AN - SCOPUS:33947268168

SN - 1424400619

SN - 9781424400614

T3 - Proceedings of the 2006 International Conference on Machine Learning and Cybernetics

SP - 1543

EP - 1546

BT - Proceedings of the 2006 International Conference on Machine Learning and Cybernetics

T2 - 2006 International Conference on Machine Learning and Cybernetics

Y2 - 13 August 2006 through 16 August 2006

ER -

Solving two-stage stochastic linear program based set cover

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this