Publications related to Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Related publications (39)

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n2) bits. In synchronous networks, with a known u ...

Society for Industrial and Applied Mathematics2025

Supercritical Tradeoffs for Monotone Circuits

Mika Tapani Göös, Gilbert Théodore Maystre, Kilian Risse

We exhibit a monotone function computable by a monotone circuit of quasipolynomial size such that any monotone circuit of polynomial depth requires exponential size. This is the first size–depth tradeoff result for monotone circuits in the so-called superc ...

ACM2025

Learning to Reason with Neural Networks: Principles and Methods

Aryo Lotfi Jandaghi

This thesis focuses on understanding and improving the reasoning capabilities of neural networks. It develops theoretical results and empirical analyses to uncover reasoning potential and limitations, leveraging these insights to guide the design of improv ...

EPFL2025

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

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

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

Stochastic Risk-driven Bidding of a Solar and Storage Aggregator in Primary Frequency and Energy Markets: A Performance-based Capacity Allocation Approach

Sidi-Rachid Cherkaoui

The ever-increasing impact of deploying renewable energy resources reducing power system inertia, requires distributed energy resource (DER) aggregators to secure high-performance, fast-responding primary frequency reserve (PFR) in ancillary service market ...

2024

HYPERBOLA METHOD ON TORIC VARIETIES

Marta Pieropan

We develop a very general version of the hyperbola method which extends the known method by Blomer and Brudern for products of projective spaces to complete smooth split toric varieties. We use it to count Campana points of bounded log-anticanonical height ...

Ecole Polytechnique2024

Contemporary Logic Synthesis: with an Application to AQFP Circuit Optimization

Siang-Yun Lee

Electronic devices play an irreplaceable role in our lives. With the tightening time to market, exploding demand for computing power, and continuous desire for smaller, faster, less energy-consuming, and lower-cost chips, computer-aided design for electron ...

EPFL2024

Laser-based manufacturing of freeform glass micro-optics through topological transformation

Samuel Youcef Benketaf

Glass has been the material of choice for making optical elements, in large part due to its intrinsic properties: a temperature-dependent viscosity, which enables shaping the material into a broad variety of functional and artistic glassware. Silica glass ...

EPFL2024

Optimization Algorithms for Decentralized, Distributed and Collaborative Machine Learning

Anastasiia Koloskova

Distributed learning is the key for enabling training of modern large-scale machine learning models, through parallelising the learning process. Collaborative learning is essential for learning from privacy-sensitive data that is distributed across various ...

EPFL2024

Modelling and solving a real-world truck-trailer scheduling problem in container transportation with separate moving objects

Thanh Trung Huynh

Container transportation is pivotal in global supply chains, facilitating the exchange of goods between companies across different countries. Given the exceedingly high operational costs of transporting containers, optimizing itinerary schedules can yield ...

Springer India2024

Workforce Allocation for Social Engagement Services via Stochastic Optimization

Michel Bierlaire

Social Engagement is a novel business model whose goal is transforming final users of a service from passive components into active ones. In this framework, people are contacted by the decision-maker (generally a company) and they are asked to perform task ...

Springer Science and Business Media Deutschland GmbH2024

BENIGN LANDSCAPES OF LOW-DIMENSIONAL RELAXATIONS FOR ORTHOGONAL SYNCHRONIZATION ON GENERAL GRAPHS

Nicolas Boumal

Orthogonal group synchronization is the problem of estimating n elements Z(1),& mldr;,Z(n) from the rxr orthogonal group given some relative measurements R-ij approximate to Z(i)Z(j)(-1). The least-squares formulation is nonconvex. To avoid its local minim ...

Siam Publications2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

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

EPFL2023

Safe Zeroth-Order Optimization Using Linear Programs

Giancarlo Ferrari Trecate, Yuning Jiang, Maryam Kamgarpour, Baiwei Guo

To solve unmodeled optimization problems with hard constraints, this paper proposes a novel zeroth-order approach called Safe Zeroth-order Optimization using Linear Programs (SZO-LP). The SZO-LP method solves a linear program in each iteration to find a de ...

New York2023

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

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Assoc Computing Machinery2023

Multi-robot task allocation for safe planning against stochastic hazard dynamics

Maryam Kamgarpour

We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...

IEEE2023

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