Online Stochastic Combinatorial Optimization under Time Constraints
Project Description
This project studies how to approach online combinatorial
optimization, i.e., optimization problems where the inputs are
revealed online. It assumes that the distribution of the inputs, or an
approximation thereof, is a black-box available for
sampling. Moreover, the project is particularly interested in
exploring applications where the decision time and the time in between
decisions is severely constrained. This project also studies online
algorithms under specific distributions, robust optimization, and
traditional stochastic optimization.
Typical industrial applications include vehicle routing, ambulance
relocation, packet routing in networks, and scheduling.
Publications
Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers.
R. Bent and P. Van Hentenryck.
Operations Research (to appear).
A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows.
R. Bent and P. Van Hentenryck.
Transportation Science, (to appear).
A Simple and Deterministic Competitive Algorithm for Online Facility Location
Aris Anagnostopoulos, Russell Bent, Eli Upfal, and Pascal Van Hentenryck
Information and Computation (to appear)
Online Stochastic and Robust Optimization
R. Bent and P. Van Hentenryck
Ninth Asian Computing Science Conference (ASIAN'04)
Chiang Mai University, December 2004.
© Springer Verlag (Invited Paper)
Regrets Only. Online Stochastic Optimization under Time Constraints
R. Bent and P. Van Hentenryck
Proceedings of the 19th National Conference on Artificial Intelligence (AAAI'04)
San Jose, CA, July 2004.
The Value of Consensus in Online Stochastic Scheduling
Russell Bent and Pascal Van Hentenryck
Proceeding of the 14th International Conference on Automated Planning & Scheduling,
Whistler, British Columbia, Canada, June 3-7 2004.
On the Complexity of the Robust Spanning Tree with Interval Data.
I. Aron and P. Van Hentenryck.
Operations Research Letters, 32(1): 36-140, 2003.
A Constraint Satisfaction Approach to the Robust Spanning Tree with Interval Data.
I. Aron and P. Van Hentenryck.
Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence,
Edmonton, Canada, August, 2002.
