Publications associées à Branch and cut

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

Efficient GPU-accelerated Join Optimization for Complex Queries

Anastasia Ailamaki, Bikash Chandra, Srinivas Karthik Venkatesh, Riccardo Mancini, Vasileios Mageirakos

Analytics on modern data analytic and data warehouse systems often need to run large complex queries on increasingly complex database schemas. A lot of progress has been made on executing such complex queries using techniques like scale out query processin ...

IEEE2022

KPC: Learning-Based Model Predictive Control with Deterministic Guarantees

Colin Neil Jones, Yuning Jiang, Paul Scharnhorst, Emilio Maddalena

We propose Kernel Predictive Control (KPC), a learning-based predictive control strategy that enjoys deterministic guarantees of safety. Noise-corrupted samples of the unknown system dynamics are used to learn several models through the formalism of non-pa ...

2021

Addressing fairness in classification with a model-agnostic multi-objective algorithm

Boi Faltings, Claudiu-Cristian Musat, Diego Matteo Antognini

The goal of fairness in classification is to learn a classifier that does not discriminate against groups of individuals based on sensitive attributes, such as race and gender. One approach to designing fair algorithms is to use relaxations of fairness not ...

2021

Data reduction for mixed integer linear programming in complex energy systems

François Maréchal, Luc Girardin, Julia Granacher, Luise Middelhauve, Natalija Ljubic

The task of optimally designing and scheduling energy systems with a high share of renewable energies is complex and computationally demanding. A widespread method for tackling this task is to apply mixed integer linear programming (MILP). Even though the ...

2021

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

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

Optimal Design of Heat-Integrated Water Allocation Networks

François Maréchal, Ivan Daniel Kantor, Maziar Kermani

Industrial operations consume energy and water in large quantities without accounting for potential economic and environmental burdens on future generations. Consumption of energy (mainly in the form of high pressure steam) and water (in the form of proces ...

2019

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

The electric autonomous dial-a-ride problem

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provides shared-ride services to users specifying their origin, destination, and preferred arrival time. Typically, the problem consists of finding minimum cost routes, satisfying operational constraint ...

Elsevier2019

Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

Daniel Kuhn, Napat Rujeerapaiboon, Kilian Schindler, Wolfram Wiesemann

Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to ...

2019

Learning to Reduce Annotation Load

Ksenia Konyushkova

Modern machine learning methods and their applications in computer vision are known to crave for large amounts of training data to reach their full potential. Because training data is mostly obtained through humans who manually label samples, it induces a ...

EPFL2019

Integrating Heuristic and Machine-Learning Methods for Efficient Virtual Machine Allocation in Data Centers

David Atienza Alonso, Marina Zapater Sancho, Ali Pahlevan, Xiaoyu Qu

Modern cloud data centers (DCs) need to tackle efficiently the increasing demand for computing resources and address the energy efficiency challenge. Therefore, it is essential to develop resource provisioning policies that are aware of virtual machine (VM ...

2018

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Ola Nils Anders Svensson, Abbas Bazzi, Sangxia Huang

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear ...

UNIV CHICAGO, DEPT COMPUTER SCIENCE2018

A Heat Load Distribution Method for Retrofitting Heat Exchanger Networks, 28th European Symposium on Computer Aided Process Engineering

François Maréchal, Ivan Daniel Kantor, Alberto Mian, Hür Ebuzer Bütün

Fluctuating energy prices, increasing environmental concerns, and regulations push industries toward more energy efficient plants. Process integration (PI) techniques, proven to be effective in providing solutions with improved energy and material efficien ...

2018

Early-stage decision making approach for the selection of optimally integrated biorefinery processes

François Maréchal, Adriano Viana Ensinas, Shivom Sharma, Ayse Dilan Celebi

Lignocellulosic biorefineries are the best non-petroleum alternatives for a sustainable development. In the biorefinery process design, it is important to implement an algorithm that allows the systematic generation and the evaluation of energy conversion ...

2017

Strengths and Limitations of Linear Programming Relaxations

Abbas Bazzi

Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...

EPFL2017

Applications of Strong Convex Relaxations to Allocation Problems

Christos Kalaitzis

Approximation algorithms are a commonly used tool for designing efficient algorithmic solutions for intractable problems, at the expense of the quality of the output solution. A prominent technique for designing such algorithms is the use of Linear Program ...

EPFL2017

Optimal Software Patching Plan for PMUs

Jean-Yves Le Boudec, Ola Nils Anders Svensson, Teklemariam Tsegay Tesfay

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the ...

2017

LP-Based Algorithms For Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming (LP) has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic me ...

Society for Industrial and Applied Mathematics2017