We consider joint chance-constrained programs with random lefthand sides.
The motivation of this project is that this class of problem has many important
applications, but there are few existing solution methods. For the most part, we
deal with the subclass of problems for which the underlying parameter distributions
are discrete. This assumption allows the original problem to be formulated as a
deterministic equivalent mixed-integer program.
We rst approach the problem as a mixed-integer program and derive a class
of optimality cuts based on irreducibly infeasible subsets of the constraints of the
scenarios of the problem. The IIS cuts can be computed effciently by means of a
linear program. We give a method for improving the upper bound of the problem
when no IIS cut can be identifi ed. We also give an implementation of an algorithm
incorporating these ideas and finish with some computational results.
We present a tabu search metaheuristic for fi nding good feasible solutions to
the mixed-integer formulation of the problem. Our heuristic works by de ning a
sufficient set of scenarios with the characteristic that all other scenarios do not have
to be considered when generating upper bounds. We then use tabu search on the
one-opt neighborhood of the problem. We give computational results that show our
metaheuristic outperforming the state-of-the-art industrial solvers.
We then show how to reformulate the problem so that the chance-constraints
are monotonic functions. We then derive a convergent global branch-and-bound algorithm using the principles of monotonic optimization. We give a finitely convergent
modi cation of the algorithm. Finally, we give a discussion on why this algorithm is
computationally ine ffective.
The last section of this dissertation details an application of joint chance-constrained
stochastic programs to a vaccination allocation problem. We show why it is necessary
to formulate the problem with random parameters and also why chance-constraints
are a good framework for de fining an optimal policy. We give an example of the problem
formulated as a chance constraint and a short numerical example to illustrate
the concepts.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-05-404 |
| Date | 16 January 2010 |
| Creators | Tanner, Matthew W. |
| Contributors | Ntaimo, Lewis |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation |
| Format | application/pdf |
Page generated in 0.0022 seconds