Optimization Online


A General Heuristic Method for Joint Chance-Constrained Stochastic Programs with Discretely Distributed Parameters

Matthew W. Tanner (mtanner***at***tamu.edu)
Eric B. Beier (ebeier***at***tamu.edu)

Abstract: We present a general metaheuristic for joint chance-constrained stochastic programs with discretely distributed parameters. We give a reformulation of the problem that allows us to define a finite solution space. We then formulate a novel neighborhood for the problem and give methods for efficiently searching this neighborhood for solutions that are likely to be improving. We formulate a reduced linear program that is all that needs to be solved each iteration of the algorithm, reducing the computational effort required for the search. Finally, we give a random tabu search heuristic to search our solution space. The algorithm differs from other work on joint chance-constrained problems in that it is valid for problems with randomness both in the constraint matrix and in the righthand side. We finish with computational experiments on two sets of test instances that show that our algorithm is highly effective at finding good feasible solutions to these problems.

Keywords: stochastic programming, optimization, tabu search, vaccine allocation

Category 1: Stochastic Programming

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Applications -- Science and Engineering (Basic Sciences Applications )

Citation: Department of Industrial and Systems Engineering Texas A&M University, Submitted to Computational Optimization and Applications

Download: [PDF]

Entry Submitted: 08/21/2007
Entry Accepted: 08/22/2007
Entry Last Modified: 05/24/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society