Source author record

Quentin Louveaux

Quentin Louveaux appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.OC math.CO Computational Engineering, Finance, and Science Computer Science and Game Theory Machine Learning math.MG math.NT Systems and Control

Catalog footprint

What is connected

7works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

On the Length of Monotone Paths in Polyhedra

Motivated by the problem of bounding the number of iterations of the Simplex algorithm we investigate the possible lengths of monotone paths followed by the Simplex method inside the oriented graphs of polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the TSP, among others. We begin by showing that combinatorial cubes have monotone and Bland pivot height bounded by their dimension and that in fact all monotone paths of zonotopes are no larger than the number of edge directions of the zonotope. We later use this to show that several polytopes have polynomial-size pivot height, for all pivot rules. In contrast, we show that many well-known combinatorial polytopes have exponentially-long monotone paths. Surprisingly, for some famous pivot rules, e.g., greatest improvement and steepest edge, these same polytopes have polynomial-size simplex paths.

preprint2015arXiv

A Quantitative Doignon-Bell-Scarf Theorem

The famous Doignon-Bell-Scarf Theorem is a Helly-type result about the existence of integer solutions on systems of linear inequalities. The purpose of this paper is to present the following quantitative generalization: Given an integer $k$, we prove that there exists a constant $c(n,k)$, depending only on the dimension $n$ and $k$, such that if a polyhedron ${x: Ax \leq b}$ contains exactly k integer solutions, then there exists a subset of the rows, of cardinality no more than $c(n,k)$, defining a polyhedron that contains exactly the same $k$ integer points. In this case $c(n,0) = 2^n$ is the original case of Doignon-Bell-Scarf for infeasible systems of inequalities. We work on both upper and lower bounds for the constant $c(n,k)$ and discuss some consequences, including a Clarkson-style algorithm to find the $l$-th best solution of an integer program with respect to the ordering induced by the objective function.

preprint2015arXiv

Parametric Polyhedra with at least $k$ Lattice Points: Their Semigroup Structure and the k-Frobenius Problem

Given an integral $d \times n$ matrix $A$, the well-studied affine semigroup $\mbox{ Sg} (A)=\{ b : Ax=b, \ x \in {\mathbb Z}^n, x \geq 0\}$ can be stratified by the number of lattice points inside the parametric polyhedra $P_A(b)=\{x: Ax=b, x\geq0\}$. Such families of parametric polyhedra appear in many areas of combinatorics, convex geometry, algebra and number theory. The key themes of this paper are: (1) A structure theory that characterizes precisely the subset $\mbox{ Sg}_{\geq k}(A)$ of all vectors $b \in \mbox{ Sg}(A)$ such that $P_A(b) \cap {\mathbb Z}^n $ has at least $k$ solutions. We demonstrate that this set is finitely generated, it is a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computations. Related results can be derived for those right-hand-side vectors $b$ for which $P_A(b) \cap {\mathbb Z}^n$ has exactly $k$ solutions or fewer than $k$ solutions. (2) A computational complexity theory. We show that, when $n$, $k$ are fixed natural numbers, one can compute in polynomial time an encoding of $\mbox{ Sg}_{\geq k}(A)$ as a multivariate generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors of bounded norm that have at least $k$ solutions. (3) Applications and computation for the $k$-Frobenius numbers. Using Generating functions we prove that for fixed $n,k$ the $k$-Frobenius number can be computed in polynomial time. This generalizes a well-known result for $k=1$ by R. Kannan. Using some adaptation of dynamic programming we show some practical computations of $k$-Frobenius numbers and their relatives.

preprint2014arXiv

A quantitative analysis of the effect of flexible loads on reserve markets

We propose and analyze a day-ahead reserve market model that handles bids from flexible loads. This pool market model takes into account the fact that a load modulation in one direction must usually be compensated later by a modulation of the same magnitude in the opposite direction. Our analysis takes into account the gaming possibilities of producers and retailers, controlling load flexibility, in the day-ahead energy and reserve markets, and in imbalance settlement. This analysis is carried out by an agent-based approach where, for every round, each actor uses linear programs to maximize its profit according to forecasts of the prices. The procurement of a reserve is assumed to be determined, for each period, as a fixed percentage of the total consumption cleared in the energy market for the same period. The results show that the provision of reserves by flexible loads has a negligible impact on the energy market prices but markedly decreases the cost of reserve procurement. However, as the rate of flexible loads increases, the system operator has to rely more and more on non-contracted reserves, which may cancel out the benefits made in the procurement of reserves.

preprint2014arXiv

Relaxations for multi-period optimal power flow problems with discrete decision variables

We consider a class of optimal power flow (OPF) applications where some loads offer a modulation service in exchange for an activation fee. These applications can be modeled as multi-period formulations of the OPF with discrete variables that define mixed-integer non-convex mathematical programs. We propose two types of relaxations to tackle these problems. One is based on a Lagrangian relaxation and the other is based on a network flow relaxation. Both relaxations are tested on several benchmarks and, although they provide a comparable dual bound, it appears that the constraints in the solutions derived from the network flow relaxation are significantly less violated.

preprint2012arXiv

Min Max Generalization for Two-stage Deterministic Batch Mode Reinforcement Learning: Relaxation Schemes

We study the minmax optimization problem introduced in [22] for computing policies for batch mode reinforcement learning in a deterministic setting. First, we show that this problem is NP-hard. In the two-stage case, we provide two relaxation schemes. The first relaxation scheme works by dropping some constraints in order to obtain a problem that is solvable in polynomial time. The second relaxation scheme, based on a Lagrangian relaxation where all constraints are dualized, leads to a conic quadratic programming problem. We also theoretically prove and empirically illustrate that both relaxation schemes provide better results than those given in [22].

preprint2006arXiv

Intermediate integer programming representations using value disjunctions

We introduce a general technique to create an extended formulation of a mixed-integer program. We classify the integer variables into blocks, each of which generates a finite set of vector values. The extended formulation is constructed by creating a new binary variable for each generated value. Initial experiments show that the extended formulation can have a more compact complete description than the original formulation. We prove that, using this reformulation technique, the facet description decomposes into one ``linking polyhedron'' per block and the ``aggregated polyhedron''. Each of these polyhedra can be analyzed separately. For the case of identical coefficients in a block, we provide a complete description of the linking polyhedron and a polynomial-time separation algorithm. Applied to the knapsack with a fixed number of distinct coefficients, this theorem provides a complete description in an extended space with a polynomial number of variables.