Publications related to Tracklet-based Multi-Commodity Network Flow for Tracking Multiple People

Learning to Remove Cuts in Integer Linear Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

Cutting plane methods are a fundamental approach for solving integer linear programs (ILPs). In each iteration of such methods, additional linear constraints (cuts) are introduced to the constraint set with the aim of excluding the previous fractional opti ...

2024

A Spatial Branch and Bound Algorithm for Continuous Pricing with Advanced Discrete Choice Demand Modeling

Michel Bierlaire

In this paper, we present a spatial branch and bound algorithm to tackle the continuous pricing problem, where demand is captured by an advanced discrete choice model (DCM). Advanced DCMs, like mixed logit or latent class models, are capable of modeling de ...

2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

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 ...

EPFL2023

Augmented Lagrangian Methods for Provable and Scalable Machine Learning

Mehmet Fatih Sahin

Non-convex constrained optimization problems have become a powerful framework for modeling a wide range of machine learning problems, with applications in k-means clustering, large- scale semidefinite programs (SDPs), and various other tasks. As the perfor ...

EPFL2023

Removing Algorithmic Discrimination (With Minimal Individual Error)

Rachid Guerraoui, El Mahdi El Mhamdi, Le Nguyen Hoang, Alexandre David Olivier Maurer

We address for the first time the problem of correcting group discriminations within a score function, while minimizing the individual error. Each group is described by a probability density function on the set of profiles. We first solve the problem analy ...

2022

Integrating advanced discrete choice models in mixed integer linear optimization

Michel Bierlaire, Meritxell Pacheco Paneque, Bernard Gendron

In many transportation systems, a mismatch between the associated design and planning decisions and the demand is typically encountered. A tailored system is not only appealing to operators, which could have a better knowledge of their operational costs, b ...

PERGAMON-ELSEVIER SCIENCE LTD2021

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

Sidi-Rachid Cherkaoui, Hossein Sekhavatmanesh

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 ...

IEEE Institute of Electrical and Electronics Engineers2020

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

Friedrich Eisenbrand

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 ...

ASSOC COMPUTING MACHINERY2020

Scalable Stochastic Optimization: Scenario Reduction with Guarantees

Kilian Schindler

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 ...

EPFL2020

Enhanced Dissipation in the Navier-Stokes Equations Near the Poiseuille Flow

Klaus Martin Widmayer

We consider solutions to the 2d Navier-Stokes equations on T x R close to the Poiseuille flow, with small viscosity nu > 0. Our first result concerns a semigroup estimate for the linearized problem. Here we show that the x-dependent modes of linear solutio ...

SPRINGER2020

Realizability of planar point embeddings from angle measurements

Frederike Dümbgen, Adam James Scholefield, Majed El Helou

Localization of a set of nodes is an important and a thoroughly researched problem in robotics and sensor networks. This paper is concerned with the theory of localization from inner-angle measurements. We focus on the challenging case where no anchor loca ...

IEEE2020

On approximation algorithms and polyhedral relaxations for knapsack problems, and clustered planarity testing

Igor Malinovic

Knapsack problems give a simple framework for decision making. A classical example is the min-knapsack problem (MinKnap): choose a subset of items with minimum total cost, whose total profit is above a given threshold. While this model successfully general ...

EPFL2019

Analytical Approach for Active Distribution Network Restoration Including Optimal Voltage Regulation

Sidi-Rachid Cherkaoui, Hossein Sekhavatmanesh

The ever-increasing utilization of sensitive loads in the industrial, commercial, and residential areas in distribution networks requires enhanced reliability and quality of supply. This can be achieved, thanks to self-healing features of smart grids that ...

IEEE Institute of Electrical and Electronics Engineers2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

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 ...

EPFL2019

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Friedrich Eisenbrand

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 ...

ASSOC COMPUTING MACHINERY2018

Delay-Power-Rate-Distortion Optimization of Video Representations for Dynamic Adaptive Streaming

Pascal Frossard, Laura Toni, Chenglin Li

Dynamic adaptive streaming addresses user heterogeneity by providing multiple encoded representations at different rates and/or resolutions for the same video content. For delay-sensitive applications, such as live streaming, there is however a stringent r ...

IEEE2018

Hierarchical control of heterogeneous large-scale urban road networks via path assignment and regional route guidance

Nikolaos Geroliminis, Mehmet Yildirimoglu, Isik Ilber Sirmatel

High level of detail renders microscopic traffic models impractical for control purposes and local control schemes cannot coordinate actions over large scale heterogeneously congested urban networks. Developing efficient models and control methods for larg ...

2018

Sharp sphere packings

Maryna Viazovska

In this talk we will speak about recent progress on the sphere packing problem. The packing problem can be formulated for a wide class of metric spaces equipped with a measure. An interesting feature of this optimization problem is that a slight change of ...

World Scientific Publishing2018

Allocation of Frequency Control Reserve from Aggregated Resources of Active Distribution Systems

Sidi-Rachid Cherkaoui, Mokhtar Bozorg, Fabrizio Sossan, Mohsen Kalantar Neyestanaki

This paper addresses the allocation of frequency control services (FCSs) from aggregated resources of active distribution systems (ARADSs) for balancing the transmission system while considering credible contingencies as well as forecast error of loads and ...

IEEE2018