Chair of Discrete Optimization

Laboratory

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.

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

We consider the problem of solving integer programs of the form min {c^⊺ x : Ax = b, x ∈ ℤ_{⩾ 0}}, where A is a multistage stochastic matrix in the following sense: the primal treedepth of A is bounded by a parameter d, which means that the columns of A ca ...

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

This paper considers vessel scheduling with pilotage and tugging constraints in berthing operations with channel restrictions at seaports. To our knowledge, pilotage and tugging requirements have not been simultaneously considered in the literature. This w ...

Designing structures from reused elements is becoming an increasingly important design task for structural engineers as it has potential to significantly reduce adverse environmental impacts of building structures. To allow for a broad application of this ...

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

The distribution network restoration problem is by nature a mixed integer and non-linear optimization problem due to the switching decisions and Optimal Power Flow (OPF) constraints, respectively. The link between these two parts involves logical implicati ...

Stochastic optimization is a popular modeling paradigm for decision-making under uncertainty and has a wide spectrum of applications in management science, economics and engineering. However, the stochastic optimization models one faces in practice are int ...

This thesis develops mathematical programming frameworks to operate electric autonomous vehicles in the context of ride-sharing services. The introduced problem is a novel variant of the Dial-a-Ride Problem (DARP), denoted by the electric Autonomous Dial-a ...

The objective of this thesis is to develop a general methodology to incorporate a disaggregate demand representation in supply-oriented optimization problems that allows to capture the interplay between the behavior of individuals and the decisions to be o ...

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

Chair of Discrete Optimization

Chat with Graph Search

A ride time-oriented scheduling algorithm for dial-a-ride problems

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Results on Sparse Integer Programming and Geometric Independent Sets

Approximation Algorithms for Allocation and Network Design

Streaming and Matching Problems with Submodular Functions

The double exponential runtime is tight for 2-stage stochastic ILPs

Discrete Optimal Transport with Independent Marginals is #P-Hard

Minimum Cost Intervention Design for Causal Effect Identification

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Efficient Sequential and Parallel Algorithms for Multistage Stochastic Integer Programming Using Proximity

Knapsack and Subset Sum with Small Items

Vessel scheduling with pilotage and tugging considerations

Computational tool for stock-constrained design of structures

New Results in Integer and Lattice Programming

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

A Novel Decomposition Solution Approach for the Restoration Problem in Distribution Networks

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

The electric autonomous dial-a-ride problem

A general framework for the integration of complex choice models into mixed integer optimization

New Graph Algorithms via Polyhedral Techniques