Publications associées à Faster Algorithms for Integer Programs with Block Structure

Spectral Estimators for High-Dimensional Matrix Inference

A key challenge across many disciplines is to extract meaningful information from data which is often obscured by noise. These datasets are typically represented as large matrices. Given the current trend of ever-increasing data volumes, with datasets grow ...

EPFL2024

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

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

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

Pergamon-Elsevier Science Ltd2024

RANDOMIZED JOINT DIAGONALIZATION OF SYMMETRIC

Daniel Kressner, Haoze He

Given a family of nearly commuting symmetric matrices, we consider the task of computing an orthogonal matrix that nearly diagonalizes every matrix in the family. In this paper, we propose and analyze randomized joint diagonalization (RJD) for performing t ...

Siam Publications2024

SPEEDING UP KRYLOV SUBSPACE METHODS FOR COMPUTING f(A)b VIA RANDOMIZATION

Daniel Kressner, Alice Cortinovis

This work is concerned with the computation of the action of a matrix function f(A), such as the matrix exponential or the matrix square root, on a vector b. For a general matrix A, this can be done by computing the compression of A onto a suitable Krylov ...

Siam Publications2024

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Colin Peter Sandon

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

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

Randomized low-rank approximation and its applications

Ulf David Persson

In this thesis we will present and analyze randomized algorithms for numerical linear algebra problems. An important theme in this thesis is randomized low-rank approximation. In particular, we will study randomized low-rank approximation of matrix functio ...

EPFL2024

Augmented Memory: Sample-Efficient Generative Molecular Design with Reinforcement Learning

Philippe Schwaller, Jeff Guo

Sample efficiency is a fundamental challenge in de novo molecular design. Ideally, molecular generative models should learn to satisfy a desired objective under minimal calls to oracles (computational property predictors). This problem becomes more apparen ...

Amer Chemical Soc2024

Accelerator-driven Data Arrangement to Minimize Transformers Run-time on Multi-core Architectures

David Atienza Alonso, Giovanni Ansaloni, Alireza Amirshahi

The increasing complexity of transformer models in artificial intelligence expands their computational costs, memory usage, and energy consumption. Hardware acceleration tackles the ensuing challenges by designing processors and accelerators tailored for t ...

2024

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

Paul Scharnhorst

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

EPFL2024

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

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

Learning Sparse Graphons And The Generalized Kesten-Stigum Threshold

Emmanuel Abbé

The problem of learning graphons has attracted considerable attention across several scientific communities, with significant progress over the re-cent years in sparser regimes. Yet, the current techniques still require diverg-ing degrees in order to succe ...

INST MATHEMATICAL STATISTICS-IMS2023

On the fast assemblage of finite element matrices with application to nonlinear heat transfer problems

Yannis Dirk Voet

The finite element method is a well-established method for the numerical solution of partial differential equations (PDEs), both linear and nonlinear. However, the repeated re -assemblage of finite element matrices for nonlinear PDEs is frequently pointed ...

ELSEVIER SCIENCE INC2023

A 16-bit Floating-Point Near-SRAM Architecture for Low-power Sparse Matrix-Vector Multiplication

David Atienza Alonso, Giovanni Ansaloni, Marco Antonio Rios, Grégoire Axel Eggermann

State-of-the-art Artificial Intelligence (AI) algorithms, such as graph neural networks and recommendation systems, require floating-point computation of very large matrix multiplications over sparse data. Their execution in resource-constrained scenarios, ...

New York2023

How to Find Molecules with Long-lasting Charge Migration?

Jiri Vanicek, Nikolay Golubev, Alan Scheidegger

Under certain conditions, the ionization of a molecule may create a superposition of electronic states, leading to ultrafast electron dynamics. If controlled, this motion could be used in attochemistry applications, but it has been shown that the decoheren ...

SWISS CHEMICAL SOC2023

Duality and bicrystals on infinite binary matrices

Thomas Gerber

The set of finite binary matrices of a given size is known to carry a finite type AA bicrystal structure. We first review this classical construction, explain how it yields a short proof of the equality between Kostka polynomials and one-dimensional sums t ...

2023

Preserving the positivity of the deformation gradient determinant in intergrid interpolation by combining RBFs and SVD: Application to cardiac electromechanics

Alfio Quarteroni, Francesco Regazzoni

The accurate, robust and efficient transfer of the deformation gradient tensor between meshes of different resolution is crucial in cardiac electromechanics simulations. This paper presents a novel method that combines rescaled localized Radial Basis Funct ...

Elsevier Science Sa2023

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

arXiv2023

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