Online Optimization

Coordination: Prof. Dr. Jörg Rambau
Contact: Prof. Dr. Jörg Rambau

Represented in MODUS since 2009/01

Members with experience in this area:

Prof. Dr. Jörg Rambau

The method "Online Optimization":

WHAT IS THIS?

Online Optimization (OO) is a model for problems for which the input data (so-called requests) are revealed over time and decisions (so-called answers) have to be given inbetween. An Online Algorithm uses for its answers for each request only the revealed information revealed up to the occurrence of the request. An Offline Algorithm may use the full request sequence in advance. There can be no better performance than the one computed by the best Offline Algorithm. For example, one has to decide whether to buy or to rent skiers with very limited knowledge about the number of skiing days in a season, i.e., in practice we can only use an Online Algorithm. OO provides analysis methods that make a comparison between various Online Algorithms possible via the comparison to an optimal Offline Algorithm. This prominent analysis method is the so-called Competitive Analysis. Competitive Analysis investigates, in a sense, the worst-case or average (over all request sequences) multiplicative regret of an Online Algorithm, i.e., the cost our Online Algorithm produced divided by the optimlal cost in hindsight on the same request sequence.

WHAT IS IT GOOD FOR?

Whenever decisions have to be made over time with no or incomplete information about the future and our goal is to minimize our regret afterwards, then Online Optimization yields appropriate models. Competetive analysis is a wide-spread method, e.g., to investigate online paging algorithms for data requests in computer science, online scheduling algorithms for job requests in production and logistics, and online routing algorithms for call requests in telecommunication.

WHERE HAVE WE APPLIED IT?

The members of MODUS have applied this method for the following challenges:

Optimal dispatching of pallet elevators in factories
Optimal dispatching of service technicians

Board of Directors: Prof. Dr. Jörg Rambau, Prof. Dr. Lars Grüne and Prof. Dr. Vadym Aizinger