Optimisation linéaire en nombres entiers

L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières. La contrainte d'intégralité sur les variables, qui différencie l'OLNE de l'optimisation linéaire classique est nécessaire pour modéliser certains problèmes, en particulier des problèmes algorithmiques. Mais cette contrainte supplémentaire rend le problème plus complexe et demande des techniques particulières. Définitions Définitions générales Un problème d'optimisation est un problème mathématique où, étant donné un ensemble de variables et des contraintes sur ces variables, on doit trouver une assignation qui maximise (ou minimise) une cer

The gene family-free median of three

Metin Balaban

Background: The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the breakpoint median of three genomes, which asks for the construction of a fourth genome that minimizes the sum of breakpoint distances to the input genomes. Methods: We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We study its computational complexity and we describe an integer linear program (ILP) for its exact solution. We further discuss a related problem called family-free adjacencies for k genomes for the special case of k

2017

Fair colorful k-center clustering

Xinrui Jia, Ola Nils Anders Svensson

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho around k of the points that meet the coverage requirements. The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations. Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes. algorithms either opened more than k centers or only worked in the special case when the input points are in the plane.

SPRINGER HEIDELBERG2021

Vehicle-to-Grid for Reliable Frequency Regulation

Dirk Lauinger

Future low-carbon societies will need to store vast amounts of electricity to stabilize electricity grids and to power electric vehicles. Vehicle-to-grid allows vehicle owners and grid operators to share the costs of electricity storage by making the batteries of electric vehicles available to the grid. In practice, vehicle owners decide when to reserve their cars for driving and when to make them available for grid services. Vehicle aggregators then decide how to commit the vehicles to grid services. For vehicle-to-grid to succeed, both vehicle owners and grid operators must be able to trust aggregators, i.e., vehicles should be available for driving and for grid services when the aggregators promise they will be. In this thesis, we solve a decision-making problem that ensures reliable commitments by vehicle aggregators for a particular grid service known as primary frequency regulation, considered one of the most profitable applications of vehicle-to-grid. Mathematically, we first formulate a robust optimization problem with functional uncertainties that maximizes the expected profit from selling primary frequency regulation to grid operators and guarantees that vehicle owners can meet their market commitments for all frequency deviation trajectories in an uncertainty set that encodes applicable European Union regulations. Functional uncertainties ensure that vehicle owners and grid operators can trust the decisions of aggregators at all times. Faithfully modeling the energy conversion losses during battery charging and discharging renders the optimization problem nonconvex. By exploiting a total unimodularity property of the proposed uncertainty sets and an exact linear decision rule reformulation, we prove that the nonconvex robust optimization problem with functional uncertainties is equivalent to a tractable linear program. Somewhat counterintuitively, the underlying deterministic problem for a known frequency deviation trajectory does not reduce to a linear program but results in a large-scale mixed-integer linear program, even if time is discretized. We believe that we have thus discovered the first practically interesting class of optimization problems that become dramatically easier through robustification. Through extensive numerical experiments using real-world data, we quantify the economic value of vehicle-to-grid and elucidate the financial incentives of vehicle owners, aggregators, equipment manufacturers, and regulators. In particular, we find that the prevailing penalties for non-delivery of promised regulation power are too low to incentivize aggregators to honor their promises toward grid operators. For general electricity storage devices, we then solve a simplified version of the decision-making problem analytically to understand how the optimal frequency regulation commitments depend on the roundtrip efficiency of the storage device, the dispersion of the frequency deviations, and the EU delivery guarantee. We show how the marginal cost of frequency regulation decreases with roundtrip efficiency and increases with frequency deviation dispersion. For energy-constrained storage devices, we find that the profits from frequency regulation are inversely proportional to the length of time for which storage operators commit regulation power. Establishing an intra-day market for frequency regulation would thus make electricity storage devices more competitive with other regulation providers, such as thermal power plants.

EPFL2022

Vehicle-to-Grid for Reliable Frequency Regulation

Dirk Lauinger

EPFL2022