Changes'04
International Workshop on Constraint Solving
Under Change and Uncertainty
Invited Talk
Online Stochastic and Robust Optimization under Time ConstraintsPascal Van Hentenryck
We consider online combinatorial optimization applications whose inputs are are characterized by a distribution and whose decisions are subject to strict time constraints. We present a generic online optimization and show how it can instantiated to a variety of stochastic algorithms. The algorithms include critical functionalities such as precomputation, service gurantees, least-commitment, and pointwise aggregations of decisions. The algorithms are evaluated and compared on network packet scheduling and complex vehicle routing. Of particular interest is the generality of the algorithm which only rely on the ability to sample the distribution and their robustness under noisy data.
Back to the workshop page
Back to the schedule