Online stochastic optimization under time constraints

DOI10.1007/S10479-009-0605-5MaRDI QIDQ1958625zbMATH OpenOpenAlexFDO

Authors Pascal Van Hentenryck, Russell Bent, Eli Upfal

Publication date 4 October 2010

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-009-0605-5

zbMATH Keywords

online algorithmsstochastic optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

Review text

In this paper the authors consider online stochastic combinatorial optimization problems (OSCO), that integrated online algorithms and stochastic optimization. In OSCO the uncertainties are characterized by distributions that can be sampled and where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. This paper reviews recent developments in OSCO and presents new theoretical and experimental results. The authors propose three main algorithms: expectation \(E\), consensus \(C\), and reset \(R\). The algorithms were evaluated experimentally and theoretically. The experimental results were obtained on three applications of different nature: packet scheduling, multiple vehicle routing with time windows, and multiple vehicle dispatching. The theoretical results show that algorithm \(E\) has an expected constant loss compared to the offline optimal solution. Algorithm \(R\) has an expected \(\rho (1+o(1))\) loss (when the regret gives an \(\rho \)-approximation to the offline problem), but is significantly faster.

Recommendations

• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• scientific article; zbMATH DE number 1688603
• An anytime multistep anticipatory algorithm for online stochastic combinatorial optimization
• Amsaa: A Multistep Anticipatory Algorithm for Online Stochastic Combinatorial Optimization
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

Cites work

• A simulation-based approach to two-stage stochastic programming with recourse
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• Adversarial queuing theory
• Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
• Approximation in stochastic scheduling
• Beyond Competitive Analysis
• Buffer Overflow Management in QoS Switches
• Competitive snoopy caching
• Continuity Properties of Expectation Functions in Stochastic Integer Programming
• scientific article; zbMATH DE number 3513051 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1321699 (Why is no real title available?)
• scientific article; zbMATH DE number 663895 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 1175949 (Why is no real title available?)
• scientific article; zbMATH DE number 2084697 (Why is no real title available?)
• Introduction to Stochastic Programming
• On structure and stability in stochastic programs with random technology matrix and complete integer recourse
• On the random 2-stage minimum spanning tree
• On the sum-of-squares algorithm for bin packing
• Online algorithms. The state of the art
• Partially dynamic vehicle routing—models and algorithms
• Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers
• Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions
• Stability of Solutions for Stochastic Programs with Complete Recourse
• Stochastic decomposition. A statistical method for large scale stochastic linear programming
• Stochastic Machine Scheduling with Precedence Constraints
• Stochastic scheduling problems I — General strategies
• Sub-optimality Approximations
• The value function of a mixed integer program. II
• Two‐stage stochastic integer programming: a survey

Cited in

(22)

• OL-DEC-MDP model for multiagent online scheduling with a time-dependent probability of success
• Modelling the mobile target covering problem using flying drones
• scientific article; zbMATH DE number 1688603 (Why is no real title available?)
• Online Optimization with Uncertain Information
• The post-disaster debris clearance problem under incomplete information
• Heuristics for dynamic and stochastic routing in industrial shipping
• Using parallel \& distributed computing for real-time solving of vehicle routing problems with stochastic demands
• scientific article; zbMATH DE number 2084697 (Why is no real title available?)
• Constrained Online Convex Optimization With Feedback Delays
• scientific article; zbMATH DE number 7626738 (Why is no real title available?)
• Integrated offline and online decision making under uncertainty
• Gap Reduction Techniques for Online Stochastic Project Scheduling
• Amsaa: A Multistep Anticipatory Algorithm for Online Stochastic Combinatorial Optimization
• An anytime multistep anticipatory algorithm for online stochastic combinatorial optimization
• Advances in Computer Science - ASIAN 2004. Higher-Level Decision Making
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima
• Divide and conquer: a granular concept-cognitive computing system for dynamic classification decision making
• Nonlinear optimization filters for stochastic time-varying convex optimization
• Data-driven customer acceptance for attended home delivery
• Online optimization: probabilistic analysis and algorithm engineering
• Solving the online on-demand warehousing problem

This page was built for publication: Online stochastic optimization under time constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1958625)