Stochastic Optimization Powered by Markov Chain Monte Carlo: Mixed-Integer Nonlinear Programming for Communications Network Scheduling

<p>Markov chain Monte Carlo methods are known for their effectiveness with a multitude of complex mathematical problems, including those in mixed spaces of continuous and discrete components. In this dissertation, we examine variations of complicated scheduling problems involving allocating spacecraft communication time on a fixed number of antenna resources located at several physical locations around the world. The antennas at these locations are used to communicate with various spacecraft sent to collect science data at many different destinations and orbits in the Solar System. Each scheduled tracking interval must satisfy several constraints enforcing various properties, and the amount of antenna resources is very scarce compared to how frequently these antennas have to be used for communicating with the spacecraft in competitive time intervals. In these scheduling problems, the scheduled tracking interval start and end times are continuous variables, while the index information for selecting antenna options are discrete variables. It is usually very hard to find a particular solver that can handle these mixed-integer models without spending lots of effort in fitting the constraints to the standard forms the solver can handle. We aim to find modern techniques that can be well adapted to solve our mixed-integer scheduling problems and perform very well. In particular, we want to focus on using the general probabilistic technique called simulated annealing, with constraints. The required Markov chain Monte Carlo sampler will be designed to use a random sampling method called the Gibbs sampling algorithm, which can be generalized to incorporate constraints. The complete system of problem modeling and its stochastic optimization will be demonstrated in some test problems.</p>

Name thesis:degree_name

Philosophy, PhD

Level thesis:degree_level

Restricted to Claremont Colleges Dissertation

Discipline thesis:degree_discipline

Institute of Mathematical Sciences

Year dc:date.available

2019

Author dc:creator

• Tran, Kristy Uyenly

Contributors dc:contributor

• Allon G. Percus
• Ali Nadim
• Chin Chang

• communication scheduling
• Deep Space Network
• Gibbs sampler
• Markov chain Monte Carlo
• optimal scheduling
• stochastic optimization
• Aerospace Engineering
• Mathematics
• Operational Research

Repository record dc:identifier

https://scholarship.claremont.edu/cgu_etd/345

OAI identifier oai:identifier

oai:scholarship.claremont.edu:cgu_etd-1370