Publication

Robust Optimization with Recovery: Application to Shortest Paths and Airline Scheduling

Michel Bierlaire
2007
Conference Papers

Abstract

In this exploratory paper we consider a robust approach to decisional problems subject to uncertain data in which we have an additional knowledge on the strategy (algorithm) used to react to an unforeseen event or recover from a disruption. This is a typical situation in scheduling problems where the decision maker has no a priori knowledge on the probabilistic distribution of such events but he only knows rough information on the event, such as its impact on the schedule. We discuss a general framework to address this situation and its links with other existing methods, we present an illustrative example on the Shortest Path Problem with Interval Data (SPPID) and we discuss a more general application to airline scheduling with recovery.

Official source

https://infoscience.epfl.ch/entities/publication/ded9fdba-12ba-4345-b871-7cc84e525f82

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Michel Bierlaire
2007
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/ded9fdba-12ba-4345-b871-7cc84e525f82

About this result

Related concepts (32)

Schedule

A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are intended to take place. The process of creating a schedule — deciding how to order these tasks and how to commit resources between the variety of possible tasks — is called scheduling, and a person responsible for making a particular schedule may be called a scheduler.

Dijkstra's algorithm

Dijkstra's algorithm (ˈdaɪkstrəz ) is an algorithm for finding the shortest paths between nodes in a weighted graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. The algorithm exists in many variants. Dijkstra's original algorithm found the shortest path between two given nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

Declarative knowledge

Declarative knowledge is an awareness of facts that can be expressed using declarative sentences, like knowing that Princess Diana died in 1997. It is also called theoretical knowledge, descriptive knowledge, propositional knowledge, and knowledge-that. It is not restricted to one specific use or purpose and can be stored in books or on computers. Epistemology is the main discipline studying declarative knowledge. Among other things, it studies the essential components of declarative knowledge.

Related publications (32)

Robust Optimization with Recovery: Application to Shortest Paths and Airline Scheduling

Chat with Graph Search

Time-Space Trade-Offs for Sumcheck

System-Level Co-design and Co-optimization of Heterogeneous Platforms for Deep-Learning Workloads

Improved branching-fraction measurements of $ {B}_{(s)}^0\to {K}_{\mathrm{S}}^0{h}^{+}h{\prime}^{-} $ decays and first observation of $ {B}_s^0\to {K}_{\mathrm{S}}^0{K}^{+}{K}^{-} $