References of "Louveaux, Quentin"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailOptimal Assignment of Off-Peak Hours to Lower Curtailments in the Distribution Network
Merciadri, Luca ULg; Mathieu, Sébastien ULg; Ernst, Damien ULg et al

in Proceedings of the 5th European Innovative Smart Grid Technologies (ISGT) (2014, October)

We consider a price signal with two settings: off-peak tariff and on-peak tariff. Some loads are connected to specific electricity meters which allow the consumption of power only in off-peak periods ... [more ▼]

We consider a price signal with two settings: off-peak tariff and on-peak tariff. Some loads are connected to specific electricity meters which allow the consumption of power only in off-peak periods. Historically, off-peak periods were located during the night and on-peak periods during the day. Changing the assignment of off-peak periods is an easy method for distribution system operators to access to the flexibility of small consumers. This solution can be implemented quickly as the infrastructure needed already exists in some countries. We propose a mixed-integer linear model to assign optimally the off-peak hours so as to minimize a societal cost. This cost gathers together the cost of electricity, the financial losses due to energy curtailments of photovoltaic installations and the loads' wellbeing. Our model considers automatic tripping of inverters and constraints of the electrical distribution networks. Simulation results show that the new disposition of off-peak hours could reduce significantly the photovoltaic energy curtailed in the summer. [less ▲]

Detailed reference viewed: 17 (3 ULg)
Full Text
Peer Reviewed
See detailA quantitative analysis of the effect of flexible loads on reserve markets
Mathieu, Sébastien ULg; Louveaux, Quentin ULg; Ernst, Damien ULg et al

in Proceedings of the 18th Power Systems Computation Conference (PSCC) (2014, August)

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 107 (19 ULg)
Full Text
Peer Reviewed
See detailRelaxations for multi-period optimal power flow problems with discrete decision variables
Gemine, Quentin ULg; Ernst, Damien ULg; Louveaux, Quentin ULg et al

in Proceedings of the 18th Power Systems Computation Conference (PSCC'14) (2014, August)

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 114 (31 ULg)
Full Text
Peer Reviewed
See detailA learning procedure for sampling semantically different valid expressions
St-Pierre, David Lupien; Maes, Francis; Ernst, Damien ULg et al

in International Journal of Artificial Intelligence (2014), 12(1), 18-35

A large number of problems can be formalized as finding the best symbolic expression to maximize a given numerical objective. Most approaches to approximately solve such problems rely on random ... [more ▼]

A large number of problems can be formalized as finding the best symbolic expression to maximize a given numerical objective. Most approaches to approximately solve such problems rely on random exploration of the search space. This paper focuses on how this random exploration should be performed to take into account expressions redundancy and invalid expressions. We propose a learning algorithm that, given the set of available constants, variables and operators and given the target finite number of trials, computes a probability distribution to maximize the expected number of semantically different, valid, generated expressions. We illustrate the use of our approach on both medium-scale and large-scale expression spaces, and empirically show that such optimized distributions significantly outperform the uniform distribution in terms of the diversity of generated expressions. We further test the method in combination with the recently proposed nested Monte-Carlo algorithm on a set of benchmark symbolic regression problems and demonstrate its interest in terms of reduction of the number of required calls to the objective function. [less ▲]

Detailed reference viewed: 17 (4 ULg)
Full Text
Peer Reviewed
See detailAn algorithm for the separation of two-row cuts
Louveaux, Quentin ULg; Poirrier, Laurent ULg

in Mathematical Programming (2014), 143(1-2), 111-146

We consider the question of finding deep cuts from a model with two rows of the type PI = {(x,s) ∈ Z2 ×Rn+ : x = f +Rs}. To do that, we show how to reduce the complexity of setting up the polar of conv(PI ... [more ▼]

We consider the question of finding deep cuts from a model with two rows of the type PI = {(x,s) ∈ Z2 ×Rn+ : x = f +Rs}. To do that, we show how to reduce the complexity of setting up the polar of conv(PI ) from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice. [less ▲]

Detailed reference viewed: 108 (16 ULg)
Full Text
Peer Reviewed
See detailA combinatorial branch-and-bound algorithm for box search
Mathieu, Sébastien ULg; Louveaux, Quentin ULg

in Discrete Optimization (2014), 13

Considering a set of points in a multi-dimensional space with an associated real value for each point, we want to find the box with the maximum sum of the values of the included points. This problem has ... [more ▼]

Considering a set of points in a multi-dimensional space with an associated real value for each point, we want to find the box with the maximum sum of the values of the included points. This problem has applications in data mining and can be formulated as a mixed-integer linear program. We propose a branch-and-bound algorithm where the bounding is obtained by combinatorial arguments instead of the traditional linear relaxation. Computational experiments show that this approach competes with current state of the art mixed-integer solvers. The algorithm proposed in this paper may be seen as a simple and dependence-free method to solve the box search problem. [less ▲]

Detailed reference viewed: 39 (17 ULg)
Full Text
See detailA Supervised Machine Learning Approach to Variable Branching in Branch-And-Bound
Marcos Alvarez, Alejandro ULg; Louveaux, Quentin ULg; Wehenkel, Louis ULg

E-print/Working paper (2014)

We present in this paper a new approach that uses supervised machine learning techniques to improve the performances of optimization algorithms in the context of mixed-integer programming (MIP). We focus ... [more ▼]

We present in this paper a new approach that uses supervised machine learning techniques to improve the performances of optimization algorithms in the context of mixed-integer programming (MIP). We focus on the branch-and-bound (B&B) algorithm, which is the traditional algorithm used to solve MIP problems. In B&B, variable branching is the key component that most conditions the efficiency of the optimization. Good branching strategies exist but are computationally expensive and usually hinder the optimization rather than improving it. Our approach consists in imitating the decisions taken by a supposedly good branching strategy, strong branching in our case, with a fast approximation. To this end, we develop a set of features describing the state of the ongoing optimization and show how supervised machine learning can be used to approximate the desired branching strategy. The approximated function is created by a supervised machine learning algorithm from a set of observed branching decisions taken by the target strategy. The experiments performed on randomly generated and standard benchmark (MIPLIB) problems show promising results. [less ▲]

Detailed reference viewed: 39 (1 ULg)
Full Text
Peer Reviewed
See detailInteger Programs with Prescribed Number of Solutions and a Weighted Version of Doignon-Bell-Scarf’s Theorem
Aliev, Iskander; De Loera, Jesus; Louveaux, Quentin ULg

in Lee, Jon; Vygen, Jens (Eds.) Proceedings of the 17th IPCO (2014)

In this paper we study a generalization of the classical fesibility problem in integer linear programming, where an ILP needs to have a prescribed number of solutions to be considered solved. We first ... [more ▼]

In this paper we study a generalization of the classical fesibility problem in integer linear programming, where an ILP needs to have a prescribed number of solutions to be considered solved. We first provide a generalization of the famous Doignon-Bell-Scarf theorem: Given an integer k, we prove that there exists a constant c(k, n), depending only on the dimension n and k, such that if a polyhedron {x : Ax ≤ b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. The second contribution of the article presents a structure theory that characterizes precisely the set Sg≥k (A) of all vectors b such that the problem Ax = b, x ≥ 0, x ∈ Zn , has at least k-solutions. We demonstrate that this set is finitely generated, a union of translated copies of a semigroup which can be computed explicitly via Hilbert bases computation. Similar results can be derived for those right-hand-side vectors that have exactly k solutions or fewer than k solutions. Finally we show that, when n, k are fixed natural numbers, one can compute in polynomial time an encoding of Sg≥k(A) as a generating function, using a short sum of rational functions. As a consequence, one can identify all right-hand-side vectors that have exactly k solutions (similarly for at least k or less than k solutions). Under the same assumptions we prove that the k-Frobenius number can be computed in polynomial time. [less ▲]

Detailed reference viewed: 24 (1 ULg)
Full Text
Peer Reviewed
See detailAn efficient algorithm for the provision of a day-ahead modulation service by a load aggregator
Mathieu, Sébastien ULg; Ernst, Damien ULg; Louveaux, Quentin ULg

in Proceedings of the 4th European Innovative Smart Grid Technologies (ISGT) (2013, October)

This article studies a decision making problem faced by an aggregator willing to offer a load modulation service to a Transmission System Operator. This service is contracted one day ahead and consists in ... [more ▼]

This article studies a decision making problem faced by an aggregator willing to offer a load modulation service to a Transmission System Operator. This service is contracted one day ahead and consists in a load modulation option, which can be called once per day. The option specifies the range of a potential modification on the demand of the loads within a certain time interval. The specific case where the loads can be modeled by a generic tank model is considered. Under this assumption, the problem of maximizing the range of the load modulation service can be formulated as a mixed integer linear programming problem. A novel heuristic-method is proposed to solve this problem in a computationally efficient manner. This method is tested on a set of problems. The results show that this approach can be orders of magnitude faster than CPLEX without significantly degrading the solution accuracy. [less ▲]

Detailed reference viewed: 109 (29 ULg)
Full Text
Peer Reviewed
See detailGénéralisation Min Max pour l'Apprentissage par Renforcement Batch et Déterministe : Relaxations pour le Cas Général T Etapes
Fonteneau, Raphaël ULg; Ernst, Damien ULg; Boigelot, Bernard ULg et al

in 8èmes Journées Francophones de Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA'13) (2013)

Cet article aborde le problème de généralisation minmax dans le cadre de l'apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par [Fonteneau, 2011], et il a ... [more ▼]

Cet article aborde le problème de généralisation minmax dans le cadre de l'apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par [Fonteneau, 2011], et il a déjà été montré qu'il est NP-dur. Deux schémas de relaxation pour le cas deux étapes ont été présentés aux JFPDA'12, et ce papier présente une généralisation de ces schémas au cas T étapes. Le premier schéma fonctionne en éliminant des contraintes afin d'obtenir un problème soluble en temps polynomial. Le deuxième schéma est une relaxation lagrangienne conduisant également à un problème soluble en temps polynomial. On montre théoriquement que ces deux schémas permettent d'obtenir de meilleurs résultats que ceux proposés par [Fonteneau, 2011]. [less ▲]

Detailed reference viewed: 35 (6 ULg)
Full Text
Peer Reviewed
See detailMin max generalization for deterministic batch mode reinforcement learning: relaxation schemes
Fonteneau, Raphaël ULg; Ernst, Damien ULg; Boigelot, Bernard ULg et al

in SIAM Journal on Control & Optimization (2013), 51(5), 33553385

We study the min max optimization problem introduced in Fonteneau et al. [Towards min max reinforcement learning, ICAART 2010, Springer, Heidelberg, 2011, pp. 61–77] for computing policies for batch mode ... [more ▼]

We study the min max optimization problem introduced in Fonteneau et al. [Towards min max reinforcement learning, ICAART 2010, Springer, Heidelberg, 2011, pp. 61–77] for computing policies for batch mode reinforcement learning in a deterministic setting with fixed, finite time horizon. First, we show that the min part of this problem is NP-hard. We then 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, can also be solved in polynomial time. We also theoretically prove and empirically illustrate that both relaxation schemes provide better results than those given in [Fonteneau et al., 2011, as cited above]. [less ▲]

Detailed reference viewed: 40 (12 ULg)
Full Text
See detailA computationally efficient algorithm for the provision of a day-ahead modulation service by a load aggregator
Mathieu, Sébastien ULg; Karangelos, Efthymios ULg; Louveaux, Quentin ULg et al

Poster (2012, October 08)

We study a decision making problem faced by an aggregator willing to offer a load modulation service to a Transmission System Operator (TSO). In particular, we concentrate on a day-ahead service ... [more ▼]

We study a decision making problem faced by an aggregator willing to offer a load modulation service to a Transmission System Operator (TSO). In particular, we concentrate on a day-ahead service consisting of a load modulation option, which can be called by the TSO once per day. The option specifies the maximum amplitude of a potential modification on the demand of the loads within a certain time interval. We consider the specific case where the loads can be modeled by a generic tank model whose inflow depends on the power consumed by the load and outflow is assumed to be known the day before for every market period. The level of the reservoir at the beginning of the market day is also assumed to be known. We show that, under these assumptions, the problem of maximizing the amplitude of the load modulation service can be formulated as a mixed integer linear programming problem (MILP). In order to solve this problem in a computationally efficient manner we introduce a novel heuristic-method. We test this method on a set of problems and demonstrate that our approach is orders of magnitude faster than CPLEX - a state-of-the-art software for solving MILP problems - without considerably compromising the solution accuracy. [less ▲]

Detailed reference viewed: 58 (15 ULg)
Full Text
Peer Reviewed
See detailGénéralisation min max pour l'apprentissage par renforcement batch et déterministe : schémas de relaxation
Fonteneau, Raphaël ULg; Ernst, Damien ULg; Boigelot, Bernard ULg et al

in Septièmes Journées Francophones de Planification, Décision et Apprentissage pour la conduite de systèmes (JFPDA 2012) (2012, May)

On s’intéresse au problème de généralisation min max dans le cadre de l’apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par Fonteneau et al. (2011). Dans ... [more ▼]

On s’intéresse au problème de généralisation min max dans le cadre de l’apprentissage par renforcement batch et déterministe. Le problème a été originellement introduit par Fonteneau et al. (2011). Dans un premier temps, on montre que le problème est NP-dur. Dans le cas où l’horizon d’optimisation vaut 2, on développe deux schémas de relaxation. Le premier schéma fonctionne en éliminant des contraintes de telle sorte qu’on obtienne un problème soluble en temps polynomial. Le deuxième schéma est une relaxation Lagrangienne conduisant à un problème conique-quadratique. On montre théoriquement et empiriquement que ces deux schémas permettent d’obtenir de meilleurs résultats que ceux proposés par Fonteneau et al. (2011). [less ▲]

Detailed reference viewed: 63 (8 ULg)
Full Text
Peer Reviewed
See detailRelaxation schemes for min max generalization in deterministic batch mode reinforcement learning
Fonteneau, Raphaël ULg; Ernst, Damien ULg; Boigelot, Bernard ULg et al

in 4th International NIPS Workshop on Optimization for Machine Learning (OPT 2011) (2011, December)

We study the min max optimization problem introduced in [Fonteneau, 2011] for computing policies for batch mode reinforcement learning in a deterministic setting. This problem is NP-hard. We focus on the ... [more ▼]

We study the min max optimization problem introduced in [Fonteneau, 2011] for computing policies for batch mode reinforcement learning in a deterministic setting. This problem is NP-hard. We focus on the two-stage case for which 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. Both relaxation schemes are shown to provide better results than those given in [Fonteneau, 2011]. [less ▲]

Detailed reference viewed: 82 (10 ULg)
Full Text
Peer Reviewed
See detailSplit rank of triangle and quadrilateral inequalities
Dey, Santanu; Louveaux, Quentin ULg

in Mathematics of Operations Research (2011), 36(3), 432-461

A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. and ... [more ▼]

A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. and Cornuéjols and Margot showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from lattice-free triangles and quadrilaterals. Through a result by Cook et al., it is known that one particular class of facet- defining triangle inequality does not have a finite split rank. In this paper, we show that all other facet-defining triangle and quadrilateral inequalities have finite split rank. The proof is constructive and given a facet-defining triangle or quadrilateral inequality we present an explicit sequence of split inequalities that can be used to generate it. [less ▲]

Detailed reference viewed: 94 (19 ULg)
Full Text
Peer Reviewed
See detailOnline Sparse Bandit for Card Games
Lupien St-Pierre, David ULg; Louveaux, Quentin ULg; Teytaud, Olivier

in Advance in Computer Games (2011)

Finding an approximation of a Nash equilibria in matrix games is an important topic that reaches beyond the strict application to matrix games. A bandit algorithm commonly used to approximate a Nash ... [more ▼]

Finding an approximation of a Nash equilibria in matrix games is an important topic that reaches beyond the strict application to matrix games. A bandit algorithm commonly used to approximate a Nash equilibrium is EXP3. However, the solution to many problems is often sparse, yet EXP3 inherently fails to exploit this property. To the knowledge of the authors, there exist only an offline truncation to tackle such issue. In this paper, we propose a variation of EXP3 to exploit the fact that solution is sparse by dynamically removing arms; the resulting algorithm empirically performs better than previous versions. We apply the resulting algorithm to a MCTS program for the Urban Rivals card game. [less ▲]

Detailed reference viewed: 34 (12 ULg)
Full Text
See detailLift-and-project inequalities
Louveaux, Quentin ULg

in Wiley Encylopedia of Operations Research and Management Science (2011)

The lift-and-project technique is a systematic way to generate valid inequalities for a mixed binary program. The technique is interesting both on the theoretical and on the practical point of view. On ... [more ▼]

The lift-and-project technique is a systematic way to generate valid inequalities for a mixed binary program. The technique is interesting both on the theoretical and on the practical point of view. On the theoretical side it allows one to construct the inequality description of the convex hull of all mixed-{0,1} solutions of a binary MIP in n repeated applications of the technique, where n is the number of binary variables. On the practical side, a variant of the method allows one to derive some cutting planes from the simplex tableau rather efficiently. [less ▲]

Detailed reference viewed: 112 (12 ULg)
Full Text
See detailSparse Two-Row Cuts and an Algorithm for the Separation Problem
Louveaux, Quentin ULg

Conference (2010, July)

We propose a systematic way to generate sparse cuts from multiple rows of the simplex tableau. We also discuss the question of separation for a multi-row model. To this end, we consideer the polar system ... [more ▼]

We propose a systematic way to generate sparse cuts from multiple rows of the simplex tableau. We also discuss the question of separation for a multi-row model. To this end, we consideer the polar system allowing to generate valid inequalities. In order to avoid generating the large number of constraints of the polar, we consider a reduced version of it that we dynamically extend. Checking the validity of an inequality is done geometrically. Computational results showing the efficiency of the algorithm are presented. This is a joint work with Laurent Poirrier. [less ▲]

Detailed reference viewed: 12 (0 ULg)
Full Text
Peer Reviewed
See detailMixed-integer sets from two rows of two adjacent simplex bases
Andersen, Kent; Louveaux, Quentin ULg; Weismantel, Robert

in Mathematical Programming (2010), 124(1-2), 455-480

In 2007 we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with ... [more ▼]

In 2007 we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our findings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be obtained from triangles and quadrilaterals. Specifically, when exactly one upper bound on a non-basic variable is intro- duced, stronger inequalities that can be derived from pentagons involving up to six variables also appear. [less ▲]

Detailed reference viewed: 102 (18 ULg)