Solving Two-Stage Stochastic Linear Program Based Set Cover

Author

Zheng, Hong-Zhen ; Chu, Dian-Hui ; Zhan, De-chen

Author_Institution

Dept. of Comput. Sci. & Technol., Harbin Inst. of Technol., Weihai

fYear

2006

fDate

13-16 Aug. 2006

Firstpage

1543

Lastpage

1546

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

optimisation; set theory; stochastic processes; integrality constraint; set cover problem; two-stage recourse model; two-stage stochastic linear program; two-stage stochastic optimization problem; Algorithm design and analysis; Application software; Approximation algorithms; Computer science; Costs; Cybernetics; Design optimization; Electronic mail; Linear programming; Machine learning; Polynomials; Probability distribution; Stochastic processes; Clustering; Set Cover; Stochastic Linear Program;

fLanguage

English

Publisher

ieee

Conference_Titel

Machine Learning and Cybernetics, 2006 International Conference on

Conference_Location

Dalian, China

Print_ISBN

1-4244-0061-9

Type

conf

DOI

10.1109/ICMLC.2006.258825

Filename

4028309